Minimal balanced collections: generation, applications and generalization

Dylan Laplace Mermoud, Michel Grabisch and Peter Sudh lter
Additional contact information
Peter Sudh lter: University of Southern Denmark
Authors registered in the RePEc Author Service: Peter Sudhölter

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

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 pratical 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 to generalize the notion of balanced collection to balanced sets

Keywords: minimal balanced collection; cooperative game; core; stable set; hypergraph; algorithm (search for similar items in EconPapers)
JEL-codes: C44 C71 (search for similar items in EconPapers)
Pages: 32 pages
Date: 2023-01
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://mse.univ-paris1.fr/pub/mse/CES2023/23001.pdf (application/pdf)
https://shs.hal.science/halshs-03972833

Related works:
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:mse:cesdoc:23001

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().