Finding and verifying the nucleolus of cooperative games

The nucleolus offers a desirable payoff-sharing solution in cooperative games, thanks to its attractive properties ---it always exists and lies in the core (if the core is non-empty), and is unique. The nucleolus is considered as the most `stable' solution in the sense that it lexicographically minimize the dissatisfactions among all coalitions. Although computing the nucleolus is very challenging, the Kohlberg criterion offers a powerful method for verifying whether a solution is the nucleolus in relatively small games (i.e., with a number of players $n \leq 15$). This approach, however, becomes more challenging for larger games because of the need to form and check the balancedness of possibly exponentially large collections of coalitions, with each collection potentially of an exponentially large size. The aim of this work is twofold. First, we develop an efficient version of the Kohlberg criterion that involves checking the balancedness of at most $n-1$ sets of coalitions. Second, we exploit these results and introduce a new constructive algorithm to find the nucleolus efficiently. We also provide a compact representation of tight sets and a fast algorithm for verifying balancedness. Our contribution includes the first open-source code for computing the nucleolus.