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 pristine structural properties of this game make it a paradigmatic setting for studying the solution concept of core, with a view to using insights developed for providing guidance on profit-sharing in real-life situations. We provide additional insights by viewing imputations in the core of this game 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. Additionally, we shed light on the phenomenon of degeneracy, 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.