Minimal balanced collections and their application to core stability and other topics of game theory

Dylan Laplace Mermoud, Michel Grabisch and Peter Sudhölter

Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL

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.

Keywords: minimal balanced collection; cooperative game; core; stable set; balancedness; hypergraph; algorithm (search for similar items in EconPapers)
Date: 2023
New Economics Papers: this item is included in nep-gth
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-04356803v1
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Published in Discrete Applied Mathematics, 2023, 341, pp.60-81. ⟨10.1016/j.dam.2023.07.025⟩

Downloads: (external link)
https://shs.hal.science/halshs-04356803v1/document (application/pdf)

Related works:
Working Paper: Minimal balanced collections and their application to core stability and other topics of game theory (2023)
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:hal:cesptp:halshs-04356803

DOI: 10.1016/j.dam.2023.07.025

Access Statistics for this paper

More papers in Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL
Bibliographic data for series maintained by CCSD ().