An efficient algorithm for nucleolus and prekernel computation in some classes 
of TU-games presented by Jeroen Kuipers Maastricht University joint research with
Ulrich Faigle (University of Twente) and Walter Kern (University of Twente)

Recent years have seen an increased interest in computational complexity aspects
of solution concepts in cooperative game theory. On the positive side, efficient
algorithms have been developed e.g. for computing the nucleolus of assignment
games [Solymosi, Raghavan, 1994], the nucleon for matching games [Faigle et al,
1996], the nucleolus of convex games [Kuipers, 1997], and the nucleolus of
standard tree games [Megiddo, 1987], [Granot et al, 1996]. On the negative side,
several NP-hardness results were obtained, e.g., for testing core membership
[Faigle et al, 1997a] or computing the nucleolus [Faigle et al, 1997b] for min
cost spanning tree games, (MCST-games).

The main result of our paper is that we can efficiently (i.e. in polynomial time)
compute a point in the intersection of the prekernel and the least core under the
following assumption (CEM). CEM: There exists an algorithm that, for a given
allocation x, computes in polynomial time a coalition S (not empty and not the
grand coalition N) for which the value c(S) - x(S) is minimal.

The theorem has interesting consequences for the computation of the nucleolus 
of some classes of games. For example, a standard result in combinatorial
optimization is that assumption (CEM) holds for these games (cf. [Grötschel et
al, 1993]). It is also well-known that for convex games the prekernel consists of
a single-point: the nucleolus (cf. [Maschler et al, 1972]). It follows that the
nucleolus, being the only point in the intersection of prekernel and least core,
can be computed in polynomial time.

The theorem can also be applied to the class of minimum cost spanning tree games
(MCST-games for short). This class of games has been widely studied in the
literature. After its introduction by [Bird, 1976], various results about the
core and nucleolus were established (see, e.g. [Granot and Huberman, 1981,
1984]). Of interest for us is a result of [Granot and Huberman, 1984] who showed
that the intersection of core and prekernel of an MCST-game consists of precisely
the nucleolus. According to our theorem, polynomial solvability of the minimum
excess problem for MCST-games would now imply that the nucleolus of an MCST-game
could be computed in polynomial time. The result of Faigle et al. shows that this
is very unlikely for the general MCST game. However, we will indicate a subclass
of MCST-games for which the minimum excess problem is solvable in polynomial
time, and for this subclass we can conclude that the nucleolus is computable in
polynomial time.

One can show that the problem of finding the minimal excess for an MCST-game 
is equivalent to another well-known combinatorial problem: the vertex weighted
Steiner tree problem (VWST problem), which was first treated by [Segev, 1987].
The general VWST problem is NP-hard. This follows for example from the fact it 
is `harder' than computing the nucleolus for an MCST-game, which is already an
NP-hard problem. In [Borie et al, 1992], however, a relatively large class of
socalled recursively constructed graphs is introduced, for which the VWST problem
(and many others) can be solved even in linear time. Basically, the idea is to
construct graphs from a finite set of base graphs. Roughly, a recursively
constructed graph is then a graph which is either one of those base graphs or 
can be obtained by merging (identifying specified nodes) of a number of already
constructed graphs. Well-known examples of recursively constructed graphs are
trees, outer planar graphs, series-parallel graphs, Halin graphs, bandwidth-k
graphs, and partial k-trees. Theorem 7 of [Borie et al, 1992] states that, e.g.,
the VWST-problem is linear time solvable for such graphs. We conclude that for
all those classes of graphs, the nucleolus of the corresponding MCST-game can be
computed in polynomial time.