An algorithm for finding the nucleolus of assignment games (Q1327070)

An assignment game is defined by a bipartite player set \(P= M\cup N\) and an \(M\times N\)-matrix \(A\geq 0\). The entry \(A_{ij}\) denotes the profit a combination of a player \(i\in M\) and a player \(j\in N\) can make. For coalitions \(S\subset P\) the coalitional value is given by an optimal matching of the players in \(S\cap M\) with players in \(S\cap N\). The profits made by the matched couples is the coalition value. In this paper the authors give a combinatorial algorithm to compute the nucleolus of an assignment game. Starting with an optimal assignment for the grand coalition they make shifts in the payoffs under the condition that matched couples share their own profit. By doing so they increase the satisfaction of non-matched couples as well as the satisfaction of unmatched players. After at most \(m\) shifts they find the nucleolus. If an optimal assignment for the grand coalition is given, their algorithm requires at most \(O(m^ 3)\) computation steps where \(m:=\min(| M|,| N|)\).