📚 Game Theory in Action: Matching Problems

Source Information: This study material is compiled from lecture slides by Roberto Lucchetti (Academic year 2025-26, Chapters 1-5) and an accompanying audio lecture transcript.

---

🎯 Introduction to Matching Problems

Matching problems are a fundamental area within game theory, focusing on how to assign individuals from two distinct groups based on their preferences, without relying on monetary transfers. These problems are ubiquitous in real-world scenarios, ranging from simple one-to-one assignments to complex many-to-many allocations.

🌍 Real-World Applications

Matching problems are critical in various domains:

• Labor Markets: Jobs and workers 🧑‍💼↔️👷
• Resource Allocation: Tasks and machines ⚙️↔️🤖
• Education: Universities and students 🎓↔️🧑‍🎓, students and courses 🧑‍🎓↔️📚
• Healthcare: Doctors and hospitals 🩺↔️🏥, organs and patients ❤️↔️🧍
• Social Pairing: Men and women (classic example) 👫

Some settings require a one-to-one assignment, while others are many-to-one or even many-to-many. Each individual possesses a preference (affinity, fit) ranking over the members on the other side.

📜 Historical Context & Significance

The foundational work in this field was laid by D. Gale & L.S. Shapley in 1962 with their paper "College admissions and the stability of marriages." Subsequent contributions by A.E. Roth and others expanded the practical applications. Roth and Shapley were awarded the Nobel Prize in Economic Sciences in 2012 for their theory of stable allocations and the practice of market design.

Notable Applications & Scale:

• 1966: Chilean college admission system.
• 1984: Hospital/residents matching (A.E. Roth).
• 2004: Kidney transplant programs (Roth, Sönmez, Ünver).
• 2005: Boston & New York public school admissions (Abdulkadiroglu, Pathak, Roth).
  • Boston School Admissions (2004): 17,000 applicants / 140 schools.
  • New York High School Admissions (2005): 90,000 applicants / 530 high schools.
  • Chilean College Admissions (2013): 118,208 applicants for 112,608 seats across 33 universities.

---

📝 Core Concepts and Definitions

📚 Matching Problem Definition

A matching problem is defined by:

1. Two sets: W (e.g., women) and M (e.g., men) with the same cardinality (number of elements).
2. Preference profiles: A set of rankings for each individual over the members of the other group. For example, ≻w denotes woman w's ranking over men, and ≻m denotes man m's ranking over women.
   • Example Notation: m1 ≻w1 m2 means woman w1 prefers man m1 over man m2.

🤝 Matching

A matching is a bijection (one-to-one correspondence) b: W → M, forming pairs between the two groups.

• Example: For W = {Anna, Giulia, Maria} and M = {Bob, Frank, Emanuele}, a matching could be [(Anna, Emanuele), (Giulia, Bob), (Maria, Frank)].

⚠️ Objecting Pair

A pair w-m objects to a matching Λ if both w and m prefer each other to their current partners in Λ.

• Example: If Λ = {(w1, m1), (w2, m2)} but m2 ≻w1 m1 (w1 prefers m2 to her current partner m1) AND w1 ≻m2 w2 (m2 prefers w1 to his current partner w2), then w1-m2 is an objecting pair.

✅ Stable Matching

A matching Λ is called stable if there is no pair (woman-man) objecting to Λ. A stable matching is efficient because no two individuals can improve their situation by unilaterally breaking their current match and forming a new one.

---

📊 The Gale-Shapley Algorithm (Deferred Acceptance)

💡 Existence of Stable Matching

A fundamental theorem states: Every matching problem admits at least one stable matching. This is proven constructively by the Gale-Shapley algorithm.

1️⃣ Algorithm Steps (Women Proposing / "Night by Night")

This iterative algorithm finds a stable matching:

1. Stage 1a (Proposals): Every woman proposes to her most preferred man.
2. Stage 1b (Provisional Acceptance/Rejection): Every man considers all proposals received. He provisionally accepts the most preferred woman among his proposers and rejects all others. If all women are provisionally matched, the algorithm ends.
3. Subsequent Stages (k):
   • Stage ka (New Proposals): Every woman who was rejected in the previous stage proposes to her next most preferred man (the next choice after the man who dismissed her).
   • Stage kb (Re-evaluation): Every man considers his current provisional partner (if any) and any new proposals. He provisionally accepts the most preferred woman among all those who have proposed to him (including his current partner) and rejects all others.
4. The process continues until no woman is rejected, and all are provisionally matched.

📈 Algorithm Properties

