Insights into the Core of the Assignment Game via Complementarity

The classic paper of Shapley and Shubik \cite{Shapley1971assignment} showed that the set of imputations in the core of the assignment game is precisely the set of optimal solutions to the dual of the LP-relaxation of this game. Since the worth of this game is given by an optimal solution to the primal LP, this naturally raises the question of studying core imputations through the lens of complementarity. Our exploration yields new insights: we obtain a relationship between the competitiveness of individuals and teams of agents and the amount of profit they accrue. This also sheds light on the phenomenon of degeneracy in assignment games, i.e., when the optimal assignment is not unique. The core is a quintessential solution concept in cooperative game theory. It contains all ways of distributing the total worth of a game among agents in such a way that no sub-coalition has incentive to secede from the grand coalition.