Insights into the Core of Matching Games via Complementarity

The assignment game forms a paradigmatic setting for studying the core -- its pristine structural properties yield an in-depth understanding of this quintessential solution concept within cooperative game theory. In turn, insights gained provide valuable guidance on profit-sharing in real-life situations. In this vein, we raise three basic questions and address them using the following broad idea. Consider the LP-relaxation of the problem of computing an optimal assignment. On the one hand, the worth of the assignment game is given by the optimal objective function value of this LP, and on the other, the classic Shapley-Shubik Theorem \cite{Shapley1971assignment} tells us that its core imputations are precisely optimal solutions to the dual of this LP. These two facts naturally raise the question of viewing core imputations through the lens of complementarity. This leads to a resolution of all our questions. Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty. We next consider the class of general graph matching games having non-empty core and again we study the three questions raised above. The answers obtained are weaker and the reason lies in the difference in the characterizations of the vertices of the Birkhoff and Balinski polytopes.