Envy-free Contracts with Subsidies
This work addresses the unbounded price of fairness in envy-free contract design for principal-agent task delegation, offering a novel solution that restores strict fairness with bounded efficiency loss.
The paper introduces envy-free contracts with subsidies (EFS) to achieve strict fairness in algorithmic contract design, showing that EFS can outperform standard envy-free contracts by an arbitrarily large factor and has a tight price of fairness bound of n^{Θ(n)}.
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^{Θ(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.