Fair Core Imputations for the Assignment Game: New Solution Concepts and Efficient Algorithms

Vijay V. Vazirani

Papers from arXiv.org

Abstract: The assignment game is a classical model for profit sharing and a cornerstone of cooperative game theory. While an imputation in its core guarantees fairness among coalitions, it provides no fairness guarantee at the level of individual agents: single agents or one sided coalitions have zero standalone value and may receive arbitrarily small payoffs. Motivated by the growing focus on individual level fairness, we ask: Can one select a core imputation that is also fair to individuals? We introduce three individual fairness driven solution concepts, each promoting equity in a different way. The leximin and leximax core imputations extend max min and min max fairness to uplift the least advantaged and constrain the most advantaged agents, respectively. The min spread core imputation minimizes the gap between the largest and smallest positive payoffs, promoting equitable profit distribution. For all three solution concepts, we develop combinatorial, strongly polynomial algorithms. The leximin and leximax algorithms are based on a novel adaptation of the primal dual paradigm, while the min spread algorithm combines partial executions of the first two. We expect our work to revive innovation on the potent primal dual paradigm as well as promote further work on the algorithmic study of fairness and stability.

Date: 2024-02, Revised 2025-11
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 ().