{"id":"b4c2b228-d342-474e-9e8c-92a0a795eed7","arxiv_id":"2507.11214","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Envy-free task-contract allocations always exist, yet maximizing principal revenue under envy-freeness is NP-hard to approximate in general; polynomial algorithms exist for constant tasks, and FPTAS for epsilon-EF and EF1 with constant agents.","lead":"This paper introduces fair contracts: a platform assigns tasks to workers with performance-based payments and requires no worker to prefer another worker's task-payment bundle. It shows such contracts always exist, but maximizing the platform's revenue under this fairness constraint is computationally hard, with tractable special cases.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4's EF1 FPTAS is unproven as stated: Algorithm 3 sets ν = min{ε, 1/(6m)} but Lemma 4.7 yields only OPT−2ν; the stated additive ε guarantee requires ν = min{ε/2, 1/(6m)}.","rationale":"I read the paper as claiming: existence of EF full-allocation contracts under Assumption 2.3 (Prop 2.4); hardness of constant-factor approximation to OPT-EF even with ϵ-EF slack (Thm 3.2); poly(n) algorithms for constant m (Thm 4.1); additive FPTAS for constant n under ϵ-EF and EF1 (Thms 4.3, 4.4); and price-of-fairness bounds (Props 5.1, 5.3, 5.4). I re-checked the main proofs. The hardness reduction is sound: the ϵ-EF violation at an edge agent is δ − δ/2 = δ/2 > ϵ = δ/3, and the revenue bound uses μ = 1/(2c), δ = 1/(8ck²), η ≥ 1/k. The constant-task EF1 algorithm is complete: enumerating removable tasks for nonempty-nonempty pairs is finite, and for empty-bundle agents the upper bounds induced by the optimal designations lie in the per-task threshold lists, the induced pattern passes the no-common-prefix feasibility check, and the LP contains α*. The ϵ-EF FPTAS has consistent constants. The adaptive grid in Thm 4.4 is also sound: Eq. (22) case (ii) holds because D_{i,j} partitions [τ_{i,j}, ᾱ_j] into intervals of length δ(ᾱ_j − τ_{i,j}) with α*_j ≤ ᾱ_j by Lemma 4.5, and Lemma 4.8's EF1 chain absorbs the 2νU_i loss via the (1−6ν) multiplicative step. The only genuine defect is the revenue constant: Algorithm 3 sets ν = min{ε, 1/(6m)} while Lemma 4.7 proves only OPT-EF − 2ν, so the stated guarantee fails as written. This matches the reader's flagged issue; the fix (ν = min{ε/2, 1/(6m)}) is local and preserves EF1 and polynomial runtime. I agree with the CONDITIONAL verdict. I diverge on the weakest-assumption diagnosis: Assumption 2.3 is a necessary domain condition (without it no full-allocation contract exists, EF or not) and every construction in the paper satisfies it, so it is not where the argument is insecure. Cosmetic issues (e.g., 'Theorem 2.3' for Assumption 2.3, 'Theorem 2.4' for Prop 2.4) should be cleaned up with the constant fix.","tokens_in":37883,"tokens_out":64025,"duration_ms":613097,"concrete_test":"Independently re-derive Lemma 4.7's revenue chain (Appendix D.3) with Algorithm 3's parameters ν = min{ε, 1/(6m)} and record the additive gap to OPT-EF; the chain should give OPT-EF − 2ν, confirming the stated ε-guarantee fails when ν = ε. Then re-run the chain with ν := min{ε/2, 1/(6m)} and verify: (i) the revenue bound becomes OPT-EF − ε; (ii) Lemma 4.8's EF1 derivation is unchanged (it needs only ν ≤ 1/(6m), and the 2νU_i loss is absorbed by the (1−6ν) multiplicative step); (iii) the DP state count, polynomial in (m/ν)^{n²+1}, stays polynomial in 1/ε for constant n. If all three hold, Theorem 4.4 is upheld after the constant fix; otherwise the EF1 FPTAS needs a different construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is a constants mismatch in the EF1 FPTAS (Theorem 4.4), the paper's headline positive result for a constant number of agents. Algorithm 3 (Section 4.2) sets ν = min{ε, 1/(6m)} and δ = ν/m, but the proof of Lemma 4.7 (Appendix D.3) loses mδ = ν on the principal's revenue when replacing the rounded revenue by the true value, and another ν via equation (14), establishing only Σ(1−α̂)p r ≥ OPT-EF − 2ν. With ν = ε, the algorithm is only 2ε-optimal, so the theorem's stated guarantee 'revenue at least OPT-EF − ε' does not follow from the provided proof. The repair is local: set ν = min{ε/2, 1/(6m)}. Lemma 4.8's EF1-recovery argument needs only ν ≤ 1/(6m) (for (1−6ν)/(1−1/m) ≥ 1), and the DP state count (m/ν)^{n²+1} stays polynomial in 1/ε, so the qualitative FPTAS claim survives. I found no other load-bearing flaw: the existence result (Prop 2.4) is a trivial zero-rent construction; the GAP-Bounded-IS reduction (Thm 3.2) is sound since edge agent b_e has positive success probability only on d_{v1}, d_{v2}, d_e, making its own utility ≤ δ/2 versus envy ≥ δ with ϵ = δ/3; the constant-task EF1 enumeration (Thm 4.1) is complete because the optimal contract's removable-task designations induce a break-even pattern that passes the feasibility check and contains α*; and the ϵ-EF FPTAS (Thm 4.3) is internally consistent. The reader's weakest assumption, Assumption 2.3, is the exact condition under which any full-allocation contract can exist and is satisfied by every construction in the paper; I do not regard it as a vulnerability.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper initiates the algorithmic study of fair contract design in a multi-task moral-hazard model. A principal chooses a full allocation of tasks to agents and task-level linear shares; an agent's utility from a bundle is her expected payoff under optimal effort, and envy-freeness requires each agent to weakly prefer her own bundle to any other agent's. The paper proves that envy-free full-allocation contracts always exist under a mild usefulness assumption, but that approximating the optimal EF revenue within any constant factor is NP-hard in general, even when the algorithm may output an epsilon-EF contract; with a constant number of agents, exact EF is hard (inapproximability below 5/2 with three agents, NP-hardness with two agents), while epsilon-EF and EF1 admit additive FPTAS against the EF benchmark; with a constant number of tasks, optimal EF, epsilon-EF, and EF1 contracts are polynomial-time computable. It also bounds the price of fairness: unbounded for exact EF, Theta(1/epsilon) for epsilon-EF for fixed n and m, and between Omega(sqrt(n)) and O(n^2) for EF1.","tokens_in":38247,"tokens_out":23943,"duration_ms":278258,"significance":"Assuming the proofs are brought to their stated strength, this is a solid and publishable contribution. The conceptual message---fairness constraints are benign for existence but computationally costly for optimization---is well supported by clean constructions: the zero-rent existence proof, the GAP-Bounded-IS reduction with auxiliary edge tasks, the break-even-share enumeration for constant-task EF1, and the adaptive-grid dynamic programs. The price-of-fairness statements give a useful quantitative picture. The proofs are largely self-contained, and the hardness reductions use standard promise problems rather than circular reasoning. The one substantive issue is the constants mismatch in Theorem 4.4, which is local and repairable; no other load-bearing flaw surfaced in my reading.","major_comments":[{"comment":"The proof of Theorem 4.4 does not establish the stated OPT-EF - epsilon revenue guarantee. Algorithm 3 sets nu = min{epsilon, 1/(6m)} (line 1), but Lemma 4.7 in Appendix D.3 proves only that the returned contract has revenue at least OPT-EF - 2nu. With the chosen nu, the guaranteed lower bound is OPT-EF - 2epsilon in the regime where the epsilon-cap binds, and OPT-EF - 1/(3m) in the regime where the 1/(6m)-cap binds; neither implies the theorem's stated OPT-EF - epsilon for all epsilon > 0. The EF1 argument in Lemma 4.8 requires only nu <= 1/(6m), so the proof can be repaired by setting nu = min{epsilon/2, 1/(6m)}; the DP state count remains polynomial in 1/epsilon. As written, however, the headline FPTAS result is not proved.","section":"Section 4.2, Theorem 4.4, Algorithm 3, Lemma 4.7"}],"minor_comments":[{"comment":"Assumption 2.3 is repeatedly called 'Theorem 2.3' in the paragraph immediately following it (e.g., 'We argue that Theorem 2.3 is rather mild' and 'under Theorem 2.3'); please fix the cross-reference.","section":"Section 2"},{"comment":"The pseudocode tests 'if {i_k}_{k in S_j} is feasible' without defining feasibility inside the algorithm; the surrounding text defines it, but the algorithm should either include that check or refer explicitly to the paragraph where it is defined.","section":"Section 4.1, Algorithm 1"},{"comment":"The claim that optimal LP-extreme-point agent utilities are either 0 or at least 2^{-f(I)} presumes rational input data; the paper should state at the outset that all probabilities, costs, and rewards are rational and specify the input encoding.","section":"Section 4.2, proof of Theorem 4.4"},{"comment":"The sentence 'For instance, the EF1 revenue in Theorem 5.2 sharply increases to 1/4' refers to a nonexistent Theorem 5.2; it should refer to Proposition 5.4.","section":"Section 5.3"},{"comment":"The displayed name 'GAP-Bounded-IS_{mu,k}' uses k, but the second parameter in the definition is eta; make the notation uniform across the definition and the proof of Theorem 3.2.","section":"Section 3.1, Definition 3.1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2507.11214. The genuinely new thing is the model: envy-freeness across agents in multi-task moral-hazard contracts with task-level linear shares. That is a natural formalization of fairness on platform work, and it opens a new subarea. The paper's first-order results are a clean existence theorem (zero-rent contracts always achieve EF under Assumption 2.3, unlike fair division) and a sharp computational map: no constant-factor approximation in general even for eps-EF; NP-hard to beat 5/2 with three agents; poly-time optimal contracts for constant tasks; additive FPTAS for eps-EF and EF1 with constant agents; price of fairness unbounded for exact EF but bounded for relaxations. That is a strong package.\n\nWhat's done well: the GAP-Bounded-IS reduction is careful, and the key compensation argument works because edge agents have positive success probability only on their two incident vertex tasks and their own edge task. The constant-task EF1 enumeration via break-even shares is a real technical idea, avoiding exponential enumeration of removable tasks. The adaptive-grid DP for EF1 is sophisticated, and the conversion of additive error into relative error is the right mechanism. The price-of-fairness bounds are clean, and the single-task lower bound for eps-EF is tight.\n\nSoft spots: the EF1 FPTAS in Theorem 4.4 is not proven as stated. Algorithm 3 sets nu = min{epsilon, 1/(6m)}, but Lemma 4.7 and the proof of Lemma 4.8 only give revenue at least OPT-2nu, so the stated OPT-epsilon guarantee does not follow. The fix is local -- set nu = min{epsilon/2, 1/(6m)} -- and the qualitative FPTAS claim survives, but the theorem statement and proof need to be aligned. There are also several mislabeled references to the paper's own results (Assumption 2.3 called Theorem 2.3, Proposition 2.4 called Theorem 2.4). Minor, but worth cleaning up. Assumption 2.3 is not a real weakness; it is exactly the condition under which full allocation is possible, and every construction in the paper satisfies it.\n\nThe citation pattern looks honest: the hardness reductions use standard NP-hard promise problems, self-citations appear only in related work, and the follow-up papers cited are distinct from this model. This paper deserves a serious referee. It launches a direction, and the core claims are likely correct, but the EF1 FPTAS constants need to be fixed and the proofs re-checked before publication.","headline":"A genuinely new model at the intersection of contract theory and fair division, with mostly sound proofs and one repairable constants bug in the EF1 FPTAS.","tokens_in":38843,"tokens_out":2565,"would_cite":true,"duration_ms":28233,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Envy-free contracts always exist, yet optimal revenue is inapproximable.","keywords":["fair contracts","envy-freeness","linear contracts","contract theory","algorithmic mechanism design","price of fairness","EF1","computational hardness"],"falsifier":"Take a two-task, two-agent instance satisfying Assumption 2.3 and run the zero-rent construction (each task to its minimal break-even share agent, paying exactly that share); the paper claims the result is always envy-free, so exhibiting any instance where one agent strictly prefers the other's bundle refutes Proposition 2.4. For the hardness claim, the decisive check is to construct a small instance from the proof of Theorem 3.2 for a chosen constant $c$, solve OPT-EF by exhaustive LP enumeration for comparison, and check whether any polynomial-time algorithm can produce an $\\epsilon$-EF contract with revenue at least $1/c$ of that benchmark on a family of such instances.","tokens_in":37622,"feed_emoji":"⚖️","tokens_out":8779,"duration_ms":95082,"temperature":0.7,"pith_summary":"This paper studies a platform that assigns many tasks to heterogeneous agents and must choose a payment share for each task, under the fairness requirement that every agent weakly prefers her own bundle of tasks and shares to any other agent's bundle. Its central findings are that an envy-free contract assigning every task always exists when each task is profitable for at least one agent, yet maximizing revenue subject to envy-freeness is NP-hard to approximate within any constant factor, even when approximate envy is allowed. The paper then maps the tractable landscape: fixing the number of tasks makes optimal EF, $\\epsilon$-EF, and EF1 contracts polynomial-time computable, while fixing the number of agents makes EF1 and $\\epsilon$-EF solvable by additive FPTAS even though exact EF remains hard. Finally, it quantifies the price of fairness, showing exact envy-freeness can destroy arbitrarily much revenue while the relaxed notions recover bounded worst-case guarantees.","feed_headline":"Envy-free contracts exist, yet optimal revenue is inapproximable","feed_subtitle":"Finding the revenue-optimal fair contract is NP-hard in general; relaxations restore tractability.","key_machinery":"The object carrying the argument is the task-level linear contract with envy-free full allocation. For each task $j$, a single share $\\alpha_j$ determines the payment $\\alpha_j r_j$ to whoever performs it; agent $i$ values the contract via her own success probability and cost, giving utility $\\max\\{\\alpha_j p_{i,j} r_j - c_{i,j}, 0\\}$. Three mechanisms do the heavy lifting. First, the break-even share $\\tau_{i,j} = c_{i,j}/(p_{i,j} r_j)$ defines the minimal payment that makes effort worthwhile; assigning every task to its minimal-$\\tau$ agent at that share yields the zero-rent envy-free contract that proves existence, and the same threshold values serve as contract upper bounds that convert EF1 constraints into enumerable threshold patterns. Second, the hardness reduction encodes a bounded-degree independent set instance so that the efficient agent can profitably absorb many vertex tasks, while each edge creates an envy constraint that rules out assigning both endpoints. Third, the constant-agent algorithms use dynamic programming over discretized $n^2$-dimensional utility profiles; for EF1, an adaptive grid refines each agent's utility scale separately so that rounding errors become relative losses small enough for deleting one task to restore envy-freeness.","core_discovery":"The central discovery is a sharp asymmetry between existence and optimization in fair contract design. Under Assumption 2.3 — every task has at least one agent whose expected surplus $p_{i,j} r_j - c_{i,j}$ is nonnegative — an envy-free full-allocation contract always exists and can be constructed by assigning each task to the agent with the smallest break-even share and paying exactly that share, so that every agent evaluates every bundle at zero utility. Revenue maximization, however, is computationally hard: reducing from a gap version of bounded-degree independent set, the paper proves that for any constant $c$ there is a constant $\\epsilon > 0$ such that no polynomial-time algorithm computes an $\\epsilon$-EF contract with revenue at least $1/c$ of the optimal EF revenue. The hardness is structural: high revenue forces many related tasks onto a single efficient agent, while envy-freeness requires those tasks to form an independent set. The paper's algorithmic contributions show that this coupling is controllable when the number of tasks is constant (LP enumeration), and that constant-agent settings admit additive FPTAS for EF1 and $\\epsilon$-EF through a dynamic program over discretized utility profiles with an adaptive grid.","pith_inferences":["The independent-set structure of the hardness result suggests that other fairness notions implying non-envy, such as proportionality or maximin-share guarantees, will likely inherit similar inapproximability in general multi-task settings.","The adaptive-grid technique that turns additive rounding errors into EF1-compatible relative losses is transferable: any allocation problem with an 'up to one item' fairness constraint and additive utilities could use the same relative-discretization recipe.","The zero-rent existence construction implies that every fairness relaxation weaker than EF (EF1, $\\epsilon$-EF, and similar notions) automatically inherits full-allocation existence, so the practical bottleneck is purely the revenue-optimality computation.","An immediate testable extension is to measure, on synthetic ride-hailing-style data with a few tasks per agent, how far the empirical ratio of unconstrained to envy-free revenue sits below the worst-case exponential gap, which would tell platform operators whether the unbounded price of fairness is a realistic threat or a worst-case artifact."],"forward_implications":["Under Assumption 2.3, every instance admits an envy-free full-allocation contract, and the zero-rent construction finds one in polynomial time.","Revenue-optimal EF contracts admit no polynomial-time constant-factor approximation in general, and the inapproximability survives comparison against an $\\epsilon$-EF benchmark.","With a constant number of tasks, the optimal EF, $\\epsilon$-EF, and EF1 contracts are computable in polynomial time by enumerating allocations and solving linear programs.","With a constant number of agents, $\\epsilon$-EF and EF1 contracts have additive polynomial-time approximation schemes against the optimal EF benchmark, while exact EF has no approximation ratio below $5/2$ even with three agents.","The price of fairness is unbounded for exact EF, at least $4\\epsilon/\\min\\{m,n^2\\}$ for $\\epsilon$-EF, and at least $1/n^2$ for EF1."],"supporting_citations":[{"why":"Supplies the gap version of bounded-degree independent set that the hardness reduction embeds into contracts.","marker":"Alon et al., 1995"},{"why":"Establishes NP-hardness of the bounded-degree gap independent-set problem used as the reduction source.","marker":"Trevisan, 2001"},{"why":"Introduces envy-freeness up to one item, the relaxation the paper's EF1 algorithms target.","marker":"Lipton et al., 2004"},{"why":"Validates EF1 as a practical fairness benchmark in combinatorial assignment, motivating its use.","marker":"Budish, 2011"},{"why":"Provides the price-of-fairness lower-bound construction that the EF1 gap adapts.","marker":"Bei et al., 2021"},{"why":"Provides the linear-programming background for the fixed-allocation reformulations and the utility-precision bound in the FPTAS.","marker":"Bertsimas and Tsitsiklis, 1997"},{"why":"Foundation of the moral-hazard contract model that the paper extends with envy constraints.","marker":"Grossman and Hart, 1992"}],"fun_headline_variants":["Envy-free contracts exist, but optimal revenue is inapproximable","Fair contracts exist, yet revenue-optimal ones are NP-hard","EF contracts always exist, revenue-optimal ones are NP-hard","Existence without envy is easy; optimizing revenue is hard","Fair design: existence simple, optimization intractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole theory assumes every task is worth doing for at least one agent: for each task $j$ there is some $i$ with $p_{i,j} r_j - c_{i,j} \\ge 0$, and tasks failing this are removed in preprocessing; if an effort-infeasible task is kept, existence and all guarantees collapse.","fun_headline_variants_meta":{"raw":{"variants":["Envy-free contracts exist, but optimal revenue is inapproximable","Fair contracts exist, yet revenue-optimal ones are NP-hard","EF contracts always exist, revenue-optimal ones are NP-hard","Existence without envy is easy; optimizing revenue is hard","Fair design: existence simple, optimization intractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1733,"prompt_tokens":939,"completion_tokens":794,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":555,"completion_tokens_details":{"reasoning_tokens":710}},"tokens_in":555,"tokens_out":794,"duration_ms":8896,"temperature":1.0,"reasoning_tokens":710,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:17:31.959201+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-task, two-agent instance satisfying Assumption 2.3 and run the zero-rent construction (each task to its minimal break-even share agent, paying exactly that share); the paper claims the result is always envy-free, so exhibiting any instance where one agent strictly prefers the other's bundle refutes Proposition 2.4. For the hardness claim, the decisive check is to construct a small instance from the proof of Theorem 3.2 for a chosen constant $c$, solve OPT-EF by exhaustive LP enumeration for comparison, and check whether any polynomial-time algorithm can produce an $\\epsilon$-EF contract with revenue at least $1/c$ of that benchmark on a family of such instances.","supporting_citations":[{"cited_title":"Learning Optimal Contracts: How to Exploit Small Action Spaces","cited_arxiv_id":"2309.09801","evidence_quote":"Supplies the gap version of bounded-degree independent set that the hardness reduction embeds into contracts."}],"review_version":1}