Notation for Stable Matching Problem
Here we collect notation related to the Stable Matching Problem and the Gale Shapley Algorithm.
Stable Marriage Problem
| Notation | Meaning |
| $n$ | Number of men and women |
| $W$ | Set of women. Typically denoted by $\{w_1,\dots,w_n\}$ |
| $M$ | Set of men. Typically denoted by $\{m_1,\dots,m_n\}$ |
| $L_w$ | Preference list for man $w\in W$ |
| $L_m$ | Preference list for woman $m\in M$ |
| $m_i > m_j$ in $L_w$ | $m_i$ is higher in $w$'s preference list than $m_j$ |
| $w_i > w_j$ in $L_m$ | $w_i$ is higher in $m$'s preference list than $w_j$ |
Gale Shapley Algorithm (Data Structures)
| Notation | Meaning |
| $M=W=[n]$ | We identify $m_i$ with $i$ (and $w_i$ with $i$) |
ManPref$[m][i]$ | ID of the $i$th most preferred woman for man $m$ |
WomanPref$[w][i]$ | ID of the $i$th most preferred man for woman $w$ |
free | Linked list of free women |
Next$[w]$ | Rank of the man $w$ should propose to next |
Current$[m]$ | $-1$ if $m$ is free and $w$ if $(m,w)$ are engaged |
Rank$[m][w]$ | Rank of $w$ in ManPref$[m]$ |