IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp667.html
   My bibliography  Save this paper

A Stable Marriage Requires Communication

Author

Listed:
  • Yannai A. Gonczarowski
  • Noam Nisan

Abstract

The Gale-Shapely algorithm for the Stable Marriage Problem is known to take \Theta(n^2) steps to find a stable marriage in the worst case, but only \Theta(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that \Theta(n^2) queries are required in a model that allows certain natural random-access queries to the participants' preferences. Using a reduction to the communication complexity of the disjointness problem, we prove a significantly more general - albeit slightly weaker - result, showing that \Omega(n^2) Boolean queries of any type are required. Our lower bound generalizes to (A) randomized algorithms, (B) even just verifying the stability of a proposed marriage, (C) even allowing arbitrary separate preprocessing of the women's preferences and of the men's preferences, and (D) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.

Suggested Citation

  • Yannai A. Gonczarowski & Noam Nisan, 2014. "A Stable Marriage Requires Communication," Discussion Paper Series dp667, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
  • Handle: RePEc:huj:dispap:dp667
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp667.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Kimmo Eriksson & Olle Häggström, 2008. "Instability of matchings in decentralized markets with various preference structures," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 409-420, March.
    2. Ashlagi, Itai & Gonczarowski, Yannai A., 2018. "Stable matching mechanisms are not obviously strategy-proof," Journal of Economic Theory, Elsevier, vol. 177(C), pages 405-425.
    3. Muriel Niederle & Alvin E. Roth, 2003. "Unraveling Reduces Mobility in a Labor Market: Gastroenterology with and without a Centralized Match," Journal of Political Economy, University of Chicago Press, vol. 111(6), pages 1342-1352, December.
    4. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    5. Roth, Alvin E, 1986. "On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets," Econometrica, Econometric Society, vol. 54(2), pages 425-427, March.
    6. Muriel Niederle & Alvin E. Roth, 2001. "Unraveling Reduces the Scope of an Entry Level Labor Market: Gastroenterology With and Without a Centralized Match," NBER Working Papers 8616, National Bureau of Economic Research, Inc.
    7. Guillaume R. Fréchette & Alvin E. Roth & M. Utku Ünver, 2007. "Unraveling yields inefficient matchings: evidence from post-season college football bowls," RAND Journal of Economics, RAND Corporation, vol. 38(4), pages 967-982, December.
    8. Roth, Alvin E, 1991. "A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom," American Economic Review, American Economic Association, vol. 81(3), pages 415-440, June.
    9. Segal, Ilya, 2007. "The communication requirements of social choice rules and supporting budget sets," Journal of Economic Theory, Elsevier, vol. 136(1), pages 341-378, September.
    10. Bogomolnaia, Anna & Laslier, Jean-Francois, 2007. "Euclidean preferences," Journal of Mathematical Economics, Elsevier, vol. 43(2), pages 87-98, February.
    11. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    12. Itai Ashlagi & Yash Kanoria & Jacob D. Leshno, 2017. "Unbalanced Random Matching Markets: The Stark Effect of Competition," Journal of Political Economy, University of Chicago Press, vol. 125(1), pages 69-98.
    13. Roth, Alvin E & Xing, Xiaolin, 1994. "Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions," American Economic Review, American Economic Association, vol. 84(4), pages 992-1044, September.
    14. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    15. Li, Hao & Rosen, Sherwin, 1998. "Unraveling in Matching Markets," American Economic Review, American Economic Association, vol. 88(3), pages 371-387, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Suat Evren, 2023. "Social Surplus Maximization in Sponsored Search Auctions Requires Communication," Papers 2305.07729, arXiv.org.
    2. Linda Cai & Clayton Thomas, 2019. "Representing All Stable Matchings by Walking a Maximal Chain," Papers 1910.04401, arXiv.org.
    3. Naveen Durvasula, 2022. "Utility-Based Communication Requirements for Stable Matching in Large Markets," Papers 2212.04024, arXiv.org.
    4. Tamás Fleiner & Zsuzsanna Jankó & Ildikó Schlotter & Alexander Teytelboym, 2023. "Complexity of stability in trading networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 629-648, September.

    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. Muriel Niederle & Alvin E. Roth, 2009. "The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices," NBER Chapters, in: Studies of Labor Market Intermediation, pages 235-271, National Bureau of Economic Research, Inc.
    2. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    3. Muriel Niederle & Alvin E. Roth & M. Utku Ünver, 2013. "Unraveling Results from Comparable Demand and Supply: An Experimental Investigation," Games, MDPI, vol. 4(2), pages 1-40, June.
    4. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    5. Marie-Pierre Dargnies & Rustamdjan Hakimov & Dorothea Kübler, 2019. "Self-Confidence and Unraveling in Matching Markets," Management Science, INFORMS, vol. 65(12), pages 5603-5618, December.
    6. Siqi Pan, 2018. "Exploding offers and unraveling in two-sided matching markets," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 351-373, March.
    7. Haruvy, Ernan & Roth, Alvin E. & Unver, M. Utku, 2006. "The dynamics of law clerk matching: An experimental and computational investigation of proposals for reform of the market," Journal of Economic Dynamics and Control, Elsevier, vol. 30(3), pages 457-486, March.
    8. C. Nicholas McKinney & Muriel Niederle & Alvin E. Roth, 2005. "The Collapse of a Medical Labor Clearinghouse (and Why Such Failures Are Rare)," American Economic Review, American Economic Association, vol. 95(3), pages 878-889, June.
    9. Benjamin N. Roth & Ran I. Shorrer, 2021. "Making Marketplaces Safe: Dominant Individual Rationality and Applications to Market Design," Management Science, INFORMS, vol. 67(6), pages 3694-3713, June.
    10. Jonathan M.V. Davis, 2017. "The Short and Long Run Impacts of Centralized Clearinghouses: Evidence from Matching Teach For America Teachers to Schools," 2017 Papers pda791, Job Market Papers.
    11. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press, vol. 33(4), pages 541-571.
    12. Muriel Niederle & Alvin E. Roth, 2009. "Market Culture: How Rules Governing Exploding Offers Affect Market Performance," American Economic Journal: Microeconomics, American Economic Association, vol. 1(2), pages 199-219, August.
    13. Alvin E. Roth, 2010. "Marketplace Institutions Related to the Timing of Transactions," NBER Working Papers 16556, National Bureau of Economic Research, Inc.
    14. Yann Bramoullé & Brian W. Rogers & Erdem Yenerdag, 2022. "Matching with Recall," AMSE Working Papers 2203, Aix-Marseille School of Economics, France.
    15. Muriel Niederle & Alvin E. Roth, 2004. "Market Culture: How Norms Governing Exploding Offers Affect Market Performance," Levine's Bibliography 122247000000000018, UCLA Department of Economics.
    16. Yannai A. Gonczarowski & Clayton Thomas, 2022. "Structural Complexities of Matching Mechanisms," Papers 2212.08709, arXiv.org, revised May 2023.
    17. Halaburda, Hanna, 2010. "Unravelling in two-sided matching markets and similarity of preferences," Games and Economic Behavior, Elsevier, vol. 69(2), pages 365-393, July.
    18. Ettore Damiano & Hao Li & Wing Suen, 2005. "Unravelling of Dynamic Sorting," Review of Economic Studies, Oxford University Press, vol. 72(4), pages 1057-1076.
    19. C. Nicholas McKinney & Muriel Niederle & Alvin E. Roth, 2003. "The collapse of a medical clearinghouse (and why such failures are rare)," NBER Working Papers 9467, National Bureau of Economic Research, Inc.
    20. Fainmesser, Itay P., 2013. "Social networks and unraveling in labor markets," Journal of Economic Theory, Elsevier, vol. 148(1), pages 64-103.

    More about this item

    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:huj:dispap:dp667. 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: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.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.