AN ALGORITHM FOR FINDING THE NUCLEOLUS OF ASSIGNMENT GAMES

Assignment games with side payments are models of certain two-sided ma rkets. 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 propert y that it satisfies each coalition as much as possible. The correspond ing prices favor neither the sellers nor the buyers, hence provide som e stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of p ayoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type stru cture of the feasible set are utilized in associating a directed graph . Finding the next payoff is translated into deter-mining 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 = m in (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.