Matching Games - Game Theory

Many allocation problems require pairing agents from two groups such that no pair would mutually prefer to be matched to each other instead. This chapter develops the theory of stable matchings and the Gale–Shapley algorithm that constructs them.

Motivating Example: Stable peer review assignment at a research conference¶

The Social Perspectives Research Symposium receives five paper submissions and recruits five expert reviewers. Each paper must be assigned to exactly one reviewer.

To promote high-quality reviews, both authors and reviewers submit ranked preference lists:

Each author ranks the reviewers based on perceived expertise, familiarity with the topic, and potential for constructive feedback.
Each reviewer ranks the submissions based on interest, alignment with their research, and methodological fit.

The participants are:

Authors: A1, A2, A3, A4, A5
Reviewers: R1, R2, R3, R4, R5

For example:

Author A1 has written a paper on representation in environmental activism and ranks R3, an expert in environmental sociology, as their top choice.
Reviewer R2 specializes in healthcare policy and ranks submission A4 as their first choice due to its relevance.
Author A5’s paper focuses on queer representation in contemporary fiction, and they rank R5 highly based on prior work in literature studies.

“R3’s expertise would be invaluable for my analysis.”
“A4’s topic fits directly with my current research.”
“R5’s previous reviews have been extremely helpful.”

The preferences of the authors are given in Table 1 and the preferences of the reviewers are given in Table 2.

Table 1:Preference table for the authors

Author	1st	2nd	3rd	4th	5th
A1	R3	R1	R4	R5	R2
A2	R2	R4	R3	R5	R1
A3	R5	R2	R3	R1	R4
A4	R2	R3	R5	R1	R4
A5	R5	R3	R4	R2	R1

The organizers aim to compute a stable matching: an assignment where no author-reviewer pair exists who would both prefer to be assigned to each other over their current assignments.

Table 2:Preference table for the reviewers

Reviewer	1st	2nd	3rd	4th	5th
R1	A3	A1	A5	A4	A2
R2	A4	A2	A5	A1	A3
R3	A1	A5	A2	A3	A4
R4	A2	A5	A3	A1	A4
R5	A5	A3	A4	A1	A2

Theory¶

Definition: Matching Game¶

A matching game of size $N$ is defined by two disjoint sets $S$ and $R$ of proposers and reviewers of size $N$ . Associated to each element of $S$ and $R$ is a preference map:

f:S\to R^N\text{ and }g:R\to S^N

(1)

A matching $M$ is any bijection between $S$ and $R$ . If $s\in S$ and $r\in R$ are matched by $M$ we denote:

M(s)=r

(2)

Example: Author Reviewer as a Matching Game¶

For Motivating Example: Stable peer review assignment at a research conference the matching game has size $N=5$ , the set of proposers $S=(A1, A2, A3, A4, A5)$ the set of reviewers $R=(R1, R2, R3, R4, R5)$ and the preference maps:

\begin{align*} f(A1)&=(R3, R1, R4, R5, R2)\\ f(A2)&=(R2, R4, R3, R5, R1)\\ f(A3)&=(R5, R2, R3, R1, R4)\\ f(A4)&=(R2, R3, R5, R1, R4)\\ f(A5)&=(R5, R3, R4, R2, R1)\\ g(R1)&=(A3, A1, A5, A4, A2)\\ g(R2)&=(A4, A2, A5, A1, A3)\\ g(R3)&=(A1, A5, A2, A3, A4)\\ g(R4)&=(A2, A5, A3, A1, A4)\\ g(R5)&=(A5, A3, A4, A1, A2) \end{align*}

(3)

One potential mapping is given by:

\begin{align*} M(A1) &= R3\\ M(A2) &= R2\\ M(A3) &= R5\\ M(A4) &= R1\\ M(A5) &= R4 \end{align*}

(4)

Definition: a blocking pair¶

A pair $(s,r)$ is said to block a matching $M$ if $M(s)\ne r$ but $s$ prefers $r$ to $M(s)$ and $r$ prefers $s$ to $M^{-1}(r)$ .

Example: Blocking pair for the author reviewer game¶

In (4) the pair $(A4, R2)$ is a blocking pair as $A4$ prefer $R2$ to $M(A4)$ and $R2$ prefers $A4$ to $M^{-1}(R2)$ .

Definition: a stable matching¶

A matching $M$ with no blocking pair is said to be stable.

Example: A stable matching for the author reviewer game¶

