Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous

Rohit Vaish, Dinesh GargIJCAI 2017 · DOI

TL;DR

This paper explores how a single woman can strategically manipulate the Gale-Shapley stable matching algorithm to get a better partner while ensuring the resulting matching remains stable and her manipulation is hard to detect. They show that optimal manipulations are indeed stability-preserving and can be made "inconspicuous" by only slightly altering her preference list.

What Problem Does This Paper Address?

The Gale-Shapley algorithm is a cornerstone of matching theory, guaranteeing a "stable" outcome where no two unmatched individuals would prefer each other over their assigned partners. However, a crucial finding is that this algorithm isn't immune to manipulation; agents might lie about their preferences to secure a better match. While it's known that the "proposing" side (men, in this paper's setup) has no incentive to lie, the "proposed-to" side (women) might. The challenge is twofold: can a woman manipulate to get a better partner without destabilizing the entire matching, and can she do so without making her manipulation obvious to a market designer who has a general idea of true preferences?

Methods

The authors focus on "permutation manipulations," where a woman reorders her true preference list. They introduce the concept of an "optimal manipulation" – one that yields the best possible partner for the manipulator. A key contribution is proving that such optimal manipulations are "stability-preserving," meaning the resulting matching is still stable with respect to everyone's true preferences.

To address the detectability issue, they define "inconspicuous manipulations." An inconspicuous manipulation is one that achieves the same outcome for the manipulator as another optimal manipulation but is derived from the true preference list by moving at most one man. They develop a "swapping lemma" (Lemma 7) that precisely describes how swapping adjacent men in a preference list affects the outcome, which is crucial for constructing these inconspicuous manipulations.

Datasets

Not discussed in the paper. The paper uses theoretical examples to illustrate its findings.

Key Insights and Ideas

  • Optimal manipulation doesn't break stability: This is a significant finding. It means that if a woman is smart about her manipulation (i.e., she aims for the absolute best partner she can get), the entire market remains stable, which is good news for market designers.
  • "Inconspicuous" is the key to stealth: While optimal manipulations are stable, they can still look very different from true preferences. The paper shows that for any optimal manipulation, there's an "inconspicuous" equivalent that achieves the same result for the manipulator but looks almost identical to her true list, differing only by the position of one man. This makes detection very difficult.
  • The "stable lattice" concept: The paper uses the idea of a "stable lattice" to formalize the relationship between different stable matchings. They show that for inconspicuous optimal manipulations, the entire lattice of stable matchings under the manipulated preferences is contained within the original stable lattice. This is a stronger stability guarantee.
  • Sub-optimal manipulation is risky: The paper provides examples showing that if a woman manipulates sub-optimally (i.e., doesn't get her absolute best partner), the resulting matching might become unstable.

Key Results

  • Theorem 3: An optimal manipulation by a single woman is always stability-preserving.
  • Theorem 4: For any optimal manipulation, there exists an inconspicuous equivalent that yields the same partner for the manipulator and differs from the true list by at most one man's position.
  • Theorem 5: For inconspicuous optimal manipulations, the stable lattice induced by the manipulation is contained within the original stable lattice.
  • Examples: The paper includes examples demonstrating that sub-optimal manipulations can lead to instability (Example 1) and that the lattice containment result doesn't hold for non-inconspicuous optimal manipulations (Example 2).

Limitations and Future Work

The authors acknowledge that their work focuses on a single manipulator. Future directions include studying scenarios with multiple self-interested manipulators and exploring equilibrium strategies. They also suggest investigating whether their techniques can lead to faster algorithms for manipulation problems and extending the analysis to other stable matching algorithms beyond Gale-Shapley.

Summary updated

BibTeX
@inproceedings{vaish2017manipulating,
  author = {Rohit Vaish and Dinesh Garg},
  title = {{Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/62},
}
Figure