IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v28y2003i1p103-126.html
   My bibliography  Save this article

A Fixed-Point Approach to Stable Matchings and Some Applications

Author

Listed:
  • Tamás Fleiner

    () (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, H-1364 Budapest, Hungary)

Abstract

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope.

Suggested Citation

  • Tamás Fleiner, 2003. "A Fixed-Point Approach to Stable Matchings and Some Applications," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 103-126, February.
  • Handle: RePEc:inm:ormoor:v:28:y:2003:i:1:p:103-126
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.28.1.103.14256
    Download Restriction: no

    References listed on IDEAS

    as
    1. Crawford, Vincent P & Knoer, Elsie Marie, 1981. "Job Matching with Heterogeneous Firms and Workers," Econometrica, Econometric Society, vol. 49(2), pages 437-450, March.
    2. Charles Blair, 1988. "The Lattice Structure of the Set of Stable Matchings with Multiple Partners," Mathematics of Operations Research, INFORMS, vol. 13(4), pages 619-628, November.
    3. Alvin E. Roth, 1985. "Conflict and Coincidence of Interest in Job Matching: Some New Results and Open Questions," Mathematics of Operations Research, INFORMS, vol. 10(3), pages 379-389, August.
    4. repec:wsi:igtrxx:v:03:y:2001:i:02n03:n:s0219198901000373 is not listed on IDEAS
    5. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    6. 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.
    7. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    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. 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.
    2. EHLERS, Lars & MORRILL, Thayer, 2017. "(Il)legal assignments in school choice," Cahiers de recherche 2017-02, Universite de Montreal, Departement de sciences economiques.
    3. repec:oup:oxford:v:33:y:2017:i:4:p:541-571. is not listed on IDEAS
    4. 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.
    5. repec:wsi:igtrxx:v:19:y:2017:i:03:n:s0219198917500177 is not listed on IDEAS
    6. repec:eee:gamebe:v:115:y:2019:i:c:p:289-313 is not listed on IDEAS
    7. Yannai A. Gonczarowski & Scott Duke Kominers & Ran I. Shorrer, 2019. "A Compact, Logical Approach to Large-Market Analysis," Papers 1906.10333, arXiv.org.
    8. repec:the:publsh:2717 is not listed on IDEAS
    9. Dimakopoulos, Philipp D. & Heller, C.-Philipp, 2018. "Matching with Waiting Times: The German Entry-Level Labor Market for Lawyers," Rationality and Competition Discussion Paper Series 68, CRC TRR 190 Rationality and Competition.
    10. Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2014. "Polyhedral Aspects of Stable Marriage," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 656-671, August.
    11. Jan Christoph Schlegel, 2018. "Equivalent Choice Functions and Stable Mechanisms," Papers 1812.10326, arXiv.org, revised Jan 2019.
    12. Satoru Fujishige & Akihisa Tamura, 2007. "A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 136-155, February.
    13. Tamás Fleiner & Naoyuki Kamiyama, 2016. "A Matroid Approach to Stable Matchings with Lower Quotas," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 734-744, May.
    14. repec:jmi:articl:jmi-v1i1a5 is not listed on IDEAS
    15. repec:eee:ecolet:v:156:y:2017:i:c:p:65-67 is not listed on IDEAS
    16. repec:spr:jogath:v:46:y:2017:i:3:d:10.1007_s00182-016-0564-4 is not listed on IDEAS
    17. Yu Yokoi, 2017. "A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 238-255, January.
    18. repec:eee:jetheo:v:176:y:2018:i:c:p:803-833 is not listed on IDEAS
    19. Jay Sethuraman & Chung-Piaw Teo & Liwen Qian, 2006. "Many-to-One Stable Matching: Geometry and Fairness," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 581-596, August.
    20. Kazuo Murota & Yu Yokoi, 2015. "On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market," Mathematics of Operations Research, INFORMS, vol. 40(2), pages 460-473, February.
    21. repec:eee:gamebe:v:109:y:2018:i:c:p:201-211 is not listed on IDEAS

    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:ormoor:v:28:y:2003:i:1:p:103-126. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.