PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the Complexity Landscape of Multi-Agent Contracts with Binary Actions

Michal Feldman, Maya Schlesinger, Shay Shani

arXiv:2609.34665v1cs.GT

TL;DR

The paper asks whether gross-substitutes rewards permit better optimal-contract approximations than general submodular rewards, and how guarantees vary across related classes. It develops algorithms and hardness results for gross-substitutes subclasses and ultra rewards. The results range from an FPTAS for partition matroids to strong inapproximability for OXS and ultra rewards.

  • Problem

    Whether gross-substitutes rewards allow stronger approximation guarantees than the known constant-factor result for submodular rewards has remained open.

    Source: §1 · p. 2

  • Method

    The paper establishes approximation algorithms and hardness results by exploiting matroid structure and reductions for OXS and weighted matroid rank rewards.

    Source: §1.1 · p. 3

  • Results

    OXS rewards are APX-complete, weighted matroid rank rewards admit an EPTAS but no randomized FPTAS, partition matroids admit an FPTAS, and ultra rewards have no polynomial-time randomized 2^o(n)-approximation in expectation.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    Approximation guarantees vary substantially across gross-substitutes subclasses, while ultra structure alone gives no subexponential approximation guarantee in the multi-agent model.

    Source: §1.1 · pp. 3–4

    The analysis is scoped to binary-action contracts with binary outcomes and a normalized unit reward upon success.

    Source: §2 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

The paper studies how reward-function structure affects optimal contract approximation in the multi-agent binary-action model, where a principal uses success-contingent payments to induce agents’ effort. It resolves open questions about gross-substitutes rewards and extends the analysis to ultra and submodular rewards, finding sharply different approximation guarantees across these classes.

1 Introduction

  • In the multi-agent binary-action model, the principal offers success-contingent payments to induce effort, and seeks to maximize expected utility at a pure Nash equilibrium.The project’s success probability is determined by the set of agents exerting effort.Source: §1 · pp. 1–2
  • The paper addresses the open question of whether gross-substitutes structure improves on the known constant-factor approximation inherited from submodularity.Additive rewards admit an FPTAS, whereas submodular rewards have a constant-factor approximation but no PTAS.Source: §1 · p. 2

1.1 Our Results

  • OXS rewards make optimal contract design APX-complete, ruling out a PTAS for gross-substitutes rewards unless P = NP.The paper attributes the hardness to marginal contributions that can depend on global reassignment in the matching representation of OXS functions.Source: §1.1 · p. 3
  • Weighted matroid rank rewards admit an EPTAS but no randomized FPTAS, while partition matroids admit an FPTAS.For the positive result, an optimal solution can be chosen as a matroid independent set, where rewards are additive and payments depend only on agent weights; the hardness reduction uses a gap around a prescribed total weight.Source: §1.1 · p. 3
  • Ultra rewards admit no polynomial-time randomized 2^o(n)-approximation in expectation in the multi-agent model, despite polynomial-time tractability for ultra rewards in the related single-agent model.The paper concludes that ultra structure alone gives essentially no approximation guarantee in this multi-agent setting and identifies submodularity as crucial for approximability.Source: §1.1 · p. 4
  • The submodular approximation improves from 258 to 3.287 with value and demand oracles, and from 642.7 to 6.128 with value-oracle access alone.The earlier guarantees are attributed to.Source: §1.1 · p. 4

1.2 Related Work

  • Earlier work established an FPTAS for additive rewards and a constant-factor approximation for submodular rewards, alongside stronger hardness for broader reward classes.The paper situates its results in the multi-agent contract literature initiated for this model by.Source: §1.2 · p. 5
  • The results refine prior multi-agent contract work by distinguishing weighted matroid rank and OXS rewards, incomparable subclasses of gross substitutes with different approximation guarantees.The related-work discussion also contrasts the binary-action partition-matroid FPTAS with the lack of a PTAS for unweighted partition matroid rank functions in the multi-agent multi-action setting.Source: §1.2 · pp. 5–6

2 Model and Preliminaries

