Minimal balanced collections and their applications to core stability and other topics of game theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912472096571392 |
|---|---|
| author | Mermoud, Dylan Laplace Grabisch, Michel Sudhölter, Peter |
| author_facet | Mermoud, Dylan Laplace Grabisch, Michel Sudhölter, Peter |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_05898 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimal balanced collections and their applications to core stability and other topics of game theory Mermoud, Dylan Laplace Grabisch, Michel Sudhölter, Peter Computer Science and Game Theory Theoretical Economics Combinatorics 91A12 (Primary), 05C65 (Secondary) 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. |
| title | Minimal balanced collections and their applications to core stability and other topics of game theory |
| topic | Computer Science and Game Theory Theoretical Economics Combinatorics 91A12 (Primary), 05C65 (Secondary) |
| url | https://arxiv.org/abs/2507.05898 |