2025/07/15 by Matteo Castiglioni, Junjie Chen, Castiglioni, Matteo +3
Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Law, Economics, and Judicial Systems #Legal principles and applications
paper · pdf · doi:10.48550/arxiv.2507.11214
openalex publication_date 2025/07/15 · openalex created_date 2025/09/22 · openalex updated_date 2026/08/01
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.