IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v52y2023i1d10.1007_s00182-022-00816-1.html
   My bibliography  Save this article

The minimum set of $$\mu $$ μ -compatible subgames for obtaining a stable set in an assignment game

Author

Listed:
  • Keisuke Bando

    (Shinshu University)

  • Yakuma Furusawa

    (Tokyo Institute of Technology)

Abstract

This study analyzes von Neumann-Morgenstern stable sets in an assignment game. Núñez and Rafels (2013) have shown that the union of the extended cores of all $$\mu $$ μ -compatible subgames is a stable set. Typically, the set of all $$\mu $$ μ -compatible subgames includes many elements, most of which are inessential for obtaining the stable set. We provide an algorithm to find a set of $$\mu $$ μ -compatible subgames for obtaining the stable set when the valuation matrix is positive. Moreover, this algorithm finds the minimum set of $$\mu $$ μ -compatible subgames for obtaining the stable set when each column and row in the valuation matrix is constituted from different positive numbers. Our simulation result reveals that the average size of the minimum set of $$\mu $$ μ -compatible subgames for obtaining the stable set is significantly lower than that of the set of all $$\mu $$ μ -compatible subgames.

Suggested Citation

  • Keisuke Bando & Yakuma Furusawa, 2023. "The minimum set of $$\mu $$ μ -compatible subgames for obtaining a stable set in an assignment game," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 231-252, March.
    • Handle: RePEc:spr:jogath:v:52:y:2023:i:1:d:10.1007_s00182-022-00816-1
    DOI: 10.1007/s00182-022-00816-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00182-022-00816-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00182-022-00816-1?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    2. Atay, Ata & Núñez, Marina, 2019. "A note on the relationship between the core and stable sets in three-sided markets," Mathematical Social Sciences, Elsevier, vol. 98(C), pages 10-14.
    3. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    4. Leonard, Herman B, 1983. "Elicitation of Honest Preferences for the Assignment of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 91(3), pages 461-479, June.
    5. Núñez, Marina & Rafels, Carles, 2008. "On the dimension of the core of the assignment game," Games and Economic Behavior, Elsevier, vol. 64(1), pages 290-302, September.
    6. Núñez, Marina & Rafels, Carles, 2013. "Von Neumann–Morgenstern solutions in the assignment market," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1282-1291.
    7. Dezső Bednay, 2014. "Stable sets in one-seller assignment games," Annals of Operations Research, Springer, vol. 222(1), pages 143-152, November.
    8. T. E. S. Raghavan & Tamás Solymosi, 2001. "Assignment games with stable core," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(2), pages 177-185.
    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. Bando, Keisuke & Kawasaki, Ryo, 2021. "Stability properties of the core in a generalized assignment problem," Games and Economic Behavior, Elsevier, vol. 130(C), pages 211-223.
    2. R. Branzei & E. Gutiérrez & N. Llorca & J. Sánchez-Soriano, 2021. "Does it make sense to analyse a two-sided market as a multi-choice game?," Annals of Operations Research, Springer, vol. 301(1), pages 17-40, June.
    3. Marina Núñez & Carles Rafels, 2009. "Von Neumann-Morgenstern stable-set solutions in the assignment market," Working Papers 412, Barcelona School of Economics.
    4. Núñez, Marina & Rafels, Carles, 2009. "A glove-market partitioned matrix related to the assignment game," Games and Economic Behavior, Elsevier, vol. 67(2), pages 598-610, November.
    5. Hirai, Toshiyuki & Watanabe, Naoki, 2018. "von Neumann–Morgenstern stable sets of a patent licensing game: The existence proof," Mathematical Social Sciences, Elsevier, vol. 94(C), pages 1-12.
    6. Nunez, Marina & Rafels, Carles, 2003. "Characterization of the extreme core allocations of the assignment game," Games and Economic Behavior, Elsevier, vol. 44(2), pages 311-331, August.
    7. Raïssa-Juvette Samba Zitou & Rhonya Adli, 2012. "Quasi stable outcomes in the assignment game," Theory and Decision, Springer, vol. 72(3), pages 323-340, March.
    8. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    9. Atay, Ata & Núñez, Marina, 2019. "A note on the relationship between the core and stable sets in three-sided markets," Mathematical Social Sciences, Elsevier, vol. 98(C), pages 10-14.
    10. Dezső Bednay, 2014. "Stable sets in one-seller assignment games," Annals of Operations Research, Springer, vol. 222(1), pages 143-152, November.
    11. van den Brink, René & Núñez, Marina & Robles, Francisco, 2021. "Valuation monotonicity, fairness and stability in assignment problems," Journal of Economic Theory, Elsevier, vol. 195(C).
    12. Ma, Jinpeng, 1998. "Competitive Equilibrium with Indivisibilities," Journal of Economic Theory, Elsevier, vol. 82(2), pages 458-468, October.
    13. David Pérez-Castrillo & Marilda Sotomayor, 2013. "Two Folk Manipulability Theorems In The General One-To-Two-Sided Matching Markets With Money," Working Papers, Department of Economics 2013_01, University of São Paulo (FEA-USP).
    14. Mishra, Debasis & Talman, Dolf, 2010. "Characterization of the Walrasian equilibria of the assignment model," Journal of Mathematical Economics, Elsevier, vol. 46(1), pages 6-20, January.
    15. T. Andersson & C. Andersson & A. Talman, 2013. "Sets in excess demand in simple ascending auctions with unit-demand bidders," Annals of Operations Research, Springer, vol. 211(1), pages 27-36, December.
    16. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    17. Tierney, Ryan, 2019. "The problem of multiple commons: A market design approach," Games and Economic Behavior, Elsevier, vol. 114(C), pages 1-27.
    18. Trudeau, Christian, 2018. "From the bankruptcy problem and its Concede-and-Divide solution to the assignment problem and its Fair Division solution," Games and Economic Behavior, Elsevier, vol. 108(C), pages 225-238.
    19. Andersson, Tommy & Svensson, Lars-Gunnar, 2024. "Strategy-proof allocation of objects: A characterization result," Mathematical Social Sciences, Elsevier, vol. 128(C), pages 1-5.
    20. Zhou, Yu & Serizawa, Shigehiro, 2023. "Multi-object auction design beyond quasi-linearity: Leading examples," Games and Economic Behavior, Elsevier, vol. 140(C), pages 210-228.

    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:spr:jogath:v:52:y:2023:i:1:d:10.1007_s00182-022-00816-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.