The following is a stable matching for Motivating Example: Stable peer review assignment at a research conference:

\begin{align*} M(A1) &= R3\\ M(A2) &= R4\\ M(A3) &= R1\\ M(A4) &= R2\\ M(A5) &= R5 \end{align*}

(5)

Definition: The Gale-Shapley algorithm¶

Here is the Gale-Shapley algorithm, which gives a stable matching for a matching game:

Assign every $s\in S$ and $r\in R$ to be unmatched
Pick some unmatched $s\in S$ , let $r$ be the top of $s$ ’s preference list:
- If $r$ is unmatched set $M(s)=r$
- If $r$ is matched:
  - If $r$ prefers $s$ to $M^{-1}(r)$ then set $M(s)=r$ and unmatch the previous partner $M^{-1}(r)$
  - Otherwise $s$ remains unmatched and remove $r$ from $s$ ’s preference list.
Repeat step 2 until all $s\in S$ are matched.

Theorem: Unique matching as output of the Gale Shapley algorithm¶

All possible executions of the Gale-Shapley algorithm yield the same stable matching and in this stable matching every suitor has the best possible partner in any stable matching.

Proof¶

Call a reviewer $r$ a stable partner of a suitor $s$ if $M''(s) = r$ in some stable matching $M''$ . We show that no suitor is ever rejected by a stable partner during an execution $\alpha$ . Since suitors propose in decreasing order of preference, this implies that each suitor ends $\alpha$ matched to their most preferred stable partner, so the outcome does not depend on $\alpha$ .

Suppose, for contradiction, that during $\alpha$ some suitor is rejected by a stable partner, and consider the first such rejection: reviewer $r'$ rejects suitor $s$ , where $r'$ is a stable partner of $s$ , so $M'(s) = r'$ for some stable matching $M'$ . The reviewer $r'$ rejects $s$ in favour of a suitor $s'$ whom $r'$ prefers to $s$ ; that is, at that moment $r'$ holds a proposal from $s'$ and prefers $s'$ to $s$ .

Because this is the first rejection by a stable partner, $s'$ has not yet been rejected by any stable partner. As suitors propose in order of preference and $s'$ is currently proposing to $r'$ , the reviewer $r'$ is at least as high in $s'$ 's list as any reviewer $s'$ has proposed to so far, and in particular at least as high as every stable partner of $s'$ . Hence $s'$ weakly prefers $r'$ to $M'(s')$ , and since preferences are strict and $M'(s') \ne r'$ (as $M'(r') = s$ ), $s'$ strictly prefers $r'$ to $M'(s')$ .

Then $s'$ prefers $r'$ to $M'(s')$ and $r'$ prefers $s'$ to $s = M'(r')$ , so $(s', r')$ blocks $M'$ , contradicting the stability of $M'$ . No suitor is therefore rejected by a stable partner, each suitor is matched in $M$ with their favourite stable reviewer, and since $\alpha$ was arbitrary all executions give the same matching.

Example: Application of the Gale-Shapley algorithm to the author reviewer game¶

We start by assigning $A1, A2, A3, A4, A5$ and $R1, R2, R3, R4, R5$ to be unmatched.

We pick $A1$ which has $f(A1)=(R3, R1, R4, R5, R2)$ , the top of the preference list is $R3$ so we set:

\begin{align*} M(A1) &= R3 \end{align*}

(6)

We now pick $A2$ which has $f(A2)=(R2, R4, R3, R5, R1)$ , the top of the preference list is $R2$ so we set:

\begin{align*} M(A1) &= R3\\ M(A2) &= R2\\ \end{align*}

(7)

We now pick $A3$ which has $f(A3)=(R5, R2, R3, R1, R4)$ , the top of the preference list is $R5$ so we set:

\begin{align*} M(A1) &= R3\\ M(A2) &= R2\\ M(A3) &= R5\\ \end{align*}

(8)

We now pick $A4$ which has $f(A4)=(R2, R3, R5, R1, R4)$ , the top of the preference list is $R2$ but $R2$ is matched ( $M(A2)=R2$ ). We have $g(R2)=(A4, A2, A5, A1, A3)$ so $R2$ prefers $A4$ to their current matching $A2$ . So $A2$ becomes unmatched and we set:

\begin{align*} M(A1) &= R3\\ M(A3) &= R5\\ M(A4) &= R2\\ \end{align*}

(9)

