IDEAS home Printed from https://ideas.repec.org/p/has/discpr/1234.html
   My bibliography  Save this paper

Fractional solutions for capacitated NTU-games, with applications to stable matchings

Author

Listed:
  • Peter Biro

    (Institute of Economics Research Centre for Economic and Regional Studies Hungarian Academy of Sciences)

  • Tamas Fleiner

    (Department of Computer Science and Information Theory Budapest University of Technology and Economics)

Abstract

In this paper we investigate some new applications of Scarf's Lemma. First, we introduce the notion of fractional core for NTU-games, which is always nonempty by the Lemma. Stable allocation is a general solution concept for games where both the players and their possible cooperations can have capacities. We show that the problem of finding a stable allocation, given a finitely generated NTU-game with capacities, is always solvable by a variant of Scarf's Lemma. Then we describe the interpretation of these results for matching games. Finally we consider an even more general setting where players' contributions in a joint activity may be different. We show that a stable allocation can be found by the Scarf algorithm in this case as well, and we demonstrate the usage of this method for the hospitals resident problem with couples. This problem is relevant in many practical applications, such as NRMP (National Resident Matching Program).

Suggested Citation

  • Peter Biro & Tamas Fleiner, 2012. "Fractional solutions for capacitated NTU-games, with applications to stable matchings," CERS-IE WORKING PAPERS 1234, Institute of Economics, Centre for Economic and Regional Studies.
    • Handle: RePEc:has:discpr:1234
    as

    Download full text from publisher

    File URL: http://econ.core.hu/file/download/mtdp/MTDP1234.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Le Breton, M & Owen, G & Weber, S, 1992. "Strongly Balanced Cooperative Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 20(4), pages 419-427.
    2. Alkan, Ahmet & Gale, David, 2003. "Stable schedule matching under revealed preference," Journal of Economic Theory, Elsevier, vol. 112(2), pages 289-306, October.
    3. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    4. Parag A. Pathak & Alvin E. Roth, 2013. "Matching with Couples: Stability and Incentives in Large Markets," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 128(4), pages 1585-1632.
    5. Kaneko, Mamoru, 1982. "The central assignment game and the assignment markets," Journal of Mathematical Economics, Elsevier, vol. 10(2-3), pages 205-232, September.
    6. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
    7. Tayfun Sönmez & Suryapratim Banerjee & Hideo Konishi, 2001. "Core in a simple coalition formation game," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(1), pages 135-153.
    8. Peter Biro & Tamas Fleiner & Rob Irving, 2013. "Matching Couples with Scarf's Algorithm," CERS-IE WORKING PAPERS 1330, Institute of Economics, Centre for Economic and Regional Studies.
    9. Kaneko, Mamoru & Wooders, Myrna Holtz, 1982. "Cores of partitioning games," Mathematical Social Sciences, Elsevier, vol. 3(4), pages 313-327, December.
    10. Péter Biró & Flip Klijn, 2013. "Matching With Couples: A Multidisciplinary Survey," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1-18.
    11. Mourad Baïou & Michel Balinski, 2002. "The Stable Allocation (or Ordinal Transportation) Problem," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 485-503, August.
    12. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    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. Peter Biro & Tamas Fleiner & Rob Irving, 2013. "Matching Couples with Scarf's Algorithm," CERS-IE WORKING PAPERS 1330, Institute of Economics, Centre for Economic and Regional Studies.
    2. Ahmet Alkan & Alparslan Tuncay, 2014. "Pairing Games and Markets," Working Papers 2014.48, Fondazione Eni Enrico Mattei.
    3. Thanh Nguyen & Rakesh Vohra, 2014. "Near Feasible Stable Matchings with Complementarities," PIER Working Paper Archive 14-028, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania.
    4. Manjunath, Vikram, 2016. "Fractional matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 321-336.

    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. Milchtaich, Igal & Winter, Eyal, 2002. "Stability and Segregation in Group Formation," Games and Economic Behavior, Elsevier, vol. 38(2), pages 318-346, February.
    2. Iehle, Vincent, 2007. "The core-partition of a hedonic game," Mathematical Social Sciences, Elsevier, vol. 54(2), pages 176-185, September.
    3. Fan-Chin Kung, 2010. "Coalition formation with local public goods and group-size effect," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(4), pages 573-583, October.
    4. Fan-chin Kung, 2005. "Coalition Formation with Local Public Goods and Network Effect," Game Theory and Information 0506007, University Library of Munich, Germany.
    5. Le Breton, Michel & Weber, Shlomo, 2004. "Group Formation with Heterogeneous Sets," IDEI Working Papers 288, Institut d'Économie Industrielle (IDEI), Toulouse.
    6. Péter Biró & Flip Klijn, 2013. "Matching With Couples: A Multidisciplinary Survey," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1-18.
    7. Emiliya Lazarova & Dinko Dimitrov, 2013. "Status-seeking in hedonic games with heterogeneous players," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(4), pages 1205-1229, April.
    8. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    9. Kovalenkov, A. & Holtz Wooders, M., 1997. "Epsilon Cores of Games and Economies With Limited Side Payments," UFAE and IAE Working Papers 392.97, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    10. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    11. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2023. "Matching markets with farsighted couples," UB School of Economics Working Papers 2023/445, University of Barcelona School of Economics.
    12. Thanh Nguyen & Rakesh Vohra, 2014. "Near Feasible Stable Matchings with Complementarities," PIER Working Paper Archive 14-028, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania.
    13. Hafalir, Isa E. & Kojima, Fuhito & Yenmez, M. Bumin, 2022. "Interdistrict school choice: A theory of student assignment," Journal of Economic Theory, Elsevier, vol. 201(C).
    14. Quint, Thomas, 1997. "Restricted houseswapping games," Journal of Mathematical Economics, Elsevier, vol. 27(4), pages 451-470, May.
    15. Greg Leo & Jian Lou & Martin Van der Linden & Yevgeniy Vorobeychik & Myrna Wooders, 2021. "Matching soulmates," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 23(5), pages 822-857, October.
    16. Kovalenkov, Alexander & Wooders, Myrna Holtz, 2001. "Epsilon Cores of Games with Limited Side Payments: Nonemptiness and Equal Treatment," Games and Economic Behavior, Elsevier, vol. 36(2), pages 193-218, August.
    17. Leduc, Matt V. & Thurner, Stefan, 2017. "Incentivizing resilience in financial networks," Journal of Economic Dynamics and Control, Elsevier, vol. 82(C), pages 44-66.
    18. Emiliya Lazarova & Dinko Dimitrov, 2010. "Status-Seeking In Coalitional Matching Problems," Economics Working Papers 10-02, Queen's Management School, Queen's University Belfast.
    19. Delorme, Maxence & García, Sergio & Gondzio, Jacek & Kalcsics, Joerg & Manlove, David & Pettersson, William, 2021. "Stability in the hospitals/residents problem with couples and ties: Mathematical models and computational studies," Omega, Elsevier, vol. 103(C).
    20. Peter Biro & Tamas Fleiner & Rob Irving, 2013. "Matching Couples with Scarf's Algorithm," CERS-IE WORKING PAPERS 1330, Institute of Economics, Centre for Economic and Regional Studies.

    More about this item

    Keywords

    Scarf lemma; core; stable matching; stable allocation; hospitals residents problem; couples;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    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:has:discpr:1234. 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: Nora Horvath (email available below). General contact details of provider: https://edirc.repec.org/data/iehashu.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.