An Algorithm for Locating the Nucleolus of Assignment Games

In cooperative game theory,  Shapley value and the nucleolus are two fundamental solution concepts.  They associate a unique imputation for the players  whose coalitional worth $s$  are  given a priori.

Assignment games are two sided matching games (say between sellers and buyers) where the coalitional worths between a buyer and seller  are specified by a nonnegative  matrix.  (Here, the rows of the matrix represent sellers and the columns  of the matrix represent buyers).  While an optimal assignment correspond to best deal,  for real estate agent eyeing on commissions from both sellers and buyers, he can always initiate an imputation from the core , via the  dual  optimal solutions. The algorithm at the end of the first iteration reaches the unique corner that favors all sellers. Nucleolus is invariably a relative interior point of the core and the  algorithm at each iteration always selects the this most favorable imputation for all sellers in  a shrinking  family of imputation polytopes. Here the shrinking process correspond to the faces of the polytope moving inside at varying speeds. We can associate  with each face of the current polytope, the so called unsettled coalitions that clamor for greater satisfaction for its members. Improvements correspond to redistributions captured through  the notion of squeezing the faces of the polytope by applying different levels of pressure and reducing the dimension of the current subset of the imputation set. The algorithm terminates when this squeezing process terminates in a single point. The determination of applying such varied pressures is achieved through the longest path ending at each vertex of an associated graph. The algorithm starts with just a set of vertices of a graph with no arcs to start with.  In each intermediate stage, one introduces directed arcs corresponding to the equivalence class of unsettled and unhappy coalitions. When more and more arcs are introduced, we reach cycles and the vertices within a cycle are identified as equivalent and are shrunk to just one representative vertex. This way, at the end of an iteration, the number of vertices of the graph are reduced at least by one. New directed arcs are introduced in the next iteration and this process continues till just one vertex survives. The  algorithm terminates at this stage and the associated imputation is the nucleolus. The algorithm exploits the special lattice structure of the core for assignment games and all computations involve only dealing with the small class of buyer seller pairs.

Many other subclasses of cooperative games like the connected games and some subclass of permutation games have similar algorithms for locating the nucleolus.  As for locating  the Shapley value, the problems are wide open.