Linear Contracts for Supermodular Functions Based on Graphs

Jacob Skitsko; Kanstantsin Pashkovich

REVIEW 2 major objections 4 minor 44 references

Linear Contracts for Supermodular Functions Based on Graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that, for graph-based collaborative rewards, a linear contract within an additive $5\sqrt{\varepsilon}$ of optimal can be computed efficiently even when agents have different costs.

desk verdict The paper answers the open question from Deo-Campo Vuong et al. with a plausible but as-written flawed construction: Lemma 2's LP is infeasible when all agents are cheap, so the main theorem is not yet proven. read the letter →

arxiv 2412.13290 v1 pith:ZRGFHA3K submitted 2024-12-17 cs.GT

Kanstantsin Pashkovich , Jacob Skitsko This is my paper · ORCID

classification cs.GT

keywords contracttheorymulti-agentcontractslinearsupermodularfunctionsgraph-basedrewardsadditivePTASrandomizedroundingpseudo-core

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that multi-agent contract design with graph-based supermodular reward functions admits an additive polynomial-time approximation scheme (PTAS) even when agents have distinct costs. This answers an open question left by prior work, which had obtained such a PTAS only for equal agent costs and had shown that no multiplicative approximation or additive FPTAS is possible unless $P = \mathcal{NP}$. The central claim is that for every constant $\varepsilon > 0$ there is an algorithm that runs in time $n^{\mathrm{poly}(1/\varepsilon)}$ and outputs a set of agents whose expected utility for the principal is within an additive $5\sqrt{\varepsilon}$ of optimal. A sympathetic reader should care because it shows that despite the intrinsic hardness of exact and FPTAS-style solutions, near-optimal contracts can still be computed efficiently in this natural collaborative setting.

What carries the argument

The load-bearing object is the $\beta$-pseudo-core of a set $S$: the inclusion-wise maximal subset $\bar{S}$ such that $\deg_{\bar{S}}(i)(\deg_{\bar{S}}(i)+1)/c'_i \ge \beta$ for every non-cheap $i \in \bar{S}$. It is computed by the greedy algorithm PseudoCore, which repeatedly removes the vertex with smallest ratio until the condition holds. The paper's iterative pseudo-coring procedure (Algorithm 3) applies PseudoCore while increasing the costs of expensive agents over $M = \log_2 \ln(\gamma(n+6/\varepsilon))$ rounds; this forces every surviving non-cheap agent to have degree at least $\Omega(n/\ln\ln n)$, giving Lemma 1. The algorithm then solves a linear program (14)-(20) over fractional inclusion variables $x_v$, with the objective of minimizing the principal's transfer to agents in $A$, constraints that enforce each $A$-agent's neighborhood sum and each $B$-agent's degree relative to its own variable, and forced values for cheap ($C$) and excluded ($D$) agents. A preprocessing procedure (Fractional Coring, Algorithm 1) trims the LP solution so that nonzero variables in $A$ are at least $1/n^{1/2}$ and each active $B$-agent's neighborhood sum is at least $\kappa n^{1/2} \ln(2n^2)$, which is precisely what makes the subsequent randomized rounding converge.

What would settle it

Exhibit a single graph with agent-specific costs and a constant $\varepsilon > 0$ such that every subset $S'$ with $g(S') \ge \mathrm{OPT} - \varepsilon$ violates at least one of the two inequalities in Lemma 1(iii)(a) for some non-cheap vertex; if such an instance exists, the LP would have no near-optimal structured feasible solution and Theorem 1 would be false.

Watch

Extended reading notes

Core claim

