A classic game-theoretical concept dating back to Shapley (1967) is the one of a (minimal) balanced set system (= collection). It has been generalized to the concept of a (minimal) semi-balanced set system in the paper
M. Studený, V. Kratochvíl: Facets of the cone of exact games. Mathematical Methods of Operations Research 95 (2022), n. 1, pp. 35-80, available at arxiv.org/abs/2103.02414.
The point is that minimal semi-balanced (= min-semi-balanced) systems correspond to the linear inequalities that delimit the cone of exact transferable-utility games. One can even determine the least possible set of such linear inequalities: these are in one-to-one correspondence with the so-called indecomposable min-semi-balanced set system, also introduced in the above paper. The detailed motivation for these two new concepts and the relevant theoretical results can be found there.
This catalogue contains all permutational types of indecomposable min-semi-balanced set systems on the basic set \(N\) having at least 3 and at most 6 elements.
Consider the Euclidean space \(\mathbb{R}^{N}\) of real vectors whose components are indexed by elements of the basic set \(N\) (= set of players in game-theoretical context). A constant vector in \(\mathbb{R}^{N}\) is such a vector in \(\mathbb{R}^{N}\) whose components equal each other. The incidence vector of a subset \(S\subseteq N\) will be denoted by \(\chi_{S}\).
We shall say that a real linear combination \(\sum_{i\in I} \lambda_{i}\cdot x_{i}\) of vectors \(x_{i}\) in \(\mathbb{R}^{N}\) is semi-conic if at most one of its coefficients \(\lambda_{i}\) is strictly negative.
Given a non-empty finite basic set \(N\) with \(|N|\geq 3\), a non-trivial set system \(\mathcal{S}\) on \(N\) is given by a non-empty list of non-empty proper subsets \(\mathcal{S} =\{S_{1},…,S_{k}\}\), \(k\geq 1\), of the basic set \(N\).
We shall say that a non-trivial set system \(\mathcal{S}\) on \(N\) is semi-balanced (on \(N\)) if there is a constant vector in \(\mathbb{R}^{N}\) which is a semi-conic combination of incidence vectors \(\{ \chi_{S}\,:\ S\in\mathcal{S}\}\) with all coefficients non-zero.
A semi-balanced system \(\mathcal{S}\) on \(N\) will be called minimal if there is no semi-balanced system \(\mathcal{C}\) on \(N\) with \(\mathcal{C}\subset\mathcal{S}\). We will then say briefly that such a set system is min-semi-balanced (on \(N\)).
In the case of a min-semi-balanced system \(\mathcal{S}\) the required semi-conic combination (of the incidence vectors) yielding the constant vector in \(\mathbb{R}^{N}\) is uniquely determined up to a positive multiple and the coefficients can be chosen to be (non-zero) integers with no common prime divisor (necessarily uniquely determined by this requirement). Thus, a min-semi-balanced system \(\mathcal{S}\) is assigned a standardized inequality \[ \sum_{S\in\mathcal{S}} \lambda_{S}\cdot m(S) \leq r \cdot m(N) \] for a real set function \(m:{\mathcal{P}}(N)\to \mathbb{R}\), where \(m(\emptyset) = 0\) and \({\mathcal{P}}(N)\) denotes the power set of \(N\) and the (semi-conic) combination \(\sum_{S\in\mathcal{S}} \lambda_{S}\cdot \chi_{S}\) yields a constant vector in \(\mathbb{R}^N\) with shared component \(r\) and the coefficients are integers with no common prime divisor. To represent the (standardized) inequality by a pictorial diagram (see below) we accept a convention: we put \(\lambda_{N}:=r\) and \(\lambda_{\emptyset}:=-r+\sum_{S\in\mathcal{S}} \lambda_{S}\). Note that these two numbers appear to be non-negative integers.
A min-semi-balanced set system \(\mathcal{S}\) is called purely min-semi-balanced if it has an exceptional set, which is the set \(T\in\mathcal{S}\) such that the coefficient \(\lambda_{T}\) is the required semi-conic combination is negative: \(\lambda_{T}<0\). This exceptional set is uniquely determined in case of a min-semi-balanced system. Since we assume \(m(\emptyset) = 0\), the respective standardized inequality can then be re-written in the form
\[\sum_{S\in\mathcal{S}\setminus\{T\}} \lambda_{S}\cdot m(S) \leq \lambda_{\emptyset}\cdot m(\emptyset) + (-\lambda_{T})\cdot m(T) + \lambda_{N}\cdot m(N).\]
Given a purely min-semi-balanced set system \(\mathcal{S}\) on \(N\) and a non-empty proper subset \(E\subset N\) which is not in \(\mathcal{S}\) we say that \(E\) yields a decomposition of \(\mathcal{S}\) if there exists a linear combination \(\sum_{S\in\mathcal{S}\cup\{E\}} \sigma_{S}\cdot\chi_{S}\) yielding a constant vector in \(\mathbb{R}^{N}\) with \(\sigma_{E}<0\) and \(\sigma_{S}\geq 0\) for \(S\in\mathcal{S}\). A purely min-semi-balanced set system on \(N\) will be called indecomposable if it has no decomposition in this sense.
Recall that the main result in the above paper says that the minimal set of linear inequalities defining the cone of exact games over \(N\) consists of those that are assigned to indecomposable min-semi-balanced set systems on \(N\).
Given a min-semi-balanced system \(\mathcal{S}\) on \(N\), its complementary system (relative to \(N\)) is the system \(\mathcal{S}^{\star}:=\{ N\setminus S : S\in\mathcal{S} \}\) where \(N\setminus S\) denotes the relative complement of \(S\) within \(N\). Basic fact about min-semi-balanced systems on \(N\) is that \(\mathcal{S}\) is indecomposable min-semi-balanced system on \(N\) iff the same holds for its complementary system \(\mathcal{S}^\star\).
In this catalogue, we use certain special pictures to represent (permutational types of) min-semi-balanced set systems. Our diagrams additionally encode the assigned (standardized) linear inequalities.
More specifically, a diagram representing a (min-semi-balanced) set system \(\mathcal{S}\) has the form of a pair of two-dimensional arrays whose entries are colorful boxes; the arrays encode the coefficient of the (extended) standardized inequality.
The rows of these arrays correspond to the elements of the basic set \(N\); they are labeled if the diagram represents a particular set system \(\mathcal{S}\) but they need not be labeled if the picture represents a permutational type of such systems.
The columns of the arrays encode sets \(S\) from the enlarged system \(\mathcal{S}\cup\{\emptyset, N\}\). Each of the sets has its color; however, the black color is reserved for the grand coalition \(N\), a fully blank (= white) column implicitly encodes the empty set and the grey color is reserved for the exceptional set \(T\) with a negative coefficient \(\lambda_{T}<0\). The other sets from \(\mathcal{S}\) have bright colors then.
The column representing a set \(S\) has boxes of the respective color just in rows corresponding to elements of \(S\). To express the value of the respective integer coefficient \(\lambda_{S}\) in the inequality the respective column is repeated \(|\lambda_{S}|\)-times.
The left array is composed of columns that correspond to sets with positive coefficient \(\lambda_{S}>0\), \(S\in\mathcal{S}\), while the array on the right-hand side has either fully black columns, fully blank (= white) columns or columns containing grey boxes.
Note that the diagram for the complementary system \(\mathcal{S}^{\star}\) to a system \(\mathcal{S}\) can easily be obtained by “reflection” from the diagram for \(\mathcal{S}\): the boxes are interchanged with non-boxes and the colors for columns are kept, under a convention that the color for blank columns is black.
The indecomposable min-semi-balanced set systems \(\mathcal{S}\) on \(N\) can be classified into three basic (classification) classes: namely
Note that the complementary systems to those in the first class belong to the second class and conversely. The complementary systems to those in the third class belong to the third class as well. If \(|N|\leq 5\) then there is no indecomposable min-semi-balanced system in the third classification class.