One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Basic Information

• Paper ID: 2511.20110
• Title: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
• Authors: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (Tel Aviv University)
• Classification: cs.GT (Game Theory)
• Publication Date/Conference: ITCS 2026 (Preprint version: November 26, 2025)
• Paper Link: https://arxiv.org/abs/2511.20110

Abstract

This paper investigates the design of multi-agent combinatorial action contracts under budget constraints, addressing a broad class of objective functions including profit, reward, and welfare. The main results include: (1) Strong Inapproximability: For submodular reward functions, no randomized polynomial-time algorithm can approximate the optimal budget-feasible value within any finite factor, even with demand oracle access; (2) Positive Results: For gross substitutes reward functions (a strict subclass of submodular functions), there exists a deterministic polynomial-time O(1)-approximation algorithm requiring only value queries; (3) FPTAS: For additive reward functions, an FPTAS exists under arbitrary budgets, which is the first FPTAS in the multi-agent combinatorial action setting. The work provides the first explicit distinction between budgeted and non-budgeted settings and identifies gross substitutability as the tractability boundary.

Research Background and Motivation

1. Research Problem

This paper studies the multi-agent combinatorial action contract design problem, where the core challenge is: when a principal faces budget constraints, how can incentive contracts be designed to induce multiple agents to select appropriate action combinations that optimize the principal's objective (profit, reward, or welfare)?

2. Problem Significance

• Theoretical Importance: Contract theory is a core field in microeconomics; the 2016 Nobel Prize in Economics awarded to Hart and Hölmström underscores its significance
• Practical Value: Widely applicable in modern computational markets, such as:
  • Startups incentivizing engineering teams through equity
  • Crowdsourcing platforms designing task reward mechanisms
  • Contract design in project outsourcing

3. Limitations of Existing Approaches

The literature contains two classes of positive results:

• (i) No budget constraint + Combinatorial actions: DEFK25 provides constant-factor approximation for submodular functions
• (ii) Budget constraint + Binary actions: FGPS25, AHT25 provide constant-factor approximation for submodular functions

However, the approximability of the combination (budget constraint + combinatorial actions) remains unknown.

4. Research Motivation

Key observation: Best-response monotonicity, which holds in the binary action setting, fails under combinatorial actions. When agents can choose action subsets, reducing actions by other agents may cause an agent to also reduce its actions, and this non-monotonicity is the source of complexity.

Core Contributions

1. Inapproximability Theorem (Theorem 3.1):
   • For submodular reward functions, under any budget B ∈ (0,1), no randomized polynomial-time algorithm (even with demand oracle access) can approximate the BEST objective within any finite factor
   • The hardness result is tight: only n-1 agents with binary actions and 1 agent with one additional action are needed
2. Constant-Factor Approximation for Gross Substitutes (Theorem 4.1 & Corollary 4.2):
   • For gross substitutes reward functions, there exists a deterministic polynomial-time O(1)-approximation algorithm
   • Requires only value queries (no demand oracle needed)
   • Applies to arbitrary budgets and all BEST objectives
3. FPTAS for Additive Functions (Theorem 5.1):
   • For additive reward functions, FPTAS exists for profit, reward, and welfare objectives
   • This is the first FPTAS in the multi-agent combinatorial action setting (even without budget constraints)
4. Theoretical Separation:
   • First explicit distinction between budgeted and non-budgeted settings in combinatorial contracts
   • First distinction between submodular and gross substitutes functions in budgeted contracts

Methodology Details

Problem Definition

Instance: ⟨A, {Ti}i∈A, f, c⟩

• A: Set of n agents
• Ti: Set of available actions for agent i; agents can choose any subset Si ⊆ Ti
• f: 2^T → 0,1: Reward function mapping action combinations to success probability
• c = {cj}j∈T: Action cost vector

Contract: α = (α1,...,αn) ∈ 0,1^n, where αi is the fraction of project success payment to agent i

Budget Constraint: ∑i∈A αi ≤ B

Objective: Find a budget-feasible contract α and Nash equilibrium S that maximize objective function φ(α,S), where φ belongs to the BEST objective class:

• Profit: uP(α,S) = (1 - ∑αi)f(S)
• Reward: f(S)
• Welfare: f(S) - c(S)

Inapproximability Construction (Section 3)

Core Idea

