arXiv preprint ·
Welfare in Envy-free Contracts: When Agents Have Sparse Interests
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Finite-Sample and Communication-Efficient Networked Information Aggregation
Steering Emergent Behavior in Multi-Agent LLM Systems via Information Networks
Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games
The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources
Learning Global Equilibria in Non-Concave Prospect Theoretic Games
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.