REVIEW 2 major objections 4 minor 5 references
Multi-Project Contracts
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper proves a polynomial-time constant-factor approximation for optimal multi-project contracts with XOS success functions, and the same guarantee for submodular functions using only value queries.
desk verdict Genuinely new model and solid algorithmic work, but the headline approximation guarantee relies on an explicitly stated equilibrium-selection assumption that does heavy lifting; worth engaging, not a fully robust contract-design result. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is an approximate demand oracle for capped subadditive functions. Given a subadditive function $f$, a cap $x$, and prices $p$, Algorithm 2 returns a set $\bar S$ whose capped surplus $\min\{f(\bar S),x\}-\sum_{i\in\bar S}p_i$ is within a constant factor and a small additive $\delta x$ of the capped demand, using only demand queries to $f$; it works by binary-searching a payment scale $\gamma$ and partitioning the resulting set into blocks of value approximately $x$. This oracle yields the approximate separation oracle for the dual of the LP (LP1), whose variables $y_{j,x,S}$ fractionally assign each set $S$ of agents to project $j$ with an estimated reward $x$, and whose constraints keep every agent below capacity one. The remaining mechanisms are a deterministic rounding procedure for XOS functions based on supporting additive valuations (Algorithm 4), which preserves half the fractional value, and a generalized scaling lemma that prunes each rounded set until every kept agent's marginal contribution is large enough relative to her cost, so that the payment formula (2) leaves at least half the reward as revenue.
What would settle it
Enumerate all partial partitions of a small instance (e.g., 3 agents, 3 projects) with XOS success functions and arbitrary costs, compute the optimal revenue by brute force, and compare it with the revenue of Algorithm 5's output; a ratio exceeding the claimed constant factor, or any instance in which a project without a dominant agent contributes revenue that the multiplicative grid $D_j$ cannot approximate within a constant factor, would falsify the theorem.
Extended reading notes
Core claim
The central claim is Theorem 3.1: when every project's success function is XOS, there is a polynomial-time algorithm that computes a contract achieving expected revenue within a constant factor of the optimal multi-project contract, given value and demand oracle access to the success functions; for submodular functions the same guarantee holds with value queries only. The paper argues that an optimal contract can be restricted to single-payment linear schemes, paying each agent in a team $S_j$ the amount $t_{ij}(S_j)=c_{ij}/(f_j(S_j)-f_j(S_j\setminus\{i\}))$, so the entire problem reduces to choosing an allocation of agents to projects. The algorithm splits the projects in the optimal allocation into those with a dominant agent, approximated by a maximum-weight bipartite matching, and those without, approximated by a linear program whose variables fractionally assign sets of agents to projects under a capped reward $\min\{f_j(S),x\}$. The fractional solution is computed by the ellipsoid method with an approximate separation oracle, rounded deterministically to an integral allocation, and scaled down so payments consume only a constant fraction of the reward. The better of the two candidate allocations is a constant-factor approximation to the global optimum.
Load-bearing premise
The paper assumes that for any chosen allocation the principal can enforce the intended all-work equilibrium, and that the optimal contract is always the single-payment linear scheme with payments equal to cost divided by marginal contribution; if agents could instead coordinate on a no-effort equilibrium, or if non-linear contracts could beat the linear scheme, the algorithm's constant-factor guarantee is measured against the wrong optimum.
Editorial extensions
If this is right
- A principal can compute an approximately optimal team assignment and payment scheme in time polynomial in the number of agents and projects, instead of enumerating all partial partitions.
- For projects with submodular success functions, the same constant-factor guarantee is obtained with only value queries, the weakest standard oracle.
- The capped-demand oracle provides a polynomial-time approximate demand query for any capped subadditive function given demand access to the original function, independent of contracts.
- Known impossibility results remain in force: no constant-factor algorithm exists for arbitrary subadditive success functions, and lower bounds of 1.42 for submodular and 1.136 for XOS set limits on improving the constant.
- The better-of-two design means the algorithm is robust to whichever regime dominates the optimal allocation: dominant-agent projects or diffuse teams.
Reading between the lines
- The LP-rounding pipeline closely tracks the welfare-maximization literature, so randomized rounding or the $\left(1-\frac1e\right)$ techniques could likely sharpen the hidden constant while keeping the same oracle model.
- A testable engineering extension is to instantiate the capped-demand oracle for structured classes such as budget-additive or coverage functions, which would turn the existence result into a ready-to-run implementation for those settings.
- The strongest practical caveat, left implicit by the model, is that the contract is optimal only when the principal can select the equilibrium agents play; a natural follow-up is to design contracts in which the intended all-work profile is the unique (or dominant) equilibrium, or to drop the equilibrium-selection assumption and study the resulting revenue loss.
- The same framework should extend to multi-project settings with non-uniform rewards or agent capacities larger than one, by replacing the partition constraints with b-matching constraints in the LP.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a model of multi-project contracts in which a principal assigns heterogeneous agents to projects, each agent can work on at most one project, and each project's success probability is a monotone combinatorial function of the assigned agents. Contracts are restricted to linear, single-payment schemes, and the paper follows the standard reduction (Babaioff et al.) that, for a fixed assignment, the optimal payment to each agent is the cost divided by her marginal contribution. The principal's problem thus reduces to finding an allocation maximizing expected revenue. The main result (Theorem 3.1) is a polynomial-time O(1)-approximation algorithm for the allocation problem when success functions are XOS, using value and demand queries, and for submodular functions using only value queries. The proof handles projects with a dominant agent by a maximum-weight matching reduction, and projects without a dominant agent through an LP with exponentially many variables solved by the ellipsoid method with an approximate separation oracle, a new approximate demand oracle for capped subadditive functions, a deterministic rounding procedure for XOS functions, and a generalized scaling lemma.
Significance. If the main theorem is accepted within its stated model, the paper makes a solid contribution: it introduces a natural multi-project variant of combinatorial contract design and provides the first constant-factor approximation for XOS and submodular success functions, with a polynomial oracle complexity. The capped-demand oracle (Lemma 5.1) is a potentially reusable technical tool, and the reduction to an LP plus rounding is well aligned with recent work on multi-agent contracts. The paper is careful about oracle access and cites prior lower bounds. The main caveat is that the revenue objective in Section 2 assumes the principal can select among multiple Nash equilibria of the induced game; without an explicit selection device the approximation guarantee is not a statement about the actual game. This caveat should be made prominent in the abstract and theorem.
major comments (2)
- [Section 2, Eq. (2) and footnote 3] The objective Rev_j(S_j) is well defined only under the assumption that the all-work profile is the realized equilibrium. The contract t_ij=c_ij/(f_j(S_j)-f_j(S_j\{i})) makes every agent exactly indifferent between working and shirking when the other agents work, so the all-work profile is a Nash equilibrium, but other equilibria generally exist (for example, the all-shirk profile whenever f_j({i})t_ij <= c_ij for every i). The O(1)-approximation guarantee in Theorem 3.1 is therefore a guarantee about a contract paired with a favorable equilibrium selection, not about the contract in the underlying game. Because Definition 2.1 does not include a selection device, this is a load-bearing modeling assumption that is not reflected in the paper's abstract or main theorem. Please either augment the model with a formal selection or commitment device, or revise the statements and interpretations to make the equilibrium-selection dependence explicit, and discuss how the guarantee degrades under worst-case equilibrium selection.
- [Section 6.1, Claims 6.2 and 6.3] The approximate separation oracle is not a separation oracle for (LP2) as stated. Case 1 checks the exact LP2 constraints, but Case 2 reports a violation under the different inequality 1/(1+1/(1-delta)) alpha_j + sum_{i in S} beta_i < min{f_j(S),x} - sum_{i in S} sqrt(c_ij x)/(2 sqrt(2)), which is not the negation of Case 1 and is not equivalent to a violated LP2 constraint (the LP2 constraint has an additional -delta(1+1/(1-delta))x term and no factor on alpha_j). The ellipsoid-based procedure in Algorithm 3 is therefore effectively solving a modified dual problem, and the proof of Claim 6.3 does not account for the additive delta*x slack or the 1/(1+1/(1-delta)) factor in the chain gamma- >= gamma+ - epsilon >= P* - epsilon. This leaves a gap in the polynomial-time guarantee for the OPT+ portion. The gap may be fixable by redesigning the oracle for the modified dual or by carrying explicit error terms through the binary search, but as written the proof does not establish Claim 6.3.
minor comments (4)
- [Claim 6.2] The oracle defines prices p_i = infinity to exclude agents with f_j({i}) > delta*x, but Lemma 5.1 and Algorithm 2 are defined for finite input prices; please replace infinity with a finite bound and state why the bound suffices, for example a bound larger than the maximum possible demand value.
- [Lemma A.1, Algorithm 6] Line 3 of Algorithm 6 divides by f(i_s | S_0 \ {i_s}), which can be zero for monotone functions; the proof should first remove zero-marginal elements or handle this case separately, since the ratio is otherwise undefined.
- [Section 7, proof of Theorem 3.1] The displayed chain "Rev(S+) >= (1/512)(1/10) Rev(S**)=OPT+" is incorrect because OPT+ = Rev(S**); the intended statement is Rev(S+) >= (1/5120) OPT+ (or with the appropriate constant), and the subsequent comparison is an asymptotic constant-factor bound rather than an equality.
- [Footnote 1 and Section 6] The informal description of discretized reward estimates in the introduction (2^i max_i f_j({i}) for i in [log n]) and the formal definition of D_j in Section 6 (2^k f_j({i}) over all i) are not aligned; please use a single notation.
Circularity Check
No significant circularity; the main theorem is derived from proven lemmas and independent prior-work results, not from its own assumptions by construction.
full rationale
Walking the derivation chain, the paper's central reduction is from contracts to an allocation problem: Equation (2) fixes t_ij = c_ij/(f_j(S_j)-f_j(S_j\{i})) and defines Rev_j(S_j) as the revenue of that contract. The subsequent LP (LP1), rounding (Algorithm 4), and scaling (Section 6.3, Lemma A.1) all optimize and approximate this explicitly defined objective. No parameter is fitted to a subset of data and then renamed a prediction; the constants (delta=1/129, 1/10, 1/512) come from inequalities, not from calibration. The only behavioral caveat is stated in footnote 3: 'There may be additional equilibria, but in this paper, we assume that the principal can select the realized equilibrium.' That is a modeling assumption defining the objective, not a circular step: the theorem's guarantee is relative to the thus-defined revenue, and the paper does not claim to predict equilibrium selection. The imported lemmas (B.1-B.3 from Dutting et al. 2023, with one current coauthor) are parameter-free theorems with explicit assumptions and are used as stated; per the review rules, such independently stated results count as real evidence and do not raise the circularity score. The proof of the capped-demand oracle (Lemma 5.1) is self-contained; Claim 6.2 reduces separation to that oracle by algebra, not by assuming the violated constraint. Thus I find no step where an output is equivalent to an input by construction or where a self-citation carries the entire claim.
Assumptions & free parameters
free parameters (1)
- delta =
1/129
assumptions (5)
- domain assumption Success functions are normalized, monotone, and belong to additive, submodular, XOS, or subadditive classes; f_j(empty)=0.
- domain assumption For a fixed team S_j, the optimal incentive-compatible linear contract pays t_ij = c_ij/(f_j(S_j)-f_j(S_j\{i})), and linear single-payment contracts are without loss.
- domain assumption The principal can select the realized equilibrium when multiple equilibria exist.
- domain assumption Value and demand oracles for each success function are available, and the demand oracle returns an exact maximizer for any nonnegative price vector.
- standard math Auxiliary lemmas B.1, B.2, and B.3 from Dutting et al. 2023 and Lemma C.1 from Sviridenko et al. 2017 and Harshaw et al. 2019 are correct and transfer to this setting.
Cite this review
Pith. "Pith review of Multi-Project Contracts." pith.science (2026). https://pith.science/paper/O5HZ4KYC
@misc{pith2026250605705,
author = {Pith},
title = {Pith review of: Multi-Project Contracts},
year = {2026},
howpublished = {\url{https://pith.science/paper/O5HZ4KYC}},
note = {Machine review of arXiv:2506.05705}
}
read the original abstract
We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each project is a combinatorial function of the agents working on it. Each agent has limited capacity and can work on at most one project, and the agents are heterogeneous, with different costs and contributions for participating in different projects. The main challenge of the principal is to decide how to allocate the agents to projects when the number of projects grows in scale. We analyze this problem under different assumptions on the structure of the expected reward functions. As our main result, for XOS functions we show how to derive a constant approximation to the optimal multi-project contract in polynomial time, given access to value and demand oracles. Along the way (and of possible independent interest), we develop approximate demand queries for \emph{capped} subadditive functions, by reducing to demand queries for the original functions. Our work paves the way to combinatorial contract design in richer settings.
Reference graph
Works this paper leans on
-
[1]
Verifies that all constraints of(LP2)are satisfied, i.e., αj + X i∈S βi ≥ 1− 1 e min{fj(S), x} − X i∈S √cijx 2 √ 2 ∀j∈[m], x∈D j, S⊆A j,x
-
[2]
Specifically, ∃j∈M, x∈D j, S⊆A j,x such thatα j + X i∈S βi <min{f j(S), x} − X i∈S √cijx 2 √ 2
Otherwise, it identifies anapproximatelyviolated constraint. Specifically, ∃j∈M, x∈D j, S⊆A j,x such thatα j + X i∈S βi <min{f j(S), x} − X i∈S √cijx 2 √ 2 . 31 Proof.We construct the approximate demand oracle using the approximate capped demand in Lemma C.1. Given an assignment{α j}i∈M ,{β i}i∈N for (LP5), we define the prices as in Claim 6.2 and compute...
-
[3]
The number of strictly positive variablesy j,x,S is polynomially bounded
-
[4]
P j∈M P x∈Dj P S⊆Aj,x yj,x,S min{fj(S), x} − √x 2 √ 2 P i∈S √cij ≥(P ⋆ S −ϵ)
-
[5]
Proof.The proof proceeds similarly to the one of Claim 6.3
For everyy j,x,S >0,f j(S)≤(1 +δ)x,f j({i})≤δxandf j(i|S j \ {i})≥ √xcij 2 √ 2 ∀i∈S. Proof.The proof proceeds similarly to the one of Claim 6.3. During the ellipsoid method execution for (LP2) with the additional constraint that the objective is less thanγ −, the algorithm identifies polynomially manyapproximatelyviolating constraints (or separating hyper...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.