Algorithmic aspects of core nonemptiness and core stability

Dylan Laplace Mermoud, Michel Grabisch and Peter Sudhölter

Post-Print 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-07
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-03354292v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 2021

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

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:hal:journl:halshs-03354292

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().