• Women's Preferences: Women generally go down their preference lists as they are rejected.
• Men's Preferences: Men generally go up their preference lists, as they only switch partners for a more preferred woman.
• Termination: The algorithm always ends. For n women and n men, it terminates in at most (n-1)² + 1 steps.
• Stability Proof:
  • No woman can be part of an objecting pair with a man she never proposed to (she's paired with someone she prefers more).
  • No woman can be part of an objecting pair with a man who rejected her (he rejected her for someone he prefers more, or she was rejected in favor of a better alternative).
  • Therefore, the resulting matching is stable.

🏆 Optimality for Proposing Side

The Gale-Shapley algorithm yields a stable matching that is optimal for the proposing side (e.g., women in the "women proposing" version). This means each woman gets the best partner she could possibly get in any stable matching. Conversely, this matching is the worst for the non-proposing side (men).

---

⚖️ Properties of Stable Matchings

🔄 Multiple Stable Matchings

For a given problem, there can be multiple stable matchings. The Gale-Shapley algorithm provides one specific stable matching.

↔️ Pre-order Relations

We can compare stable matchings using pre-order relations:

• ∆ ≽M Θ: For every man, he is either associated with the same woman in both matchings, or he is associated with a preferred woman in ∆ than in Θ.
• ∆ ≽W Θ: For every woman, she is either associated with the same man in both matchings, or she is associated with a preferred man in ∆ than in Θ. These relations are reflexive and transitive but not necessarily complete (some matchings might not be comparable).

⚖️ Women vs. Men Theorem

Let Ω be the stable matching from the women-proposing algorithm and Σ be from the men-proposing algorithm. Let Θ be any other stable matching.

• Ω ≽W Θ ≽W Σ (Women prefer Ω most, Σ least).
• Σ ≽M Θ ≽M Ω (Men prefer Σ most, Ω least). This theorem highlights the inherent conflict of interest: what is best for one side is worst for the other.

---

🔍 Alternative Method: Dominance-Free Algorithm

This method systematically eliminates pairs that cannot be part of any stable matching.

1. Initial Elimination: For each woman w, consider her top choice m. If m prefers w to another woman w', then the pair (w', m) can be excluded from any stable matching (because w-m would object).
2. Iterative Refinement: Repeat this process, updating preference lists as pairs are excluded. This also applies to men's preferences.
3. Result: This method identifies the set of all possible stable matchings and can reveal the two extreme stable matchings (women-optimal and men-optimal) generated by the Gale-Shapley algorithm.

---

😈 Strategic Considerations

🤥 Incentive to Lie

• Proposing Side: The Gale-Shapley algorithm is incentive-compatible for the proposing side. By truthfully stating their preferences, they are guaranteed their optimal stable partner. There is no benefit to misrepresenting preferences.
• Non-Proposing Side: The algorithm is not incentive-compatible for the non-proposing side. They may have an incentive to misrepresent their preferences to achieve a better outcome than what they would get by being truthful.

🌐 Availability

A(w) denotes the set of men with whom woman w can be paired in some stable matching. During the women-proposing algorithm, no woman w can be rejected by a man belonging to her A(w) set.

---

🧩 Extensions of Matching Models

The basic one-to-one matching model can be extended to more complex scenarios:

🔢 Unequal Group Sizes

If nM > nW (more men than women), the definition of matching and objecting pairs must be adapted:

• Matching: A function where each man m is associated with a woman w or single, and each woman w is associated with only one man.
• Objecting Pair: A pair w-m objects if:
  • m is single or matched with w1 (whom he prefers less than w).
  • w is matched with m1 (whom she prefers less than m).
  • m prefers w over being single.
  • w prefers m over being single.

💔 "Not at Any Cost" Preferences

Individuals might prefer to remain single rather than be matched with certain undesirable partners. The definition of an objecting pair is extended to include cases where an individual prefers being single over their current partner.

🧑‍🎓📚 Many-to-Many Matching

This involves situations where individuals can be matched with multiple partners, subject to quotas.

• Example: Students choosing courses. Student s can choose up to qs courses, and course c can accept up to qc students.
• Feasible Matching: A subset of admissible pairs respecting all quotas.
• Stability: Redefined to account for multiple partners and quotas.

👯 Unisexual Matching (Within-Group Matching)

This involves matching individuals within a single group (e.g., roommates, committee assignments).

• Challenge: Unlike two-sided matching, a stable matching is not always guaranteed to exist in unisexual matching problems. Objecting pairs can persist regardless of the matching formed.

---

🏁 Conclusion

Matching problems are a vital area of game theory, providing frameworks for efficient allocation based on preferences.

• ✅ Two-sided matching involves two groups with reciprocal preferences.
• ✅ The concept of a stable matching (free from objecting pairs) is central.
• ✅ The Gale-Shapley algorithm guarantees the existence of a stable matching and is optimal for the proposing side.
• ✅ Dominance-free methods can identify all stable matchings.
• ⚠️ Strategic behavior is a key consideration, as the non-proposing side may have incentives to misrepresent preferences.
• 💡 The framework extends to unequal group sizes, preferences for being single, and many-to-many assignments.
• ❌ However, unisexual matching does not always guarantee a stable outcome.