The section defines the binary-action contract model and reduces optimal contract design to choosing an incentivizable team of agents. It also establishes the reward-function and approximation concepts used in the paper.

Model and Preliminaries

  • The principal delegates a binary-outcome project to agents who choose effort or shirking, with success probability given by a normalized, monotone reward function f.An action profile is identified with the set of agents exerting effort; f(∅) = 0 and f(S) ≤ f(T) whenever S ⊆ T.Source: §2 · p. 6
  • With success-contingent linear contracts, agent i’s minimum payment share for effort in team S is ci/fi(S), and the principal’s optimal utility for S is captured by g(S).The optimization reduces to finding an incentivizable set maximizing g(S); a positive-cost agent with zero marginal contribution makes g(S) = −∞.Source: §2 · pp. 6–7
  • The reward function may be accessed through value or demand queries, and value and demand oracles are polynomially equivalent for ultra functions and their subclasses.For monotone functions, value queries can be implemented using polynomially many demand queries, but the converse does not generally hold.Source: §2 · p. 7
  • The paper distinguishes additive, weighted matroid rank, OXS, gross-substitutes, ultra, and submodular rewards by their structural properties.OXS functions are represented by maximum-weight matching; GS functions satisfy an exchange condition, ultra functions a related exchange condition, and submodular functions have diminishing marginal contributions; for monotone functions, GS = Submodular ∩ Ultra.Source: §2 · p. 7
  • Approximation schemes are distinguished by their running times: PTAS permits an ε-dependent polynomial exponent, EPTAS has an ε-dependent factor, and FPTAS is polynomial in both input size and 1/ε.A γ-approximation achieves at least OPT/γ, and a constant-factor guarantee uses a constant γ independent of input size.Source: §2 · p. 8

3 No PTAS for Gross Substitutes Rewards

The paper proves that optimal contract design is APX-complete even for explicitly represented OXS rewards, ruling out a PTAS for gross-substitutes rewards unless P = NP. Its reduction encodes cubic Max-Cut through OXS matching rewards and shows that arbitrary incentivizable teams can be replaced by assignment sets.

3 No PTAS for Gross Substitutes Rewards

  • Explicitly represented OXS contract design is APX-complete under PTAS reductions, so no PTAS exists for gross-substitutes rewards unless P = NP.OXS is a subclass of gross substitutes, and the result follows from APX-hardness together with membership in APX.Source: §3 · p. 8, §3.3 · p. 11

3.1 From MAX-CUT to Contracts with OXS Rewards

  • The reduction encodes cubic Max-Cut using state agents for vertex assignments and detector agents for clauses, whose marginal contributions make satisfying more clauses costlier to incentivize.An assignment satisfies m − cut(ρ) clauses, so minimizing detector payments corresponds to maximizing the cut.Source: §3 · p. 8, §3.1 · p. 9

3.2 Assignment Sets

  • Among assignment sets, the principal’s utility increases with the size of the encoded cut.Each assignment set is incentivizable; its utility follows from the state-agent and detector marginal contributions in the matching construction.Source: §3.2 · pp. 9–10
  • Every incentivizable team can be converted in polynomial time to an assignment set with at least as much principal utility.Cubicity bounds the payment increases from filling unoccupied vertex slots, and the construction’s small η makes the reward gain cover those increases.Source: §3.2 · pp. 10–11

3.3 Putting It All Together

  • A (1 − ηε/24)-approximate OXS contract solution yields a (1 − ε)-approximate cut, establishing the PTAS reduction from cubic Max-Cut.Cubic Max-Cut is APX-complete, completing the hardness argument.Source: §3.3 · p. 11

4 Weighted Matroid Rank Function (WMRF) Rewards

This section studies optimal contract design for WMRF rewards, establishing an EPTAS and showing that no randomized FPTAS exists, while partition matroids admit an FPTAS. It also shows that an optimal solution can be chosen independent and describes a dynamic program for the partition case.

