Source-linked AI summary
Approximating Combinatorial Contracts with Arbitrary Costs
Xiaotie Deng, Hanyu Li, Chenghua Liu
TL;DR
Exact optimization can require exponentially many supply queries, while prior approximation methods’ cost-based scale certificate does not extend to supermodular or arbitrary costs. The algorithm tries singleton rewards as anchors to localize the optimal retained-share scale, then uses geometric search and monotonicity of response reward. For the class in the lower bound of [6], exact optimization requires 2Ω(n) supply queries, whereas a (1 −ε)-approximation requires O(n log(n + 1)/ε) supply queries.
Problem
Exact optimization can require exponentially many supply queries, while prior approximation methods’ cost-based scale certificate does not extend to supermodular or arbitrary costs.
Source: §1 · pp. 2–3Method
The algorithm tries singleton rewards as anchors to localize the optimal retained-share scale, then uses geometric search and monotonicity of response reward.
Source: §1 · p. 4, §4.1 · p. 6Results
Takeaways & Limitations
The representation-independent approximation guarantee extends to normalized monotone subadditive rewards and arbitrary normalized nonnegative costs under best-response and value-query access.
Source: §6 · p. 12Extension to monotone rewards beyond subadditivity remains open because the proof uses subadditivity for both the welfare–profit comparison and singleton-reward localization.
Source: §6 · p. 12
Abstract
from arXiv · showhide
We study single-agent combinatorial contracts under linear payments. Under a reward share $\alpha\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $\alpha f(S)-c(S)$, while the principal receives $(1-\alpha)f(S)$. For nonnegative additive rewards and monotone supermodular costs, D\"utting et al. (SODA 2026) proved an exponential supply-query lower bound for exact optimization and left open whether a representation-independent approximation is possible. We resolve this question in a stronger form, removing all structural assumptions on the cost function: for nonnegative additive rewards, arbitrary normalized nonnegative set costs, and every $\varepsilon\in(0,1)$, we give a deterministic $(1-\varepsilon)$-approximation using $O(n\log(n+1)/\varepsilon)$ supply queries, with query complexity independent of numerical bit lengths and breakpoint separation. More generally, the same guarantee and asymptotic query complexity hold for normalized monotone subadditive rewards and arbitrary normalized nonnegative costs under exact best-response and value-query access. The key idea is a cost-independent, reward-side scale certificate. The algorithm tries all singleton rewards as candidate anchors; one of them brackets the optimal retained share within a factor $n^2$. Geometric search and monotonicity of the induced response reward then yield the approximation without enumerating best-response breakpoints.
1 Introduction
Combinatorial contracts incentivize an agent’s hidden actions through a share of observable reward, while the principal must anticipate the induced response. This paper resolves whether representation-independent approximation is possible beyond structured costs, giving a deterministic approximation with polynomial query complexity and a reward-based scale search.
1 Introduction
- Hidden actions make the principal choose payments based on observable outcomes while anticipating how incentives change the agent’s behavior.In the combinatorial-action model, the agent can choose any subset of n actions, whose rewards may exhibit substitutes or complements.Source: §1 · pp. 1–2
- Dütting et al. [6] showed exact optimization needs 2^Ω(n) supply queries for additive rewards and monotone supermodular costs, leaving representation-independent approximation open.Prior representation-independent approximation methods depended on cost structure: their singleton-cost scale certificate fails for supermodular or arbitrary costs.Source: §1 · pp. 2–3
- For nonnegative additive rewards and arbitrary normalized nonnegative costs, a deterministic (1 − ε)-approximation uses O(n log(n + 1)/ε) supply queries, independent of numerical values and breakpoint separation.The algorithm also uses O(n) reward-value queries and one cost-value query.Source: §1 · p. 3
- For normalized monotone subadditive rewards and arbitrary normalized nonnegative costs, the same approximation guarantee holds with exact best-response and value queries.The query bound is independent of numerical values and breakpoint separation; additivity is needed only to implement best responses using standard supply queries.Source: §1 · p. 3
- Trying all singleton rewards brackets the optimal retained share within a factor n^2, enabling a geometric search that finds a near-optimal contract without enumerating response breakpoints.The approach retains the welfare–guess–search template but replaces the cost anchor with a singleton-reward anchor; follow-up results address additive best-response error and very high accuracy.Source: §1 · p. 4
2 Related work
Prior work established hardness and exact tractability across classes of combinatorial rewards and costs, while representation-independent approximation results depended on restricted settings. This paper retains that approximation guarantee while removing structural assumptions on costs.
2 Related work
- The original combinatorial-action work gave an exact algorithm for gross-substitutes rewards, proved NP-hardness for submodular rewards, and gave a weakly polynomial FPTAS for general monotone rewards and costs.With submodular rewards and additive costs, a constant-factor approximation by a polynomial-time value-query algorithm is impossible unless P = NP [8].Source: §2 · p. 4
- Breakpoint-enumeration algorithms are polynomial in the number of breakpoints and give exact tractability for supermodular rewards and submodular costs [2].The number of breakpoints can make enumeration costly, as noted in the introduction.Source: §2 · p. 5
- Dütting et al. gave a representation-independent FPTAS for general monotone rewards with additive costs, and Dütting et al. [6] extended the approach to subadditive costs and proved an exact lower bound for supermodular costs.The present result retains the representation-independent query bound while removing every structural assumption on cost.Source: §2 · p. 5
- Recent work studies special reward and cost classes [10], demand-type representations [1], and budgeted-variant inapproximability [9], but not the subadditive-reward, arbitrary-cost oracle guarantee proved here.Source: §2 · p. 5
3 Model, objective, and oracle access
The model has an agent choose a subset of hidden actions, producing reward for the principal and incurring cost to the agent. A linear contract shares reward, and oracle access captures the resulting best response and the functions’ values.
3 Model, objective, and oracle access
- The agent chooses a subset S of n hidden actions, generating gross reward f(S) for the principal and cost c(S) for the agent.The principal cannot pay directly for the unobserved actions, so it shares the observable reward instead.Source: §3 · p. 5
- Under share α, the agent maximizes αf(S) − c(S), and the principal keeps 1 − α of the reward, with ties broken toward larger reward.The algorithm seeks a contract whose principal utility is at least (1 − ε) times optimum.Source: §3 · p. 5
- For normalized monotone subadditive rewards and arbitrary normalized nonnegative costs, maximum total surplus W is a scale benchmark, while the principal’s objective remains P(α).At α = 1, a best-response query computes W; exact best-response and value queries provide access without requiring explicit function descriptions.Source: §3 · p. 5
- With additive rewards, a best response at α > 0 is implemented by a standard supply query to costs using item prices p_i = αv_i.The larger-cost tie-breaking convention agrees with principal-favoring tie-breaking.Source: §3 · pp. 5–6
4 Reward-anchored geometric search
The section turns approximation into locating the optimal retained-share scale, then builds a reward-based bracket that supports geometric search despite arbitrary costs.
4.1 From approximation to scale localization
- Because response reward is monotone in agent share, a geometric grid over a polynomial-width bracket finds a near-optimal retained share without identifying the exact breakpoint.A uniform additive grid is insufficient because δ* has no inverse-polynomial lower bound.Source: §4.1 · p. 6
4.2 The reward-anchored scale certificate
- The welfare benchmark W controls OPT through a response-curve argument that charges welfare growth to at most n newly appearing actions, without cost-structure assumptions.The extension of the response-curve argument uses no additivity or other structure of the cost function.Source: §4.2 · pp. 7–8
- Trying each singleton reward as an anchor gives one bracket for δ* whose endpoint ratio is at most n^2.The certificate replaces the singleton-cost anchor, which does not control whole-response costs under arbitrary costs.Source: §4.1 · p. 6, §4.2 · p. 8
4.3 The resulting FPTAS
- One α = 1 query computes W, singleton reward queries enumerate anchors, and grid searches require no breakpoint computation.For additive rewards, queried response values are computed from singleton values; one additional cost-value query computes W.Source: §4.3 · pp. 9–10
- O(n log(n + 1)/ε) best-response and value queries suffice for a (1−ε)-approximation.The algorithm returns the best queried contract.Source: §4.3 · p. 10
5 Beyond the FPTAS: robustness and limits
The paper studies robustness to approximate best responses and the limits of reward-anchored scale localization. The method tolerates additive response error, but very high accuracy can again require identifying a hidden breakpoint.
5 Beyond the FPTAS: robustness and limits
- The FPTAS uses exact best responses and searches for breakpoint scale rather than breakpoint identity.The paper states that additive response error causes only an additive utility loss, while the scale-based search has accuracy limits.Source: §5 · p. 10
5.1 Robustness to approximate best responses
- Approximate best responses preserve the reward-anchored search guarantee, with response error affecting utility additively.The guarantee applies to the response selection implemented by the oracle and requires exact reward and cost values.Source: §5.1 · p. 11
5.2 Limits of scale localization
- The section also identifies a trade-off: scale localization supports ordinary approximation, while exponentially fine accuracy can force recovery of the hidden breakpoint identity.The hidden perturbation changes the unique optimum while barely changing its scale.Source: §5.2 · p. 11
- At relative accuracy γn = Θ(2^-n), randomized approximation requires 2^Ω(n) supply queries, even with polynomially many cost-value queries.This is a high-accuracy boundary, not a lower bound for constant or inverse-polynomial accuracy.Source: §5.2 · p. 11
- The localization constructions show that the certificate width can be tight, but do not establish a matching query lower bound.The bracket width enters the algorithm only logarithmically.Source: §5.2 · p. 12
6 Conclusion and discussion
The paper resolves representation-independent approximation for additive rewards with arbitrary set costs, and extends the guarantee to monotone subadditive rewards. It identifies extending the result beyond subadditivity as the main remaining question.
6 Conclusion and discussion
- The paper resolves representation-independent approximation for additive rewards with arbitrary set costs and for monotone subadditive rewards under best-response access.The separation from exact optimization is explained by locating the optimal breakpoint's scale without identifying its hidden identity.Source: §6 · p. 12
- The main open question is whether arbitrary-cost approximation extends to monotone rewards beyond subadditivity.The proof uses subadditivity for both a polynomial welfare–profit comparison and approximation of optimal-response reward by a singleton reward.Source: §6 · p. 12
A Proof of approximate-response robustness
The proof adapts the scale search to an approximate-response oracle by estimating welfare, widening the bracket, and undershooting the target retained share. This creates room to absorb response error while preserving a near-optimal utility guarantee.
A Proof of approximate-response robustness
- Querying the approximate oracle at α = 1 gives lower estimate L = max{0, f(T) − c(T)}; if L ≤ τ, then W ≤ L + τ ≤ 2τ.Returning α = 1 gives zero principal utility, satisfying the claimed bound because P* ≤ W.Source: A Proof of approximate-response… · p. 14
- For each positive singleton reward, the proof searches a geometric grid covering a multiplicative width of 2n^2.The grid ratio is q = 1 − ε/3, and the bracket uses the welfare upper bound U and singleton reward a.Source: A Proof of approximate-response… · p. 14
- The algorithm deliberately undershoots the target retained share to preserve utility while creating enough agent-utility margin to absorb response error.The proof preserves at least a q^2 fraction of the retained share and allocates ρ = ε/3 to oracle error.Source: A Proof of approximate-response… · p. 14
- The proof returns the queried contract–response pair with greatest realized utility, yielding the claimed approximation bound.The grid requires O(log(n + 1)/ε) queries per singleton anchor, plus one cost-value query.Source: A Proof of approximate-response… · p. 14
B Equal-revenue family and high-accuracy lower bound
The equal-revenue family makes the gap between exact optimization and ordinary approximation concrete: many critical contracts have equal utility, and singleton rewards locate their scale. At exponentially fine relative accuracy, however, identifying the hidden optimum matters again.
B Equal-revenue family and high-accuracy lower bound
- The construction assigns each subset a binary index t and gives it reward f(S_t) = t.The costs are monotone and supermodular, and each S_t has an associated critical contract share.Source: B Equal-revenue family and… · p. 15
- Every critical contract in the equal-revenue family gives the principal the same utility, with P* = 1.The response curve visits S_0, S_1, …, S_N in order as the contract share changes.Source: B Equal-revenue family and… · p. 15
- Despite a Θ(n) welfare–profit gap, a singleton reward locates every critical contract's scale within a factor of two.The largest-reward action in S_t provides the singleton anchor.Source: B Equal-revenue family and… · p. 15
- Ordinary approximation can ignore which breakpoint is optimal, but accuracy comparable to the hidden utility advantage requires identifying its hidden set.The perturbation is Θ(4^-n) on a set of reward Θ(2^n), producing a relative principal-utility advantage Θ(2^-n).Source: B Equal-revenue family and… · p. 15
B.1 The high-accuracy query lower bound
Hidden cost perturbations make high-accuracy approximation require exponentially many supply queries. The lower bound follows by making a successful approximation identify which set received a small cost reduction, then reducing supply queries to value queries.
B.1 The high-accuracy query lower bound
- The hidden-perturbation family also gives a partial answer on the dependence on 1/ε: error at the perturbation scale again requires exponentially many queries.The passage states this lower bound once the requested relative error reaches the scale of the hidden perturbation.Source: §B.1 · p. 16
- A cost reduction of ζ = 1/(8N^2) on one hidden set makes that set the unique optimal contract under the stipulated tie-breaking.Its principal utility becomes strictly larger than the utility of every other response.Source: §B.1 · pp. 16–17
- The perturbations preserve nonnegativity, monotonicity, and supermodularity while keeping the response-line order intact.The small reduction shifts the hidden set’s entry breakpoint, without invalidating the relevant comparisons.Source: §B.1 · p. 16
- Because only a query to the hidden set distinguishes its perturbed cost from the known base cost, identifying its index requires Ω(N) value queries.A supply query can be simulated using O(n^2) value queries by enumerating the sparse approximate-supply set.Source: §B.1 · pp. 16–17
- Q ≥ N/poly(n) = 2^Ω(n) supply queries are required for a successful (1 − γn)-approximation.Such an approximation must induce the hidden set Sk and therefore identify its index.Source: §B.1 · p. 17
C Tightness constructions
The tightness constructions give instances where the optimal contract selects a set whose reward is large relative to its singleton rewards, and where ordered singleton responses yield equal principal utility.
C Tightness constructions
- In the first construction, every nonempty set S other than A has cost c(S)=2f(S); dividing every reward and cost by f([n]) leaves all responses and ratios unchanged when rewards must lie in [0,1].Source: C Tightness constructions · p. 18
- The first construction’s unique optimum is (α*, S*) = (α0, A), giving the principal utility P0 = 1 + η rather than 1 at later intersections.The upper envelope visits ∅, A, and the singleton sets in order.Source: C Tightness constructions · p. 18
- In that construction, W = P0 + m/2, while 1 − α* = P0/m and the largest singleton reward in S* is 1.These quantities are stated as the substitution establishing part (i).Source: C Tightness constructions · p. 18
- In part (ii), the costs are monotone and supermodular, and sets of size at least two are never best responses.The singleton upper envelope visits actions in order, each yielding principal utility P, so P* = P.Source: C Tightness constructions · p. 18