We now pick $A2$ (for the second time) which has $f(A2)=(R2, R4, R3, R5, R1)$ , the top of the preference list is $R2$ but $R2$ is matched and prefers their current matching so we remove it from $A2$ ’s preference list:

f(A2)=(R4, R3, R5, R1)

(10)

We could pick any unmatched author, we will pick $A2$ again (for the third time), $A2$ has preference list $f(A2)=(R4, R3, R5, R1)$ , the top of the preference list is $R4$ so we set:

\begin{align*} M(A1) &= R3\\ M(A2) &= R4\\ M(A3) &= R5\\ M(A4) &= R2\\ \end{align*}

(11)

We now pick $A5$ , the final unmatched author, which has $f(A5)=(R5, R3, R4, R2, R1)$ , the top of the preference list is $R5$ but $R5$ is matched ( $M(A3)=R5$ ). We have $g(R5)=(A5, A3, A4, A1, A2)$ so $R5$ prefers $A5$ to their current matching. So we set:

\begin{align*} M(A1) &= R3\\ M(A2) &= R4\\ M(A4) &= R2\\ M(A5) &= R5\\ \end{align*}

(12)

We now pick $A3$ , the one remaining unmatched author, which has $f(A3)=(R5, R2, R3, R1, R4)$ , the top of the preference list is $R5$ but $R5$ is matched and prefers their current matching so we remove it from $A3$ ’s preference list:

f(A3)=(R2, R3, R1, R4)

(13)

We now pick $A3$ again as it is still the only unmatched author. The top of the preference list is $R2$ but $R2$ is matched and prefers their current matching so we remove it from $A3$ ’s preference list:

f(A3)=(R3, R1, R4)

(14)

We pick $A3$ again. The top of the preference list is $R3$ but $R3$ is matched and prefers their current matching so we remove it from $A3$ ’s preference list:

f(A3)=(R1, R4)

(15)

We pick $A3$ again and match it to $R1$ giving the final matching:

\begin{align*} M(A1) &= R3\\ M(A2) &= R4\\ M(A3) &= R1\\ M(A4) &= R2\\ M(A5) &= R5\\ \end{align*}

(16)

Theorem: Reviewer sub optimality of the Gale Shapley Algorithm¶

In a suitor-optimal stable matching each reviewer has the worst possible matching.

Proof¶

Assume that the result is not true. Let $M_0$ be a suitor-optimal matching and assume that there is a stable matching $M'$ such that $\exists$ $r$ such that $r$ prefers $s=M_0^{-1}(r)$ to $s'=M'^{-1}(r)$ . Since preferences are strict and $M'(s) \ne r$ , the suitor $s$ either prefers $M'(s)$ to $M_0(s) = r$ or prefers $M_0(s) = r$ to $M'(s)$ . The former is impossible, as suitor-optimality means $s$ has no stable match they prefer to $M_0(s)$ . Hence $s$ prefers $r$ to $M'(s)$ , and as $r$ prefers $s$ to $M'(r) = s'$ , the pair $(r,s)$ blocks $M'$ , contradicting its stability. Every reviewer therefore does at least as badly in $M_0$ as in any stable matching, so $M_0$ is reviewer-pessimal.

Exercises¶

Exercise 1

Obtain stable suitor optimal and reviewer optimal matchings for the games shown:

$\begin{align*} f(A1)&=(R2, R1, R3)\\ f(A2)&=(R1, R3, R2)\\ f(A3)&=(R1, R3, R2)\\ g(R1)&=(A1, A2, A3)\\ g(R2)&=(A2, A1, A3)\\ g(R3)&=(A2, A3, A1)\\ \end{align*}$
(17)
$\begin{align*} f(A1)&=(R1, R3, R2)\\ f(A2)&=(R2, R3, R1)\\ f(A3)&=(R1, R3, R2)\\ g(R1)&=(A1, A2, A3)\\ g(R2)&=(A2, A3, A1)\\ g(R3)&=(A2, A3, A1)\\ \end{align*}$
(18)
$\begin{align*} f(A1)&=(R1, R4, R2, R3)\\ f(A2)&=(R2, R1, R3, R4)\\ f(A3)&=(R4, R1, R3, R2)\\ f(A4)&=(R1, R4, R3, R2)\\ g(R1)&=(A1, A4, A2, A3)\\ g(R2)&=(A1, A3, A4, A2)\\ g(R3)&=(A4, A1, A3, A2)\\ g(R4)&=(A2, A4, A1, A3)\\ \end{align*}$
(19)
$\begin{align*} f(A1)&=(R2, R1, R4, R3)\\ f(A2)&=(R2, R3, R1, R4)\\ f(A3)&=(R1, R4, R3, R2)\\ f(A4)&=(R1, R4, R3, R2)\\ g(R1)&=(A1, A2, A4, A3)\\ g(R2)&=(A4, A2, A1, A3)\\ g(R3)&=(A4, A1, A3, A2)\\ g(R4)&=(A3, A2, A4, A1)\\ \end{align*}$
(20)

