Insights into the Core of the Assignment Game via Complementarity

The classic paper of Shapley and Shubik \cite{Shapley1971assignment} characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay. The worth of this game is given by an optimal solution to the primal LP and core imputations correspond to optimal solutions to the dual LP. This fact naturally raises the question of viewing core imputations through the lens of complementarity. Our exploration along these lines yields new insights: we obtain a relationship between the competitiveness of individuals, and teams of agents, and the amount of profit they accrue. It also sheds light on the phenomenon of degeneracy, i.e., when the optimal assignment is not unique. Shapley and Shubik's suggestion for dealing with degeneracy was to perturb the edge weights of the underlying graph to make the optimal assignment unique; however, this destroys crucial information contained in the original instance and the outcome becomes a function of the vagaries of the randomness imposed on the instance. 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.