The paper's core discovery is Theorem 1: an additive PTAS for linear contracts over graph-based supermodular rewards with general costs. The proof works by first establishing a structural lemma (Lemma 1) asserting that, for any instance and any constant $\varepsilon > 0$, there exists a set $S'$ with $g(S') \ge \mathrm{OPT} - \varepsilon$ in which every non-cheap agent $v$ has degree at least $\Omega(n/\ln\ln n)$ and satisfies $\deg_{S'}(v)(\deg_{S'}(v)+1)/c_v \ge \gamma(n^2+(6/\varepsilon)n)$. The algorithm does not find $S'$ directly; instead it uses sampling and exhaustive guessing to learn enough statistics (the high-degree set $H$ and the degrees of its members) to formulate a linear program whose optimal value approximates $1 - L(S')$. A preprocessing step modifies the LP solution so that all nonzero variables are at least $1/n^{1/2}$ and the neighborhood sums for $B$-agents are large, which makes randomized rounding provably concentrate. The rounded integral solution $S''$ satisfies $g(S'') \ge g(S') - 4\sqrt{\varepsilon} \ge \mathrm{OPT} - 5\sqrt{\varepsilon}$ with probability at least $1 - \sqrt{\varepsilon} - 1/n$, and repeating the rounding polylogarithmically many times boosts the success probability to $1 - 1/n$.

Load-bearing premise

The whole proof collapses if Lemma 1 is false: there must exist a near-optimal set $S'$ whose non-cheap vertices all have degree at least $\Omega(n/\ln\ln n)$ and satisfy the quadratic degree-per-cost condition, and every later step assumes such an $S'$ exists.

Editorial extensions

If this is right

For any constant $\varepsilon > 0$, a contract with expected utility at least $\mathrm{OPT} - 5\sqrt{\varepsilon}$ can be computed in $n^{\mathrm{poly}(1/\varepsilon)}$ time, regardless of how unequal the agents' costs are.
The additive PTAS for equal costs from [17] is generalized, so the open question posed there is settled affirmatively.
The LP pre-processing and randomized-rounding method yields a near-feasible, concentrated solution for a class of covering-like LPs where ground set and covering sets coincide; this may be useful beyond contract theory.
Because the algorithm is oblivious to the optimal set and relies on sampling and exhaustive guesses, it achieves its guarantee with high probability rather than with certainty.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If Lemma 1's structural guarantee holds for richer supermodular rewards—e.g., edge counts on hypergraphs or densest-subgraph-type objectives—the same sampling-LP-rounding blueprint might yield additive PTASs there, though the degree bounds and LP constraints would need re-deriving.
The additive error of $5\sqrt{\varepsilon}$ may be improvable by strengthening the concentration bounds; a natural test is whether the constants in Theorem 3 can be tightened without new structural ideas.
The Fractional Coring preprocessing could be applied to other linear programs where randomized rounding fails because small fractional variables create weak concentration; the condition that surviving variables be bounded away from zero is a general recipe.
The pseudo-core technique introduces a cost-raising schedule that might be a template for other iterative 'core' definitions, suggesting that similar structural lemmas could be proven for other graph properties.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here is my honest take. This paper is a real attempt at the open question from Deo-Campo Vuong et al., and the core ideas—beta-pseudo-cores, iterative coring, the LP-rounding framework—are substantive. The constants are explicit, the dependence on epsilon is concrete, and the citations to [17], [5], and [16] line up. Lemma 1's structural existence claim looks like the heart of the paper, and I don't see an obvious break there.

The problem is in Lemma 2's LP. The LP excludes all agents with cost at most epsilon/(2n) from A and H; they are forced into C with x_v = 1. Yet constraint (15) asks the A-side weighted degrees to account for all of |E(S')|. On an input where every agent is cheap—say all costs zero on a dense graph—C = V, H = A = B = empty, and the constraint reads 0 >= 2(1-epsilon)|E(S')|, impossible as soon as S' has any edges. The proof claims x' = 1_{S' union C} is feasible, but the left side of (15) is zero. Then Theorem 3's rounding step has no A union B population to sample, so it outputs the empty set. That is not a corner case; it is a perfectly legal instance with OPT close to 1.

The stress-test note is right about this. Definition 1 fixes H as a subset of V \ C, so the bad case is intrinsic, not an artifact of one choice of S'. The gap is in the LP, not necessarily in the pseudo-core machinery. Lemma 1 might survive; the edge constraint needs to account for C, or the all-cheap regime needs a separate argument (for example, just return all of C when the cheap agents already carry the reward).

The paper deserves a serious referee—it addresses an open question, the techniques are nontrivial, and the intended result is plausible. But as submitted, the main theorem is not proven, and the reader's ACCEPT is too generous. I would send it to peer review with a request for major revision, not desk-reject. I would not cite it in this form.

Referee Report

2 major / 4 minor

Summary. The paper studies the principal-agent problem with linear contracts in a multi-agent setting where agents are vertices of a graph and the principal's reward is the number of edges induced by the set of agents exerting costly effort. The main claim is an additive PTAS for general (heterogeneous) agent costs, resolving an open question from Deo-Campo Vuong et al. The proof strategy is: prove a structural lemma (Lemma 1) giving a near-optimal set S' with strong degree/cost properties; partition agents into sets A, B, C, D and write an LP relaxation (14)-(20); preprocess an optimal LP solution to obtain a near-feasible solution x* satisfying concentration-friendly properties (Theorem 2); and round x* by randomized sampling to obtain S'' (Theorem 3). The error bound claimed is g(S'') >= OPT - 5*sqrt(epsilon). The appendix contains the omitted proofs of the structural and rounding claims.

Significance. If the claimed result were correct, it would be a significant contribution: it resolves an open question, introduces the notion of beta-pseudo-core and iterative pseudo-coring, and develops a preprocessing/rounding technique for a class of covering-like LPs. The constants are explicit, and Lemma 1 is a nontrivial structural statement. However, the proof as written contains a central error in Lemma 2 that invalidates the claimed PTAS on valid inputs. The paper cannot be accepted in its current form; substantial revision is needed to repair the LP formulation and the rounding analysis.

major comments (2)

[Section 3, Lemma 2 and Definition 1] Lemma 2 is false as stated because the characteristic vector of S' union C is not generally feasible for LP (14)-(20). If all costs are zero, or all costs are at most epsilon/(2n), then C = V, so H = A = B = D = empty. Constraint (15) then becomes 0 >= 2(1-epsilon)|E(S')|, which is violated whenever S' contains an edge. This is not an isolated boundary case: in a complete graph with one vertex of cost 1 and n-1 vertices of cost 0, A contains only the expensive vertex, so the left-hand side of (15) is O(n) while the right-hand side is Omega(n^2), and the characteristic vector of S' union C is again infeasible. The rounding step in Theorem 3 also fails in the all-cheap case, because when A union B is empty no cheap vertex is ever included, so the algorithm outputs the empty set rather than a near-optimal set. The LP and rounding rules therefore need to be redesigned, for example by including degree information for cheap vertices or by treating cheap-dominated instances with a separate argument.
[Appendix A.1, proof of Theorem 3, bound on R(S'')] The displayed chain bounding |E(S'')| contains an arithmetic error. From (34) and (25), for v in A we have deg_{S''}(v) >= (1-epsilon) * sum_{u in N(v)} x*_u >= (1-epsilon)^3/(1+epsilon) * hat d_v, not (1-epsilon)^2/(1+epsilon) * hat d_v. The chain as written therefore yields (1-epsilon)^6/(1+epsilon) |E(S')| rather than the claimed (1-epsilon)^5/(1+epsilon) |E(S')|. This error is repairable by absorbing the extra factor of (1-epsilon) into the constants, but the calculation in the manuscript is incorrect as it stands.