Programming¶

The python Matching library Wilde et al., 2020 implements the Gale-Shapley algorithm as well as a number of other algorithms for different generalisations of matching games.

import matching
import matching.games

authors = [
    matching.Player("A1"),
    matching.Player("A2"),
    matching.Player("A3"),
    matching.Player("A4"),
    matching.Player("A5"),
]

reviewers = [
    matching.Player("R1"),
    matching.Player("R2"),
    matching.Player("R3"),
    matching.Player("R4"),
    matching.Player("R5"),
]

A1, A2, A3, A4, A5 = authors
R1, R2, R3, R4, R5 = reviewers

A1.set_prefs((R3, R1, R4, R5, R2))
A2.set_prefs((R2, R4, R3, R5, R1))
A3.set_prefs((R5, R2, R3, R1, R4))
A4.set_prefs((R2, R3, R5, R1, R4))
A5.set_prefs((R5, R3, R4, R2, R1))

R1.set_prefs((A3, A1, A5, A4, A2))
R2.set_prefs((A4, A2, A5, A1, A3))
R3.set_prefs((A1, A5, A2, A3, A4))
R4.set_prefs((A2, A5, A3, A1, A4))
R5.set_prefs((A5, A3, A4, A1, A2))

game = matching.games.StableMarriage(authors, reviewers)
print(f"Stable matching: {game.solve()}")

Stable matching: {A1: R3, A2: R4, A3: R1, A4: R2, A5: R5}

Notable Research¶

The original Gale-Shapley algorithm was presented in Gale & Shapley, 1962, a rigorous combinatorial treatment of the algorithm is given in Knuth, 1976. Some refinements to the algorithm are given in Gusfield & Irving, 1989 which is considered to be the reference text on matching games.

In the original paper Gale & Shapley, 1962 Gale and Shapley present the so called hospital-resident matching problem which is a matching problem aiming to match many to one. They do so in the context of College admissions in North America. In Roth, 1984 presents the problem in the context of hospital resident assignement. Further to this, Roth considered the problem of kidney exchange in Roth et al., 2004 as a further matching problem.

In 2012, Lloyd Shapley and Alvin Roth were awarded the Nobel Prize in Economic Sciences for their contributions to stable matching and market design. David Gale, who co-authored the foundational 1962 paper introducing the Gale-Shapley algorithm, was ineligible for the award, having passed away in 2008.

Conclusion¶

In this chapter we introduced the theory of matching games, motivated by the practical problem of assigning reviewers to papers at a research conference. The central concept of stability ensures that no pair of participants would prefer to deviate from the assignment, making stable matchings attractive in many real-world settings.

The Gale-Shapley algorithm provides an elegant and efficient solution to the stable matching problem, always producing a suitor-optimal stable matching. While stable matchings always exist in the one-to-one setting, extensions to many-to-one settings (such as hospital-resident assignments) preserve many of the desirable properties of the original algorithm.

A summary of key concepts introduced in this chapter is given in Table 3.

Table 3:Summary of key concepts in matching games

Concept	Description
Matching Game	A game where two disjoint sets have preferences over each other
Stable Matching	A matching with no blocking pairs
Blocking Pair	A pair who would both prefer to be matched to each other over their current assignments
Gale-Shapley Algorithm	An algorithm that produces a stable matching by iteratively proposing and accepting/rejecting proposals
Suitor-optimality	The property that each suitor receives the best possible partner across all stable matchings
Reviewer-pessimality	The property that in suitor-optimal matchings, each reviewer receives the worst acceptable partner

Solutions¶

Solution to Exercise 1 #

For each game we run the Gale-Shapley algorithm from the suitor (A) side to obtain the suitor-optimal matching, then repeat with the reviewer (R) side proposing to obtain the reviewer-optimal (equivalently, suitor-pessimal) matching.

