{"id":"34d1124c-4fe0-4996-92d5-9173b57dc6f5","arxiv_id":"2412.13290","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An additive PTAS exists for linear contracts with graph-based supermodular rewards and arbitrary agent costs.","lead":"This paper gives a polynomial-time approximation scheme for designing linear contracts when several agents with different costs cooperate on a graph. It answers an open question from prior work, which only had such a scheme when all agents cost the same.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's LP relaxation is infeasible when a near-optimal set consists mostly of cheap agents; the PTAS proof fails for valid inputs with all costs at most epsilon/(2n).","rationale":"The reader's weakest assumption is the structural existence lemma (Lemma 1). My concern is different and more direct: even granting Lemma 1, the LP in Lemma 2 is not a valid relaxation for a broad class of instances. The proof of Lemma 2 asserts that the characteristic vector of S' union C is feasible, but constraint (15) sums only over A, which by Definition 1 excludes all cheap vertices. When the near-optimal set S' is composed entirely of cheap vertices (all costs <= epsilon/(2n)), A is empty and the constraint is violated. Such instances are explicitly permitted by the model (costs are in R_{\\ge 0}) and have OPT = 1 for a complete graph, so the PTAS must handle them. The same gap affects the rounding: Theorem 3 starts with S'' drawn only from A union B and then adds C vertices only if adjacent to S'', so an all-cheap optimal set is never recovered. This is an internal inconsistency in the proof, not a disagreement with existing consensus. The concrete test would confirm it. Consequently the central claim is not established by the current write-up; the verdict should move to REJECT unless the authors add a separate treatment of the all-cheap case (e.g., via the densest-subgraph PTAS).","tokens_in":22509,"tokens_out":21818,"duration_ms":194546,"concrete_test":"Set G = K_n and c_i = 0 for all i (or c_i = epsilon/(2n)) for a small constant epsilon. Run the proposed PTAS or simply check Lemma 2. With the correct guess |E(S')| = n(n-1)/2, LP (14)-(20) has A = B = D = empty, so constraint (15) demands 0 >= n(n-1)(1-epsilon), making the LP infeasible. The only feasible guesses (e.g., |E| = 0) round under Theorem 3 to S'' = empty because no A union B vertices are sampled; the output has g = 0 while OPT = 1, violating the promised additive approximation. This check settles whether the central proof handles general costs.","verdict_should_be":"REJECT","load_bearing_attack":"Definition 1 defines C = {i : c_i <= epsilon/(2n)} and A subseteq H subseteq V\\C, so cheap vertices are excluded from A and from constraint (15). Lemma 2 claims that the characteristic vector x' of S' union C is feasible for LP (14)-(20). Consider an instance with all costs c_i = 0 (or all c_i <= epsilon/(2n)) on a dense graph, so OPT >= epsilon. Lemma 1 can take S' to be a near-optimal dense set, which lies entirely in C. Then H = A = B = D = empty. Constraint (15) becomes 0 >= 2(1-epsilon)|E(S')|, impossible whenever |E(S')| > 0. Hence the LP has no feasible solution, and the proof of Lemma 2 collapses. Moreover, Theorem 3's rounding rule includes C vertices only if they have a neighbor in the sampled A union B set; when A union B is empty, S'' = empty, so the algorithm outputs the empty set, far from OPT. This is not an artifact of one choice of S': any near-optimal set in such an instance is all-cheap, so the difficulty is intrinsic to the LP formulation as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22753,"tokens_out":21193,"duration_ms":201420,"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":[{"comment":"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.","section":"Section 3, Lemma 2 and Definition 1"},{"comment":"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.","section":"Appendix A.1, proof of Theorem 3, bound on R(S'')"}],"minor_comments":[{"comment":"There are typographical errors in the author affiliation and running text, including 'Deptartment', 'mul ti-agent', and 'colla borations'.","section":"Affiliation and introduction"},{"comment":"The notation uses both epsilon and varepsilon interchangeably; one symbol should be used consistently.","section":"Throughout"},{"comment":"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.","section":"Appendix A.2, Lemma 11"},{"comment":"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.","section":"Appendix A.2, Lemma 9"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern is valid and, in my reading, is more damaging than a boundary case: constraint (15) fails whenever cheap vertices contribute a large share of the edges of S', and the rounding rule then drops those cheap vertices. The main theorem may still be true, but the current algorithmic proof does not establish it. I recommend major revision rather than outright rejection, provided the authors can repair the LP formulation and the rounding analysis; if they cannot, the paper should ultimately be rejected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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).\n\nThe 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.","headline":"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.","tokens_in":23258,"tokens_out":5549,"would_cite":false,"duration_ms":56048,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["contract theory","multi-agent contracts","linear contracts","supermodular functions","graph-based rewards","additive PTAS","randomized rounding","pseudo-core"],"falsifier":"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.","tokens_in":22325,"feed_emoji":"⚖️","tokens_out":14479,"duration_ms":110602,"temperature":0.7,"pith_summary":"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.","feed_headline":"Near-optimal contracts for unequal-cost agents are now feasible","feed_subtitle":"A sampling-and-rounding scheme finds a contract within an additive epsilon of optimal, answering an open question.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the problem formulation, the equal-cost additive PTAS, the hardness results, and the open question that this paper resolves.","marker":"[17]"},{"why":"Provides the additive-PTAS sampling framework for dense instances that underlies the degree-estimation step.","marker":"[5]"},{"why":"Gives the oblivious sampler used in Lemma 3 to guess the high-degree set H and degree estimates.","marker":"[16]"},{"why":"Establishes hardness for exact multi-agent contract design and the constant-approximation baselines for other reward classes.","marker":"[20]"},{"why":"Introduces the combinatorial-agency model and the Nash-equilibrium characterization that defines the objective g(S).","marker":"[6]"}],"fun_headline_variants":["Additive PTAS closes contract gap for unequal costs","Graph-based contracts: general costs now get near-optimal deals","Sampling and rounding solve costly multi-agent contracting","Answering open question: additive PTAS for graph contracts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Additive PTAS closes contract gap for unequal costs","Graph-based contracts: general costs now get near-optimal deals","Sampling and rounding solve costly multi-agent contracting","Answering open question: additive PTAS for graph contracts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000184,"raw_usage":{"total_tokens":1391,"prompt_tokens":1093,"completion_tokens":298,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":233}},"tokens_in":709,"tokens_out":298,"duration_ms":3355,"temperature":1.0,"reasoning_tokens":233,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:15:58.480777+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: Proceedings of the 2024 Annu al ACM-SIAM Sym- posium on Discrete Algorithms (SODA)","cited_arxiv_id":null,"evidence_quote":"Supplies the problem formulation, the equal-cost additive PTAS, the hardness results, and the open question that this paper resolves."},{"cited_title":"In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing","cited_arxiv_id":null,"evidence_quote":"Provides the additive-PTAS sampling framework for dense instances that underlies the degree-estimation step."},{"cited_title":"In: Proceedings of the forty-first annual ACM symposium on Theor y of computing","cited_arxiv_id":null,"evidence_quote":"Gives the oblivious sampler used in Lemma 3 to guess the high-degree set H and degree estimates."},{"cited_title":"In: Proceedings of the 55th Annual ACM Symposium on Theory of Com puting","cited_arxiv_id":null,"evidence_quote":"Establishes hardness for exact multi-agent contract design and the constant-approximation baselines for other reward classes."},{"cited_title":"In: Proceedings of the 7th ACM Conference on Electronic Commerce","cited_arxiv_id":null,"evidence_quote":"Introduces the combinatorial-agency model and the Nash-equilibrium characterization that defines the objective g(S)."}],"review_version":1}