Equitable Core Imputations via a New Adaptation of The Primal-Dual Framework

The classic paper of Shapley and Shubik \cite{Shapley1971assignment} characterized the core of the assignment game. We observe that a sub-coalition consisting of one player (or a set of players from the same side of the bipartition) can make zero profit, and therefore its profit under a core imputation can be an arbitrary amount. Hence an arbitrary core imputation makes {\em no fairness guarantee at the level of individual agents}. Can this deficiency be addressed by picking a ``good'' core imputation? To arrive at an appropriate solution concept, we give specific criteria for picking a special core imputation, and we undertake a detailed comparison of four solution concepts. Leximin and leximax core imputations come out as clear winners; we define these to be {\em equitable core imputations}. These imputations achieve ``fairness'' in different ways: whereas leximin tries to make poor agents more rich, leximax tries to make rich agents less rich. We give combinatorial strongly polynomial algorithms for computing these imputations via a novel adaptation of the classical primal-dual paradigm. It will not be surprising if our work leads to new uses of this powerful technique. Additionally, we expect more work on computing the leximin and leximax core imputations of other natural games, in addition to the recent follow-up work \cite{Leximin-max}.