\begin{align*} f(A1)&=(R2, R1, R3)\\ f(A2)&=(R1, R3, R2)\\ f(A3)&=(R1, R3, R2)\\ g(R1)&=(A1, A2, A3)\\ g(R2)&=(A2, A1, A3)\\ g(R3)&=(A2, A3, A1)\\ \end{align*}

(21)

Suitor-optimal matching (A proposes):

A1 proposes to R2 (top of A1’s list). R2 is unmatched, so $M(A1)=R2$ .
A2 proposes to R1 (top of A2’s list). R1 is unmatched, so $M(A2)=R1$ .
A3 proposes to R1 (top of A3’s list). R1 is matched to A2. $g(R1)=(A1,A2,A3)$ , so R1 prefers A2 to A3. A3 is rejected; remove R1 from A3’s list: $f(A3)=(R3, R2)$ .
A3 proposes to R3. R3 is unmatched, so $M(A3)=R3$ .

Suitor-optimal matching:

M_S: \quad M(A1)=R2,\quad M(A2)=R1,\quad M(A3)=R3

(22)

Verification (no blocking pairs):

$(A1, R1)$ : A1 prefers R2 to R1 (R2 is first in A1’s list). Not blocking.
$(A1, R3)$ : A1 prefers R2 to R3. Not blocking.
$(A2, R2)$ : A2 prefers R1 to R2. Not blocking.
$(A2, R3)$ : A2 prefers R1 to R3. Not blocking.
$(A3, R1)$ : A3 prefers R1 to R3, but R1 prefers A2 (current match) to A3. Not blocking.
$(A3, R2)$ : A3 prefers R3 to R2 (R3 is second, R2 is third in A3’s remaining list). Actually $f(A3)=(R1,R3,R2)$ originally, so A3 prefers R3 to R2. Not blocking.

The matching is stable.

Reviewer-optimal matching (R proposes):

R1 proposes to A1 (top of R1’s list). A1 is unmatched, so $M^{-1}(R1)=A1$ .
R2 proposes to A2 (top of R2’s list). A2 is unmatched, so $M^{-1}(R2)=A2$ .
R3 proposes to A2 (top of R3’s list). A2 is matched to R2. $f(A2)=(R1,R3,R2)$ , so A2 prefers R3 to R2. R2 is rejected; $M^{-1}(R3)=A2$ . R2 removes A2 from its list: $g(R2)=(A1,A3)$ .
R2 proposes to A1. A1 is matched to R1. $f(A1)=(R2,R1,R3)$ , so A1 prefers R2 to R1. R1 is rejected; $M^{-1}(R2)=A1$ . R1 removes A1 from its list: $g(R1)=(A2,A3)$ .
R1 proposes to A2. A2 is matched to R3. $f(A2)=(R1,R3,R2)$ , so A2 prefers R1 to R3. R3 is rejected; $M^{-1}(R1)=A2$ . R3 removes A2 from its list: $g(R3)=(A3,A1)$ .
R3 proposes to A3. A3 is unmatched, so $M^{-1}(R3)=A3$ .

Reviewer-optimal matching:

M_R: \quad M(A1)=R2,\quad M(A2)=R1,\quad M(A3)=R3

(23)

In this case both matchings coincide.

\begin{align*} f(A1)&=(R1, R3, R2)\\ f(A2)&=(R2, R3, R1)\\ f(A3)&=(R1, R3, R2)\\ g(R1)&=(A1, A2, A3)\\ g(R2)&=(A2, A3, A1)\\ g(R3)&=(A2, A3, A1)\\ \end{align*}

(24)

Suitor-optimal matching (A proposes):

A1 proposes to R1. R1 is unmatched, so $M(A1)=R1$ .
A2 proposes to R2. R2 is unmatched, so $M(A2)=R2$ .
A3 proposes to R1. R1 is matched to A1. $g(R1)=(A1,A2,A3)$ , so R1 prefers A1 to A3. A3 is rejected; $f(A3)=(R3,R2)$ .
A3 proposes to R3. R3 is unmatched, so $M(A3)=R3$ .

Suitor-optimal matching:

M_S: \quad M(A1)=R1,\quad M(A2)=R2,\quad M(A3)=R3

(25)

Reviewer-optimal matching (R proposes):

