Envy-free sharing of indivisible goods guaranteed with perfect complements
Envy-Free Allocation of Indivisible Goods under Leontief Preferences
Computer Science and Game TheoryComputational Complexity
Summary
Fair division means giving items to people so no one feels jealous of another’s share. This paper studies a type of preference where goods must be combined in fixed proportions, called Leontief preferences, often seen as perfect complements. The authors show that if there are at least two goods, it is always possible to divide them fairly without envy. They also explore how hard it is to find the fairest such division and identify scenarios where this task is easier or harder. Their work helps understand fairness in situations where items cannot be split and must be combined in specific ways.
What this means in practice
- •For resource allocators: Determine when fair division without envy is possible for resources that require fixed combinations, improving allocation transparency and satisfaction.
- •For market designers: Assess computational feasibility of welfare-maximizing envy-free allocations under complementary demand patterns for indivisible goods.
A theory result. No direct application yet.
Authors
Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
Abstract
Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.