skip to main content
10.5555/1558013.1558105guideproceedingsArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article
Free access

Manipulation and gender neutrality in stable marriage procedures

Published: 10 May 2009 Publication History

Abstract

The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications ranging from matching resident doctors to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale-Shapley algorithm, which runs in polynomial time.
It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale-Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale-Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.

References

[1]
K. J. Arrow, A. K. Sen and K. Suzumura. Handbook of Social Choice and Welfare. North Holland, Elsevier, 2002
[2]
J. Bartholdi and J. Orlin. Single transferable vote resists strategic voting. In Social Choice and Welfare, 8(4):341--354, 1991.
[3]
J. J. Bartholdi, C. A. Tovey and M. A. Trick, The computational difficulty of manipulating an election. In Social Choice and Welfare 6(3):227--241, 1989.
[4]
V. Conitzer and T. Sandholm. Nonexistence of voting rules that are usually hard to manipulate. In Proc. AAAI'06, 2006.
[5]
V. Conitzer and T. Sandholm. Universal Voting Protocol Tweaks to Make Manipulation Hard. In Proc. IJCAI'03: 781--788, 2003.
[6]
G. Demange, D. Gale, and M. Sotomayor. A further note on the stable matching problem. In Discrete Applied Mathematics, 16:217--222, 1987.
[7]
L. Dubins and D. Freedman. Machiavelli and the Gale-Shapley algorithm. In American Mathematical Monthly, 88:485--494, 1981.
[8]
D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. In Amer. Math. Monthly, 69:9--14, 1962.
[9]
D. Gale and M. Sotomayor. Some remarks on the stable matching prob- lem. Discrete Applied Mathematics, 11:223--232, 1985.
[10]
D. Gale and M. Sotomayor. Machiavelli and the stable matching problem. American Mathematical Monthly, 92:261--268, 1985.
[11]
A. Gibbard. Manipulation of Voting Schemes: A General Result. In Econometrica, 41(3):587--601, 1973.
[12]
D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston, Mass., 1989.
[13]
D. Gusfield. Three fast algorithms for four problems in stable marriage. In SIAM J. of Computing, 16(1), 1987.
[14]
C.-C. Huang. Cheating by men in the Gale-Shapley stable matching algorithm. In ESA'06, pages 418--431, Springer-Verlag, 2006.
[15]
Robert W. Irving, P. Leather and D. Gusfield, An efficient algorithm for the "optimal" stable marriage, In JACM 34(3):532--543, 1987.
[16]
B. Klaus and F. Klijin. Procedurally fair and stable matching. In Economic Theory, 27:431--447, 2006.
[17]
J. Liebowitz and J. Simien. Computational efficiencies for multi-agents: a look at a multi-agent system for sailor assignment. In Electronic government: an International Journal 2 (4):384--402, 2005.
[18]
F. Masarani and S. S. Gokturk. On the existence of fair matching algorithms. In Theory and Decision, 26:305--322, Kluwer, 1989.
[19]
A. D. Procaccia and J. S. Rosenschein. Junta Distributions and the Average-Case Complexity of Manipulating Elections. In JAIR 28:157--181, 2007.
[20]
A. E. Roth. The Economics of Matching: Stability and Incentives. In Mathematics of Operations Research, 7:617--628, 1982.
[21]
A. E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. In Journal of Political Economy 92:991--1016, 1984.
[22]
A. Roth and M. Sotomayor. Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press, 1990.
[23]
A. Roth and V. Vate. Incentives in two-sided matching with random stable mechanisms. In Economic Theory, 1(1):31--44, 1991.
[24]
M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare function. In Economic Theory, 10(3):187--217, 1975.
[25]
C.-P. Teo, J. Sethuraman and W.-P. Tan. Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications. In Management Science, 47(9):1252--1267, 2001.

Cited By

View all
  • (2024)Strategic aspects of stable matching marketsProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/893(8077-8085)Online publication date: 3-Aug-2024
  • (2018)Coalitional Permutation Manipulations in the Gale-Shapley AlgorithmProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237837(928-936)Online publication date: 9-Jul-2018
  • (2010)Is computational complexity a barrier to manipulation?Proceedings of the 11th international conference on Computational logic in multi-agent systems10.5555/1893859.1893861(1-7)Online publication date: 16-Aug-2010

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1
May 2009
701 pages
ISBN:9780981738161

Sponsors

  • Drexel University
  • Wiley-Blackwell
  • Microsoft Research: Microsoft Research
  • Whitestein Technologies
  • European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
  • The Foundation for Intelligent Physical Agents

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 10 May 2009

Qualifiers

  • Research-article

Acceptance Rates

AAMAS '09 Paper Acceptance Rate 132 of 651 submissions, 20%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)27
  • Downloads (Last 6 weeks)8
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Strategic aspects of stable matching marketsProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/893(8077-8085)Online publication date: 3-Aug-2024
  • (2018)Coalitional Permutation Manipulations in the Gale-Shapley AlgorithmProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237837(928-936)Online publication date: 9-Jul-2018
  • (2010)Is computational complexity a barrier to manipulation?Proceedings of the 11th international conference on Computational logic in multi-agent systems10.5555/1893859.1893861(1-7)Online publication date: 16-Aug-2010

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media