ON FINDING THE NUCLEOLUS OF AN N-PERSON COOPERATIVE GAME

Kohlberg (1972) has shown how the nucleolus for an n-person game with side-payments may be found by solving a single minimization LP in case the imputation space is a polytope. However the coefficients in the LP have a very wide range even for problems with 3 or 4 players. Therefore the method is computationally viable only for small problems on machines with finite precision. Maschler et al. (1979) find the nucleolus by solving a sequence of minimization LPs with constraint coefficients of either -1, 0 or 1. However the number of LPs to be solved is o(4n). In this paper, we show how to find the nucleolus by solving a sequence of o(2n) LPs whose constraint coefficients are -1, 0 or 1.