Envy-free allocations feasible with individual budget constraints
Envy-free Allocations with Individual Payments
Computer Science and Game TheoryData Structures and Algorithms
Summary
Sometimes when dividing things fairly, it's impossible to make everyone feel they got a fair share without some payments. The authors study how people can pay each other, respecting each person's spending limits, to fix these fairness problems. They found it's easy to check if a given division can be fixed this way but hard to find a good division from scratch. They also developed ways to handle some special cases efficiently and answered part of an open question about such problems.
What this means in practice
- •For market designers: Determine if a proposed division of indivisible goods can be adjusted fairly with payments among participants respecting their budgets.
- •For auction platform engineers: Design algorithms that verify and compute envy-free allocations with budget-limited payments in allocation and auction scenarios.
A theory result. No direct application yet.
Authors
Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
Abstract
When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this limitation by allowing only monetary transfers between agents, with each agent's payments constrained by their individual budget. We show that while it is polynomial-time tractable to determine whether a given allocation can be made envy-free by payments under individual budgets, the general problem of computing such an allocation from scratch is NP-hard, even when agents have relatively large budgets. Motivated by this intractability, we conduct a parameterized complexity analysis, establishing fixed-parameter tractability with respect to the number of goods or to the joint parameter number of agents and good types, and we provide efficient algorithms in several special cases. For explicitly listed items, our type-based algorithm answers the envy-freeness part of an open question of T. T. Nguyen and J. Rothe, "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey."