Welcome back. In our last lesson, we introduced the foundational concepts of two-sided matching markets, defined what makes a pairing "stable," and saw a high-level overview of the Gale-Shapley algorithm. We noted its crucial property of being proposer-optimal and saw a glimpse of how it could be adapted for non-monogamous pairings.
This lesson is dedicated to application. We will move from the theoretical overview to a detailed, practical walkthrough of the Gale-Shapley algorithm, fulfilling this module's goal of applying it to find stable pairings in a hotwife context. We will start with a visual review of the standard one-to-one algorithm before diving into a more formal treatment of the many-to-one adaptation. The core of our work today will be a detailed case study where we apply this "polygamous" version of the algorithm to a realistic partner-selection scenario.
A Visual Refresher: The Standard Algorithm
Before we adapt the model, let's quickly review the mechanics of the classic one-to-one matching process. The image below provides a clear, four-round illustration of how the Gale-Shapley algorithm iteratively resolves conflicts to arrive at a stable state.
As you trace the proposals and rejections from Round 1 to Round 4, keep the core principles from our last lesson in mind:
- Proposals: One side (here, the women) consistently proposes down their preference list.
- Tentative Acceptance & "Trading Up": The other side (the men) tentatively accepts the best offer they currently have. If a better offer arrives in a later round, they are free to "trade up," rejecting their previous tentative partner.
- Termination & Stability: The process stops when no more proposals are made. The resulting set of pairs is guaranteed to be stable—meaning no "rogue couple" exists who would both prefer to leave their assigned partners for each other.
This iterative process of proposal and rejection is the engine that drives the market toward a stable equilibrium.
Adapting the Algorithm for Polyamory: Formalizing the Rules
The classic algorithm assumes a one-to-one matching. As we noted previously, this can be extended to the many-to-one or many-to-many scenarios common in polyamory and hotwife dynamics. Given your background in operations research and algorithms, you will appreciate moving beyond the informal description to the more rigorous definitions required for this adaptation.
The academic paper "Sisterhood in the Gale-Shapley Matching Algorithm" provides a formal generalization. We will focus on the section that redefines the key concepts for a "polygamous" market.
Sisterhood in the Gale-Shapley Matching Algorithm
This paper delves into strategic manipulation but contains an excellent section formally generalizing the algorithm to one-to-many matching, which is precisely what we need. It refers to this as the "polygamous" scenario, using the analogy of assigning students to colleges.
Please read the section titled 3.1 Polygamous Matchings. Pay close attention to the following modifications to the standard model: The introduction of a quota n_p for each person p, representing the number of partners they seek. The re-definition of a matching and, critically, stability for this new context. Notice that instability still revolves around a blocking pair, but the conditions are slightly more nuanced. You can find this under Definition 18. The description of how the algorithm itself is modified. The core logic is the same, but proposers now approach multiple parties simultaneously, as described in the paragraph beginning "On each night".
The key takeaway from this reading is that the elegant logic of Gale-Shapley holds up beautifully. We simply replace the binary state of "matched" or "unmatched" with a quota system.
- Proposers continue making proposals down their list until their own quota is filled.
- Acceptors evaluate all incoming offers and tentatively hold the best ones up to their quota, rejecting the rest. If a new, superior offer arrives, they drop their least-preferred current partner to make room.
Now, let's put this into practice.
Case Study: A Hotwife Matching Market
Consider a scenario with two hotwives, Hannah and Isabelle, and four potential bulls, Leo, Max, Noah, and Oscar.
Quotas:
- Hannah is looking for one partner (
n_H = 1). - Isabelle is open to two partners (
n_I = 2). - All four bulls are each looking for one partner (
n_Bull = 1).
Preference Lists:
| Participant | Preferences (ranked from most to least preferred) |
|---|---|
| Hannah | Oscar > Leo > Max > Noah |
| Isabelle | Leo > Noah > Oscar > Max |
| Leo | Hannah > Isabelle |
| Max | Isabelle > Hannah |
| Noah | Isabelle > Hannah |
| Oscar | Isabelle > Hannah |
We will now run the Gale-Shapley algorithm to find a stable matching. Crucially, the outcome depends on who does the proposing.
Scenario 1: The Bulls Propose (Bull-Optimal Outcome)
Let's see what happens when the bulls take the initiative.
Round 1:
- Each bull proposes to his first choice.
- Leo proposes to Hannah.
- Max, Noah, and Oscar all propose to Isabelle.
- The hotwives evaluate their offers.
- Hannah has one offer from Leo. Her quota is 1. She tentatively accepts.
- Tentative Match: (Hannah, Leo)
- Isabelle has three offers: Max, Noah, Oscar. Her quota is 2. She consults her preference list (Leo > Noah > Oscar > Max). She accepts the best two offers and rejects the third.
- Tentative Matches: (Isabelle, Noah) and (Isabelle, Oscar)
- Rejection: Isabelle rejects Max.
- Hannah has one offer from Leo. Her quota is 1. She tentatively accepts.
End of Round 1:
- Current pairings: (Hannah, Leo), (Isabelle, Noah), (Isabelle, Oscar).
- Unmatched: Max.
Round 2:
- The rejected bull, Max, proposes to his next choice. His first choice (Isabelle) rejected him, so he proposes to his second choice, Hannah.
- The hotwives evaluate their offers.
- Hannah now has a new suitor (Max) while being tentatively engaged to Leo. She checks her preferences: she prefers Leo to Max. Therefore, she rejects the new offer.
- Rejection: Hannah rejects Max.
- Isabelle has no new offers. Her pairings are unchanged.
- Hannah now has a new suitor (Max) while being tentatively engaged to Leo. She checks her preferences: she prefers Leo to Max. Therefore, she rejects the new offer.
End of Round 2:
- Current pairings: (Hannah, Leo), (Isabelle, Noah), (Isabelle, Oscar).
- Unmatched: Max. Max has now exhausted his preference list and remains un-matched.
The algorithm terminates because there are no more rejected parties who can make a new proposal.
Final Bull-Optimal Matching:
- Hannah is matched with Leo.
- Isabelle is matched with Noah and Oscar.
- Max remains unmatched.
This matching is stable. You can verify that no other pairing (e.g., Hannah and Oscar) constitutes a "rogue couple." For instance, Hannah would prefer Oscar to her current partner Leo, but Oscar is matched with Isabelle and prefers Isabelle to Hannah. Since Oscar has no incentive to switch, the (Hannah, Oscar) pair cannot destabilize the outcome.
Scenario 2: The Hotwives Propose (Hotwife-Optimal Outcome)
What if the power dynamic were reversed? Let's run the algorithm with Hannah and Isabelle proposing.
Round 1:
- Each hotwife proposes to her top choice(s) up to her quota.
- Hannah (quota 1) proposes to her first choice, Oscar.
- Isabelle (quota 2) proposes to her first choice, Leo, and her second choice, Noah.
- The bulls evaluate their offers.
- Oscar has one offer from Hannah. He accepts.
- Tentative Match: (Oscar, Hannah)
- Leo has one offer from Isabelle. He accepts.
- Tentative Match: (Leo, Isabelle)
- Noah has one offer from Isabelle. He accepts.
- Tentative Match: (Noah, Isabelle)
- Max has no offers.
- Oscar has one offer from Hannah. He accepts.
End of Round 1:
- All proposals were accepted. No one was rejected, so there are no new proposals to be made in a second round. The algorithm terminates immediately.
Final Hotwife-Optimal Matching:
- Hannah is matched with Oscar.
- Isabelle is matched with Leo and Noah.
- Max remains unmatched.
Notice that this outcome is different from the bull-optimal one.
- Hannah is now with Oscar, whom she prefers to Leo. She is better off.
- Oscar is now with Hannah, whom he prefers to Isabelle (this is subtle: he ranked Isabelle first, but in the bull-proposing scenario, he ended up with her anyway as part of a stable match. Here, he is matched with his second choice, Hannah, but in a way that is stable from the hotwives' perspective).
- Leo is now with Isabelle, whom he prefers less than Hannah. He is worse off.
This case study perfectly illustrates the proposer-optimality principle we discussed. When the bulls propose, they get the best possible stable outcome for them. When the hotwives propose, they get the best possible stable outcome for them. The choice of who initiates fundamentally shapes the final arrangement, providing a significant strategic advantage.
Conclusion
In this lesson, we moved from theory to practice, applying the Gale-Shapley algorithm to a specific hotwife matching market. By extending the algorithm with participant quotas, we were able to model a realistic, non-monogamous partner search and find a guaranteed stable outcome.
Key Takeaways:
- The Gale-Shapley algorithm can be adapted from one-to-one to many-to-one ("polygamous") scenarios by introducing quotas for each participant.
- The core mechanics of proposals, tentative acceptance, rejection, and "trading up" remain the foundation of the adapted algorithm.
- Working through a case study demonstrates how these rules play out in iterative rounds, eventually converging on a stable matching.
- The proposer-optimality of the algorithm is a powerful strategic insight: the side that takes the initiative in proposing secures the best possible stable outcome for itself, and the worst for the other side.
Preview of the Next Lesson:
The Gale-Shapley algorithm is a powerful tool, but it assumes a static market where all participants and preferences are known upfront. Reality is often more dynamic. What happens when you encounter potential partners sequentially and must decide on the spot whether to commit or to continue your search, knowing a rejected option may be lost forever? Our next lesson will explore this by formulating partner selection as an optimal stopping problem, famously known as the Secretary Problem.