Abstract:We study algorithmic fair contract design, where a principal designs task-level contracts and fairly delegates a set of tasks to a set of agents. Prior work on this setting, particularly on envy-free (EF) contracts, either suffers from an unbounded price of fairness (PoF) or avoids this unboundedness by losing strict fairness. To address these limitations, we propose a novel scheme, called {\it Envy-free Contracts with Subsidies} (EFS), in which the principal may additionally offer agent-specific subsidies. We show that EFS contracts not only restore strict fairness, but can also outperform EF contracts by an arbitrarily large factor. Moreover, in sharp contrast to EF contracts, we prove that EFS contracts admit a tight $n^{\Theta(n)}$ bound on the price of fairness, where $n$ is the number of agents. We further show that computing optimal EFS contracts is NP-hard in general. Nevertheless, when the number of tasks is constant, we provide a polynomial-time algorithm for computing optimal EFS contracts.
From: Junjie Chen [view email]
[v1]
Wed, 24 Jun 2026 05:50:06 UTC (55 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。