R1 proposes to A1. A1 is unmatched, so $M^{-1}(R1)=A1$ .
R2 proposes to A2. A2 is unmatched, so $M^{-1}(R2)=A2$ .
R3 proposes to A2. A2 is matched to R2. $f(A2)=(R2,R3,R1)$ , so A2 prefers R2 to R3. R3 is rejected; $g(R3)=(A3,A1)$ .
R3 proposes to A3. A3 is unmatched, so $M^{-1}(R3)=A3$ .

Reviewer-optimal matching:

M_R: \quad M(A1)=R1,\quad M(A2)=R2,\quad M(A3)=R3

(26)

Again both matchings coincide.

\begin{align*} f(A1)&=(R1, R4, R2, R3)\\ f(A2)&=(R2, R1, R3, R4)\\ f(A3)&=(R4, R1, R3, R2)\\ f(A4)&=(R1, R4, R3, R2)\\ g(R1)&=(A1, A4, A2, A3)\\ g(R2)&=(A1, A3, A4, A2)\\ g(R3)&=(A4, A1, A3, A2)\\ g(R4)&=(A2, A4, A1, A3)\\ \end{align*}

(27)

Suitor-optimal matching (A proposes):

A1 proposes to R1. R1 is unmatched, so $M(A1)=R1$ .
A2 proposes to R2. R2 is unmatched, so $M(A2)=R2$ .
A3 proposes to R4. R4 is unmatched, so $M(A3)=R4$ .
A4 proposes to R1. R1 matched to A1. $g(R1)=(A1,A4,A2,A3)$ : R1 prefers A1 to A4. A4 rejected; $f(A4)=(R4,R3,R2)$ .
A4 proposes to R4. R4 matched to A3. $g(R4)=(A2,A4,A1,A3)$ : R4 prefers A4 to A3. A3 displaced; $M(A4)=R4$ . A3’s list: $f(A3)=(R1,R3,R2)$ .
A3 proposes to R1. R1 matched to A1. $g(R1)=(A1,A4,A2,A3)$ : R1 prefers A1 to A3. A3 rejected; $f(A3)=(R3,R2)$ .
A3 proposes to R3. R3 unmatched, so $M(A3)=R3$ .

Suitor-optimal matching:

M_S: \quad M(A1)=R1,\quad M(A2)=R2,\quad M(A3)=R3,\quad M(A4)=R4

(28)

Reviewer-optimal matching (R proposes):

R1 proposes to A1. A1 unmatched, so $M^{-1}(R1)=A1$ .
R2 proposes to A1. A1 matched to R1. $f(A1)=(R1,R4,R2,R3)$ : A1 prefers R1 to R2. R2 rejected; $g(R2)=(A3,A4,A2)$ .
R3 proposes to A4. A4 unmatched, so $M^{-1}(R3)=A4$ .
R4 proposes to A2. A2 unmatched, so $M^{-1}(R4)=A2$ .
R2 proposes to A3. A3 unmatched, so $M^{-1}(R2)=A3$ .

Reviewer-optimal matching:

M_R: \quad M(A1)=R1,\quad M(A2)=R4,\quad M(A3)=R2,\quad M(A4)=R3

(29)

\begin{align*} f(A1)&=(R2, R1, R4, R3)\\ f(A2)&=(R2, R3, R1, R4)\\ f(A3)&=(R1, R4, R3, R2)\\ f(A4)&=(R1, R4, R3, R2)\\ g(R1)&=(A1, A2, A4, A3)\\ g(R2)&=(A4, A2, A1, A3)\\ g(R3)&=(A4, A1, A3, A2)\\ g(R4)&=(A3, A2, A4, A1)\\ \end{align*}

(30)

Suitor-optimal matching (A proposes):

A1 proposes to R2. R2 unmatched, so $M(A1)=R2$ .
A2 proposes to R2. R2 matched to A1. $g(R2)=(A4,A2,A1,A3)$ : R2 prefers A2 to A1. A1 displaced; $M(A2)=R2$ . A1’s list: $f(A1)=(R1,R4,R3)$ .
A3 proposes to R1. R1 unmatched, so $M(A3)=R1$ .
A4 proposes to R1. R1 matched to A3. $g(R1)=(A1,A2,A4,A3)$ : R1 prefers A4 to A3. A3 displaced; $M(A4)=R1$ . A3’s list: $f(A3)=(R4,R3,R2)$ .
A1 proposes to R1. R1 matched to A4. $g(R1)=(A1,A2,A4,A3)$ : R1 prefers A1 to A4. A4 displaced; $M(A1)=R1$ . A4’s list: $f(A4)=(R4,R3,R2)$ .
A4 proposes to R4. R4 unmatched, so $M(A4)=R4$ .
A3 proposes to R4. R4 matched to A4. $g(R4)=(A3,A2,A4,A1)$ : R4 prefers A3 to A4. A4 displaced; $M(A3)=R4$ . A4’s list: $f(A4)=(R3,R2)$ .
A4 proposes to R3. R3 unmatched, so $M(A4)=R3$ .

