Note on the computational complexity of least core concepts for min-cost spanning tree games. (Q1403160)

A cooperative game is usually described by its characteristic function \(v(S)\) which assigns, to each possible coalition of players \(S\subseteq N\), the value that this coalition can guarantee if its participants act together. If they all act together, they gain \(v(N)\); the problem is how to allocate this amount between the participants, i.e., how to assign the value \(x_i\) to each participant \(i\in N\) so that \(\sum\limits_{i\in N} x_i=v(N)\). In some situations, there exist allocations for which for every coalition \(S\), the gained amount \(x(S)=\sum\limits_{i\in S} x_i\) is not smaller than \(v(S)\): \(x(S)\geq v(S)\); the set of all such allocations is called a core. For allocations from the core, no coalition \(S\) benefits from acting separately. In many games, however, the core is empty. In this case, it is desirable to select allocations for which the benefit of breaking the rules is the smallest, i.e., for which \(x(S)\geq v(S)-\varepsilon\cdot f(S)\) for all \(S\) -- for the smallest possible \(\varepsilon>0\) for which these inequalities are possible; the set of such allocations is called the \textit{least core}. We may want to choose \(f(S)=1\), in which case we bound the absolute difference \(v(S)-x(S)\); we may choose \(f(S)=v(S)\), in which case we bound the relative difference \((v(S)-x(S))/v(S)\); we may choose \(v(S)=| S| \), in which case we bound the difference per person. The authors show that even for simple games -- in which \(v(S)\) is the cost of the minimum spanning tree -- for each of these functions \(f(S)\), computing the least core is NP-hard. As a corollary, the authors prove that for such games, many other solution concepts also result in NP-hard problems.