CS Paper Radar

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

Junjie Chen, Cong Chen, Takuro Yamashita

cs.GT ·submitted 2026-11-08 08:22 UTC · v1

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.

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.78
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.76
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

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

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

cs.GT ·2026-09-13 ·Mainak Sarkar, Soumyarup Sadhukhan
theory similarity 0.71
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

A Polynomial-Time Algorithm for Constant-Factor EFX Allocations of Chores

cs.GT ·2026-11-16 ·Aniket Murhekar
similarity 0.71
Abstract · 32 pages

We study the fair division of indivisible chores among agents with additive disutilities, focusing on the central fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. Although the existence of constant-factor approximations to EFX are known, computing such an allocation in polynomial time remained open. We resolve this question by giving an algorithm that, for every $\varepsilon\in(0,1)$, computes a $(3+\varepsilon)$-EFX allocation in time polynomial in the input length and $1/\varepsilon$. Our result relies on two algorithmic contributions. First, we give a fully polynomial-time approximation scheme (FPTAS) for earning-restricted (ER) equilibria with equal earning requirements and arbitrary feasible chore earning limits. We develop a new nonconvex program with chore payouts and money-flow variables, and prove that every local maximum yields an exact ER equilibrium. We then give a mirror-ascent algorithm for this program and prove that it converges to an approximate ER equilibrium in polynomial time. Second, we give a new procedure that converts the approximate equilibrium into a $(3+\varepsilon)$-EFX-friendly allocation, a suitable starting point for the chore-swap framework of Garg and Murhekar (2026). The procedure uses a flexible price threshold to choose swap chores and their recipients together, overcoming a factor-four bottleneck in the earlier approaches while accommodating approximate earnings. We expect these ideas to be useful more broadly in fair division, including for goods and other fairness notions.

0.32

Computing EF1 Allocations under Budget Constraints in Polynomial Time

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

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

cs.GT ·2026-10-22 ·Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
benchmark similarity 0.71
Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

0.31

Temporal Fair Division: Simultaneous Guarantees for Goods and Chores

cs.GT ·2026-11-18 ·Tianqi Chen
similarity 0.70
Abstract

We study temporal fair division of indivisible items in both the goods and chores settings, with $n \ge 2$ agents and nonnegative additive values or costs. Items arrive one at a time and must be assigned immediately and irrevocably. The arrival order and all agents' values or costs are known in advance, and the cumulative allocation must satisfy the fairness requirements after each arrival. For goods, we give a polynomial-time algorithm that simultaneously achieves exact temporal proportionality up to one item (TPROP1), a $1/n$ approximation to temporal maximin share (TMMS), and a $1/(n-1)$ approximation to temporal envy-freeness up to one item (TEF1). The TMMS factor is optimal. For chores, we give a polynomial-time algorithm that simultaneously achieves exact TPROP1 and a $2-1/n$ approximation to TMMS. Classical scheduling lower bounds based on fixed sequences carry over to chores TMMS, establishing the optimality of this factor for $n=2,3$. For every $n \ge 2$, we further show that $2-1/n$ is the optimal TMMS factor subject to exact TPROP1. For every fixed $n \ge 3$ and every finite $β\ge 1$, we construct an instance of chores admitting no $β$-TEF1 allocation.

0.13