Combinatorial Contracts Through Demand Types

Elizabeth Baldwin; Maya Schlesinger; Michal Feldman; Paul Duetting

arxiv: 2604.15125 · v1 · submitted 2026-04-16 · 💻 cs.GT

Combinatorial Contracts Through Demand Types

Elizabeth Baldwin , Paul Duetting , Michal Feldman , Maya Schlesinger This is my paper

Pith reviewed 2026-05-10 09:32 UTC · model grok-4.3

classification 💻 cs.GT

keywords combinatorial contract designdemand typesall substitutes and complementscritical valueslinear contractsgross substitutessupermodular rewardsvalue queries

0 comments

The pith

The all-substitutes-and-complements class of reward functions admits at most O(n squared) critical values in combinatorial contract design.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a geometric framework that links the combinatorial contract design problem to demand types in consumer theory. It defines the class of all-substitutes-and-complements functions and proves that any such function has at most quadratically many points where the agent's best-response action set changes. This bound directly yields polynomial-time algorithms for finding the optimal linear contract, and it unifies earlier special cases that mixed substitutes with complements. A reader would care because delegation of complex projects to agents now becomes tractable for a wider family of reward structures without enumerating exponentially many action subsets.

Core claim

We develop a unified geometric framework for algorithmic contract design by establishing a fundamental link to the theory of demand types from consumer theory. Under this geometric view, bounding the number of critical values reduces to counting the best-response regions which the contract ray pierces. Leveraging this connection, we introduce the class of All Substitutes and Complements (ASC) functions, and show that it admits at most O(n^2) critical values, strictly generalizing and unifying all previously known classes admitting poly-many critical values. Turning to the demand query aspect, we develop a new technique for efficiently computing a demand query using value queries, which works

What carries the argument

The contract ray through the arrangement of best-response regions induced by an ASC demand type, whose crossings determine the critical values of the linear contract parameter.

If this is right

Optimal linear contracts can be computed in polynomial time for every reward function in the ASC class.
Any prior class known to have polynomially many critical values, such as gross substitutes or supermodular rewards, is now a special case of ASC.
The same geometric counting argument applies to any demand type whose best-response regions admit a quadratic bound on ray crossings.
Demand queries for succinct ASC types can be answered using only value queries, removing the need for an oracle that directly returns demanded bundles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same ray-crossing technique may extend to non-linear contracts if their parameter space can be embedded into a similar low-dimensional arrangement.
If the maximality conjecture holds, then any reward function outside ASC will require super-polynomial time for optimal contract computation under standard complexity assumptions.
One could check whether real-world delegation settings, such as software project incentives, produce reward functions that fall inside or outside the ASC class.

Load-bearing premise

That the demand types arising from ASC reward functions remain succinct enough for the new value-query technique to compute the agent's best response in polynomial time.

What would settle it

An explicit ASC reward function on n actions whose associated contract ray crosses more than c n squared best-response regions for some constant c, or for which the best response cannot be recovered from polynomially many value queries.

Figures

Figures reproduced from arXiv: 2604.15125 by Elizabeth Baldwin, Maya Schlesinger, Michal Feldman, Paul Duetting.

