A Cooperative Based Algorithm to Compute Solutions in the Assignment Game

Based on some recent results about non-balanced TU-games (games with transferable utilities) we propose a new procedure to get optimal assignments for the assignment game of Shapley and Shubik (1972). The method exhibits some particular features that could be exploited to obtain a highly parallelizable competitive algorithm. The key fact to develop the scheme is a strong relationship between some cycles of pre-imputation which appear in connection with non-balanced games, and the matching associated to optimal assignments. In this note we relate the solutions of an assignment game with some kind of cycles used previously to characterize non-balanced TU-games. This relationship is then used to develop a practical method to compute solutions of the assignment game with an approach which seems to be new.