minor comments (4)

[Affiliation and introduction] There are typographical errors in the author affiliation and running text, including 'Deptartment', 'mul ti-agent', and 'colla borations'.
[Throughout] The notation uses both epsilon and varepsilon interchangeably; one symbol should be used consistently.
[Appendix A.2, Lemma 11] The estimate |tilde S setminus S_M| <= n/(1-epsilon) <= epsilon n/6 is justified only for sufficiently small epsilon (roughly epsilon <= 1/7), and this restriction is not stated. The paper should either state an explicit small-epsilon assumption or explain why larger epsilon makes the approximation guarantee vacuous.
[Appendix A.2, Lemma 9] The phrase 'true for large enough n' is not quantified. The paper should state how small graphs are handled, e.g., by brute force, so that the PTAS claim covers all n.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; the PTAS proof rests on a new structural existence lemma and explicit rounding analysis, not on restating its own inputs.

full rationale

The derivation chain is self-contained. Lemma 1 is a new existential structural statement proved by the iterative pseudo-coring procedure of Algorithm 3; its quantitative degree/cost conclusions are derived from the algorithm and explicit constants, not assumed as part of the statement. Lemma 2's LP is written using the unknown set S' as an analysis device, and its proof supplies a candidate feasible solution from S', which is a proof obligation rather than a definitional identity. Theorem 2 is an algorithmic preprocessing result, and Theorem 3 is a randomized rounding argument using explicit Chernoff and Hoeffding bounds. The external tools referenced, namely the oblivious sampling estimates from [17,16] and the prior hardness/PTAS framework from [17], are cited from other research groups and do not assume the theorem being proved. No parameters are fitted to the target objective, and no known result is merely renamed or imported by self-citation. A reviewer might question whether Lemma 2's constraint (15) remains feasible when a near-optimal set consists mostly of cheap vertices; that concern is a proof-correctness issue, not a circularity, because it would show the lemma is false rather than that the theorem is equivalent to its assumptions by construction.

