Combinatorial Contracts Through Demand Types
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917413955567616 |
|---|---|
| author | Baldwin, Elizabeth Duetting, Paul Feldman, Michal Schlesinger, Maya |
| author_facet | Baldwin, Elizabeth Duetting, Paul Feldman, Michal Schlesinger, Maya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15125 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Combinatorial Contracts Through Demand Types Baldwin, Elizabeth Duetting, Paul Feldman, Michal Schlesinger, Maya Computer Science and Game Theory 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. |
| title | Combinatorial Contracts Through Demand Types |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.15125 |