1. A cooperative based algorithm to compute solutions in the assignment game

J. C. CESCO

Brazilian Journal of Business Economics

Año: 2007

Based on some recent results about non-balanced TU-games (games withtransferable utilities) we propose a new procedure to get optimal assignmentsfor the assignment game of Shapley and Shubik (1972). The method exhibitssome particular features that could be exploited to obtain a highly parallelizablecompetitive algorithm. The key fact to develop the scheme is a strong relationshipbetween some cycles of pre-imputation which appear in connection withnon-balanced games, and the matching associated to optimal assignments. In thisnote we relate the solutions of an assignment game with some kind of cycles usedpreviously to characterize non-balanced TU-games. This relationship is then usedto develop a practical method to compute solutions of the assignment game withan approach which seems to be new.