Algorithmic aspects of core nonemptiness and core stability

Dylan Laplace Mermoud, Michel Grabisch and Peter Sudhölter

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

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 nonempty 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 of 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 (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Pages: 22 pages
Date: 2021-07
New Economics Papers: this item is included in nep-des, nep-gth and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://mse.univ-paris1.fr/pub/mse/CES2021/21028.pdf (application/pdf)
https://halshs.archives-ouvertes.fr/halshs-03354292

Related works:
Working Paper: Algorithmic aspects of core nonemptiness and core stability (2021)
Working Paper: Algorithmic aspects of core nonemptiness and core stability (2021)
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:mse:cesdoc:21028

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().