\chapter{Structures of Stable Matchings}

Now that we have laid the groundwork to formalize and talk about matching problems, let us look at the structure of stable matchings in both the one-to-one and many-to-one settings. In particular, although we have shown that at least one stable matching exists, we would like to understand whether there are multiple stable matchings possible and how to compare these matchings. In addition, we hope to understand how the set of stable matchings compares on metrics like Pareto optimality to the general set of possible matchings.

\section{Structures of One-to-One Matchings}

In an above subsection, we demonstrated one example of deferred acceptance. Now, let us provide a second example in order to understand the types of stable matchings that exist.

\subsection{Deferred Acceptance Example, Revisited}

In the description of the deferred acceptance algorithm, we have men propose, but men and women play symmetrical roles in the marriage market, so we can consider the matching that occurs when women propose. Let us call the matching from Section \ref{sub:1to1existence} $\mu_M$ to denote the fact that men propose. 

Now, let us now consider the matching $\mu_W$, which results if the women propose instead of the men, while keeping the same preferences as the example in Section \ref{sub:1to1existence}. Given that the first-choice preferences of each woman is different, we only need to complete one step of the deferred acceptance algorithm to reach a stable matching, namely that $\mu_W$ consists of the marriages $(w_1, m_3)$, $(w_2, m_2)$, and $(w_3, m_1)$.

Note that all women clearly prefer $\mu_W$ to $\mu_M$, as in $\mu_W$, each woman marries their first choice man, whereas in $\mu_M$, each woman marries either their second or last choice man. Similarly, note that all men prefer $\mu_M$ to $\mu_W$. In $\mu_M$, each man marries either their first or second choice woman, whereas in $\mu_W$, each man marries their last choice woman. 

This example elucidates three points. Firstly, there may be more than one stable matching, and in this section, we find two distinct stable matchings by switching which side of the market gets to propose in the deferred acceptance algorithm. Secondly, one stable matching may be unilaterally preferred by one side of the market compared to another stable matching. Lastly, we see that the side of the market that proposes gets more favorable outcomes in their matches.

\subsection{Comparing Stable Matchings}

To formalize our comparison of different stable matchings, let $\mu \succ_M \mu'$ denote that all men like matching $\mu$ at least as much as $\mu'$, with at least one man preferring $\mu$ to $\mu'$ outright. Mathematically, we would say that $\mu(m) \succeq_m \mu'(m)$ for all $m\in M$, and $\mu(m)\succ_m \mu'(m)$ for at least one man $m\in M$. Similarly, $\mu\succeq_M \mu'$ implies that either $\mu \succ_M\mu'$ or all men are indifferent between the two matchings. Unlike an individual's preference relation $\succ_i$ for $i\in M\cup W$, the preference relation $\succ_M$, representing the common preferences of all men, is a partial ordering. This is because it is possible for some men to prefer $\mu$ and others to prefer $\mu'$, so there is no common agreement about which matching is preferred by all. We can similarly define $\succ_W$ and $\succeq_W$ for women, and like individual preferences, these common preferences are also transitive.

\begin{definition}[M-Optimal]
A stable matching $\mu$ is M-optimal if every man likes it at least as well as any other stable matching, that is, if for every other stable matching $\mu'$, $\mu\succ_M\mu'$.
\end{definition}

\begin{definition}[W-Optimal]
A stable matching $\nu$ is W-optimal if every woman likes it at least as well as any other stable matching, that is, if for every other stable matching $\nu'$, $\nu\succ_W\nu'$.
\end{definition}

\subsection{Optimal Stable Matchings}

\begin{definition}[Achievable]
A woman $w$ and a man $m$ are achievable for each other in a marrige market if $m$ and $w$ are paired in some stable matching.
\end{definition}

Based on this definition, if men and women all have strict preferences in our marriage market, each individual has only one favorite match among their set of achievable spouses. Thus, a M-optimal stable matching would naturally match each man to his most preferred achievable woman and similarly, a W-optimal stable matching must match each woman to her most preferred achievable man. This means there is at most one M-optimal stable matching and one W-optimal stable matching, and we will prove that these matchings do, in fact, exist.

\begin{theorem}
When all men and women have strict preferences, there always exists an M-optimal stable matching and a W-optimal stable matching. The M-optimal stable matching $\mu_M$ is produced by deferred acceptance with men proposing and the W-optimal stable matching $\mu_W$ is produced by deferred acceptance with women proposing. 
\end{theorem}

\begin{proof}
We seek to show using induction that when men propose using deferred acceptance, no man is ever rejected by an achievable woman. Thus, the stable matching $\mu_M$ that is produced must match each man to his most preferred achievable woman and is the unique M-optimal stable matching.

