Algorithmic aspects of core nonemptiness and core stability

Dylan Laplace Mermoud (), Michel Grabisch () and Peter Sudhölter
Additional contact information
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 nationale des ponts et chaussées - 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

Working Papers from HAL

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.

Keywords: Core; stable sets; balanced collections; core stability; cooperative game; coeur; ensembles stables; collections équilibrées; stabilité du coeur; jeu coopératif (search for similar items in EconPapers)
Date: 2021-09-24
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-03354292v1
References: Add references at CitEc
Citations:

Downloads: (external link)
https://shs.hal.science/halshs-03354292v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:halshs-03354292

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().