Introduction
Welcome to the first lesson of our module on Cooperative Games for Partner Selection. In our previous module, we concluded by examining trigger strategies—the enforcement mechanisms that ensure stability within an established relationship. Now, we shift our focus from maintaining partnerships to forming them. How do stable pairings emerge in a world of diverse preferences and competing interests?
This lesson addresses precisely that question by modeling the partner selection process as a two-sided matching market. You will learn to apply the classic Gale-Shapley algorithm, a cornerstone of cooperative game theory, to this problem. We will define what makes a set of pairings "stable" and walk through the algorithm that guarantees finding such a stable outcome. This provides a powerful, formal framework for analyzing how hotwives and bulls, or any group of individuals with ranked preferences, can form partnerships that are resistant to being broken up by outside offers.
What is a Stable Matching?
Imagine a scenario: several couples are open to the hotwife having a secondary partner ("bull"), and there are several bulls looking for a partner. Each hotwife has a ranked list of bulls she's interested in, and each bull has a ranked list of hotwives he'd like to partner with. The goal is to create a set of pairings.
But what makes a set of pairings "good"? From a structural perspective, the most important quality is stability. An arrangement is unstable if there's a "rogue pair" waiting to happen: a hotwife and a bull who are not paired together, but who both would rather be with each other than with their current partners (or with being alone). Such a pair has both the motive and the opportunity to leave their current situation and form a new partnership, destabilizing the entire arrangement.
A stable matching is one where no such rogue pair exists. This doesn't mean everyone gets their first choice. It simply means that for any two people who are not paired together, at least one of them prefers their current situation.
The following video from the Numberphile channel provides an excellent, intuitive introduction to this concept, known formally as the Stable Marriage Problem.
Stable Marriage Problem - Numberphile
This video introduces the Stable Marriage Problem, defines stability, and presents the Gale-Shapley algorithm for finding a solution.
Please watch the following segments: The definition of stability. Focus on Dr. Riehl's explanation of what constitutes an unstable pair—the core problem we want to avoid. The description of the algorithm. This lays out the step-by-step "proposal-rejection" process that forms the heart of the model. The example walkthrough. Following the algorithm with concrete preferences will solidify your understanding of the mechanics.
The Gale-Shapley Algorithm: A Step-by-Step Scenario
The great insight of David Gale and Lloyd Shapley was not just defining stability, but providing an algorithm that is guaranteed to find a stable matching, for any number of participants and any set of preferences. Let's apply it to a scenario directly relevant to your interests.
Scenario: Three Bulls (Alex, Ben, Chris) and three Hotwives (Chloe, Dana, Eve) are looking to match. The preferences are as follows:
Preference Tables:
| Proposers (Bulls) | Preferences (1st, 2nd, 3rd) |
|---|---|
| Alex | Eve, Chloe, Dana |
| Ben | Chloe, Eve, Dana |
| Chris | Chloe, Dana, Eve |
| Acceptors (Hotwives) | Preferences (1st, 2nd, 3rd) |
|---|---|
| Chloe | Alex, Ben, Chris |
| Dana | Alex, Chris, Ben |
| Eve | Ben, Alex, Chris |
We will run the Gale-Shapley algorithm with the Bulls as the "proposing" side.
Round 1:
- Each bull proposes to his first choice.
- Alex proposes to Eve.
- Ben proposes to Chloe.
- Chris proposes to Chloe.
- The hotwives now evaluate their offers.
- Eve has one offer from Alex. She tentatively accepts. (Eve-Alex)
- Chloe has two offers: Ben and Chris. She consults her preference list. She prefers Ben to Chris. She tentatively accepts Ben and rejects Chris. (Chloe-Ben)
- Dana has no offers.
End of Round 1: We have two tentative pairs: (Chloe, Ben) and (Eve, Alex). Chris is un-matched and has been rejected.
Round 2:
- Any bull who was rejected in the previous round proposes to his next choice.
- Chris was rejected by Chloe. His next choice is Dana. Chris proposes to Dana.
- The hotwives evaluate new offers.
- Dana receives a proposal from Chris. He is her only offer, so she tentatively accepts. (Dana-Chris)
- Chloe and Eve received no new proposals, so their tentative pairings (Chloe-Ben, Eve-Alex) remain.
End of Round 2: All individuals are now in a tentative pairing: (Chloe, Ben), (Eve, Alex), (Dana, Chris). Since there are no more un-matched proposers, the algorithm terminates.
Final Stable Matching:
- Chloe is paired with Ben.
- Dana is paired with Chris.
- Eve is paired with Alex.
Let's check for stability. Could a "rogue pair" form? Consider Chloe and Alex. Chloe is paired with Ben (her 2nd choice) and Alex is with Eve (his 1st choice). Chloe prefers Alex to Ben. However, Alex prefers his current partner, Eve, to Chloe. So, Alex has no incentive to leave Eve for Chloe. The (Chloe, Alex) pair is not a source of instability. You can verify that no other combination of a bull and a hotwife who are not paired together would both prefer to switch. This matching is stable.
The Strategic Power of Proposing
The algorithm is simple, but its consequences are profound. A critical feature, which your background in analysis will appreciate, is that the outcome is biased in favor of the side that makes the proposals.
The follow-up video from Numberphile2 explains the mathematical properties of the algorithm's outcome.
Stable Marriage Problem (the math bit)
This video delves into the mathematical proofs and consequences of the Gale-Shapley algorithm, including its optimality properties and strategy-proofness.
Please focus on the following key theorems explained in the video: Proof of Stability: The argument for why the algorithm always produces a stable matching. Proposer-Optimality and Acceptor-Pessimality: This is the most crucial part. Understand the claim that the algorithm gives every member of the proposing group their best possible stable partner, while giving every member of the accepting group their worst possible stable partner. Strategy-Proofness: The presenter notes that it is not possible to "game" the algorithm by lying about your preferences. For the proposers, honesty is the best policy.
The implications are massive. In our scenario, the bulls proposed. The resulting matching—(Chloe, Ben), (Eve, Alex), (Dana, Chris)—is the best possible stable outcome for the bulls and the worst possible stable outcome for the hotwives.
What if the hotwives had proposed? The outcome would be different. It would be the best possible stable matching for the hotwives and the worst for the bulls. This reveals a fundamental power dynamic in matching markets: it is strategically advantageous to be the side that proposes.
Extending the Model: From Monogamy to Polyamory
The classic Gale-Shapley algorithm assumes a one-to-one matching. However, in your field of interest, relationships are often not one-to-one. The model can be adapted to handle this, as discussed in the article "Poly Gale-Shapley."
Poly Gale-Shapley - Optimization Process
This article provides a brief but insightful overview of how to adapt the Gale-Shapley algorithm for a polyamorous dating market, which is directly applicable to one-to-many hotwife scenarios.
Read the first few paragraphs, focusing on the core modification described: the adaptation. Note how the concepts of "matched" or "unmatched" are replaced with "polysaturation."
The adaptation is surprisingly straightforward and relies on two key changes:
- Polysaturation: Each person has a number representing the maximum number of partners they want. For a hotwife, this might be 1 or 2. For a bull, it might be several.
- Modified Algorithm Rules:
- Proposers (e.g., bulls) don't stop after being accepted once. They continue proposing down their preference list until they have reached their polysaturation number.
- Acceptors (e.g., hotwives) accept offers until they are saturated. If they are already saturated and receive a proposal from someone they prefer over one of their current partners, they will drop their least-preferred current partner and accept the new, better offer.
This "Poly Gale-Shapley" model provides a much more realistic framework for analyzing partner selection in non-monogamous contexts. It retains the core logic of achieving stability but allows for the many-to-one or many-to-many structures common in these relationship styles.
Conclusion
In this lesson, we have established a formal model for understanding partner selection. By framing it as a two-sided matching market, we can move beyond intuition and analyze the process with game-theoretic rigor.
Key Takeaways:
- Partner selection can be modeled as a two-sided matching market with two sets of agents, each with ranked preferences over the other.
- A stable matching is a set of pairings with no "rogue pairs"—no two people who would mutually prefer each other to their current situation.
- The Gale-Shapley algorithm is a constructive procedure that is guaranteed to find a stable matching in any such market.
- The algorithm is proposer-optimal: the side that makes the proposals secures the best possible outcome for themselves out of all possible stable matchings. This gives a significant strategic advantage to the proactive party.
- The classic one-to-one model can be extended to polyamorous or hotwife contexts by replacing the binary matched/unmatched status with a "polysaturation" level for each participant.
Preview of the Next Lesson:
The Gale-Shapley algorithm assumes a "closed market" where all potential partners are known and can be evaluated simultaneously. But what if the search for a partner is sequential? What if you meet potential partners one by one and must decide whether to commit or to keep searching, knowing that a rejected option might be gone forever? Our next lesson will tackle this dynamic search problem by formulating it as an optimal stopping problem, famously known as the Secretary Problem.