Assumptions & free parameters 1 free parameters · 5 assumptions · 1 invented entities

The central claim is an algorithmic existence theorem. The PTAS introduces no data-fitted free parameters; all constants are explicit functions of epsilon. It relies on standard LP and concentration results, and on the model-level assumption from contract theory that contracts can be optimized over pure Nash equilibria. The heaviest imported tool is the oblivious sampling lemma of [17,16], which is cited rather than re-derived. The pseudo-core is a new internal construct rather than a new physical entity.

free parameters (1)

epsilon (approximation tolerance) = Arbitrary input in (0,1)
The PTAS is parameterized by epsilon. Derived constants kappa, sigma, delta, delta_epsilon, gamma_prime, gamma are explicit functions of epsilon; none are fitted to data.

assumptions (5)

domain assumption Optimal contract for incentivizing exactly a set S is t_i = c_i / f(i|S) for i in S and zero otherwise (Section 1.2).
Inherited from contract theory literature [6,20,17]; the whole objective g(S) is built on this equilibrium characterization.
domain assumption Agents play pure Nash equilibria of the induced contract game, and the principal can optimize over the intended equilibrium set S.
Section 1.2 defines the Nash equilibrium conditions; the paper maximizes g(S) over S without discussing equilibrium multiplicity or selection.
domain assumption Lemma 3: the oblivious sampler from [17,16] returns degree estimates with the stated high-probability guarantees.
The PTAS uses these estimates to instantiate the LP without knowing S'; the lemma is cited from prior work and not proved in this paper.
standard math Standard Chernoff and Hoeffding concentration inequalities hold as used in Lemma 5 and Theorem 3.
These inequalities are used to bound rounding errors and are assumed as background.
standard math Linear programs can be solved in polynomial time.
The algorithm solves the LP (14)-(20) and treats this as a polynomial-time step.

invented entities (1)

beta-pseudo-core
purpose: Structured subset of S* balancing degree against cost, used to prove existence of a near-optimal set S' with high degrees.
Introduced in Section A.2; existence and uniqueness are proven in the paper. It is an internal algorithmic construct, not a physical entity with independent falsifiable predictions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear Contracts for Supermodular Functions Based on Graphs." pith.science (2026). https://pith.science/paper/ZRGFHA3K

@misc{pith2026241213290,
  author       = {Pith},
  title        = {Pith review of: Linear Contracts for Supermodular Functions Based on Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZRGFHA3K}},
  note         = {Machine review of arXiv:2412.13290}
}

abstract

We study linear contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a linear contract with several agents, each of whom can decide to take a costly action or not. The principal observes only the outcome of the agents' collective actions, not the actions themselves, and obtains a reward from this outcome. Agents that take an action incur a cost, and so naturally agents require a fraction of the principal's reward as an incentive for taking their action. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized. Our focus is on the case when the agents are vertices in a graph and the principal's reward corresponds to the number of edges between agents who take their costly action. This case represents the natural scenario when an action of each agent complements actions of other agents though collaborations. Recently, Deo-Campo Vuong et.al. showed that for this problem it is impossible to provide any finite multiplicative approximation or additive FPTAS unless $\mathcal{P} = \mathcal{NP}$. On a positive note, the authors provided an additive PTAS for the case when all agents have the same cost. They asked whether an additive PTAS can be obtained for the general case, i.e when agents potentially have different costs. We answer this open question in positive.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 41 canonical work pages

