Article,
Minimal balanced collections and their application to core stability and other topics of game theory
Affiliations
- [1] Centre d'Économie de la Sorbonne [NORA names: France; Europe, EU; OECD];
- [2] Paris School of Economics, Université Paris 1 Panthéon-Sorbonne, France [NORA names: France; Europe, EU; OECD];
- [3] University of Southern Denmark [NORA names: SDU University of Southern Denmark; University; Denmark; Europe, EU; Nordic; OECD]
Abstract
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.