Suitor-optimal matching:

M_S: \quad M(A1)=R1,\quad M(A2)=R2,\quad M(A3)=R4,\quad M(A4)=R3

(31)

Reviewer-optimal matching (R proposes):

R1 proposes to A1. A1 unmatched, so $M^{-1}(R1)=A1$ .
R2 proposes to A4. A4 unmatched, so $M^{-1}(R2)=A4$ .
R3 proposes to A4. A4 matched to R2. $f(A4)=(R1,R4,R3,R2)$ : A4 prefers R3 to R2. R2 rejected; $M^{-1}(R3)=A4$ . $g(R2)=(A2,A1,A3)$ .
R4 proposes to A3. A3 unmatched, so $M^{-1}(R4)=A3$ .
R2 proposes to A2. A2 unmatched, so $M^{-1}(R2)=A2$ .

Reviewer-optimal matching:

M_R: \quad M(A1)=R1,\quad M(A2)=R2,\quad M(A3)=R4,\quad M(A4)=R3

(32)

Both matchings again coincide.

The following code verifies the suitor-optimal matchings using the matching library:

import matching
import matching.games


def solve_matching(suitor_prefs, reviewer_prefs):
    suitor_names = list(suitor_prefs.keys())
    reviewer_names = list(reviewer_prefs.keys())
    suitors = {name: matching.Player(name) for name in suitor_names}
    reviewers = {name: matching.Player(name) for name in reviewer_names}
    for name, prefs in suitor_prefs.items():
        suitors[name].set_prefs([reviewers[r] for r in prefs])
    for name, prefs in reviewer_prefs.items():
        reviewers[name].set_prefs([suitors[s] for s in prefs])
    game = matching.games.StableMarriage(
        list(suitors.values()), list(reviewers.values())
    )
    result = game.solve()
    return {str(k): str(v) for k, v in result.items()}


# Game 1
result1 = solve_matching(
    {"A1": ["R2","R1","R3"], "A2": ["R1","R3","R2"], "A3": ["R1","R3","R2"]},
    {"R1": ["A1","A2","A3"], "R2": ["A2","A1","A3"], "R3": ["A2","A3","A1"]},
)
print("Game 1 suitor-optimal:", result1)

Game 1 suitor-optimal: {'A1': 'R2', 'A2': 'R1', 'A3': 'R3'}

# Game 2
result2 = solve_matching(
    {"A1": ["R1","R3","R2"], "A2": ["R2","R3","R1"], "A3": ["R1","R3","R2"]},
    {"R1": ["A1","A2","A3"], "R2": ["A2","A3","A1"], "R3": ["A2","A3","A1"]},
)
print("Game 2 suitor-optimal:", result2)

Game 2 suitor-optimal: {'A1': 'R1', 'A2': 'R2', 'A3': 'R3'}

# Game 3
result3 = solve_matching(
    {
        "A1": ["R1","R4","R2","R3"],
        "A2": ["R2","R1","R3","R4"],
        "A3": ["R4","R1","R3","R2"],
        "A4": ["R1","R4","R3","R2"],
    },
    {
        "R1": ["A1","A4","A2","A3"],
        "R2": ["A1","A3","A4","A2"],
        "R3": ["A4","A1","A3","A2"],
        "R4": ["A2","A4","A1","A3"],
    },
)
print("Game 3 suitor-optimal:", result3)

Game 3 suitor-optimal: {'A1': 'R1', 'A2': 'R2', 'A3': 'R3', 'A4': 'R4'}

# Game 4
result4 = solve_matching(
    {
        "A1": ["R2","R1","R4","R3"],
        "A2": ["R2","R3","R1","R4"],
        "A3": ["R1","R4","R3","R2"],
        "A4": ["R1","R4","R3","R2"],
    },
    {
        "R1": ["A1","A2","A4","A3"],
        "R2": ["A4","A2","A1","A3"],
        "R3": ["A4","A1","A3","A2"],
        "R4": ["A3","A2","A4","A1"],
    },
)
print("Game 4 suitor-optimal:", result4)

