When Contracts Get Complex: Information-Theoretic Barriers

Basic Information

• Paper ID: 2403.09794
• Title: When Contracts Get Complex: Information-Theoretic Barriers
• Authors: Paul Dütting (Google Research), Michal Feldman (Tel Aviv University), Yoav Gal-Tzur (Tel Aviv University), Aviad Rubinstein (Stanford University)
• Classification: cs.GT (Game Theory)
• Publication Time/Venue: SODA 2026 (Full version dated November 27, 2025)
• Paper Link: https://arxiv.org/abs/2403.09794

Abstract

This paper investigates information-theoretic barriers in the combinatorial-action contract model. In this model, a principal delegates a complex project to an agent who can choose any subset of actions. Each action set incurs a cost for the agent (represented by set function c) and generates expected revenue for the principal (represented by set function f). The paper proves that even with demand queries, finding optimal contracts requires exponential query complexity when f is submodular and c is additive, thereby negatively answering a fundamental open question in the field. The research further extends results to different combinations of submodular/supermodular f and c, and establishes exponential lower bounds under the communication complexity model.

Research Background and Motivation

Problem Definition

The core problem studied in this paper is combinatorial-action contract design:

• A principal must design a contract to incentivize an agent to execute a complex project
• The agent can choose any subset S from n actions
• Choosing action set S incurs cost c(S) and success probability f(S)
• The contract specifies payment α upon success; the principal aims to maximize their own utility

Problem Significance

1. Theoretical Importance: Contract design is a cornerstone of economic theory (the 2016 Nobel Prize in Economics was awarded to Hart and Holmström), with the hidden-action principal-agent model as its foundation
2. Computational Complexity: Combinatorial functions typically require exponential bits to represent, necessitating query-based access
3. Fundamental Open Question: After the model was proposed at FOCS'21, a core unresolved question emerged: Can demand queries make the problem tractable?

Limitations of Existing Approaches

• Known Positive Results:
  • When f exhibits gross-substitutes, solvable with polynomial value queries
  • When f is supermodular and c is submodular, solvable with polynomial value queries
• Known Negative Results:
  • No constant approximation with value queries for submodular f and additive c (EFS24)
  • Computing optimal contracts is NP-hard
• Critical Gap: Can demand queries overcome the limitations of value queries?

Research Motivation

Demand queries have natural economic interpretations and are more powerful than value queries (a single demand query can return the action set maximizing agent utility). Determining the capability boundaries of demand queries is crucial for understanding the inherent complexity of combinatorial contract problems.

Core Contributions

The main contributions of this paper include:

1. Demand Query Hardness (Main Result 1): Proves that for submodular f and additive c, any algorithm computing optimal contracts requires exponential demand queries, thereby negatively answering the open question from FOCS'21
2. Supply Query Hardness: Dually, proves that additive f and supermodular c require exponential supply queries
3. Communication Complexity Lower Bounds (Main Result 2): In the communication model where f and c are held by two parties, computing optimal contracts requires exponential communication even with polynomial best-response queries:
   • Submodular f and submodular c
   • Supermodular f and supermodular c
   • Submodular f and supermodular c
4. Novel Technical Framework: Introduces two key properties as black-box tools for establishing lower bounds:
   • Equal-Revenue Construction: Exponentially many distinct contracts are all optimal
   • Sparse Demand: For any price vector, the number of approximately optimal sets is polynomial
5. Tightness: All lower bound results are tight when instance representation size is poly(n), matching known FPTAS algorithms

Methodology Details

Task Definition

Optimal Contract Problem (Definition 1):

• Input: Triple ⟨n, f, c⟩
  • n: number of actions
  • f: 2^n → 0,1 (reward/success probability function)
  • c: 2^n → ℝ≥0 (cost function)
• Output: Optimal contract α* ∈ 0,1, maximizing principal utility
  • Agent utility: u_a(α, S) = αf(S) - c(S)
  • Principal utility: u_p(α, S) = (1-α)f(S)
  • Agent chooses S_α = argmax_S u_a(α, S)
  • Optimal contract: α* = argmax_α u_p(α, S_α)

Query Models:

