Stable Matching Problems: Proofs and Counterexamples from CSCI570 Homework 1

Introduction to Stable Matching in CSCI570

Stable matching problems are a cornerstone of algorithm design, often taught in courses like CSCI570. These problems model scenarios where participants have preferences over each other, and we seek a pairing that is stable—meaning no two unmatched participants would rather be together. The classic example is the Stable Marriage Problem, but variations like the stable roommate problem add complexity. In this tutorial, we'll dissect key proofs and counterexamples from a typical homework assignment, using analogies from AI-driven dating apps and esports team formation to make concepts relatable.

Problem 1: Stable Roommate with Four Students

The stable roommate problem asks: given a set of students with strict preferences over each other, can we always find a stable matching? For four students (A, B, C, D), the answer is no. A counterexample exists: A prefers B > C > D; B prefers C > A > D; C prefers A > B > D; D's preferences are arbitrary. In this instance, any pairing leads to instability. For example, if pairs are (A,B) and (C,D), then C prefers A over D, and A prefers C over B, so they form a blocking pair. This shows that stable matchings are not guaranteed for non-bipartite settings, unlike the classic stable marriage problem.

Problem 2: Mutual First Preferences

If a man m and woman w rank each other first, then in every stable matching, m must be matched with w. Proof: Suppose they are not matched. Then m is matched with some w', and w with some m'. Since m prefers w over w', and w prefers m over m', (m,w) is a blocking pair, contradicting stability. This result is intuitive and often used in algorithm analysis.

Problem 3: Gale-Shapley with Men Proposing

Can the Gale-Shapley algorithm (men-proposing) ever match every woman to her least preferred man? For n ≥ 2, the answer is no. The algorithm guarantees a man-optimal and woman-pessimal stable matching, meaning each woman gets the worst partner she could have in any stable matching. But being worst among stable matchings is not necessarily her overall least preferred man; there could be unstable matchings where she does worse. Thus, the scenario is impossible because the algorithm always outputs a stable matching, and a woman's least preferred man might not be part of any stable matching.

Problem 4: No Stable Matching for Six Students

Given preferences for Harry, Ron, Hermione, Luna, Neville, and Ginny, we must prove no stable matching exists. This is a classic impossibility result similar to the four-student case. By checking all possible pairings, one can find blocking pairs in each. For instance, if pairs are (Harry, Hermione) and (Ron, Ginny) and (Neville, Luna), then Ron prefers Hermione over Ginny, and Hermione prefers Ron over Harry, so they block. A systematic check shows every matching has a blocking pair, confirming instability.

Ungraded Problems Insights

Two Women with Same Best Valid Partner

It is possible: consider two women who both have the same man as their top choice, and that man has them as his top two. In the men-proposing GS, that man will propose to his first choice, leaving the other woman with a worse partner. But the best valid partner for a woman is the best man she can be matched with in any stable matching. If the man's first choice is the other woman, then the second woman's best valid partner could be the same man if he is also her best stable partner? Actually, the best valid partner is unique per woman; two women cannot share the same best valid partner because that would require the man to be matched to both in different stable matchings, which is impossible. So the statement is false; each woman has a distinct best valid partner.

Stable Matching with Mutual First Preferences Always Exists?

Not always. Consider a scenario with two men and two women where m1 and w1 rank each other first, but m2 and w2 also rank each other first. Then the stable matching is {(m1,w1), (m2,w2)}. But if preferences are such that m1 and w1 are mutual first, but m2 prefers w1 over w2, and w2 prefers m1 over m2, then the only stable matching might not include (m1,w1) because (m1,w2) could be stable? Actually, if m1 and w1 are mutual first, they must be together in every stable matching as per Problem 2. So the statement is true: there is always a stable matching containing that pair (the pair itself is part of every stable matching).

Gale-Shapley Matching Every Woman to Her Most Preferred Man

Is it possible that with men proposing, every woman gets her most preferred man, even if no man has that woman as his first? Yes, consider three men and three women where women's preferences are cyclic: w1: m1 > m2 > m3; w2: m2 > m3 > m1; w3: m3 > m1 > m2. Men's preferences: m1: w2 > w3 > w1; m2: w3 > w1 > w2; m3: w1 > w2 > w3. Here, no woman is first for her most preferred man. But running GS with men proposing: m1 proposes to w2 (accepts), m2 to w3 (accepts), m3 to w1 (accepts). Each woman gets her first choice. So the statement is true.

Woman Manipulating Preferences

Can a woman get a better partner by swapping two men in her preference list before running GS? Yes, it's possible. For example, consider two men m1, m2 and two women w1, w2. Actual preferences: w1: m1 > m2; w2: m2 > m1; m1: w1 > w2; m2: w1 > w2. GS with men proposing: m1 proposes to w1 (accepts), m2 proposes to w1 (rejected), then m2 proposes to w2 (accepts). w1 gets m1 (her first). If w1 swaps to m2 > m1 (falsely), then GS: m1 proposes to w1 (accepts), m2 proposes to w1 (rejected), m2 proposes to w2 (accepts). w1 still gets m1. But with different preferences, manipulation can work. For instance, w1's actual: m2 > m1 > m3; false: m1 > m2 > m3. If men propose in order, w1 might get m2 under truth but m1 under false, which is worse. So to get better, she needs a specific setup. A known example involves three men and three women; by swapping, w1 can get her first instead of second. So the statement is true: manipulation can improve her outcome.

Trend-Inspired Analogies

Think of stable matching like team selection in esports tournaments (e.g., League of Legends Worlds 2026). Players have preferences for teammates, and a stable team is one where no two players would rather form a duo together. The Gale-Shapley algorithm is akin to a draft system where top players propose to teams. Similarly, AI-powered dating apps use stable matching to suggest partners, but manipulation (like fake profiles) can sometimes yield better matches—a lesson in mechanism design.

Conclusion

Stable matching problems reveal deep algorithmic insights. From the impossibility of stable roommate to the robustness of Gale-Shapley, these proofs sharpen analytical skills. As AI and game theory evolve, understanding these fundamentals helps design fair systems in real-world applications.