On the computation of the nucleolus of a cooperative game

We consider classes of cooperative games. We show that we can efficiently c ompute an allocation in the intersection of the prekernel. and the least co re of the game if we can efficiently compute the minimum excess for any giv en allocation. In the case where the prekernel of the game contains exactly one core vector, our algorithm computes the nucleolus of the game. This ge neralizes both a recent result by Kuipers on the computation of the nucleol us for convex games and a classical result by Megiddo on the nucleolus of s tandard tree games to classes of more general minimum cost spanning tree ga mes. Our algorithm is based on the ellipsoid method and Maschler's scheme f or approximating the prekernel.