Source-linked AI summary
Envy-Free Allocation of Indivisible Goods under Leontief Preferences
Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
TL;DR
Fair allocation of indivisible goods under Leontief preferences, which model perfect complements, has received comparatively little attention. The paper studies envy-free existence and welfare-maximizing computation, finding an existence guarantee with at least two goods and contrasting complexity results across settings.
Problem
Envy-freeness under complementary preferences is less studied than under additive valuations, where exact envy-free allocations may fail to exist.
Source: §1 · p. 1Method
The paper analyzes envy-free allocation under Leontief preferences, including existence, welfare-maximizing computation, and parameterized complexity.
Source: §1 · pp. 2–3Results
With at least two goods, an envy-free allocation always exists; welfare-maximizing envy-free allocation is NP-hard generally but polynomial-time solvable for single-good or identical-demand cases.
Source: §1 · pp. 2–3Takeaways & Limitations
The paper establishes a multi-good existence guarantee and identifies tractable cases for welfare-maximizing envy-free allocation.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction motivates envy-free allocation under Leontief preferences as a relatively understudied problem for indivisible, complementary goods. It presents existence and computation results, including a sharp distinction between single-good and multi-good settings and complexity results for welfare maximization.
1 Introduction
- Leontief preferences model perfect complements, yet their role in indivisible-goods fair allocation has received little attention compared with additive and divisible-resource settings.Source: §1 · pp. 1–2
- The paper studies complete allocations, assigning every copy of every good, and frames this as avoiding idle resources and preserving their possible future value.Source: §1 · p. 2
- With at least two goods, every instance admits an envy-free allocation, and one can be computed in polynomial time.The paper contrasts this guarantee with additive valuations, where exact envy-free allocations may fail to exist.Source: §1 · p. 2
- For a single good, envy-free allocations may not exist, but their existence can be characterized and decided in polynomial time.Source: §1 · p. 2
- Welfare-maximizing envy-free allocation is NP-hard in general, but polynomial-time solvable for single-good demands or identical agent demands.The objective is to maximize social welfare among envy-free allocations.Source: §1 · pp. 2–3
- The welfare-maximization problem is W[1]-hard parameterized by welfare, while algorithms are given for parameters n and m + qmax.The algorithm parameterized by n has pseudo-polynomial dependence on qmax; qmax is the maximum number of copies of any good.Source: §1 · p. 3
2 Preliminaries
The preliminaries specify the allocation instance, Leontief utility, fairness and welfare objectives, and the parameterized-complexity terminology used later.
2 Preliminaries
- An instance specifies agents, goods, the number of copies of each good, and positive-integer demand data for each agent and good.Source: §2 · pp. 3–4
- An allocation assigns integer quantities of goods to agents; unless stated otherwise, it is complete, so all copies are assigned.Partial allocations may leave copies unassigned, while the single-good case represents each agent's allocation and demand by a quantity.Source: §2 · p. 4
- Under Leontief utility, an agent's bundle value is the maximum number of complete demand bundles it can form from that bundle.Source: §2 · p. 4
- An allocation is envy-free when each agent values its own bundle at least as highly as every other agent's; welfare is the sum of agents' utilities.LEFA seeks an envy-free allocation if one exists, whereas LWMEFA seeks the welfare-maximizing envy-free allocation.Source: §2 · p. 4
- A problem is fixed-parameter tractable in parameter k when solvable in f(k) · poly(n) time; W[1]-hardness is presented as evidence against such tractability.Source: §2 · pp. 4–5
3 LEFA: Existence and Computation
With at least two goods, an envy-free allocation under Leontief preferences always exists and can be computed in polynomial time; with one good, envy-freeness may fail, but existence can be decided and an allocation computed when one exists.
3 LEFA: Existence and Computation
- With at least two goods, an envy-free allocation always exists and is computable in O(mn) time; a complete construction gives different goods to two agents, leaving every bundle with zero utility.The construction gives one agent all copies of one good and another agent the remaining goods, so each bundle lacks a required complement.Source: §3 · p. 5
- With one good, envy-freeness may fail: with one copy and two unit-demand agents, whoever misses the copy envies its recipient.Source: §3 · p. 5
- For one good, existence holds exactly when nx* ≥ q; Algorithm 1 decides and computes an envy-free allocation in O(n log q) time.Here x* is the largest number of copies received by any agent in an envy-free allocation.Source: §3 · pp. 5–6
- The single-good algorithm gives each agent floor(x*/di)di copies first, then distributes the remainder without exceeding x* per agent.This preserves each agent's utility target while allocating all remaining copies.Source: §3 · p. 6
4 Welfare Maximising Envy-Free Allocation
This section studies welfare-maximizing envy-free allocation, establishing hardness and tractable cases and presenting algorithms for it. It also examines parameterized approaches based on the number of agents, the number of goods, and maximum supply.
4 Welfare Maximising Envy-Free Allocation
- Even α-PO cannot generally reconcile envy-freeness with efficiency: in a two-agent, two-good instance, the only envy-free split has zero welfare and is not α-PO for any α ≥ 0.An envy-free allocation maximizing total utility is Pareto optimal within the space of envy-free allocations.Source: §4 · p. 7
- LWMEFA decision is NP-complete via a solution-size-preserving reduction from Independent Set, and no polynomial-time algorithm approximates its welfare within n^(1−ε) unless P = NP.The reduction also preserves approximability from Independent Set to LWMEFA.Source: §4 · pp. 7, 9
- With equal supplies, LWMEFA decision is W[1]-hard parameterized by desired welfare w and, under ETH, has no f(w)·(n + m)^o(w)-time algorithm for any computable f.The ETH lower bound is stated for the special case in which all good-copy counts are equal.Source: §4 · p. 7
4.1 Polynomial-Time Solvable Cases
- For a single good, LWMEFA is solvable in O(n log q) time; when an envy-free allocation exists, Algorithm 1 returns one maximizing welfare.The welfare guarantee is conditional on existence of an envy-free allocation.Source: §4.1 · p. 9
- With identical demand vectors and at least two goods, LWMEFA is solvable in O(nm) time, attaining maximum welfare by giving all agents the same utility and distributing remaining goods without increasing anyone’s utility.The maximum common utility is determined by the tightest good supply relative to the agents’ shared demand.Source: §4.1 · pp. 9–10
4.2 A Pseudo-Polynomial FPT Algorithm Parameterized by n
- Parameterized by n, LWMEFA has a 2^O(n^4 log n)·poly(n, m, log(qmax))·qmax-time algorithm, which is pseudo-polynomial rather than standard FPT in numeric qmax.The method uses ILP to find an optimal utility vector, then extends the resulting partial envy-free allocation to a complete one while preserving welfare and envy-freeness.Source: §4.2 · p. 10
- An ILP with n integer variables yields an envy-free allocation of maximum welfare in n^{O(n)}·poly(m,n,log qmax) time.Its solution is an envy-free allocation whose welfare equals the maximum welfare of a complete envy-free allocation.Source: §4.2 · pp. 13–14
- When m ≤ n^2 + 1, a direct MILP handles floor and minimum utility constraints with O(n^2m) integer variables and solves LWMEFA in (n^2m)^{O(n^2m)}·poly(n,m,log qmax) time.The formulation encodes minimum utilities using the Big-M method and floors using fractional variables.Source: §4.2 · pp. 14–15
- LWMEFA can be solved in 2^{O(n^4 log n)}·poly(n,m,log(qmax))·qmax time, using a direct MILP for small m and an ILP plus completion for large m.The split is at m = n^2 + 1; the large-m approach finds an optimal utility vector and completes its partial allocation without losing welfare.Source: §4.2 · p. 16
4.3 An FPT Algorithm parameterized by m + qmax
- For parameter m + qmax, the dynamic program enumerates candidate utility vectors by demand type and tests each for extension to a complete envy-free allocation; for fixed t, it runs in O(n · Q^{3m} · m) time.The algorithm returns an extendible vector with maximum welfare, calculated as the sum of each type's population times its utility.Source: §4.3 · pp. 16–18
- LWMEFA is fixed-parameter tractable in m + qmax, with running time O(nmQ^(Q^m+3m)) for Q = qmax + 1.The running time combines the enumeration of utility targets with a dynamic program taking O(nmQ^3m) time per target.Source: §4.3 · p. 19
- The algorithm considers at most Q^m effective demand types and Q^(Q^m) utility targets, using a feasibility DP for each and selecting the feasible target with maximum welfare.Demand values above available supply yield zero utility, so only Q effective demand values per good are needed.Source: §4.3 · p. 19
5 Outlook
The paper opens directions on other fairness notions, combining envy-freeness with equitability, and envy-freeness when some agents have zero demand for some goods. It also gives a zero-welfare existence result under a positive-demand condition and notes that several algorithms extend to this setting.
5 Outlook
- Future work includes studying equitability, whether it can be achieved alongside envy-freeness, and whether envy-free allocations always exist when some agents have zero demand for some goods.Source: §5 · p. 19
- When every agent positively demands at least two goods, an envy-free allocation exists with zero welfare, as the paper notes is easy to show.Source: §5 · p. 19
- The algorithms for single-good instances, identical agents, and FPT parameterized by m + qmax also work when some agents may have zero demand for some goods.Source: §5 · p. 19