**Figure 2.** Figure 2: The relationship between an auction buyer’s utility and the agent’s best response, for [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: The connection between the auction buyer’s utility at prices [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: Examples of the LIP, when n = 2. Left (f1): f1(∅) = 0, f1({1}) = 2, f1({2}) = 3, f1({1, 2}) = 4. Middle (f2): f2(∅) = 0, f2({1}) = 3, f2({2}) = 3, f2({1, 2}) = 4. Right (f3): f3(∅) = 0, f3({1}) = 1, f3({2}) = 1, f3({1, 2}) = 4 a characterization of possible changes in demand in response to sufficiently small generic price changes. Informally, this characterization is the demand type. We start by stating th… view at source ↗

**Figure 5.** Figure 5: Examples of the linear contract ray relative to the facet-piercing property. The colored [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗

**Figure 6.** Figure 6: A two-item example of the price-space path traced by our demand query algorithm, [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗

**Figure 7.** Figure 7: An illustration of the coverage function construction, with [PITH_FULL_IMAGE:figures/full_fig_p036_7.png] view at source ↗

read the original abstract

In the combinatorial action model of contract design, a principal delegates a complex project to an agent, incentivizing a subset of actions from a ground set of $n$ actions, via a linear contract. Computing the optimal contract is a challenging problem that generally hinges on two factors: (i) the number of "critical values" - values of the linear contract parameter at which the agent's best response changes from one set to another, and (ii) the complexity of the agent's best-response problem (demand query). Prior work has used this approach to devise polynomial-time algorithms for the optimal contract problem under specific reward functions: gross substitutes, supermodular, and ultra. We develop a unified geometric framework for algorithmic contract design by establishing a fundamental link to the theory of demand types from consumer theory. Under this geometric view, bounding the number of critical values reduces to counting the best-response regions which the "contract ray" pierces. Leveraging this connection, we introduce the class of All Substitutes and Complements (ASC) functions, and show that it admits at most $O(n^2)$ critical values, strictly generalizing and unifying all previously known classes admitting poly-many critical values. We conjecture that, under some mild assumptions, ASC is the maximal such class. Turning to the demand query aspect, we develop a new technique for efficiently computing a demand query using value queries, which works in general for "succinct" demand types. Combining these structural and algorithmic results, we obtain polynomial-time algorithms for new classes of reward functions that exhibit substitutes and complements simultaneously.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

ASC unifies the known poly-time contract classes under an O(n²) critical-value bound via demand-type geometry, but the algorithmic extension to new mixed cases depends on whether general ASC functions yield succinct demand types.

read the letter

The main thing here is the geometric unification. By connecting the contract problem to demand types, the authors show that the number of critical values is bounded by how many best-response regions the contract ray hits. For their new ASC class this bound is O(n²), which covers and extends the gross-substitutes, supermodular, and ultra cases from earlier work. They also supply a technique that turns value queries into demand queries for succinct demand types. This combination gives polynomial-time algorithms for some reward functions that have both substitutes and complements. The structural result on critical values looks clean. The geometric counting argument is a nice way to see why the bound holds and why previous classes fit inside ASC. The new examples of tractable mixed functions are the practical payoff. The algorithmic side is less settled. The stress-test note is on point: the poly-time result requires that ASC functions always produce succinct demand types so the query reduction runs fast. The abstract states that they do, but it is not obvious from the high-level description whether this is proven for the whole class or only inherited from the special cases. If succinctness does not hold generally, then the O(n²) bound alone does not give an efficient algorithm for arbitrary ASC rewards. The maximality conjecture is also left conditional on mild assumptions whose content is not detailed in the abstract. This paper is for researchers in algorithmic mechanism design who work on contract design. Anyone following the line of work on gross substitutes and related classes will want to see how ASC fits in and what new functions it makes tractable. It deserves a serious referee. The geometric framework is a genuine new lens, the bound is concrete, and the query technique is useful even if the full scope needs verification in the proofs. I would recommend sending it out for review rather than desk rejecting it.

Referee Report

1 major / 1 minor

Summary. The paper develops a geometric framework linking combinatorial contract design to demand types from consumer theory. It introduces the All Substitutes and Complements (ASC) class of reward functions and proves that ASC admits at most O(n²) critical values by a contract-ray piercing argument that counts best-response regions, strictly generalizing gross substitutes, supermodular, and ultra classes. The paper conjectures that ASC is maximal under mild assumptions, develops a value-query technique for computing demand queries on succinct demand types, and combines the results to obtain polynomial-time algorithms for new classes of reward functions that mix substitutes and complements.

Significance. If the central O(n²) bound and the query technique hold, the work is significant: it unifies prior polynomial-time contract results under a single geometric lens and identifies a broader class with polynomially many critical values. The demand-type connection is a novel bridge that could enable further cross-fertilization between mechanism design and consumer theory. The maximality conjecture, if substantiated, would delineate the precise boundary of tractable contract design.

major comments (1)

[Abstract] Abstract and algorithmic results section: the polynomial-time claim for new classes rests on those classes having succinct demand types to which the value-query technique applies. The manuscript does not derive or prove that general ASC reward functions (as opposed to the special cases already known to be succinct) induce succinct demand types; without this, the algorithmic contribution does not automatically extend to the full ASC class even though the O(n²) structural bound does.

minor comments (1)

[Abstract] Abstract: the phrase 'under some mild assumptions' for the maximality conjecture should be expanded with a precise statement of those assumptions so readers can evaluate the conjecture's scope.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and insightful review. The feedback highlights an important distinction between the structural and algorithmic contributions, which we address below. We believe the geometric framework and O(n²) bound remain intact, and we will clarify the scope of the polynomial-time results.

read point-by-point responses

Referee: [Abstract] Abstract and algorithmic results section: the polynomial-time claim for new classes rests on those classes having succinct demand types to which the value-query technique applies. The manuscript does not derive or prove that general ASC reward functions (as opposed to the special cases already known to be succinct) induce succinct demand types; without this, the algorithmic contribution does not automatically extend to the full ASC class even though the O(n²) structural bound does.

Authors: We agree that the manuscript does not prove (and does not claim) that arbitrary ASC reward functions induce succinct demand types. The O(n²) bound on critical values is established for the full ASC class via the contract-ray piercing argument that counts best-response regions. The polynomial-time algorithms, however, are derived only for explicitly constructed new classes that simultaneously belong to ASC (securing the O(n²) critical values) and admit succinct demand-type representations (to which the value-query technique applies). These new classes are specific mixtures of substitutes and complements that extend the previously known succinct cases (gross substitutes, supermodular, ultra) while preserving succinctness. We will revise the abstract and the algorithmic-results section to state this scope explicitly and remove any potential ambiguity that the algorithmic results extend to general ASC functions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation imports external demand-type geometry and proves O(n^2) bound independently

full rationale

The paper's central structural claim—that ASC functions admit O(n^2) critical values—is established via a geometric contract-ray piercing argument that counts best-response regions in the space of linear contracts. This counting step is independent of the algorithmic component and does not reduce to any fitted parameter or self-referential definition of ASC. The demand-query technique is introduced as a general method applicable to any succinct demand type, with the combination yielding polynomial-time results for ASC instances; no equation or definition in the provided text equates the succinctness property to the ASC definition by construction. The framework explicitly draws the demand-type lens from consumer theory as an external import rather than deriving it from quantities internal to the paper. No self-citation load-bearing steps, ansatz smuggling, or renaming of known results appear. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper imports the existing theory of demand types as background and postulates that ASC functions induce succinct demand types; no free parameters or new invented entities are visible in the abstract.

axioms (1)

domain assumption Demand types arising from ASC reward functions are succinct
Required for the new technique that computes demand queries from value queries.

pith-pipeline@v0.9.0 · 5579 in / 1327 out tokens · 44172 ms · 2026-05-10T09:32:40.694714+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

doi: 10.4230/LIPICS.STACS.2025.50. A. S. Kelso and V. P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483–1504, 1982. doi: 10.2307/1913392. D. Lehmann. Ultra valuations.CoRR, abs/1712.04236, 2017. doi: 10.48550/arXiv.1712.04236. URL https://arxiv.org/abs/1712.04236. P. Milgrom and B. Strulovici. Substitute goods...

work page doi:10.4230/lipics.stacs.2025.50 2025
[2]

doi: 10.1016/J.GEB.2017.10.016. 22 N. Sun and Z. Yang. Equilibria and indivisibilities: Gross substitutes and complements. Econometrica, 74(5):1385–1402, 2006. doi: 10.1111/j.1468-0262.2006.00708.x. R. D. Vuong, S. Dughmi, N. Patel, and A. Prasad. On supermodular contracts and dense subgraphs. In Proc. 35th ACM-SIAM SODA, pages 109–132, 2024. doi: 10.1137...

work page doi:10.1016/j.geb.2017.10.016 2017
[3]

Note that{1} is also demanded

(1, 1, 1) /∈ V (f): Assume towards contradiction that there exists a price vectorp such that ∅ and {1, 2, 3} are demanded. Note that{1} is also demanded

work page
[5]

(1, 1, 0) /∈ V (f): f |{1,2} and f(◦ | 3) are GS

work page
[6]

(1, 0, −1) /∈ V (f): f |{1,3} and f(◦ | 2) are supermodular

work page
[7]

Lemma B.4(Supermodular \( Ultra ∪ GSC))

(0, 1, −1) /∈ V (f): f |{2,3} and f(◦ | 1) are supermodular. Lemma B.4(Supermodular \( Ultra ∪ GSC)). There exists a set functionf : 2[3] → R≥0 which is supermodular, but is not ultra or GSC. Proof. Consider the functionf : 2[3] → R≥0 defined by f(S) = ( |S|2 if S ̸= {2, 3} |S|2 + 0.01 else. Clearly f is supermodular. To see that it is not ultra, we takeS...

work page
[8]

Note that{1} is also demanded

(1, 1, 1) /∈ V (f) : Assume towards contradiction that there exists a price vectorp such that ∅ and {1, 2, 3} are demanded. Note that{1} is also demanded

work page
[9]

/∈ V (f): Assume towards contradiction that there exists a price vector p such that {i} and [3] \ {i} are demanded

Let i ∈ [3], ( 1 j ̸= i −1 j = i. /∈ V (f): Assume towards contradiction that there exists a price vector p such that {i} and [3] \ {i} are demanded. Clearly[3] is also demanded

work page
[10]

(1, 1, 0) /∈ V (f): f |{1,2} and f(◦ | 3) are additive

work page
[11]

(1, 0, −1) /∈ V (f): f |{1,3} and f(◦ | 2) are additive

work page
[12]

Lemma B.6 (( Ultra ∩ Supermodular )\ GSC)

(0, 1, −1) /∈ V (f): f |{2,3} and f(◦ | 1) are supermodular. Lemma B.6 (( Ultra ∩ Supermodular )\ GSC). There exists a set function f : 2 [3] → R≥0 which is ultra and supermodular, but is not GSC. Proof. Consider the set functionf : 2[3] → R≥0 defined byf(S) = |S|2. Because it is symmetric, it must be ultra (as was observed in Lehmann [2017]). Additionall...

work page 2017
[13]

This is in contrast to Baldwin and Klemperer [2019], where the demand type is always non-empty

In our setting, the demand type defined by a demand coverV is empty unlessV contains ei for all i ∈ [n]. This is in contrast to Baldwin and Klemperer [2019], where the demand type is always non-empty. (see Lemma C.1)

work page 2019
[14]

redundant

In our setting, different demand covers can lead to the same demand type (see Lemma C.2), in contrast to the more general setting of Baldwin and Klemperer [2019] where this cannot happen. In our setting this can happen because some vectorv in the demand cover may be “redundant” i.e., there exists no functionf of that demand type withv ∈ V (f). Since we’re...

work page 2019
[15]

(Costly 1-substitution) there existb < a ∈ [n] such thatSi \Si−1 = {a} and Si−1 \Si = {b}

work page
[16]

binary counter

(Costly 2-substitution) there existsa ∈ [n] and b, c, d < a such that Si \ Si−1 = {a, b} and Si−1 \ Si = {c, d}. Proof. Before defining S1, . . . , Sk, we define T0, . . . , Tm−1, such that m ≥ √ 2 √n , and c(T0) < · · · < c (Tm−1) but the transition property in Lemma F.2 doesn’t necessarily hold. We then add intermediate sets in between the setsTi, to ac...

work page

[1] [1]

doi: 10.4230/LIPICS.STACS.2025.50. A. S. Kelso and V. P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483–1504, 1982. doi: 10.2307/1913392. D. Lehmann. Ultra valuations.CoRR, abs/1712.04236, 2017. doi: 10.48550/arXiv.1712.04236. URL https://arxiv.org/abs/1712.04236. P. Milgrom and B. Strulovici. Substitute goods...

work page doi:10.4230/lipics.stacs.2025.50 2025

[2] [2]

doi: 10.1016/J.GEB.2017.10.016. 22 N. Sun and Z. Yang. Equilibria and indivisibilities: Gross substitutes and complements. Econometrica, 74(5):1385–1402, 2006. doi: 10.1111/j.1468-0262.2006.00708.x. R. D. Vuong, S. Dughmi, N. Patel, and A. Prasad. On supermodular contracts and dense subgraphs. In Proc. 35th ACM-SIAM SODA, pages 109–132, 2024. doi: 10.1137...

work page doi:10.1016/j.geb.2017.10.016 2017

[3] [3]

Note that{1} is also demanded

(1, 1, 1) /∈ V (f): Assume towards contradiction that there exists a price vectorp such that ∅ and {1, 2, 3} are demanded. Note that{1} is also demanded

work page

[4] [5]

(1, 1, 0) /∈ V (f): f |{1,2} and f(◦ | 3) are GS

work page

[5] [6]

(1, 0, −1) /∈ V (f): f |{1,3} and f(◦ | 2) are supermodular

work page

[6] [7]

Lemma B.4(Supermodular \( Ultra ∪ GSC))

(0, 1, −1) /∈ V (f): f |{2,3} and f(◦ | 1) are supermodular. Lemma B.4(Supermodular \( Ultra ∪ GSC)). There exists a set functionf : 2[3] → R≥0 which is supermodular, but is not ultra or GSC. Proof. Consider the functionf : 2[3] → R≥0 defined by f(S) = ( |S|2 if S ̸= {2, 3} |S|2 + 0.01 else. Clearly f is supermodular. To see that it is not ultra, we takeS...

work page

[7] [8]

Note that{1} is also demanded

(1, 1, 1) /∈ V (f) : Assume towards contradiction that there exists a price vectorp such that ∅ and {1, 2, 3} are demanded. Note that{1} is also demanded

work page

[8] [9]

/∈ V (f): Assume towards contradiction that there exists a price vector p such that {i} and [3] \ {i} are demanded

Let i ∈ [3], ( 1 j ̸= i −1 j = i. /∈ V (f): Assume towards contradiction that there exists a price vector p such that {i} and [3] \ {i} are demanded. Clearly[3] is also demanded

work page

[9] [10]

(1, 1, 0) /∈ V (f): f |{1,2} and f(◦ | 3) are additive

work page

[10] [11]

(1, 0, −1) /∈ V (f): f |{1,3} and f(◦ | 2) are additive

work page

[11] [12]

Lemma B.6 (( Ultra ∩ Supermodular )\ GSC)

(0, 1, −1) /∈ V (f): f |{2,3} and f(◦ | 1) are supermodular. Lemma B.6 (( Ultra ∩ Supermodular )\ GSC). There exists a set function f : 2 [3] → R≥0 which is ultra and supermodular, but is not GSC. Proof. Consider the set functionf : 2[3] → R≥0 defined byf(S) = |S|2. Because it is symmetric, it must be ultra (as was observed in Lehmann [2017]). Additionall...

work page 2017

[12] [13]

This is in contrast to Baldwin and Klemperer [2019], where the demand type is always non-empty

In our setting, the demand type defined by a demand coverV is empty unlessV contains ei for all i ∈ [n]. This is in contrast to Baldwin and Klemperer [2019], where the demand type is always non-empty. (see Lemma C.1)

work page 2019

[13] [14]

redundant

In our setting, different demand covers can lead to the same demand type (see Lemma C.2), in contrast to the more general setting of Baldwin and Klemperer [2019] where this cannot happen. In our setting this can happen because some vectorv in the demand cover may be “redundant” i.e., there exists no functionf of that demand type withv ∈ V (f). Since we’re...

work page 2019

[14] [15]

(Costly 1-substitution) there existb < a ∈ [n] such thatSi \Si−1 = {a} and Si−1 \Si = {b}

work page

[15] [16]

binary counter

(Costly 2-substitution) there existsa ∈ [n] and b, c, d < a such that Si \ Si−1 = {a, b} and Si−1 \ Si = {c, d}. Proof. Before defining S1, . . . , Sk, we define T0, . . . , Tm−1, such that m ≥ √ 2 √n , and c(T0) < · · · < c (Tm−1) but the transition property in Lemma F.2 doesn’t necessarily hold. We then add intermediate sets in between the setsTi, to ac...

work page