4 Weighted Matroid Rank Function (WMRF) Rewards

  • For every incentivizable set, an independent subset has the same reward and weakly greater principal utility, so an optimal solution exists among independent sets.Source: §4 · p. 12

4.1 An EPTAS for WMRF Rewards

  • WMRF optimal contract design admits an EPTAS under value-oracle access, using a geometric grid of payment budgets and a BMIS approximation.The grid is polynomially sized because either a singleton is nearly optimal or the optimal residual share is bounded away from zero.Source: §4.1 · pp. 12–13

Putting it all together.

  • The EPTAS checks the empty set and all singletons, then runs BMIS approximation across geometric residual-share budgets in time h'(1/ε)·L^O(1).The resulting contract achieves at least (1 − ε) times the optimal utility.Source: Putting it all together · pp. 13–14

4.2 No FPTAS for WMRF Rewards

  • No randomized FPTAS exists for WMRF contract design, even with demand-oracle access; a reduction from Exact Matroid Basis would distinguish its yes- and no-instances.The reduction constructs an instance with OPT = 1/4 for a yes-instance and a strictly smaller upper bound for a no-instance.Source: §4.2 · pp. 14–17

4.3 FPTAS for WMRF Rewards with Partition Matroids

  • For partition-matroid WMRF rewards, optimal contract design admits an FPTAS under value-oracle access.The algorithm recovers an equivalent partition representation using O(n^2) independence queries, hence O(n^2) value queries.Source: §4.3 · pp. 17–18
  • For each guess, the dynamic program processes matroid blocks and tracks the minimum t(S) for each rounded total weight and current-block cardinality.Back pointers recover a corresponding independent set, and the algorithm evaluates recovered sets using true utility.Source: §4.3 · p. 18
  • Choosing the largest weight in an optimal set as the guess retains that set, and the recovered set at its total weight has no greater t(S).The proof then compares the recovered set's utility with the optimum using the rounded-weight definition.Source: §4.3 · pp. 18–19
  • With at most n guesses, the transitions and block initializations fit within the same bound, giving total running time O(n^2 r^3/ε), including backtracking and evaluation of recovered sets.Source: §4.3 · p. 19

5 Ultra Rewards

The paper constructs ultra reward functions that are hard to optimize with polynomially many value queries. A hidden set determines the only positive-utility outputs, making it difficult to identify and yielding a no-subexponential-approximation result.

5 Ultra Rewards

  • No randomized algorithm using polynomially many value or demand queries achieves a 2^o(n)-approximation in expectation for ultra rewards.The result follows from a family with a hidden set and a bound on how often polynomially many value queries can identify it.Source: §5 · p. 19, §5.4 · p. 23

5.1 The Hard Family

  • A single downward perturbation of a cardinality-based valuation at a hidden set preserves the ultra property.The construction defines f_T by changing only the value at T; the paper verifies that f_T is normalized, monotone, and ultra.Source: §5 · p. 19, §5.1 · p. 20, §5.3 · p. 22

5.2 The Optimal Sets

  • With equal agent costs, the only positive-utility sets are T ∪ {x} for x outside T, and each has the same optimal utility G.Every other set has nonpositive utility.Source: §5.2 · pp. 21–22

5.3 Negligible Probability of Identifying the Hidden Set

  • Value queries reveal only cardinality unless the queried set is exactly T, so finding a positive-utility output requires querying the hidden set.The construction's value agrees with its cardinality profile on every set except T; the query argument shows positive utility implies that T was queried.Source: §5.3 · pp. 22–23

5.4 Putting It Together

  • Yao’s principle yields an instance where every randomized algorithm with polynomially many value queries obtains only a 2^-Ω(n) fraction of optimal utility in expectation.A 2^o(n)-approximation would require a 2^-o(n) fraction, contradicting this bound.Source: §5.4 · p. 23

A.1 Utility of Assignment Sets

For each assignment, the corresponding assignment set is incentivizable, and its utility is expressed in terms of the assignment’s cut size.