First, assume that up to step $n-1$ in the deferred acceptance procedure, no man has been rejected yet by any woman who is achievable for him. In step $n$, suppose that woman $w$ rejects man $m$. We must show that $w$ is not achievable for $m$ here as well by considering two cases.

\textbf{Case 1:} \ If woman $w$ rejects man $m$ as unacceptable because she would prefer to be single rather than marry man $m$, then woman $w$ is unachievable for man $m$ and we are done.

\textbf{Case 2:} \ If woman $w$ rejects man $m$ in favor of man $m'$, to whom she stays engaged to, then she prefers $m'$ to $m$. The deferred acceptance procedure tells us that $m'$ must prefer $w$ to any woman except for those who have already rejected him in a previous step, who by the inductive assumption, are unachievable for him. Consider for contradiction a matching $\mu$ that matches $m$ to $w$ and everyone else to an achievable mate. Then, $m'$ prefers woman $w$ to his current match $\mu(m')$. Thus, $(m',w)$ form a blocking pair because $w$ prefers $m'$ to $m$ and $m'$ prefers $w$ to $\mu(m')$, implying the hypothetical matching $\mu$ is unstable. Thus, there are no stable matchings which pair $m$ and $w$, so they are unachievable for each other and prove the inductive step.
\end{proof}

Given this theorem, agents on one side of the market are in agreement on the best stable matching when preferences are strict, and thus, have a common interest regarding the set of stable matchings. In fact, it turns out that agents on opposite sides of the markets have opposite interests in this regard, and the optimal stable matching for one side of the market is the worst stable matching for agents on the other side of the market. Moreover, any stable matching that is better for all men is worse for all women, and vice versa. 

\begin{lemma}
When all agents have strict preferences, if $\mu$ and $\mu'$ are stable matchings, then all men like $\mu$ at least as well as $\mu'$ if and only if all women like $\mu'$ at least as well as $\mu$. More concisely, $\mu \succ_M \mu' \iff \mu' \succ_W \mu$.
\end{lemma}

\begin{theorem}
When all agents have strict preferences, the M-optimal stable matching is the worst stable matching for the women and it matches each woman with her least preferred achievable mate. Similarly, the W-optimal stable matching matches each man with his least preferred achievable mate.
\end{theorem}
\begin{proof}
Let $\mu, \mu'$ be stable matchings and assume that $\mu\succ_M\mu'$. Assume for contradiction that we do not have $\mu'\succ_W\mu$. Then there must exist some woman $w$ who prefers $\mu$ to $\mu'$, meaning $\mu(w)\succ_w \mu'(w)$. Because individuals have strict preferences and at least one woman has a different mate in $\mu$ than in $\mu'$ because at least one man does and the marriage are bilateral, we see that woman $w$ must have a different spouse in $\mu$ than in $\mu'$. Thus, man $m = \mu(w)$ must also have a different spouse in $\mu$ than in $\mu'$. Since all stable matchings are individually rational, the fact that $w$ prefers $\mu(w)$ to $\mu'(w)$ implies $w$ is not single at $\mu$. Since man $m$ also has strict preferences, then $(m,w)$ forms a blocking pair for the matching $\mu'$, which contradicts the original assumption that $mu'$ is stable. Thus, $\mu'\succ_W\mu$ as desired.
\end{proof}

While we have discussed the M and W-optimal stable matchings at length, the set of stable matchings is not limited to just these. In fact, there can exist a much larger set of stable matchings which vary in optimality for the two sides of the market.

\subsection{Lattice Structure of Stable Matchings}\label{subsec:latt-struc}
\begin{definition}[Lattice]
A lattice is a partially ordered set $L$ for which any two of its elements $a,b$ have a supremum, denoted $a\vee b$, and an infimum, denoted by $a\wedge b$. 
\end{definition}

\begin{definition}[Distributive Lattice]
A lattice is distributive if and only if for all $a,b,c\in L$ the two following conditions hold
\begin{align*}
    a\wedge (b\vee c) &= (a \wedge b) \vee (a \wedge c) \\
    a\vee (b\wedge c) &= (a \vee b) \wedge (a \vee c)
\end{align*} 
\end{definition}

Using these definitions of algebraic lattices, we provide three theorems linking the structure of stable matchings to lattice theory.

\begin{theorem}\label{stable-lattice}
When all preferences are strict, if $\mu,\mu'$ are stable matchings, then the functions $\lambda = \mu\vee_M \mu'$ and $\nu = \mu\wedge_M\mu'$ are both stable matchings \cite{knuth}.
\end{theorem}
\begin{proof}
We need to show that both $\lambda$ and $\nu$ are stable matchings. First, we show $\lambda$ is a matching by showing that $\lambda(m) = w$ if and only if $\lambda(w)=m$. Because both $\mu, \mu'$ are stable, we know that $\lambda(m)=w$ implies $\lambda(w)=m$. 

In the other direction, let us define the set \[M' = \{m \text{ such that } \lambda(m) \text{ is in } W\} = \{m \text{ such that } \mu(m) \text{ or } \mu'(m) \text{ is in } W\}\] Similarly, define the set \[W' = \{m \text{ such that } \lambda(w) \text{ is in } M\} = \{w \text{ such that } \mu(w) \text{ or } \mu'(w) \text{ is in } M\}\] Using the direction proved above, we know that $\lambda(M')$ is contained in $W'$. However, we also know that the size of $\lambda(M')$ is the same as $M'$ because $\lambda(m) = \lambda(m') = w$ only if $m = m' = \lambda(w)$. Furthermore, $\lambda(M')$ is at least as large as $\mu(W')$, so $\lambda(M')$ and $W'$ are the same size and $\lambda(M')=W'$. Thus, for $w\in W'$, $\lambda(w)=m$ for some $m\in M'$ so $\lambda(w)=m$. If $w\notin W'$ then $\lambda(w)=w$. This means $\lambda(w)=m$ implies $\lambda(m)=w$. This shows that $\lambda$ is a matching.

Now, we will prove that $\lambda$ is stable. Suppose for contradiction that $(m,w)$ is blocking $\lambda$. Then \[w\succ_m \lambda(m)\implies w\succ_m\mu(m) \implies w\succ_m \mu'(m)\] On the other hand, we also have $m\succ_w \lambda(w)$. Thus, $(m,w)$ blocks the matching $\mu$ if $\lambda(w) = \mu(w)$ and blocks the matching $\mu'$ if $\lambda(w) = \mu'(w)$. In both cases, we get a contradiction, since both $\mu,\mu'$ are stable and cannot have any blocking pairs. Thus, $\lambda$ is a stable matching.

By a symmetric argument, we can show that $\nu$ is also a stable matching.
\end{proof}

\begin{corollary}\label{coro:distlattice}
When preferences are strict, the set of stable matchings is a distributive lattice under the common order of men dual to the common order of women.
\end{corollary}
\begin{proof}
This corollary follows directly from Theorem \ref{stable-lattice}.
\end{proof}

Mathematically, we can also see that both Theorem \ref{stable-lattice} and Corollary \ref{coro:distlattice} are direct results of Tarski's fixed point theorem \cite{fleiner_2003,hatfield_milgrom_2005}.

Not only do we see structure at the macro level, using the lattice theory language of meets and joins to understand the set of stable matchings, but there is also structure at the micro level in the set of individual agents involved in every stable matching.

\begin{theorem}[Lone Wolf Theorem]\label{thm:1to1single}
In a marriage market with strict preferences, the set of people who are single is the same for all stable matchings \cite{mcvitie_wilson_1970}.
\end{theorem}

\subsection{Pareto Optimality}

While we have seen that the M-optimal stable matching is the best stable match men can achieve, a stronger characteristic of matchings that we might care about is Pareto optimality, which measures efficiency. 

\begin{definition}[Weak Pareto Optimality]
A matching $\mu$ is weakly Pareto optimal for men if there are no alternative matchings that would would be \emph{strictly preferred} by \emph{all} men \cite{roth}.
\end{definition}

\begin{definition}[Strong Pareto Optimality]
A matching $\mu$ is strongly Pareto optimal for men if there are no alternative matchings that would would be strictly preferred by some men and weakly preferred by all men. This means that the matching is liked at least as well by all men and preferred by some men.
\end{definition}

In particular, we are interested to see if there is an unstable matching that all men would prefer, indicating that the men are paying a price for stability. However, we see that this is not true.

\begin{theorem}\label{thm:1to1pareto}
There is no individually rational matching $\mu$ (stable or not) such that $\mu\succ_m\mu_M$for all $m\in M$. This means $\mu_M$ is weakly Pareto optimal for all men $M$.
\end{theorem}

\begin{proof}
Let us consider the man-proposing deferred acceptance algorithm. Assume for contradiction that a better matching $\mu$ existed. Then, it would match every man $m$ to some woman $w$ who had rejected him in the algorithm in favor of some other man $m'$. This means that that set of women, $\mu(M)$, would have also been matched under $\mu_M$, more formally written as $\mu_M(\mu(M)) = M$. However, since all men in $M$ are matched under the M-optimal matching $\mu_M$, then any woman who got a proposal in the last step of the algorithm has not rejected any acceptable man, since the algorithm stops as soon as every woman in $\mu_M(M)$ holds an acceptable proposal. Since every man prefers $\mu$ to $\mu_M$, this would mean that such a woman would have had to be single at $\mu$, which contradicts the fact that $\mu_M(M) = \mu(M)$.
\end{proof}

Through the below example, we see that the M-optimal matching, while weakly Pareto optimal, is not strongly Pareto optimal.

Consider the following preferences for a set of three men and three women.
\begin{align*}
    P(m_1) = w_2\succ w_1\succ w_3 &\qquad P(w_1) = m_1\succ m_2\succ m_3 \\
    P(m_2) = w_1\succ w_2\succ w_3 &\qquad P(w_2) = m_3,m_1\succ m_2 \\
    P(m_3) = w_1\succ w_2\succ w_3 &\qquad P(w_3) = m_1\succ m_2\succ m_3 
\end{align*}

Then using the man-proposing deferred acceptance algorithm, we get than the M-optimal matching is \[\mu_M(m_1) = w_1 \quad \mu_M(m_2) = w_3 \quad \mu_M(m_3) = w_2\]

However, the below matching \[\mu(m_1) = w_2 \quad \mu(m_2) = w_3 \quad \mu(m_3) = w_1\] leaves $m_2$ with the same match as he had under $\mu_M$, but improves the matches of $m_1$ and $m_3$. Thus, the M-optimal matching is not strongly Pareto optimal, and there may be some non-stable matchings which are liked at least well as $\mu_M$ by all men and preferred by some men.


\section{Structures of Many-to-One Matchings}

In this section, we will see that the results of optimal stable matchings extend from the one-to-one to the many-to-one setting, wherease the Pareto-optimality conditions no longer hold true when looking at the many-to-one market.

\subsection{Optimal Stable Matchings}

In Theorem \ref{thm:nmrp}, we proved that the NMRP algorithm gives a stable matching. Extending the one-to-one definition, a hospital $H$ and student $s$ are achievable if there is some stable matching in which they are matched. For each hospital $H_i$ with quota $q_i$, we can define $a_i$ to be the number of achievable students, and let $k_i = \min(a_i,q_i)$. Thus, for any set of preferences submitted by hospitals over students, the NMRP algorithm produces a matching that is hospital-optimal, which we will now prove.

\begin{theorem}
For any submitted list of strict preferences over individuals, the NMRP algorithm produces a matching that gives each hospital $H_i$ its $k_i$ highest ranked achievable students.
\end{theorem}
\begin{proof}
In order to show that the final assignment gives each hospital its top $q_i$ achievable students, whether it has many achievable students when $a_i > q_i$ or all its achievable students if $a_i < q_i$, it is equivalent to show that no achievable student is ever deleted from a hospital's rank-order list. We will proceed by induction.

Suppose that up to the $r$-th iteration of the algorithm, no student has been deleted from the ranking of a hospital for whom they are achievable and that on the $(r+1)$-th iteration, student $s_j$ is tentatively matched with hospital $H_i$ and deleted from the ranking of hospital $H_k$. Then, any assignment that matches $s_j$ with $H_k$ and assigns achievable matches to $H_i$ must be unstable for two reasons. First, $H_i \succ_{s_j} H_k$. Second, because $s_j$ was top-ranked by $H_i$ at the end of the $r$-th iteration when no achievable students had yet been deleted from $H_i$'s rank-order list, $s_j$ must be ranked higher by $H_i$ than one of its assignees. Therefore, $s_j$ is not achievable for $H_k$. Therefore, no achievable student will ever deleted from a hospital's rank order list and the final assignment must give each hospital its top $q_i$ achievable students.
\end{proof}

\begin{corollary}
When preferences are strict, there exists a hospital-optimal stable matching that every hospital likes as well as any other matching, and a student-optimal stable matching that every student likes as well as any other stable matching.
\end{corollary}
\begin{proof}
The existence of the hospital-optimal stable matching follows from the preceding theorem. The existence of the the student-optimal stable matching when preferences are strict follows directly from the one-to-one setting.
\end{proof}

Since the matching found is the unique hospital-optimal stable matching, hospitals ought to prefer the matching from the NMRP algorithm to any other stable matching possible given the preference lists. In fact, this result is stronger than the one-to-one setting. Whereas in the M-optimal matching, the men receive their most preferred achievable mate, in the many-to-one setting, each hospital is able to receive its $k_i$ most preferred achievable students.

\subsection{Geographic Constraints}

At the end of Section \ref{subsec:latt-struc}, we see that the set of single individuals is the same in every stable matching. This result extends to the many-to-one setting as follows.
\begin{theorem}\label{thm:geoconstraints}
When all preferences over individuals are strict, the set of students admitted and seats filled in the hospital-intern problem is the same at every stable matching \cite{roth_1986}.
\end{theorem}
\begin{proof}
This proof follows directly from the one-to-one result (Theorem \ref{thm:1to1single}) and the equivalence of the hospital-intern problem with the related marriage markets problem (Theorem \ref{thm:marriage-hospital}).
\end{proof}

Unlike the one-to-one setting, this has direct implications in the many-to-one setting of the hospital-intern market. Using the NMRP algorithm, it was noticed that many rural hospitals have difficulty filling positions and are largely filled with foreign students. In particular, this has led to concerns about the quality of medical care in rural communities. Given this problem, it has been proposed to alter the NMRP algorithm so as to equalize the distribution of interns across urban and rural hospitals. However, it is highly difficult to modify the algorithm to more fairly re-distribute interns across US hospitals while still maintaining the stability constraint. In fact, Theorem \ref{thm:geoconstraints} demonstrates that this goal is impossible, due to the structural limitations of who gets assigned in every stable matching.

\subsection{Pareto Optimality}
In contrast with the Pareto optimality results from the one-to-one matching setting, similar results do not hold for the hospital-intern model. 

\begin{theorem}
When preferences over individuals are strict, the student-optimal stable matching is weakly Pareto optimal for students, but the hospital-optimal stable matching may not be weakly Pareto optimal for hospitals. 
\end{theorem}

\begin{proof}
The first part can be proved by looking at the weak Pareto optimality result from one-to-one matching in Theorem \ref{thm:1to1pareto} and noting that the set of stable matchings from the hospital-intern model and the related marriage market problem are equivalent.

The second part can be shown via counterexample. Consider the set of hospitals $\{h_1,h_2,h_3\}$ and set of students $\{s_1,s_2,s_3,s_4\}$, with $q_{h_1} = 2$ and $q_{h_2} = q_{h_3} = 1$. The preferences are given below.
\begin{align*}
    P(s_1) = h_3\succ h_1\succ h_2 &\quad P(h_1) = s_1\succ s_2\succ s_3\succ s_4\\
    P(s_2) = h_2\succ h_1\succ h_3 &\quad P(h_2) = s_1\succ s_2\succ s_3\succ s_4 \\
    P(s_3) = h_1\succ h_3\succ h_2 &\quad P(h_3) = s_3\succ s_1\succ s_2\succ s_4 \\
    P(s_4) = h_1\succ h_2\succ h_3 &\quad
\end{align*}
The only stable matching that is hospital-optimal is $\mu_H$ given by \[\mu_H(h_1) = s_3, s_4 \quad \mu_H(h_2) = s_2 \quad \mu_H(h_3) = s_1\] However, the matching $\mu$ given by \[\mu(h_1) = s_2, s_4 \quad \mu(h_2) = s_1 \quad \mu(h_3) = s_3\] gives both hospitals $h_2, h_3$ their first choice student over their second choice student, so they both prefer $\mu$ to $\mu_H$. Since $h_1$ gets their second and fourth choice students over their third and fourth choice students, $h_1$ also prefers $\mu$ to $\mu_H$, meaning every hospital prefers $\mu$ to $\mu_H$ and the hospital-optimal stable matching may not be even weakly Pareto optimal. Note that $\mu$ is not a stable matching because $(h_1,s_1)$ are a hospital-student blocking pair, as $h_1$ would prefer to be matched to $s_1,s_4$ over $s_2,s_4$, and $s_1$ prefers $h_1$ to $h_2$.
\end{proof}

\section{Chapter Summary}
In Chapter 2, we saw direct analogies between the one-to-one and many-to-one settings in the existence of stable matchings through constructive algorithms. However, in this chapter, we see that the results from one-to-one matching do not always transfer to the many-to-one matching setting. While there are direct connections between the set of optimal stable matchings as well as the set of individuals matched in each stable matching, characteristics of efficiency such as weak Pareto optimality do not hold in the many-to-one setting as they do in the one-to-one setting. Thus, when implementing matching algorithms in practice, especially in many-to-one settings, the efficiency-stability tradeoff must be considered. Additionally, we see that the lattice structure of the set of stable matchings implies that any implementation of two-sided matching algorithms in the real-world will favor one side of the market. Hence, the choice of who gets to propose in matching mechanisms such as deferred acceptance remains in question for any policymaker seeking to implement them.