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. Next, we consider the class of general graph matching games having non-empty core and again we study these three questions. The answers obtained are weaker and the reason lies in the difference in the characterizations of the vertices of the Birkhoff and Balinski polytopes.