[17]

In: Proceedings of the 2024 Annu al ACM-SIAM Sym- posium on Discrete Algorithms (SODA)

Deo-Campo Vuong, R., Dughmi, S., Patel, N., Prasad, A.: O n supermodular con- tracts and dense subgraphs. In: Proceedings of the 2024 Annu al ACM-SIAM Sym- posium on Discrete Algorithms (SODA). pp. 109–132. SIAM (20 24)

work page 2024
[5]

In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

Arora, S., Karger, D., Karpinski, M.: Polynomial time app roximation schemes for dense instances of np-hard problems. In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. pp. 284–293 (1995)

work page 1995
[16]

In: Proceedings of the forty-ﬁrst annual ACM symposium on Theor y of computing

Daskalakis, C., Papadimitriou, C.H.: On oblivious ptas ’s for nash equilibrium. In: Proceedings of the forty-ﬁrst annual ACM symposium on Theor y of computing. pp. 75–84 (2009)

work page 2009
[1]

In: Proceedings of the 24th ACM Conference on Econom ics and Computa- tion

Alon, T., Duetting, P., Li, Y., Talgam-Cohen, I.: Bayesia n analysis of linear con- tracts. In: Proceedings of the 24th ACM Conference on Econom ics and Computa- tion. pp. 66–66 (2023)

work page 2023
[2]

In: Proceedings of the 22nd ACM Conference on Economi cs and Computa- tion

Alon, T., Dütting, P., Talgam-Cohen, I.: Contracts with p rivate cost per unit-of- eﬀort. In: Proceedings of the 22nd ACM Conference on Economi cs and Computa- tion. pp. 52–69 (2021)

work page 2021
[3]

Operations Research 72(1), 288–299 (2024)

Alon, T., Talgam-Cohen, I., Lavi, R., Shamash, E.: Incomp lete information vcg contracts for common agency. Operations Research 72(1), 288–299 (2024)

work page 2024
[4]

In: Internatio nal Conference on Artiﬁcial Intelligence and Statistics

Ananthakrishnan, N., Bates, S., Jordan, M., Haghtalab, N .: Delegating data col- lection in decentralized machine learning. In: Internatio nal Conference on Artiﬁcial Intelligence and Statistics. pp. 478–486. PMLR (2024)

work page 2024
[6]

In: Proceedings of the 7th ACM Conference on Electronic Commerce

Babaioﬀ, M., Feldman, M., Nisan, N.: Combinatorial agenc y. In: Proceedings of the 7th ACM Conference on Electronic Commerce. pp. 18–28 (20 06)

work page

Show all 44 references

[7]

arXiv preprint arXiv:2209.1368 8 (2022)

Babichenko, Y., Talgam-Cohen, I., Xu, H., Zabarnyi, K.: I nformation design in the principal-agent problem. arXiv preprint arXiv:2209.1368 8 (2022)

2022
[8]

In: Proc eedings of the forty- seventh annual ACM symposium on Theory of computing

Barman, S.: Approximating nash equilibria and dense bipa rtite subgraphs via an approximate version of caratheodory’s theorem. In: Proc eedings of the forty- seventh annual ACM symposium on Theory of computing. pp. 361 –369 (2015)

2015
[9]

arXiv preprint arXiv:2402.16547 (2024)

Bernasconi, M., Castiglioni, M., Celli, A.: Agent-desig ned contracts: How to sell hidden actions. arXiv preprint arXiv:2402.16547 (2024)

2024 arXiv
[10]

Castiglioni, M., Chen, J., Li, M., Xu, H., Zuo, S.: A reduc tion from multi-parameter to single-parameter bayesian contract design (2024)

2024
[11]

In: Proceedings of the 22nd ACM Conference on Eco nomics and Com- putation

