Settling the Complexity Landscape of Multi-Agent Contracts with Binary Actions
We study the computational complexity of optimal contract design in the multi-agent binary-action model, focusing on gross-substitutes reward functions and related classes. While additive rewards admit an FPTAS and general submodular rewards admit only constant-factor approximation, the complexity within the intermedia...