Game 4 suitor-optimal: {'A1': 'R1', 'A2': 'R2', 'A3': 'R4', 'A4': 'R3'}

Solution to Exercise 2 #

Claim: If all reviewers share the same preference list over suitors, there is exactly one stable matching.

Proof:

Let the shared reviewer preference list rank the suitors as $s_{\sigma(1)} \succ s_{\sigma(2)} \succ \cdots \succ s_{\sigma(N)}$ (where $\sigma$ is a permutation of $\{1, \dots, N\}$ giving the common ordering).

We argue by induction on the number of suitors that the stable matching is unique. The base case of a single suitor and reviewer is immediate.

Consider the top-ranked suitor $s_{\sigma(1)}$ , whom every reviewer prefers to every other suitor. Let $r^\star$ be $s_{\sigma(1)}$ 's own most preferred reviewer. In any stable matching $M$ , the suitor $s_{\sigma(1)}$ is matched to $r^\star$ : if instead $M(s_{\sigma(1)}) \ne r^\star$ , then $s_{\sigma(1)}$ prefers $r^\star$ to $M(s_{\sigma(1)})$ , and $r^\star$ prefers $s_{\sigma(1)}$ to its own partner $M^{-1}(r^\star)$ (as $r^\star$ , like every reviewer, ranks $s_{\sigma(1)}$ first), so $(s_{\sigma(1)}, r^\star)$ blocks $M$ . Hence every stable matching pairs $s_{\sigma(1)}$ with $r^\star$ .

Removing $s_{\sigma(1)}$ and $r^\star$ leaves an instance on $N - 1$ suitors in which the reviewers still share a common ranking (the restriction of the original one). A matching of the full instance is stable if and only if it pairs $s_{\sigma(1)}$ with $r^\star$ and restricts to a stable matching of the smaller instance: no pair involving $s_{\sigma(1)}$ or $r^\star$ can block, since each has its most preferred partner, and any other blocking pair would block the smaller instance too. By the induction hypothesis the smaller instance has a unique stable matching, so the full instance does as well.

Hence there is exactly one stable matching. ◼

References¶

Wilde, H., Knight, V., & Gillard, J. (2020). Matching: A python library for solving matching games. Journal of Open Source Software, 5(48), 2169.
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9–15.
Knuth, D. E. (1976). Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal.
Gusfield, D., & Irving, R. W. (1989). The stable marriage problem: structure and algorithms. MIT press.
Roth, A. E. (1984). The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92(6), 991–1016.
Roth, A. E., Sönmez, T., & Ünver, M. U. (2004). Kidney Exchange. Quarterly Journal of Economics, 119(2), 457–488.

Author	1st	2nd	3rd	4th	5th
A1	R3	R1	R4	R5	R2
A2	R2	R4	R3	R5	R1
A3	R5	R2	R3	R1	R4
A4	R2	R3	R5	R1	R4
A5	R5	R3	R4	R2	R1

Reviewer	1st	2nd	3rd	4th	5th
R1	A3	A1	A5	A4	A2
R2	A4	A2	A5	A1	A3
R3	A1	A5	A2	A3	A4
R4	A2	A5	A3	A1	A4
R5	A5	A3	A4	A1	A2

Author	1st	2nd	3rd	4th	5th
A1	R3	R1	R4	R5	R2
A2	R2	R4	R3	R5	R1
A3	R5	R2	R3	R1	R4
A4	R2	R3	R5	R1	R4
A5	R5	R3	R4	R2	R1

Reviewer	1st	2nd	3rd	4th	5th
R1	A3	A1	A5	A4	A2
R2	A4	A2	A5	A1	A3
R3	A1	A5	A2	A3	A4
R4	A2	A5	A3	A1	A4
R5	A5	A3	A4	A1	A2

Author	1st	2nd	3rd	4th	5th
A1	R3	R1	R4	R5	R2
A2	R2	R4	R3	R5	R1
A3	R5	R2	R3	R1	R4
A4	R2	R3	R5	R1	R4
A5	R5	R3	R4	R2	R1

Reviewer	1st	2nd	3rd	4th	5th
R1	A3	A1	A5	A4	A2
R2	A4	A2	A5	A1	A3
R3	A1	A5	A2	A3	A4
R4	A2	A5	A3	A1	A4
R5	A5	A3	A4	A1	A2