Skip to main content
SpringerLink
Log in

Preference profiles determining the proposals in the Gale–Shapley algorithm for stable matching problems

  • Original Paper
  • Area 1
  • Published:
Japan Journal of Industrial and Applied Mathematics Aims and scope Submit manuscript

Abstract

Concerning the strategic manipulability of the stable matching produced by the Gale–Shapley algorithm, Kobayashi and Matsui recently considered the existence problem of a preference profile of women, that is, given a preference profile of men, find a preference profile of women that makes the Gale–Shapley algorithm produce the prescribed complete matching of men and women. Reformulating this problem by introducing the set of proposals to be made through the execution of the algorithm, and switching the roles of men and women, we consider the existence problem of a preference profile of men and show that the problem is reduced to a problem of checking if a directed graph is a rooted tree and it is solvable in polynomial time. We also show that the existence problem of preference profiles of both sexes when a set of proposals is given is solvable in polynomial time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berge C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)

    MATH  Google Scholar 

  2. Fujishige S.: A primal approach to the independent assignment problem. J. Oper. Res. Soc. Jpn. 20, 1–15 (1977)

    MathSciNet  MATH  Google Scholar 

  3. Gabow H.N., Tarjan R.E.: Efficient algorithms for a family of matroid intersection problems. J. Algorithms 5, 80–131 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Gale D., Shapley L.S.: College admissions and stability of marriage. Am. Math. Monthly 69, 9–15 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  5. Gusfield D., Irving R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)

    MATH  Google Scholar 

  6. Knuth, D.E.: Mariages stables et leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Universitè de Montrèal (1976). English translation Goldstein, M.: Stable marriage and its relation to other combinatorial problems. In: CRM Proceedings and Lecture Notes, vol. 10. American Mathematical Society, Providence (1997)

  7. Kobayashi H., Matsui T.: Successful manipulation in stable marriage model with complete preference lists. IEICE Trans. Inf. Syst. E E92-D, 116–119 (2009)

    Article  Google Scholar 

  8. Kobayashi H., Matsui T.: Cheating strategies for the Gale–Shapley algorithm with complete preference lists. Algorithmica 58, 151–169 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Lawler E.L.: Combinatorial Optimization: Network and Matroids, Holt. Rinehart and Winston, New York (1976)

    Google Scholar 

  10. Teo C.-T., Sethuraman J., Tan W.-P.: Gale–Shapley stable marriage problem revisited: strategic issues and applications. Manag. Sci. 47, 1252–1267 (2001)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Japan

    Noriyoshi Sukegawa

  2. Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba, Japan

    Yoshitsugu Yamamoto

Authors
  1. Noriyoshi Sukegawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yoshitsugu Yamamoto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yoshitsugu Yamamoto.

Additional information

The second author is partly supported by Grant-in-Aid for Scientific Research (C) 22510136.

About this article

Cite this article

Sukegawa, N., Yamamoto, Y. Preference profiles determining the proposals in the Gale–Shapley algorithm for stable matching problems. Japan J. Indust. Appl. Math. 29, 547–560 (2012). https://doi.org/10.1007/s13160-012-0077-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13160-012-0077-x

Keywords

Mathematics Subject Classification

Search

Navigation