Castiglioni, M., Marchesi, A., Gatti, N.: Bayesian agen cy: Linear versus tractable contracts. In: Proceedings of the 22nd ACM Conference on Eco nomics and Com- putation. pp. 285–286 (2021)

2021
[12]

In: Proceedings of the 23rd ACM C onference on Eco- nomics and Computation

Castiglioni, M., Marchesi, A., Gatti, N.: Designing men us of contracts eﬃciently: the power of randomization. In: Proceedings of the 23rd ACM C onference on Eco- nomics and Computation. pp. 705–735 (2022)

2022
[13]

In: Proc eedings of the 24th ACM Conference on Economics and Computation

Castiglioni, M., Marchesi, A., Gatti, N.: Multi-agent c ontract design: How to com- mission multiple agents with individual outcomes. In: Proc eedings of the 24th ACM Conference on Economics and Computation. pp. 412–448 (2023 )

2023
[14]

In: International Conference on Machine Learning

Chen, J., Li, M., Xu, H.: Selling data to a machine learner : Pricing via costly sig- naling. In: International Conference on Machine Learning. pp. 3336–3359. PMLR (2022)

2022
[15]

In: Proceed- ings of the 24th ACM Conference on Economics and Computation

Dasaratha, K., Golub, B., Shah, A.: Equity pay in network ed teams. In: Proceed- ings of the 24th ACM Conference on Economics and Computation . pp. 512–512 (2023)

2023
[18]

arXiv preprint arXiv:2405.08260 (2024) Linear Contracts for Supermodular Functions Based on Graph s 15

Duetting, P., Ezra, T., Feldman, M., Kesselheim, T.: Mul ti-agent combinatorial contracts. arXiv preprint arXiv:2405.08260 (2024) Linear Contracts for Supermodular Functions Based on Graph s 15

2024 arXiv
[19]

In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer S cience (FOCS)

Dütting, P., Ezra, T., Feldman, M., Kesselheim, T.: Comb inatorial contracts. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer S cience (FOCS). pp. 815–826. IEEE (2022)

2022
[20]

In: Proceedings of the 55th Annual ACM Symposium on Theory of Com puting

Dütting, P., Ezra, T., Feldman, M., Kesselheim, T.: Mult i-agent contracts. In: Proceedings of the 55th Annual ACM Symposium on Theory of Com puting. pp. 1311–1324 (2023)

2023
[21]

In: Proceedings of the 2024 Annual ACM-SIAM Sympo sium on Discrete Algorithms (SODA)

Dutting, P., Feldman, M., Gal Tzur, Y.: Combinatorial co ntracts beyond gross sub- stitutes. In: Proceedings of the 2024 Annual ACM-SIAM Sympo sium on Discrete Algorithms (SODA). pp. 92–108. SIAM (2024)

2024
[22]

arXiv preprint arXiv:2302.07621 (2023)

Dütting, P., Feldman, M., Peretz, D.: Ambiguous contrac ts. arXiv preprint arXiv:2302.07621 (2023)

2023 arXiv
[23]

In: Proceedings of the 2019 ACM Conference on Economics and C omputation

Dütting, P., Roughgarden, T., Talgam-Cohen, I.: Simple versus optimal contracts. In: Proceedings of the 2019 ACM Conference on Economics and C omputation. pp. 369–387 (2019)

2019
[24]

SIAM Journal on Computing 50(1), 211–254 (2021)

Dutting, P., Roughgarden, T., Talgam-Cohen, I.: The com plexity of contracts. SIAM Journal on Computing 50(1), 211–254 (2021)

2021
[25]

Dütting, P., Feldman, M., Gal-Tzur, Y., Rubinstein, A.: The query complexity of contracts (2024)

2024
[26]

Theoretical Computer Science 452, 56–74 (2012)

Emek, Y., Feldman, M.: Computing optimal contracts in co mbinatorial agencies. Theoretical Computer Science 452, 56–74 (2012)

2012
[27]

In: 15th Innovations in Theoretical Comp uter Science Conference (ITCS 2024)

