IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v47y2001i9p1252-1267.html
   My bibliography  Save this article

Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications

Author

Listed:
  • Chung-Piaw Teo

    (Department of Decision Sciences, Faculty of Business Administration, National University of Singapore, FBA 1-15 Law Link, Singapore 117591)

  • Jay Sethuraman

    (Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027)

  • Wee-Peng Tan

    (Department of Decision Sciences, Faculty of Business Administration, National University of Singapore, FBA 1-15 Law Link, Singapore 117591)

Abstract

We study strategic issues in the Gale-Shapley stable marriage model. In the first part of the paper, we derive the optimal cheating strategy and show that it is not always possible for a woman to recover her women-optimal stable partner from the men-optimal stable matching mechanism when she can only cheat by permuting her preferences. In fact, we show, using simulation, that the chances that a woman can benefit from cheating are slim. In the second part of the paper, we consider a two-sided matching market found in Singapore. We study the matching mechanism used by the Ministry of Education (MOE) in the placement of primary six students in secondary schools, and discuss why the current method has limited success in accommodating the preferences of the students, and the specific needs of the schools (in terms of the "mix" of admitted students). Using insights from the first part of the paper, we show that stable matching mechanisms are more appropriate in this matching market and explain why the strategic behavior of the students need not be a major concern.

Suggested Citation

  • Chung-Piaw Teo & Jay Sethuraman & Wee-Peng Tan, 2001. "Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications," Management Science, INFORMS, vol. 47(9), pages 1252-1267, September.
  • Handle: RePEc:inm:ormnsc:v:47:y:2001:i:9:p:1252-1267
    DOI: 10.1287/mnsc.47.9.1252.9784
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.47.9.1252.9784
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.47.9.1252.9784?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    2. Roth, Alvin E., 1985. "The college admissions problem is not equivalent to the marriage problem," Journal of Economic Theory, Elsevier, vol. 36(2), pages 277-288, August.
    3. Sonmez, Tayfun, 1997. "Manipulation via Capacities in Two-Sided Matching Markets," Journal of Economic Theory, Elsevier, vol. 77(1), pages 197-204, November.
    4. Tadenuma, Koichi & Toda, Manabu, 1998. "Implementable stable solutions to pure matching problems," Mathematical Social Sciences, Elsevier, vol. 35(2), pages 121-132, March.
    5. Kara, Tarik & Sonmez, Tayfun, 1996. "Nash Implementation of Matching Rules," Journal of Economic Theory, Elsevier, vol. 68(2), pages 425-439, February.
    6. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    7. Alvin E. Roth & Uriel G. Rothblum, 1999. "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, Econometric Society, vol. 67(1), pages 21-44, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    2. Alexander Westkamp, 2013. "An analysis of the German university admissions system," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 53(3), pages 561-589, August.
    3. Ma, Jinpeng, 2010. "The singleton core in the college admissions problem and its application to the National Resident Matching Program (NRMP)," Games and Economic Behavior, Elsevier, vol. 69(1), pages 150-164, May.
    4. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    5. Assaf Romm, 2014. "Implications of capacity reduction and entry in many-to-one stable matching," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(4), pages 851-875, December.
    6. Diss, Mostapha & Doghmi, Ahmed & Tlidi, Abdelmonaim, 2016. "Strategy proofness and unanimity in many-to-one matching markets," MPRA Paper 75927, University Library of Munich, Germany, revised 08 Dec 2016.
    7. Alcalde, José, 2018. "Beyond the Spanish MIR with consent: (Hidden) cooperation and coordination in matching," Games and Economic Behavior, Elsevier, vol. 110(C), pages 32-49.
    8. Coles, Peter & Shorrer, Ran, 2014. "Optimal truncation in matching markets," Games and Economic Behavior, Elsevier, vol. 87(C), pages 591-615.
    9. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    10. Ergin, Haluk & Sonmez, Tayfun, 2006. "Games of school choice under the Boston mechanism," Journal of Public Economics, Elsevier, vol. 90(1-2), pages 215-237, January.
    11. Mumcu, Ayse & Saglam, Ismail, 2007. "College Admissions under Early Decision," MPRA Paper 1906, University Library of Munich, Germany.
    12. Claus-Jochen Haake & Bettina Klaus, 2009. "Monotonicity and Nash implementation in matching markets with contracts," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 41(3), pages 393-410, December.
    13. Itai Ashlagi & Flip Klijn, 2010. "Manipulability in Matching Markets: Conflict and Coincidence of Interests," Working Papers 479, Barcelona School of Economics.
    14. Parag A. Pathak & Tayfun Sönmez, 2013. "School Admissions Reform in Chicago and England: Comparing Mechanisms by Their Vulnerability to Manipulation," American Economic Review, American Economic Association, vol. 103(1), pages 80-106, February.
    15. Schummer, James & Abizada, Azar, 2017. "Incentives in landing slot problems," Journal of Economic Theory, Elsevier, vol. 170(C), pages 29-55.
    16. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    17. Jiang, Zhishan & Tian, Guoqiang, 2013. "Matching with Couples: Stability and Algorithm," MPRA Paper 57936, University Library of Munich, Germany, revised Jul 2014.
    18. Onur Kesten, 2012. "On two kinds of manipulation for school choice problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 51(3), pages 677-693, November.
    19. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    20. Mustafa Afacan, 2013. "The welfare effects of pre-arrangements in matching markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 53(1), pages 139-151, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:47:y:2001:i:9:p:1252-1267. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.