Construct a parameterized instance family I(A'), where A' ⊆ n and |A'| = n/2:

Agent Setup:

• n agents with binary actions (action i or no action)
• 1 special agent (n+1) with two actions: G ("good") and B ("bad")

Reward Function Design: f^(A')(S) = f1(S) + f2(S) - f3(S,A'), where:

f1(S) = max(1/2 · 1[G∈S], ε · 1[B∈S])
f2(S) = ε · min(|S\{G}|, n/2+1)
f3(S,A') = (ε/2) · 1[S = {B}∪A']

Parameter Choice: ε < min((1-B)/(K(n)·(n+4)), 4n/B)

Key Properties

1. f^(A') is submodular (Lemma 3.4): Verified through monotonicity and submodularity checks
2. Demand queries simulable by value queries (Lemma 3.5): Any demand query computable with 12 value queries
3. Existence of good equilibrium (Lemma 3.6): There exists a budget-feasible contract incentivizing A'∪{G} with reward ≥ 1/2
4. Other equilibria have low reward (Lemma 3.7): For any budget-feasible equilibrium S ≠ A'∪{G}, f(S) ≤ (n/2+2)ε

Proof Strategy

Step 1: Prove that achieving good approximation requires incentivizing G

• Sets containing G: f(S) ≥ 1/2
• Sets not containing G: f(S) ≤ (n/2+2)ε ≈ 0

Step 2: Prove that incentivizing G requires simultaneously incentivizing exactly A'

• Via the f3 term, the marginal reward of B decreases when S-{n+1} = A'
• Budget constraint ensures only incentivizing the correct n/2 agents allows incentivizing G

Step 3: Information-theoretic lower bound

• There are (n choose n/2) = 2^Ω(n) candidate sets A'
• Polynomial-query algorithms cannot identify A' with non-negligible probability
• Apply Yao's principle: For uniform distribution over A', any deterministic algorithm has poor expected performance

Positive Results for Gross Substitutes (Section 4)

Key Property: Best-Response Monotonicity

Lemma 4.3 (Best-Response Monotonicity): For gross substitutes functions f, if S is an equilibrium for contract α, then for any agent i and S'{-i} ⊆ S{-i}, there exists S'_i ⊇ S_i such that S'i is a best response for i against S'{-i}.

Proof Sketch:

1. Transform best-response problem into demand bundle problem
2. Define price vectors p and q such that:
   • S_i is best response to S_{-i} ⟺ S is demand bundle w.r.t. p
   • S'i is best response to S'{-i} ⟺ S' is demand bundle w.r.t. q
3. Since S'{-i} ⊆ S{-i}, we have p ≤ q (coordinate-wise)
4. Apply gross substitutability: There exists demand bundle S' ⊇ S with S'{-i} = S'{-i}

Dimension Reduction Lemma (Lemma 4.5)

Given (α,S) ∈ C(B) and parameter M ≥ 3, one can find in polynomial time (α',S') ∈ C(B) such that:

• f(S') ≥ f(S)/(2M-2)
• ∑α'_i ≤ (5/M)∑αi or there exists i such that α' = α|_i

Algorithm (Algorithm 2):

1. Identify high-payment agent set Z = {i: αi > p/M}
2. If some i∈Z contributes significantly alone, return single-agent contract
3. Otherwise, partition remaining agents into groups with total payment ≤ p/M each
4. Find group U with sufficient reward
5. Apply doubling lemma (Lemma 2.2) to construct new contract

Equivalence Theorem (Theorem 4.1)

Decomposition Lemma (Lemma 4.8):

Max-φ(B) ≤ 2·Max-Reward-Bounded(B) + max_i Best-Single_i-φ(B)

Reduction Chain:

1. Max-φ(B) → Max-Reward-Bounded(B) (Lemma 4.10)
2. Max-Reward-Bounded(B) → Max-φ(B') (Lemma 4.11)
3. Single-agent problems solvable exactly (Lemma 4.9)

FPTAS for Additive Functions (Section 5)

Dynamic Programming Approach

Discretization:

• Set δ = ε/|T|
• Define f̃(S) = ∑_{a∈S} ⌊f({a})/(δb)⌋(δb)

DP Table Definition:

A^(φ)(j,x) = min_{S,α} {∑αi | f̃(S) ≥ x, S ∈ NE(α), S ⊆ T1∪...∪Tj}

Key Observation (Additive Functions):

• Agent i's best response is a prefix: includes all actions satisfying c_a ≤ αi·f({a})
• DP transition: A^(φ)(j,x) = min_{ℓ} {A(j-1, x-f̃({a1,...,aℓ})) + c_{aℓ}/f({aℓ})}

Approximation Guarantee:

f̃(S*) ≥ (1-ε)f(S*)

Thus the returned contract achieves (1-ε)-approximation.

Experimental Setup

This is a purely theoretical paper with no experimental section. All results are mathematical proofs.

Theoretical Verification Methods

1. Constructive Proofs: Prove inapproximability through explicit hard instance construction
2. Algorithm Design: Provide concrete algorithms (Algorithm 1, 2) with performance guarantees
3. Complexity Analysis: Analyze algorithm time complexity and query complexity

Experimental Results

Not applicable (purely theoretical work)

Related Work

1. Combinatorial Contracts

Binary Action Model:

• BFN06a, BFNW12: Introduce combinatorial agent model
• DEFK23: Constant-factor approximation for XOS functions
• FGPS25, AHT25: Binary actions under budget constraints

Combinatorial Action Model:

• DEFK21: Single-agent combinatorial actions, gross substitutes tractable
• DEFK25: Multi-agent combinatorial actions, O(1)-approximation for submodular (no budget)

2. Linear Contracts

• Car15: Robustness of linear contracts
• DRT19: Approximation guarantees for linear contracts
• DFPS24: Ambiguity proofs

3. Contracts Under Budget Constraints

• HG24: Budget constraints for independent tasks
• DASSTC25: Agent budget constraints
• FGPS25: Equivalence of BEST objectives

4. Advantages of This Work

Conclusions and Discussion

Main Conclusions

1. Three-Dimensional Barrier: Inapproximability only emerges when three attributes coexist:
   • Submodular reward functions
   • Budget constraints
   • Combinatorial actions Any combination of two attributes allows constant-factor approximation (Figure 1)
2. Gross Substitutes Boundary: Gross substitutability is the tractability boundary for budgeted combinatorial contracts
3. Special Nature of Additive Functions: Fully polynomial-time approximation schemes exist

Limitations

1. Tightness of Inapproximability:
   • Requires only n-1 binary agents + 1 agent with 3 actions
   • Construction is highly artificial, possibly uncommon in practice
2. Gross Substitutes Assumption:
   • Stronger than submodularity
   • Many practical applications may not satisfy it
3. BEST Objective Limitation:
   • FPTAS only applies to profit, reward, welfare
   • Does not apply to all BEST objectives
4. Single Budget:
   • Only considers aggregate budget constraint
   • Does not address individual budget constraints

Future Directions

1. Computational Complexity:
   • Does PTAS/FPTAS exist for gross substitutes?
   • Exact complexity of single-agent problems
2. Richer Models:
   • Multi-project settings ACC+25
   • Fairness constraints CCL25b
   • Private information ADT21
3. Learning Perspective:
   • Online contract design ZBY+23
   • Sample complexity DFPS25
4. Empirical Studies:
   • Characterization of function classes in practice
   • Performance of heuristic algorithms

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • First inapproximability result under budget constraints
   • Tight hardness result (minimal hard instance)
   • Complete complexity characterization (Figure 1's triangle)
2. Technical Innovation:
   • Precise characterization of best-response non-monotonicity as hardness source
   • Clever hardness construction: using f3 term to implement "hidden set"
   • Best-response monotonicity proof for gross substitutes
3. Result Completeness:
   • Negative results (inapproximability)
   • Positive results (gross substitutes, additive)
   • Matching algorithms and lower bounds
4. Clear Presentation:
   • Clear motivation (startup example)
   • Clear technical roadmap
   • Figure 1 intuitively presents main results

Weaknesses

1. Practical Considerations:
   • Hardness construction is highly artificial
   • Applicability of gross substitutes assumption in practice not discussed
   • Lacks analysis of real application cases
2. Technical Limitations:
   • FPTAS only applies to subset of BEST objectives
   • Specific constants in constant-factor approximation not provided
   • Single-agent FPTAS requires demand oracle
3. Theoretical Gaps:
   • Intermediate classes between gross substitutes and submodular?
   • Complexity of individual budget constraints
   • Potential for randomized contracts
4. Proof Complexity:
   • Some proofs are highly technical (e.g., Lemma 3.7)
   • Necessity of demand oracle simulation not sufficiently intuitive

Impact

Theoretical Contributions:

• First explicit distinction between budgeted/non-budgeted settings
• Establishes gross substitutability as tractability boundary
• Provides benchmark for future research

Methodological Value:

• Framework for analyzing best-response monotonicity
• Design pattern for dimension reduction lemma
• Hardness construction techniques

Practical Value:

• Guides contract design practice: identify tractable cases
• Warns against oversimplified models
• Provides theoretical bounds for approximation algorithms

Applicable Scenarios

Suitable Applications:

1. Gross Substitutes Scenarios:
   • Teams with complementary skills (different expertise)
   • Resource allocation problems
   • Market design
2. Additive Scenarios:
   • Crowdsourcing independent tasks
   • Simple incentive mechanisms

Unsuitable Applications:

1. Tasks with strong complementarities (violate gross substitutes)
2. Unconstrained budget scenarios (better algorithms available)
3. Scenarios requiring exact solutions

Key References

1. DEFK25 Dütting et al., "Multi-agent combinatorial contracts", SODA 2025
   • Directly extended by this work
2. FGPS25 Feldman et al., "Budget-feasible contracts", EC 2025
   • Budget contracts for binary actions
3. DEFK21 Dütting et al., "Combinatorial contracts", FOCS 2021
   • Foundation for single-agent combinatorial actions
4. Car15 Carroll, "Robustness and linear contracts", AER 2015
   • Theoretical foundation for linear contracts
5. Pae17 Paes Leme, "Gross substitutability: An algorithmic survey", GEB 2017
   • Survey on gross substitutability

Summary

This is a theoretically excellent game theory paper that makes important contributions by precisely characterizing the complexity boundaries of budgeted combinatorial contracts. The paper's core insight is best-response non-monotonicity as the source of complexity, and through tight hardness constructions and matching positive algorithms, it completely characterizes problem tractability. Gross substitutability is established as the tractability boundary for budgeted combinatorial contracts, a finding with significant implications for future research. Despite lacking empirical studies, its theoretical value and methodological contributions make it an important work in algorithmic contract theory.