A.1 Utility of Assignment Sets

  • Every assignment set is incentivizable, and its utility is given by a formula involving the assignment’s cut size.The formula expresses g(Sρ) as a constant term plus a term proportional to cut(ρ).Source: §A.1 · p. 25
  • The selected state agents occupy their vertex slots, while detectors occupy clause slots, giving the matching value f(Sρ)=1.The proof argues that the matching is optimal because the total weight available from all slots is at most 1.Source: §A.1 · p. 25
  • The utility expression follows from the agents’ payment shares and the identity sat(ρ)=m−cut(ρ).The proof uses the marginal contributions of state agents and detectors to compute total payments, then subtracts them from f(Sρ).Source: §A.1 · pp. 25–26

A.2 Assignment Sets Are Without Loss of Generality

Every incentivizable set can be replaced in polynomial time by an assignment set with at least as much principal utility.

A.2 Assignment Sets Are Without Loss of Generality

  • For every incentivizable set S, a polynomial-time procedure computes an assignment ρ whose assignment set has utility at least g(S).The procedure constructs the assignment from a maximum-weight matching between selected agents and slots.Source: §A.2 · pp. 26–27
  • In the matching, selected detectors occupy their own clause slots, while state agents occupy vertex slots or clause slots whose detectors are absent.These matching constraints enable the procedure to choose a state for each vertex.Source: §A.2 · pp. 26–27
  • The procedure bounds the added payment for missing detectors and any increased payments for selected detectors to control the assignment set’s total cost.Increased detector payments are associated with vertices whose slots are unoccupied, and each chosen state satisfies at most three clauses.Source: §A.2 · p. 27

B Deferred Proofs from Section 4

The deferred proof reduces maximization over all sets to maximization over independent sets. A maximum-weight independent subset preserves reward and does not decrease the objective.

B Deferred Proofs from Section 4

C A Constant-Factor Approximation for Submodular Rewards

This section refines a demand-query framework for submodular rewards by accounting for optimal-contract payments when selecting agents and prices. It proves a polynomial-time (3.287 + ε)-approximation with value- and demand-oracle access.

C A Constant-Factor Approximation for Submodular Rewards

  • For gross-substitutes rewards, exact demand queries can be implemented with polynomially many value queries, so the same guarantee holds with value-oracle access alone.Source: C A Constant-Factor Approximation for… · p. 28
  • A polynomial-time (3.287 + ε)-approximation is achievable for submodular rewards with value- and demand-oracle access.The analysis optimizes the light-agent cutoff and guides demand-query prices using the payments in an optimal contract.Source: C A Constant-Factor Approximation for… · p. 28
  • The analysis separates optimal agents into light agents and at most one heavy agent by setting the light-agent threshold to an optimized fraction of total payment.The earlier framework fixed the threshold at 1/2; here it is optimized for the approximation analysis.Source: C A Constant-Factor Approximation for… · pp. 28–29
  • The candidate utility bound compares its utility with the light agents’ reward, while a singleton handles the case f(L) = 0.The scale is chosen using a payment-dependent bound; the threshold choice τ = 0.8442 optimizes the analysis.Source: C A Constant-Factor Approximation for… · pp. 29, 31
  • For each candidate light-agent prefix and scale x, prices p_i = √(c_i x) define a demand set that is reduced along a deletion chain to a candidate with reward closest to x/2.The best singleton is also considered, and a geometric grid approximates the unknown scale.Source: C A Constant-Factor Approximation for… · pp. 29, 32, 33
  • The algorithm enumerates at most n + 1 prefixes and O(ε^-1 log(n + 1)) scales, using polynomially many queries and running in polynomial time.It returns the highest-utility candidate among the constructed sets, singletons, and the empty set.Source: C A Constant-Factor Approximation for… · pp. 32–33

D Extension to Submodular Rewards with Value Queries

The section extends the submodular approximation to value queries by replacing exact demand with approximate demand, then pruning to recover the marginal bounds needed for payment analysis. The resulting polynomial-time guarantee is (6.128 + ε).

D Extension to Submodular Rewards with Value Queries

Loading 2609.34665v1…