A Cooperative Based Algorithm to Compute Solutions in the Assignment Game

Abstract

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.

Com base em alguns resultados de jogos TU não balanceados (jogos com utilidades transferíveis) propomos um novo procedimento para obter designações ótimas para o jogo de designação de Shapley and Shubik (1972). O método possui alguns aspectos particulares que permite obter um algoritmo comparável altamente competitivo. O elemento principal para desenvolver este esquema é a forte relação entre alguns ciclos de pré-imputação, os quais aparecem em conexão com jogos não balanceados e os casamentos associados a designações ótimas. Nesta nota relacionamos as soluções de um jogo de designação com alguns tipos de ciclos utilizados previamente para caracterizar jogos TU não balanceados. Esta relação é logo utilizada para desenvolver um método prático para computar soluções de jogos de designação com um novo tratamento.