1. Value Query: Input set S, return f(S) or c(S)
2. Demand Query: Input price vector p, return argmax_S(f(S) - Σp_i)
3. Supply Query: Input price vector p, return argmax_S(Σp_i - c(S))
4. Best-Response Query: Input contract α, return argmax_S(αf(S) - c(S))

Core Technical Framework

The proof is built on three layers of construction:

Layer One: Equal-Revenue Construction (Section 3)

Definition (Definition 5): Instance ⟨n, f, c⟩ is equal-revenue if:

1. Every non-empty set can be incentivized
2. There exist 2^n-1 distinct optimal contracts {α_t}, each yielding the same utility to the principal

Construction Method (Theorem 1 - Submodular f and Additive c):

• Set costs: c_i = 2^(i-1), so that c(S_t) = t (where t is the binary representation of S)
• Define recursively: α_0 = 0, α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1)
• Define rewards: f_t = f(S_t) = 1/(1-α_t)

Key Properties:

• Lemma 1: α_t is strictly increasing and α_t < 1
• Lemma 2: Discrete derivative f_(t+1) - f_t is decreasing (implies submodularity)
• Proposition 2: f is monotone submodular

The elegance of this construction lies in:

1. Using exponential costs and binary encoding to achieve perfect set indexing
2. The recursive relationship ensures each critical value satisfies the equal-revenue condition
3. Monotonicity of discrete derivatives naturally yields submodularity

Layer Two: Sparse Demand Property (Section 4.3)

Definition (Definition 6): Function f has σ-sparse demand if for any price vector p, the σ-approximate demand set D_{σ,p} = {S | max_T(f(T) - Σp_i) - (f(S) - Σp_i) ≤ σ} has polynomial size in n.

Core Lemma (Lemma 3): Define fuzzy intervals l_i, r_i, where:

• r_i = max{t | S_t ∈ D_{σ,p}, i ∈ S_t}
• l_i = max{r_i - 2^i, 0}

For any S_t ∈ D_{σ,p}:

• If t > r_i, then i ∉ S_t
• If t < l_i, then i ∈ S_t

Proof Strategy:

1. Use equal-revenue property: there exists contract α_{S_t{i}} where marginal reward < marginal cost
2. Therefore p_i < c_i/α_{S_t{i}} + σ
3. For sets S_{t'} with indices far smaller than t, if i ∉ S_{t'}, then p_i makes S_{t'}∪{i} better
4. This creates a "forced inclusion" effect

Counting Argument (Lemma 4):

• Map each approximately optimal set S_t to the smallest action i such that t ∈ l_i, r_i
• Each action i corresponds to at most O(n) sets
• Total of O(n²) approximately optimal sets

Proposition 6: The constructed f has σ-sparse demand (for appropriately small σ)

Layer Three: From Equal-Revenue to Query Hardness

Value Query Hardness (Proposition 5):

• Construct perturbation family I = {⟨n, f_k, c⟩}, where f_k(S_k) = f(S_k) + ε
• Use "hidden special set" argument
• Any deterministic algorithm needs to query 2^(n-1) sets to find the perturbed set
• Expected query complexity ≥ 2^(n-2)

Demand Query Hardness (Theorem 3): Key observation: If the algorithm knows the original f, it can simulate demand queries with poly value queries

• The set returned by demand query for price p must be in approximate demand D_{ε,p}
• D_{ε,p} is independent of f_k's identity, can be precomputed
• Use |D_{ε,p}| ≤ poly(n) value queries to find the optimal set
• Therefore demand queries are not stronger than value queries (at most polynomial factor)
• Demand query lower bound follows from value query lower bound

Communication Complexity Construction (Section 5)

Model: Alice holds f, Bob holds c, both can communicate and access best-response oracle

Construction Steps:

1. Perturb Cost Function (Make c strictly submodular):
   • c̃(S) = c(S) - δ|S|²
   • Choose δ to preserve 2^n-1 critical values
   • Proposition 9: Ĩ = ⟨n, f, c̃⟩ has sparse best-response
2. Add (n+1)-th Action: Parameterize marginal rewards and costs using vectors x_f, x_c ∈ {0,1}^(n choose n/2):

   f̂(n+1 | S_t) = z/4  if |S_t|=n/2 ∧ S_t ∈ x_f
                  0    otherwise (for |S_t|≥n/2)
   
   ĉ(n+1 | S_t) = αt·z/4  if |S_t|=n/2 ∧ S_t ∈ x_c  
                  z/2      otherwise
   

3. Reduction to DISJ:
   • Observation 5: Sets of form S_t∪{n+1} can be incentivized ⟺ |S_t|=n/2 ∧ S_t ∈ x_f∩x_c
   • Proposition 12: If x_f∩x_c ≠ ∅, then optimal contract incentivizes some S_t∪{n+1}
   • Corollary 3: Finding optimal contract requires solving DISJ_{(n choose n/2)}
   • By Fact 1 (KS92, Raz92): DISJ_k requires Ω(k) communication
   • Obtain Ω(2^n/√n) communication lower bound

Key Technical Points:

• Choice of z = min{ϕ_c̃, ψ_c̃, ϕ_f, ψ_f, ζ, σ} ensures submodularity and sparsity
• Careful design of marginal costs ensures only special sets can be incentivized with action n+1
• Proposition 13: Even with best-response oracle, can simulate with poly communication (using sparsity)

Experimental Setup

This is a pure theory paper with no experimental component. All results are established through rigorous mathematical proofs.

Theoretical Verification Methods

1. Construction Verification: Verify equal-revenue construction properties through mathematical induction and inequality proofs
2. Lower Bound Proofs: Use information-theoretic arguments (Yao's minimax principle) and reduction techniques
3. Tightness Analysis: Compare with known algorithmic upper bounds (FPTAS)

Experimental Results

Main Theoretical Results

Table 1 Summary:

Where:

• Demand/Supply Query Hardness: Requires exp(n) queries
• CC+BR Hardness: Requires Ω(2^n/√n) communication (even with poly best-response queries)
• Polynomial Time: Efficient algorithms exist (DFG24)

Key Theorem Statements

Theorem 2 (Demand Query Hardness): When f is submodular and c is additive, any algorithm computing optimal contracts requires exponential demand queries.

Theorem 4 (Communication Complexity - Submodular f and c): When both f and c are submodular, computing optimal contracts requires Ω(2^n/√n) bits of communication even with poly(n) best-response queries.

Theorem 8 (Supply Query Hardness): When f is additive and c is supermodular, any algorithm computing optimal contracts requires exponential supply queries.

Theorems 10, 11 (Communication Complexity for Other Combinations):

• Submodular f and supermodular c: Ω(2^n/√n) communication
• Supermodular f and supermodular c: Ω(2^n/√n) communication

Tightness Results

1. Matching FPTAS: DEFK21's FPTAS runs in polynomial time when instances are represented in poly(n) bits. This paper's hard instances can also be represented in poly(n) bits (Appendix H), so the lower bounds are tight.
2. Tractability of Subadditive Costs: Appendix B observes that DEFK25's FPTAS extends to subadditive c, so results are also tight in this generalized model.

Technical Highlights

1. Universality of Equal-Revenue Construction: The same construction technique applies to:
   • Submodular f + Additive c (Section 3)
   • Additive f + Supermodular c (Appendix D)
2. Robustness of Sparse Demand:
   • Preserved under perturbations (Proposition 9)
   • Extends to sparse best-response (Definition 10)
3. Modular Proof Structure:
   • Equal-revenue → Value query hardness (black-box)
   • Equal-revenue + Sparse demand → Demand query hardness (black-box)
   • Perturbation + Add action → Communication complexity hardness (black-box)

Related Work

Combinatorial Contract Design

1. DEFK21 (FOCS'21):
   • Proposed combinatorial-action contract model
   • Gross-substitutes f solvable with polynomial value queries
   • Submodular f is NP-hard
   • Posed open question on demand query tractability
2. EFS24 (ITCS'24):
   • Proved no constant approximation with value queries (assuming P≠NP)
   • This paper strengthens to information-theoretic lower bounds for demand queries
3. DFG24 (SODA'24):
   • Supermodular f + Submodular c solvable with polynomial value queries
   • This paper proves other combinations are hard
4. DEFK25 (SODA'25):
   • Strongly polynomial FPTAS for monotone f + Additive c
   • Extends to subadditive c (this paper's Appendix B)

Multi-Agent Contracts

1. BFN06a, BFNW12: Multi-agent + Boolean functions
2. DEFK23: Multi-agent + XOS rewards with constant approximation
3. DDPP24: Approximation hardness for supermodular rewards

Query and Communication Complexity

1. NS06: Communication requirements in mechanism design
2. Dob11: Impossibility for submodular valuations
3. EFN+19: Communication complexity in combinatorial auctions

This paper is the first to establish communication complexity results in the contract literature.

Other Contract Directions

• Simple vs optimal contracts (Car15, DRT19)
• Online learning (HSV14, ZBY+23)
• Typed agents (GSW21, CMG22)
• Information design (BTCXZ24)

Conclusions and Discussion

Main Conclusions

1. Answering Open Question: Demand queries cannot make contract design tractable for submodular f + additive c; there exist fundamental information-theoretic barriers
2. Complete Characterization: Except for (supermodular f, submodular c) and (additive f, additive c), all submodular/supermodular combinations face:
   • Query complexity barriers (when one function is additive)
   • Communication complexity barriers (when both functions are combined)
3. Technical Contributions: Equal-revenue construction and sparse demand property provide general tools for studying complexity of combinatorial contracts

Limitations

1. Open Questions:
   • Does supermodular c (even with additive f) allow approximation? (Marked open in Table 1)
   • Communication complexity for strict subclasses (e.g., XOS, gross-substitutes)?
2. Model Assumptions:
   • Linear contracts (though known optimal in many cases)
   • Binary outcomes (success/failure)
   • Single-agent setting
3. Representation Size:
   • Main results assume O(1) space representation
   • Appendix H extends to poly(n) bits
   • Unbounded representation model might be easier for some problems

Future Directions

1. Complexity of Strict Subclasses:
   • Gap between gross-substitutes (known tractable) and general submodular
   • Ultra functions (FY25 recently extended tractability boundaries)
2. Approximation Algorithms:
   • Approximation possibilities for supermodular c
   • Better characterization of approximation ratios
3. Refined Communication Models:
   • Capabilities of different communication protocols
   • Necessity of best-response oracle
4. Multi-Agent Extensions:
   • Can techniques extend to multi-agent settings?
   • DEFK25 has preliminary results
5. Practical Algorithms:
   • Despite worst-case hardness, do instance-dependent efficient algorithms exist?
   • Smoothed analysis or average-case complexity

In-Depth Evaluation

Strengths

1. Major Theoretical Breakthrough:
   • Resolves core open question from FOCS'21
   • Establishes first communication complexity results in this field
   • Provides nearly complete complexity characterization (Table 1)
2. Technical Innovation:
   • Equal-revenue construction cleverly uses exponential costs and recursion
   • Sparse demand property discovery and proof are highly insightful (Lemma 3's "forced inclusion" argument)
   • Modular framework allows black-box application to different settings
3. Elegance of Proofs:
   • Recursive relation α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1) naturally yields all properties
   • Binary encoding achieves perfect indexing
   • DISJ reduction construction is remarkably clever
4. Completeness of Results:
   • Covers all submodular/supermodular combinations
   • Considers both query and communication models
   • Tightness analysis (matches FPTAS)
   • Extension to poly(n) bit representation (Appendix H)
5. Writing Quality:
   • Clear structure, progressing from simple to complex
   • Technical overview (Section 1.2) very helpful
   • Extensive appendices provide complete proofs

Weaknesses

1. Technical Limitations:
   • Approximation for supermodular c remains unresolved (explicitly marked open)
   • Counting argument for sparse demand, while correct, is quite technical with limited direct intuition
   • Rounding analysis for poly(n) bit representation (Appendix H) is lengthy and technical
2. Practical Considerations:
   • Pure theory results without practical applications discussed
   • Worst-case bounds; actual instances may be easier
   • No exploration of heuristics or approximation schemes
3. Scope Limitations:
   • Only linear contracts considered
   • Single-agent setting
   • No fine-grained analysis of other function classes (XOS, subadditive)
4. Presentation Details:
   • Some proofs (e.g., Lemma 2) involve tedious algebraic manipulations
   • Communication model motivation could be more thorough (why separate f and c?)

Impact

1. Theoretical Impact:
   • Establishes complexity boundaries for combinatorial contract design
   • Equal-revenue and sparse demand likely become standard tools for other contract problems
   • Opens new direction for communication complexity applications in contract theory
2. Inspiration for Future Research:
   • Clarifies need to find new structural properties or restrictions for tractability
   • Highlights importance of studying strict subclasses
   • Provides systematic method for constructing hard instances
3. Methodological Contributions:
   • Shows how to combine equal-revenue construction with sparsity
   • Technique of adding single action from semi-combinatorial to full combinatorial
   • Connects information-theoretic lower bounds with computational complexity
4. Reproducibility:
   • All proofs are constructive
   • Hard instances can be explicitly constructed
   • Theory results require no experimental validation

Applicable Scenarios

1. Theoretical Research:
   • Complexity lower bounds in algorithmic game theory
   • Computability boundaries of contract design
   • Query and communication complexity studies
2. Algorithm Design Guidance:
   • Clarifies which cases need approximation algorithms
   • Guides heuristic method design
   • Identifies scenarios requiring additional structural assumptions
3. Economic Theory:
   • Understands information's role in contract design
   • Computational perspective on principal-agent problems
   • Information costs of incentive design
4. Practical Implications:
   • Even seemingly simple submodular+additive cases may have hard optimal contracts
   • Need to balance optimality with computability
   • Simple contracts may be preferable in practice

Technical Depth Analysis

Mathematical Beauty of Equal-Revenue Construction

The recursive relation derivation demonstrates profound mathematical insight:

From equal-revenue condition (1-α_t)f_t = 1 and critical value condition α_(t+1) = 1/(f_(t+1)-f_t), we obtain:

α_(t+1) = (1-α_(t+1))(1-α_t)/(α_(t+1)-α_t)

This equation's solution has elegant properties:

• Generates strictly increasing sequence
• Automatically satisfies α_t < 1
• Derived f_t is naturally submodular

Combinatorial Argument for Sparse Demand

Lemma 4's proof uses sophisticated combinatorial reasoning:

1. Define minimal fuzzy action m(S_t) = min{i | t ∈ l_i, r_i}
2. Observe that for fixed i*, sets with m(S_t) = i* form a "chain": (S_t1 ∩ i*-1) ⊇ ... ⊇ (S_tk ∩ i*-1)
3. Chain length ≤ i*, so total ≤ Σi* · 4i* = O(n²) sets

This "chain structure" discovery is key to proving sparsity.

Cleverness of Communication Complexity Reduction

The (n+1)-th action construction carefully designs marginal rewards and costs such that:

• Only "special" sets of size n/2 can be incentivized with action n+1
• Optimality strictly depends on whether x_f ∩ x_c is non-empty
• Simultaneously maintains submodularity and sparse best-response

This construction technique may inspire other communication complexity lower bounds.

Selected References

1. DEFK21 Dütting, Ezra, Feldman, Kesselheim. "Combinatorial Contracts." FOCS 2021. (Original model)
2. EFS24 Ezra, Feldman, Schlesinger. "On the (In)Approximability of Combinatorial Contracts." ITCS 2024. (Value query hardness)
3. DFG24 Dütting, Feldman, Gal-Tzur. "Combinatorial Contracts Beyond Gross Substitutes." SODA 2024. (Positive results)
4. KS92 Kalyanasundaram, Schintger. "The Probabilistic Communication Complexity of Set Intersection." SIDMA 1992. (DISJ lower bound)
5. DRT19 Dütting, Roughgarden, Talgam-Cohen. "Simple versus Optimal Contracts." EC 2019. (Simple contracts)

Overall Assessment: This is an outstanding theoretical paper that resolves the core open question in combinatorial contract design by introducing novel technical tools (equal-revenue construction and sparse demand), and establishes the field's first communication complexity results. The technical depth, result completeness, and writing clarity all meet top-tier standards. While purely theoretical, the established complexity boundaries provide crucial guidance for future research in this area. Main limitations are the unresolved approximation question for supermodular costs and lack of practical application discussion, though these are explicitly marked as future directions.