Algorithms and Some Algorithmic Issues for Assignment Games

Abstract

Assignment games are special classes of cooperative games where players are of two types, like buyesr-sellers, males-females, employers-employees, students, colleges and many others of this type. ?Any coalitional effort is meaningful only between one person from each side. ?This can be captured through a matrix for side payment games. The players are keen on the most fruitful collaboration that benefit them and the players are eyeing on their best deal. Here it is not just cooperation but competition to get the best partner. Two solution concepts are fundamental, namely the Shapley value and the Nucleolus. We will discuss how to locate the nucleolus for these games by some graph theoretic tools. The efficient algorithmic aspects of computing the Shapley value are still open.