Algorithmic Fair Contracts
For researchers in algorithmic game theory and contract theory, this paper provides the first computational analysis of fairness in contract design, identifying both hardness results and tractable approximations.
This paper initiates the algorithmic study of fair contract design, showing that envy-free contracts always exist but optimizing revenue under this constraint is computationally hard. The authors identify tractable regimes for EF1 and ε-EF contracts, and show that exact EF can have an unbounded price of fairness while ε-EF and EF1 restore bounded revenue loss.
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 $ε$-EF contracts are computable in polynomial time. With a constant number of agents, exact EF remains hard, even for three agents, while EF1 and $ε$-EF admit additive FPTAS against the EF benchmark. We also show that exact EF can have an unbounded price of fairness, whereas $ε$-EF and EF1 can restore bounded revenue loss.