Marriage, honesty, and stability

ABSTRACT

Many centralized two-sided markets form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. However, as we will show in this paper, in a probabilistic setting where the preference lists of one side of the market are composed of only a constant (independent of the the size of the market) number of entries, each drawn from an arbitrary distribution, the number of participants that have more than one stable partner is vanishingly small. This proves (and generalizes) a conjecture of Roth and Peranson [23]. As a corollary of this result, we show that, with high probability, the truthful strategy is the best response for a given player when the other players are truthful. We also analyze equilibria of the deferred acceptance stable marriage game. We show that the game with complete information has an equilibrium in which a (1 - o(1)) fraction of the strategies are truthful in expectation. In the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a (1 + o(1))-approximate Bayesian-Nash equilibrium. Our results have implications in many practical settings and were inspired by the work of Roth and Peranson [23] on the National Residency Matching Program.

REFERENCES

• 1: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 2: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: Lawrence Bodin , Aaron Panken, High tech for a higher authority: the placement of graduating rabbis from Hebrew union college--Jewish institute of religion, Interfaces, v.33 n.3, p.1-11, May-June 2003 [doi>10.1287/inte.33.3.1.16013]
• 4: L. E. Dubins and D. A. Freedman. Machiavelli and the Gale-Shapley algorithm. American Mathematical Monthly, 88(7):485--494, 1981.
• 5: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 6: D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9--15, 1962.
• 7: Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics, 2nd ed. Addison-Wesley, 1994.
• 8: Dan Gusfield , Robert W. Irving, The stable marriage problem: structure and algorithms, MIT Press, Cambridge, MA, 1989
• 9: N. Johnson and S. Kotz. Urn models and their application: an approach to modern discrete probability theory. John Wiley & Sons, 1977.
• 10: D. E. Knuth. Marriages Stables et leurs relations avec d'autres problémes combinatoires. Les Presses de l'Université de Montréal, 1976.
• 11: Donald E. Knuth , Rajeev Motwani , Boris Pittel, Stable husbands, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.397-404, January 22-24, 1990, San Francisco, California, United States
• 12: Donald E. Knuth, Rajeev Motwani, and Boris Pittel. Stable husbands. Random Structures and Algorithms, 1:1--14, 1990.
• 13: D. G. McVitie and L. B. Wilson. Stable marriage assignments for unequal sets. BIT, 10:295--309, 1970.
• 14: S. J. Mongell and A. E. Roth. Sorority rush as a two-sided matching mechanism. American Economic Review, 81:441--464, 1991.
• 15: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 16: Martin J. Osborne and Ariel Rubinstein. A course in game theory. MIT Press, 1994.
• 17: B. Pittel, The average number of stable matchings, SIAM Journal on Discrete Mathematics, v.2 n.4, p.530-549, Nov. 1989 [doi>10.1137/0402048]
• 18: Boris Pittel, On likely solutions of a stable matching problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.10-15, September 1992, Orlando, Florida, United States
• 19: Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. forthcoming in Econometrica.
• 20: Alvin E. Roth. The economics of matching: stability and incentives. Mathematics of Operations Research, 7:617--628, 1982.
• 21: Alvin E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92:991--1016, 1984.
• 22: Alvin E. Roth. The national residency matching program as a labor market. Journal of the American Medical Association, 275(13):1054--1056, 1996.
• 23: Alvin E. Roth and Elliott Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American Economic Review, 89:748--780, 1999.
• 24: Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-sided Matching; A Study in Game-theoretic Modeling and Analysis. Cambridge University Press, 1990.
• 25: Chung-Piaw Teo , Jay Sethuraman , Wee-Peng Tan, Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.429-438, June 09-11, 1999
• 26: Chung-Piaw Teo , Jay Sethuraman , Wee-Peng Tan, Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Management Science, v.47 n.9, p.1252-1267, September 2001 [doi>10.1287/mnsc.47.9.1252.9784]
• 27: J. H. van Lint and R. M. Wilson. A Course in Combinatorics. Cambridge Univ. Press, 1992.