IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2009.11689.html
   My bibliography  Save this paper

A characterization of absorbing sets in coalition formation games

Author

Listed:
  • Agustin G. Bonifacio
  • Elena Inarra
  • Pablo Neme

Abstract

Given a standard myopic dynamic process among coalition structures, an absorbing set is a minimal collection of such structures that is never left once entered through that process. Absorbing sets are an important solution concept in coalition formation games, but they have drawbacks: they can be large and hard to obtain. In this paper, we characterize an absorbing set in terms of a collection consisting of a small number of sets of coalitions that we refer to as a "reduced form" of a game. We apply our characterization to study convergence to stability in several economic environments.

Suggested Citation

  • Agustin G. Bonifacio & Elena Inarra & Pablo Neme, 2020. "A characterization of absorbing sets in coalition formation games," Papers 2009.11689, arXiv.org, revised May 2024.
    • Handle: RePEc:arx:papers:2009.11689
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2009.11689
    File Function: Latest version
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Alvin E. Roth, 2018. "Marketplaces, Markets, and Market Design," American Economic Review, American Economic Association, vol. 108(7), pages 1609-1658, July.
    2. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    3. H. Peyton Young, 1987. "On Dividing an Amount According to Individual Claims or Liabilities," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 398-414, August.
    4. Ray, Debraj, 2007. "A Game-Theoretic Perspective on Coalition Formation," OUP Catalogue, Oxford University Press, number 9780199207954, Decembrie.
    5. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    6. Thomas Demuynck & P. Jean‐Jacques Herings & Riccardo D. Saulle & Christian Seel, 2019. "The Myopic Stable Set for Social Environments," Econometrica, Econometric Society, vol. 87(1), pages 111-138, January.
    7. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    8. 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.
    9. P Jean-Jacques Herings & Riccardo D Saulle & Christian Seel, 2021. "The Last Will be First, and the First Last: Segregation in Societies with Relative Pay-off Concerns," The Economic Journal, Royal Economic Society, vol. 131(637), pages 2119-2143.
    10. Kalai, Ehud & Smorodinsky, Meir, 1975. "Other Solutions to Nash's Bargaining Problem," Econometrica, Econometric Society, vol. 43(3), pages 513-518, May.
    11. Kalai, Ehud & Postlewaite, Andrew & Roberts, John, 1979. "A group incentive compatible mechanism yielding core allocations," Journal of Economic Theory, Elsevier, vol. 20(1), pages 13-22, February.
    12. Koczy, Laszlo A. & Lauwers, Luc, 2004. "The coalition structure core is accessible," Games and Economic Behavior, Elsevier, vol. 48(1), pages 86-93, July.
    13. Stovall, John E., 2014. "Collective rationality and monotone path division rules," Journal of Economic Theory, Elsevier, vol. 154(C), pages 1-24.
    14. Hart, Sergiu & Kurz, Mordecai, 1983. "Endogenous Formation of Coalitions," Econometrica, Econometric Society, vol. 51(4), pages 1047-1064, July.
    15. Iehle, Vincent, 2007. "The core-partition of a hedonic game," Mathematical Social Sciences, Elsevier, vol. 54(2), pages 176-185, September.
    16. Bettina Klaus & Flip Klijn, 2005. "Corrigendum: Stable Matchings and Preferences of Couples," UFAE and IAE Working Papers 653.05, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    17. Ray, Debraj & Vohra, Rajiv, 2015. "Coalition Formation," Handbook of Game Theory with Economic Applications,, Elsevier.
    18. Nash, John, 1950. "The Bargaining Problem," Econometrica, Econometric Society, vol. 18(2), pages 155-162, April.
    19. Barberà, Salvador & Beviá, Carmen & Ponsatí, Clara, 2015. "Meritocracy, egalitarianism and the stability of majoritarian organizations," Games and Economic Behavior, Elsevier, vol. 91(C), pages 237-257.
    20. Effrosyni Diamantoudi & Licun Xue, 2003. "Farsighted stability in hedonic games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(1), pages 39-61, August.
    21. Iñarra, E. & Larrea, C. & Molis, E., 2013. "Absorbing sets in roommate problems," Games and Economic Behavior, Elsevier, vol. 81(C), pages 165-178.
    22. Roth, Alvin E & Vande Vate, John H, 1990. "Random Paths to Stability in Two-Sided Matching," Econometrica, Econometric Society, vol. 58(6), pages 1475-1480, November.
    23. Lloyd S. Shapley, 1967. "On balanced sets and cores," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(4), pages 453-460.
    24. O'Neill, Barry, 1982. "A problem of rights arbitration from the Talmud," Mathematical Social Sciences, Elsevier, vol. 2(4), pages 345-371, June.
    25. Diamantoudi, Effrosyni & Miyagawa, Eiichi & Xue, Licun, 2004. "Random paths to stability in the roommate problem," Games and Economic Behavior, Elsevier, vol. 48(1), pages 18-28, July.
    26. Roger B. Myerson, 1977. "Graphs and Cooperation in Games," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 225-229, August.
    27. Jackson, Matthew O. & Watts, Alison, 2002. "The Evolution of Social and Economic Networks," Journal of Economic Theory, Elsevier, vol. 106(2), pages 265-295, October.
    28. Hakan İnal, 2015. "Core of coalition formation games and fixed-point methods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 745-763, December.
    29. Gallo, Oihane & Inarra, Elena, 2018. "Rationing rules and stable coalition structures," Theoretical Economics, Econometric Society, vol. 13(3), September.
    30. Ballester, Coralio, 2004. "NP-completeness in hedonic games," Games and Economic Behavior, Elsevier, vol. 49(1), pages 1-30, October.
    31. Greenberg, Joseph & Weber, Shlomo, 1986. "Strong tiebout equilibrium under restricted preferences domain," Journal of Economic Theory, Elsevier, vol. 38(1), pages 101-117, February.
    32. Kalai, Ehud & Schmeidler, David, 1977. "An admissible set occurring in various bargaining situations," Journal of Economic Theory, Elsevier, vol. 14(2), pages 402-411, April.
    33. Marek Pycia, 2012. "Stability and Preference Alignment in Matching and Coalition Formation," Econometrica, Econometric Society, vol. 80(1), pages 323-362, January.
    34. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
    35. 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.
    36. Olaizola, Norma & Valenciano, Federico, 2014. "Asymmetric flow networks," European Journal of Operational Research, Elsevier, vol. 237(2), pages 566-579.
    37. Fuhito Kojima & M. Ünver, 2008. "Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 473-488, March.
    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. Agustín G. Bonifacio & Elena Inarra & Pablo Neme, 2022. "Stable Decompositions of Coalition Formation Games," Working Papers 110, Red Nacional de Investigadores en Economía (RedNIE).
    2. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2019. "Paths to stability for overlapping group structures," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 19-24.
    3. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2018. "Constitutions and groups," Games and Economic Behavior, Elsevier, vol. 107(C), pages 135-152.
    4. Ana Mauleon & Nils Roehl & Vincent Vannetelbosch, 2014. "Constitutions and Social Networks," Working Papers CIE 74, Paderborn University, CIE Center for International Economics.
    5. Alcalde-Unzu, Jorge & Gallo, Oihane & Inarra, Elena & Moreno-Ternero, Juan D., 2024. "Solidarity to achieve stability," European Journal of Operational Research, Elsevier, vol. 315(1), pages 368-377.
    6. Gallo, Oihane & Klaus, Bettina, 2024. "Stable partitions for proportional generalized claims problems," Games and Economic Behavior, Elsevier, vol. 147(C), pages 485-516.
    7. Jean-Jacques Herings, P. & Mauleon, Ana & Vannetelbosch, Vincent, 2017. "Stable sets in matching problems with coalitional sovereignty and path dominance," Journal of Mathematical Economics, Elsevier, vol. 71(C), pages 14-19.
    8. Ana Mauleon & Elena Molis & Vincent Vannetelbosch & Wouter Vergote, 2014. "Dominance invariant one-to-one matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 925-943, November.
    9. László Á. Kóczy, 2018. "Partition Function Form Games," Theory and Decision Library C, Springer, number 978-3-319-69841-0, December.
    10. Heinrich Nax & Bary Pradelski, 2015. "Evolutionary dynamics and equitable core selection in assignment games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(4), pages 903-932, November.
    11. Nax, Heinrich H. & Pradelski, Bary S. R., 2015. "Evolutionary dynamics and equitable core selection in assignment games," LSE Research Online Documents on Economics 65428, London School of Economics and Political Science, LSE Library.
    12. Imamura, Kenzo & Konishi, Hideo & Pan, Chen-Yu, 2023. "Stability in matching with externalities: Pairs competition and oligopolistic joint ventures," Journal of Economic Behavior & Organization, Elsevier, vol. 205(C), pages 270-286.
    13. Alison Watts, 2007. "Formation of segregated and integrated groups," International Journal of Game Theory, Springer;Game Theory Society, vol. 35(4), pages 505-519, April.
    14. Klaus, Bettina & Klijn, Flip & Walzl, Markus, 2010. "Stochastic stability for roommate markets," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2218-2240, November.
    15. Kenzo Imamura & Hideo Konishi, 2023. "Assortative Matching with Externalities and Farsighted Agents," Dynamic Games and Applications, Springer, vol. 13(2), pages 497-509, June.
    16. Papai, Szilvia, 2004. "Unique stability in simple coalition formation games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 337-354, August.
    17. 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.
    18. Péter Biró & Gethin Norman, 2013. "Analysis of stochastic matching markets," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(4), pages 1021-1040, November.
    19. Dominik Karos, 2015. "Stable partitions for games with non-transferable utilities and externalities," Economics Series Working Papers 741, University of Oxford, Department of Economics.
    20. Han, Lining & Juarez, Ruben & Vargas, Miguel, 2023. "Robust equilibria in tournaments," Games and Economic Behavior, Elsevier, vol. 142(C), pages 423-439.

    More about this item

    JEL classification:

    • 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

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2009.11689. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.