Algorithmic aspects of core nonemptiness and core stability

Dylan Laplace Mermoud (1, 2) , Michel Grabisch (1, 3) , Peter Sudhölter (4)

1 CES - Centre d'économie de la Sorbonne
2 UP1 - Université Paris 1 Panthéon-Sorbonne
3 PSE - Paris School of Economics
4 Department of Business and Economics

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.

En 1944, von Neumann and Morgenstern ont développé le concept d'ensembles stables comme une solution pour les jeux coopératifs. Quinze années plus tard, Gillies réhabilite la notion de coeur, qui est un polytope convexe quand il est non vide. Nous commençons notre étude du coeur par l'implémentation de la méthode récursive de Peleg (1965) générant les collections minimales équilibrées, puis à partir de celle-ci nous développons un algorithme vérifiant si le coeur d'un jeu donné est vide ou non, en utilisant le théorème de Bondareva-Shapley. En 2020, Grabisch et Sudhölter formulent un théorème décrivant une condition nécessaire et suffisante pour qu'un jeu admette un coeur stable, utilisant les notions d'équilibre imbriqué, de sous-ensembles équilibrés, de coalitions exacte et strictement vitales-exactes. Pour faire cela, nous avons besoin d'identifier une collection particulière de coalitions qui déterminent le coeur. Ensuite, il nous faut trouver une manière de vérifier si un sous-ensemble donné est équilibré dans son ensemble ambiant. Enfin, on implémente cela dans un programme fonctionnel qui vérifie si un jeu admet un coeur stable ou non.

Mots clés: Core; stable sets; balanced collections; core stability; cooperative game

Mots clés: coeur; ensembles stables; collections équilibrées; stabilité du coeur; jeu coopératif

Domaines: Economies et finances

Dylan Laplace Mermoud, Michel Grabisch, Peter Sudhölter. Algorithmic aspects of core nonemptiness and core stability. 2021. ⟨halshs-03354292⟩