Nothing Special   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/hal/journl/halshs-03354292.html
   My bibliography  Save this paper

Algorithmic aspects of core nonemptiness and core stability

Author

Listed:
  • Dylan Laplace Mermoud

    (CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique, UP1 - Université Paris 1 Panthéon-Sorbonne)

  • Michel Grabisch

    (CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique, PSE - Paris School of Economics - UP1 - Université Paris 1 Panthéon-Sorbonne - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris Sciences et Lettres - EHESS - École des hautes études en sciences sociales - ENPC - École des Ponts ParisTech - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement)

  • Peter Sudhölter

    (Department of Business and Economics - SDU - University of Southern Denmark)

Abstract
In 1944, von Neumann and Morgenstern developed the concept of stable sets as a solution for coalitional games. Fifteen years later, Gillies popularized the concept of the core, which is a convex polytope when nonempty. In the next decade, Bondareva and Shapley formulated independently a theorem describing a necessary and sufficient condition for the non emptiness of the core, using the mathematical objects of minimal balanced collections. We start our investigations of the core by implementing Peleg's (1965) inductive method for generating the minimal balanced collections as a computer program and then, an algorithm that checks if a game admits a nonemptiy core or not. In 2020, Grabisch and Sudhölter formulated a theorem describing a necessary and sufficient condition for a game to admit a stable core, using several mathematical objects and concepts such as nested balancedness, balanced subsets which generalized balanced collections, exact and vital coalitions, etc. In order to reformulate the aforementioned theorem as an algorithm, a set coalitions has to be found that, among other conditions, determines the core of the game. We study core stability, geometric properties of the core and in particular, such core determining sets of coalitions. Furthermore, we describe a procedure for checking whether a subset of a given set is balanced. Finally, we implement the algorithm as a computer program that allows to check if an arbitrary balanced game admits a stable core or not.

Suggested Citation

  • Dylan Laplace Mermoud & Michel Grabisch & Peter Sudhölter, 2021. "Algorithmic aspects of core nonemptiness and core stability," Post-Print halshs-03354292, HAL.
    • Handle: RePEc:hal:journl:halshs-03354292
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-03354292
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-03354292/document
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Michel Grabisch & Peter Sudhölter, 2020. "Characterization of TU games with stable cores by nested balancedness," Documents de travail du Centre d'Economie de la Sorbonne 20009, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    2. Lloyd S. Shapley, 1967. "On balanced sets and cores," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(4), pages 453-460.
    3. Shellshear, Evan & Sudhölter, Peter, 2009. "On core stability, vital coalitions, and extendability," Games and Economic Behavior, Elsevier, vol. 67(2), pages 633-644, November.
    4. Bezalel Peleg, 1965. "An inductive method for constructing mimmal balanced collections of finite sets," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 12(2), pages 155-162, June.
    5. Lucas, William F., 1992. "Von Neumann-Morgenstern stable sets," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 17, pages 543-590, Elsevier.
    6. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    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. Sudhölter, Peter & Grabisch, Michel & Laplace Mermoud, Dylan, 2022. "Core stability and other applications of minimal balanced collections," Discussion Papers on Economics 4/2022, University of Southern Denmark, Department of Economics.
    2. Stéphane Gonzalez & Michel Grabisch, 2015. "Autonomous coalitions," Annals of Operations Research, Springer, vol. 235(1), pages 301-317, December.
    3. Sylvain Béal & Sylvain Ferrière, 2019. "Examination design: an axiomatic approach," Working Papers 2019-05, CRESE.
    4. Lohmann, E. & Borm, P. & Herings, P.J.J., 2012. "Minimal exact balancedness," Mathematical Social Sciences, Elsevier, vol. 64(2), pages 127-135.
    5. Allouch, N. & Guardiola, Luis A. & Meca, A., 2024. "Measuring productivity in networks: A game-theoretic approach," Socio-Economic Planning Sciences, Elsevier, vol. 91(C).
    6. Moshe Babaioff & Uriel Feige, 2019. "A New Approach to Fair Distribution of Welfare," Papers 1909.11346, arXiv.org.
    7. László Á. Kóczy, 2018. "Partition Function Form Games," Theory and Decision Library C, Springer, number 978-3-319-69841-0, December.
    8. Jung, Hanjoon Michael, 2009. "Spatial pillage game," Journal of Mathematical Economics, Elsevier, vol. 45(11), pages 701-707, December.
    9. Gonzalez, Stéphane & Rostom, Fatma Zahra, 2022. "Sharing the global outcomes of finite natural resource exploitation: A dynamic coalitional stability perspective," Mathematical Social Sciences, Elsevier, vol. 119(C), pages 1-10.
    10. Judith Timmer & Werner Scheinhardt, 2018. "Customer and Cost Sharing in a Jackson Network," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 20(03), pages 1-10, September.
    11. Sun, Ning & Trockel, Walter & Yang, Zaifu, 2008. "Competitive outcomes and endogenous coalition formation in an n-person game," Journal of Mathematical Economics, Elsevier, vol. 44(7-8), pages 853-860, July.
    12. Sylvain Béal & Stéphane Gonzalez & Philippe Solal & Peter Sudhölter, 2023. "Axiomatic characterizations of the core without consistency," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 687-701, September.
    13. 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.
    14. Nunnari, Salvatore, 2021. "Dynamic legislative bargaining with veto power: Theory and experiments," Games and Economic Behavior, Elsevier, vol. 126(C), pages 186-230.
    15. Martí Jané Ballarín, 2023. "The complexity of power indices in voting games with incompatible players," UB School of Economics Working Papers 2023/441, University of Barcelona School of Economics.
    16. Csóka, Péter & Illés, Ferenc & Solymosi, Tamás, 2022. "On the Shapley value of liability games," European Journal of Operational Research, Elsevier, vol. 300(1), pages 378-386.
    17. 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.
    18. Gustavo Bergantiños & Juan D. Moreno-Ternero, 2022. "On the axiomatic approach to sharing the revenues from broadcasting sports leagues," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(2), pages 321-347, February.
    19. Jinpeng Ma, 1998. "Strategic Formation of Coalitions," Departmental Working Papers 199810, Rutgers University, Department of Economics.
    20. Pedro Calleja & Francesc Llerena & Peter Sudhölter, 2020. "Monotonicity and Weighted Prenucleoli: A Characterization Without Consistency," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1056-1068, August.

    More about this item

    Keywords

    Core; stable sets; balanced collections; core stability; cooperative game; coeur; ensembles stables; collections équilibrées; stabilité du coeur; jeu coopératif;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    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:hal:journl:halshs-03354292. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.