Algorithmic Fair Contracts

Abstract

We initiate the algorithmic study of fair contract design. A principal assigns multiple tasks to heterogeneous agents and chooses task-level linear contracts; agents differ in costs and success probabilities, and fairness requires each agent to prefer her own task-contract bundle to any other agent's. Unlike envy-free allocations of indivisible items, envy-free full-allocation contracts always exist, but optimizing revenue under this constraint is computationally difficult: no polynomial-time algorithm can achieve any constant-factor approximation in general. We therefore identify tractable regimes. With a constant number of tasks, optimal EF, EF1, and $\hat{I}\mu$-EF contracts are computable in polynomial time. With a constant number of agents, exact EF remains hard, even for three agents, while EF1 and $\hat{I}\mu$-EF admit additive FPTAS against the EF benchmark. We also show that exact EF can have an unbounded price of fairness, whereas $\hat{I}\mu$-EF and EF1 can restore bounded revenue loss.

some improvements