Nucleolus Computation by Non-Zero-Constrained Optimization
About
We extend the list of games where the nucleolus is computable in polynomial time. Based on the classical MPS scheme, nucleolus computation can be reduced to the problem of finding a coalition with minimum excess that does not belong to a given linear subspace. We call this problem LSA-MinExcess, and show that it is equivalent to NZ-MinExcess: Given integral values per player, find a coalition with minimum excess whose player values do not sum up to $0$. Exploiting this representation, we prove that the nucleolus is computable in polynomial time for arboricity games, network strength games, and certain $b$-matching games. Along these lines, we show that for $b$-matching games with $b \leq 2$, LSA-MinExcess is polynomially equivalent to Shortest Non-Zero Cycle. Further, we prove that in general, linear subspace avoidance strictly increases the complexity of the minimum excess problem, even for monotone games. We still provide a reduction that trades linear subspace avoidance against an arbitrarily small approximation error. Finally, we show that the nucleolus is unstable in the following sense: A small change in the value function of the game can lead to a change in the nucleolus that is exponential in the number of players.