CS Paper Radar

Envy-free Allocations with Individual Payments

Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey

cs.GT cs.DS ·submitted 2026-10-07 07:54 UTC · v1
survey

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."

Closest papers

Nearest neighbours by meaning across the whole index.

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

cs.GT cs.CC ·2026-09-23 ·Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
theory similarity 0.84
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.

0.03

Computing EF1 Allocations under Budget Constraints in Polynomial Time

cs.GT cs.DS ·2026-11-09 ·Tingwei Hu, Lili Mei, Guochuan Zhang
similarity 0.83
Abstract

We study the fair allocation of indivisible items to agents with budget constraints and additive valuations. Each agent compares its own bundle with the subsets of another bundle that fit its budget. An allocation is envy-free up to one item (EF1) if, for every agent and every nonempty subset under comparison, removing an item of maximum value to that agent eliminates its envy. We require EF1 both between agents and towards the charity, which contains all unallocated items. EF1 allocations exist, but computing them in polynomial time has remained open even for homogeneous valuations. We resolve this problem with a polynomial-time algorithm for EF1 allocations under heterogeneous valuations. We also prove that detecting an EF1 violation is NP-complete. Equivalently, checking whether a given allocation is EF1 is coNP-complete. Finally, we give polynomial-time algorithms for envy-freeness up to any item (EFX) both when each agent's valuation is proportional to item size and when each agent has a fixed number of distinct positive item values. As an application, for homogeneous valuations and any $\varepsilon>0$, we obtain an EF1 allocation with at least a $(1/2-\varepsilon)$ fraction of the maximum social welfare in time polynomial in the input length and $1/\varepsilon$.

0.04

The Complexity of Minimizing Subsidies in Envy-Free House Allocation

cs.GT cs.CC ·2026-08-23 ·Sijia Dai, Minming Li, Xiaowei Wu, Yong Zhang
similarity 0.82
Abstract

The house allocation problem is a classical one-sided matching problem that concerns the assignment of a set of $m$ houses to $n$ agents according to their preferences, where each agent is assigned exactly one house. Among the various objectives studied in this setting, envy-freeness is one of the most widely adopted fairness criteria. As envy-free house allocations do not always exist, we address this challenge by introducing subsidies and aim to compute allocations that achieve envy-freeness with minimum total subsidy. For binary instances, we show that a total subsidy of at most $(n-1)$ suffices to guarantee envy-freeness in house allocation, and this bound is tight. Building on the known NP-hardness for general utilities, we further show that computing an allocation that minimizes the total subsidy is NP-hard, even under binary utilities. However, when there are only a bounded number of types of agents with binary utilities, the problem can be solved in polynomial time. Finally, we present a polynomial time algorithm that computes the minimum subsidy required to achieve envy-freeness for two types of agents with general utilities.

0.22

Resolving Envy by Adding Goods with Bounded Supply: A Type-Count Dichotomy and Two-Agent Hardness

cs.GT cs.DS ·2026-08-10 ·Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen, Stéphane Vialette, Géraldine Jean +2 more
theory similarity 0.80
Abstract

We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary additive valuations. With one additional item type, EEAG is polynomial-time solvable for any number of agents. More generally, our algorithm permits arbitrary nonnegative integer per-copy values. The envy constraints form a system of difference constraints, and Bellman--Ford returns the componentwise least feasible extension. In contrast, with exactly two additional item types, EEAG is \textsf{NP}-complete even when both types have positive finite supply and the approvers of one type form a subset of the approvers of the other. This closes the two-type case left open by Bentert et al. Separately, we prove weak \textsf{NP}-completeness even for two agents with identical additive valuations, one initially endowed good, and a growing number of unit-supply item types. Thus, bounded-supply hardness appears both with two item-types and many agents and with two agents and many item-types.

0.04

Welfare in Envy-free Contracts: When Agents Have Sparse Interests

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.78
Abstract

We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

0.11

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.78
Abstract · 43 pages

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

0.23

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.76
Abstract · Accepted by WINE'26

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

0.16

On the Complexity of Envy Cycle Elimination

cs.GT cs.CCcs.DS ·2026-11-18 ·Warut Suksompong
similarity 0.76
Abstract

The envy cycle elimination (ECE) algorithm is a fundamental algorithm for the fair allocation of indivisible goods, guaranteeing an allocation that is envy-free up to one good under arbitrary monotone utilities. We show that the ECE algorithm can be implemented in $O(nm)$ time for $n$ agents and $m$ goods, and establish the tightness of this bound.

0.29