M. Studeny, V. Kratochvil, J. Vomlel:
On irreducible min-balanced set systems.
In Symbolic and Quantitative Approaches to Reasoning with Uncertainty
(G. Kern-Isberner, Z. Ognjanovic eds.),
Lecture Notes in Artificial Intelligence 1126,
Springer-Verlag, Cham 2019, pp. 444-454.
- Abstract
-
Non-trivial minimal balanced systems (= collections) of sets are known to characterize through their induced
linear inequalities the class of the so-called balanced (coalitional) games. In a recent paper a concept of
an irreducible min-balanced (= minimal balanced) system of sets has been introduced and the irreducible systems
have been shown to characterize through their induced inequalities the class of totally balanced games.
In this paper we recall the relevant concepts and results, relate them to various contexts and offer a
catalogue of permutational types of non-trivial min-balanced systems in which the irreducible systems
are indicated. The present catalogue involves all types of such systems on sets with
at most 5 elements; it has been obtained as a result of an alternative characterization of min-balanced systems.
- AMS classification 91A12 68R05 68T30
- Keywords
- balanced set system
- irreducible min-balanced system
- totally balanced games
- exact games
- A
pdf version of a preprint (299kB) is available.
Moreover, the result of the work is also an
interactive electronic catalogue of min-balanced system on at most 5 variables.
The manuscript builds on the following papers:
- T. Kroupa, M. Studeny:
Facets of the cone of totally balanced games.
Mathematical Methods of Operation Research
90 (2019), pp. 271-300.
- L.S. Shapley:
On balanced sets and cores.
Naval Research Logistics Quarterly
14 (1967), pp. 453-460.