An Algorithm for Finding the Nucleolus of Assignment Games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market.

An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite numberof payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an $(m, n)$-person assignment game with $m = min(m, n)$ the nucleolus is found in at most 1/2 $m(m+3)$ steps, each one requiring at most $O(m n)$ elementary operations.