Ezra, T., Feldman, M., Schlesinger, M.: On the (in) appro ximability of combina- torial contracts. In: 15th Innovations in Theoretical Comp uter Science Conference (ITCS 2024). Schloss-Dagstuhl-Leibniz Zentrum für Inform atik (2024)

2024
[28]

Ezra, T., Feldman, M., Schlesinger, M.: Sequential cont racts (2024)

2024
[29]

arXiv preprint arXiv:2402.16553 (2024)

Ezra, T., Leonardi, S., Russo, M.: Contracts with inspec tions. arXiv preprint arXiv:2402.16553 (2024)

2024
[30]

Grossman, S.J., Hart, O.D.: An Analysis of the Principal - Agent Problem, pp. 302–340. Springer Netherlands, Dor- drecht (1992). https://doi.org/10.1007/978-94-015-7957-5_16 , https://doi.org/10.1007/978-94-015-7957-5_16

1992 doi
[31]

arXiv preprint arXiv:2401.16198 (2024)

Guruganesh, G., Kolumbus, Y., Schneider, J., Talgam-Co hen, I., Vlatakis- Gkaragkounis, E.V., Wang, J.R., Weinberg, S.M.: Contracti ng with a learning agent. arXiv preprint arXiv:2401.16198 (2024)

2024 arXiv
[32]

In: Proceedings of the 22nd ACM Conferen ce on Economics and Computation

Guruganesh, G., Schneider, J., Wang, J.R.: Contracts un der moral hazard and adverse selection. In: Proceedings of the 22nd ACM Conferen ce on Economics and Computation. pp. 563–582 (2021)

2021
[33]

In: Proceedings of the 24nd ACM Conference on E conomics and Computation (2023)

Guruganesh, G., Schneider, J., Wang, J.R., Zhao, J.: The power of menus in con- tract design. In: Proceedings of the 24nd ACM Conference on E conomics and Computation (2023)

2023
[34]

Hoefer, M., Schecker, C., Schewior, K.: Contract design for pandora’s box (2024)

2024
[35]

The Bell Journal of Economics 10(1), 74–91 (1979), http://www.jstor.org/stable/3003320

Holmström, B.: Moral hazard and observability. The Bell Journal of Economics 10(1), 74–91 (1979), http://www.jstor.org/stable/3003320

1979
[36]

Advances in Neural Information Processing Systems 36 (2024)

Saig, E., Talgam-Cohen, I., Rosenfeld, N.: Delegated cl assiﬁcation. Advances in Neural Information Processing Systems 36 (2024)

2024
[37]

of Sciences, R.S.A.: Scientiﬁc background on the 2016 no bel prize in economic sciences (2016)

2016
[38]

Weitzman, M.: Optimal search for the best alternative, v ol. 78. Department of Energy (1978)

1978
[39]

zeroes out

Xiao, S., Wang, Z., Chen, M., Tang, P., Yang, X.: Optimal c ommon contract with heterogeneous agents. In: Proceedings of the AAAI Conferen ce on Artiﬁcial Intel- ligence. vol. 34, pp. 7309–7316 (2020) 16 Kanstantsin Pashkovich and Jacob Skitsko A Appendix: Omitted Proofs A.1 L...

2020
[40]

