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

Vijay V. Vazirani

Papers from arXiv.org

Abstract: 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. The ``engine'' driving them involves insights into core imputations obtained via complementarity. It will not be surprising if our work leads to new uses of this powerful technique. Furthermore, 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}.

Date: 2024-02, Revised 2024-12
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2402.11437 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2402.11437

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators (help@arxiv.org).