Manipulation and gender neutrality in stable marriage procedures

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: Vincent Conitzer , Tuomas Sandholm, Nonexistence of voting rules that are usually hard to manipulate, Proceedings of the 21st national conference on Artificial intelligence, p.627-634, July 16-20, 2006, Boston, Massachusetts
• 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 , M. Sotomayor, A further note on the stable matching problem, Discrete Applied Mathematics, v.16 n.3, p.217-222, March 1987 [doi>10.1016/0166-218X(87)90059-X]
• 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: Dan Gusfield , Robert W. Irving, The stable marriage problem: structure and algorithms, MIT Press, Cambridge, MA, 1989
• 13: Dan Gusfield, Three fast algorithms for four problems in stable marriage, SIAM Journal on Computing, v.16 n.1, p.111-128, Feb. 1987 [doi>10.1137/0216010]
• 14: Chien-Chung Huang, Cheating by men in the gale-shapley stable matching algorithm, Proceedings of the 14th conference on Annual European Symposium, p.418-431, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_39]
• 15: Robert W. Irving , Paul Leather , Dan Gusfield, An efficient algorithm for the “optimal” stable marriage, Journal of the ACM (JACM), v.34 n.3, p.532-543, July 1987 [doi>10.1145/28869.28871]
• 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: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Theory