Similarly, notice that at thi s point we have ∑ v∈A ˆdvxv− ∑ v∈A ˆdvx∗ v≤ n3/2 , which implies that (

Thus, we obtain ∑ u∈N (v) x∗ u≥ ( 1− ε 1 + ε ) · ˆdv for all v∈ A Linear Contracts for Supermodular Functions Based on Graph s 17 Algorithm 1: Fractional Coring Input: Feasible solution x to LP ( 14)-(20) 1 x∗← x, j← 1 2 for v∈ A do 3 if x∗ v≤ 1/n1/2 then 4 x∗ v← 0 5 while tru...
[41]

Now we consider how the rest of the algorithm changes x∗ from this point onwards, i.e

is true at this point. Now we consider how the rest of the algorithm changes x∗ from this point onwards, i.e. from the moment when the algorithm moves to line 5 for the ﬁrst time. Let J be the value of j immediately before Algorithm 1 terminated. Observe that at the end of the...
[42]

holds for x∗. Note, the entries of x∗ indexed by v ∈ A∪ C did not change after the ﬁrst loop of the algorithm, implying that ( 21), ( 23), ( 24) and ( 27) hold for x∗, and we have x∗ v≥ 1/n1/2 or x∗ v = 0 for all v∈ A. By line 10 in Algorithm 1, for all v∈ B with x∗ v > 0 we h...
[43]

Now we use Hoeﬀding’s inequality to bound the probability th e event in ( 33) does not occur

does not occur, and obtain Pr [ ∑ v∈A∩S′′ ˆdv < (1− ε) ∑ v∈A ˆdvx∗ v ] = Pr [ ∑ v∈A∩S′′ ˆdv < (1− ε)E [ ∑ v∈A∩S′′ ˆdv ]] ≤ exp   − 2ε2E [ ∑ v∈A∩S′′ ˆdv ] 2 n ( maxv∈A ˆdv ) 2   ≤⋆ exp ( − 2ε2(1− ε)4 (ε/6· n)4 n3 ) ≤ 1 n2 here the inequality ⋆ follows from ˆdv≤ n for all ...
[44]

Before we proceed, let us make some observations about the st ructure of an optimal set S∗

The desired set S′ is the output of Algorithm 3 with input given by the optimal set S∗ and the original costs ci, i∈ V . Before we proceed, let us make some observations about the st ructure of an optimal set S∗. The next lemma can be shown by starting with the set S∗ and iter...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [17]

In: Proceedings of the 2024 Annu al ACM-SIAM Sym- posium on Discrete Algorithms (SODA)

Deo-Campo Vuong, R., Dughmi, S., Patel, N., Prasad, A.: O n supermodular con- tracts and dense subgraphs. In: Proceedings of the 2024 Annu al ACM-SIAM Sym- posium on Discrete Algorithms (SODA). pp. 109–132. SIAM (20 24)

work page 2024

[2] [5]

In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

Arora, S., Karger, D., Karpinski, M.: Polynomial time app roximation schemes for dense instances of np-hard problems. In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. pp. 284–293 (1995)

work page 1995

[3] [16]

In: Proceedings of the forty-ﬁrst annual ACM symposium on Theor y of computing

Daskalakis, C., Papadimitriou, C.H.: On oblivious ptas ’s for nash equilibrium. In: Proceedings of the forty-ﬁrst annual ACM symposium on Theor y of computing. pp. 75–84 (2009)

work page 2009

[4] [1]

In: Proceedings of the 24th ACM Conference on Econom ics and Computa- tion

Alon, T., Duetting, P., Li, Y., Talgam-Cohen, I.: Bayesia n analysis of linear con- tracts. In: Proceedings of the 24th ACM Conference on Econom ics and Computa- tion. pp. 66–66 (2023)

work page 2023

[5] [2]

In: Proceedings of the 22nd ACM Conference on Economi cs and Computa- tion

Alon, T., Dütting, P., Talgam-Cohen, I.: Contracts with p rivate cost per unit-of- eﬀort. In: Proceedings of the 22nd ACM Conference on Economi cs and Computa- tion. pp. 52–69 (2021)

work page 2021

[6] [3]

Operations Research 72(1), 288–299 (2024)

Alon, T., Talgam-Cohen, I., Lavi, R., Shamash, E.: Incomp lete information vcg contracts for common agency. Operations Research 72(1), 288–299 (2024)

work page 2024

[7] [4]

In: Internatio nal Conference on Artiﬁcial Intelligence and Statistics

Ananthakrishnan, N., Bates, S., Jordan, M., Haghtalab, N .: Delegating data col- lection in decentralized machine learning. In: Internatio nal Conference on Artiﬁcial Intelligence and Statistics. pp. 478–486. PMLR (2024)

work page 2024

[8] [6]

In: Proceedings of the 7th ACM Conference on Electronic Commerce

Babaioﬀ, M., Feldman, M., Nisan, N.: Combinatorial agenc y. In: Proceedings of the 7th ACM Conference on Electronic Commerce. pp. 18–28 (20 06)

work page