Abstract
Stable matching markets, such as those used for school choice and medical residencies, rely on algorithms like Deferred Acceptance (DA) to ensure no two agents prefer each other over their assigned partners. However, while DA is strategy-proof for the proposing side, it is vulnerable to manipulation by the receiving side. This survey provides a comprehensive map of strategic "gaming" in these markets, moving beyond individual lies to explore complex coalitional strategies, "accomplice" manipulations, and the inherent tension between market stability and fairness.
Introduction
In a two-sided matching market, the gold standard is stability: a state where no two agents would both prefer to ditch their current partners for each other. The famous Deferred Acceptance (DA) algorithm guarantees this outcome. However, a significant theoretical catch exists: the algorithm is only strategy-proof for the side making the proposals. The receiving side can often achieve a more desirable outcome by misreporting their true preferences. While individual manipulation is well-documented, this survey addresses the gap in understanding coalitional and two-sided strategic behavior, such as collusion between a student and a school.
Theoretical Framework
The study of strategic matching often relies on small-scale preference profiles to prove the existence of specific manipulation types. These theoretical instances allow researchers to trace how changes in a single agent's list can ripple through the market to alter the final stable matching.
Categorizing Strategic Behavior
The survey synthesizes decades of research into a unified framework, categorizing strategic manipulations along three main axes:
- One-Sided Manipulation: Strategies such as truncation (declaring acceptable partners as unacceptable) or permutation (shuffling the order of preferences).
- Two-Sided Manipulation: Novel concepts like Accomplice Manipulation, where an agent on the proposing side—who typically has no incentive to lie—misreports their list to help someone on the receiving side without harming their own match ("no-regret").
- Externalities: Scenarios involving bribery or external control to influence market outcomes.
Key Insights: Accomplices and Synergy
One of the most compelling insights is the role of the "No-Regret" Accomplice. In a men-proposing DA, a man can lie to help a woman secure a better match while he remains matched to the same person. This makes the manipulation "free" for the accomplice. Furthermore, the authors highlight a "Two-for-One Synergy": a woman can sometimes achieve a better result if both she and an accomplice man lie, compared to the results of acting individually.
Many optimal strategies are also "inconspicuous," requiring an agent to change the position of only a single partner in their list. This subtlety makes detecting strategic behavior extremely difficult for market designers.
Computational Complexity and Practicality
The paper evaluates these strategies based on their computational complexity. Most single-agent permutation and truncation manipulations can be computed in polynomial time, suggesting that agents do not require immense computing power to find an optimal lie.
Despite these theoretical vulnerabilities, empirical simulations suggest that manipulation may be rare in practice. In simulated markets, only about 5.1% of agents on the receiving side actually benefited from misreporting. However, the survey notes that manipulation can sometimes be used for "social good" to close the welfare gap and lead to more "sex-equal" or fair outcomes, as DA is often pessimal for the receiving side.
Future Directions
The authors identify several open problems at the frontier of the field:
- Exhaustiveness: Determining if simple truncation strategies are sufficient to capture all benefits in two-sided coalitional manipulations.
- Average-Case Hardness: Designing markets that are difficult to game on average, even if they are vulnerable in the worst case.
- Fairness via Strategy: Intentionally using strategic frameworks to achieve socially desirable outcomes that standard algorithms might ignore.
- Beyond DA: Exploring the strategic aspects of other mechanisms, such as the Top Trading Cycle.
Summary updated