Minimal balanced collections and their application to core stability and other topics of game theory
Fiche du document
2023
- handle: 10670/1.a6143y
- halshs: halshs-04356803
- doi: 10.1016/j.dam.2023.07.025
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2023.07.025
info:eu-repo/semantics/OpenAccess
Mots-clés
minimal balanced collection cooperative game core stable set balancedness hypergraph algorithm MSC: 91A12, 05C65 C - Mathematical and Quantitative Methods/C.C4 - Econometric and Statistical Methods: Special Topics/C.C4.C44 - Operations Research • Statistical Decision Theory C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining Theory/C.C7.C71 - Cooperative GamesSujets proches
nucléusCiter ce document
Dylan Laplace Mermoud et al., « Minimal balanced collections and their application to core stability and other topics of game theory », HAL-SHS : économie et finance, ID : 10.1016/j.dam.2023.07.025
Métriques
Partage / Export
Résumé
Minimal balanced collections are a generalization of partitions of a finite set of n elements and have important applications in cooperative game theory and discrete mathematics. However, their number is not known beyond n = 4. In this paper we investigate the problem of generating minimal balanced collections and implement the Peleg algorithm, permitting to generate all minimal balanced collections till n = 7. Secondly, we provide practical algorithms to check many properties of coalitions and games, based on minimal balanced collections, in a way which is faster than linear programming-based methods. In particular, we construct an algorithm to check if the core of a cooperative game is a stable set in the sense of von Neumann and Morgenstern. The algorithm implements a theorem according to which the core is a stable set if and only if a certain nested balancedness condition is valid. The second level of this condition requires generalizing the notion of balanced collection to balanced sets.