Complexity classes revealed for multi-agent binary action contract optimization
Settling the Complexity Landscape of Multi-Agent Contracts with Binary Actions
Computer Science and Game Theory
Summary
Designing the best contracts for multiple people making simple yes-or-no choices is usually tricky. The authors studied how hard it is to find the best contract when rewards have different mathematical properties. They found some versions of the problem where good solutions can be found efficiently, others where no perfect fast method exists, and some where even approximate solutions are very hard. This helps clarify when and why contract design problems are computationally difficult.
What this means in practice
- •For contract designers: Know which reward structures allow efficient approximate contract optimization and which do not, guiding practical contract formulation.
- •For game theoreticians: Understand computational limits when designing contracts involving simple agent decisions under different reward scenarios.
A theory result. No direct application yet.
Authors
Michal Feldman, Maya Schlesinger, Shay Shani
Abstract
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 intermediate class of gross substitutes has remained largely open. We uncover a fine-grained approximation landscape within this class. We first show that the optimal contract problem is APX-complete even for OXS rewards - a strict subclass of gross substitutes rewards, ruling out a PTAS for gross substitutes unless $\mathsf{P}=\mathsf{NP}$. In contrast, for weighted matroid rank functions (WMRFs) - another natural subclass of gross substitutes - we obtain an EPTAS and show that no randomized FPTAS exists in general. We further identify the special case of partition (weighted) matroid rank functions, for which we obtain an FPTAS. This stands in contrast to the multi-agent multi-action setting, where no PTAS exists even for unweighted partition matroid rank functions. Finally, we consider the broader class of ultra reward functions. While ultra rewards retain the tractability of gross substitutes in a related combinatorial contract model with a single agent, we show a sharp contrast in the multi-agent model: no polynomial-time randomized algorithm using value queries can achieve a $2^{o(n)}$-approximation in expectation. Together, our results reveal several qualitatively distinct computational regimes within and beyond gross substitutes, and identify submodularity as a crucial ingredient for the approximability of multi-agent contracts.