CS Paper Radar

The Complexity of Minimizing Subsidies in Envy-Free House Allocation

Sijia Dai, Minming Li, Xiaowei Wu, Yong Zhang

cs.GT cs.CC ·submitted 2026-08-23 04:40 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Envy-free Allocations with Individual Payments

cs.GT cs.DS ·2026-10-07 ·Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
survey similarity 0.82
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."

0.15

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

Online House Allocation with Subsidy

cs.GT ·2026-08-31 ·Nicholas Teh, Saar Cohen, Karen Frilya Celine, Benjamin Yu, Michael J. Wooldridge
code/data similarity 0.78
Abstract

House allocation is a fundamental problem in which each agent is assigned exactly one house. While the classical model assumes that all houses are available before the allocation is computed, many practical settings require decisions to be made as houses become available over time. We introduce the online house allocation problem, where houses arrive sequentially and the algorithm must maintain an allocation without knowledge of future arrivals. Unlike online fair division, the one-house-per-agent constraint makes recourse an inherent part of the problem, as accepting a newly arrived house may require reassigning previously allocated houses. We study online house allocation under subsidy-based fairness, where monetary subsidies eliminate envy among agents. We show that envy-freeability can always be maintained online using bounded recourse and that reassignment chains of length linear in the number of agents are unavoidable in the worst case. In contrast, minimizing the total subsidy is fundamentally harder: no deterministic online algorithm against an adaptive adversary, and no randomized online algorithm against a non-adaptive adversary, admits a bounded competitive ratio, even for two agents and four houses. We complement these impossibilities by showing that exact online subsidy minimization is possible whenever there is at most one extra house beyond the number of agents, and that this guarantee is best possible with respect to the number of extra houses. Finally, we develop learning-augmented algorithms that recover the offline optimum under accurate predictions while providing explicit robustness guarantees when predictions are inaccurate.

0.54

Computing EF1 Allocations under Budget Constraints in Polynomial Time

cs.GT cs.DS ·2026-11-09 ·Tingwei Hu, Lili Mei, Guochuan Zhang
similarity 0.76
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

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.76
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

On the Complexity of Envy Cycle Elimination

cs.GT cs.CCcs.DS ·2026-11-18 ·Warut Suksompong
similarity 0.75
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.28

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

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.74
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

Envy-Free Chore Allocation with Unit Subsidies under Negative Dichotomous Valuations

cs.GT ·2026-09-13 ·Mainak Sarkar, Soumyarup Sadhukhan
theory similarity 0.73
Abstract · Revised version: Added a unit-subsidy guarantee for objective mixed instances with signed binary marginals, along with additional results on…

We study the allocation of indivisible chores with subsidies under negative dichotomous valuations, where the marginal disutility of every chore is either zero or one. This is the chore analogue of the dichotomous goods model of Barman et al. (2022), for which a subsidy of at most one unit per agent is known to suffice for envy-freeness. Our main contribution is to show that the same optimal guarantee holds for chores under no structural assumption beyond binary marginals. For every instance with negative dichotomous valuations, there exists a complete allocation $\mathcal{A}$ and a subsidy vector $p\in\{0,1\}^n$ with $\sum_{i\in N} p_i\le n-1$ such that $(\mathcal{A},p)$ is envy-free. Moreover, $\mathcal{A}$ is EF1 even before subsidies are paid. The subsidy bound is tight, and both the allocation and the subsidies can be computed in polynomial time in the value-oracle model. Unlike in the corresponding goods setting, a natural incremental extension approach does not work for chores. Our proof instead exploits key properties of an envy-free partial allocation and its associated equality graph to complete the allocation and determine which agents require subsidies. As a further extension of the main theorem, we establish the same optimal unit-subsidy guarantee for objective mixed instances with signed binary marginals, where every item is a good for all agents or a chore for all agents; these valuations need not be additive. The key step is to prove that the goods-side extension argument of Barman et al.~\cite{BKNS22} remains valid even when the previously allocated bundles contain chores. Finally, even for negative dichotomous chore valuations, we show that the unit-subsidy guarantee cannot, in general, be maintained if Pareto optimality is also required.

0.14