{"id":"ab775677-325f-4e33-b7e1-44c01fedbb68","arxiv_id":"2608.04337","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Universally truthful budget-feasible mechanisms with constants 3, e+1, and 2e+1 for submodular, XOS, and subadditive valuations, plus a polynomial-time demand-query mechanism with approximation C+epsilon (C<86.399) for subadditive valuations.","lead":"This paper designs truthful payment mechanisms that buy services from strategic sellers under a fixed budget, improving the best-known approximation ratios for submodular, XOS, and subadditive valuations, and delivering the first polynomial-time constant-factor mechanism for subadditive valuations. It also proves a structural lemma showing any subadditive function can be approximated within a factor of 2 by a self-bounding function.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tail concentration bound (Lemma 5.6) is load-bearing and its corrupted display prevents full audit; reconstructed math appears sound, so CONDITIONAL stands.","rationale":"The reader's weakest_assumption targets exactly the tail concentration analysis: Lemma D.3's variance bound and Lemma 5.6's conversion into a lower bound on E[ν]. I audited these in detail. Lemma D.3 is a clean Efron–Stein argument using the self-bounding property of v~; the identity 1/2 Σ_i E[Δ_i] = E[Σ_{i∈T*_0} Δ_i] holds by symmetry, and the final bound Var ≤ (M/2)E[v~(T*_0)] is correct. Lemma 5.6(17) follows from E[min(X,Y)] ≥ E[X] − (1/2)E|X−Y| ≤ E[X] − √Var(X) and monotonicity of z − √((M/2)z) on z ≥ v/2. The corrupted (18) reconstructs as stated, and the cross-term uses Lemma 5.1(12). Lemma 5.7's thinning bound also checks out: the product Π(1−qx_i) ≥ e^{−1} follows from qΣ x_i/(1−x_i) ≤ 1−q, and Lemma D.2 supplies E[v~(S)] ≥ (qℓ/(ℓ+1))v~(D). Lemma 5.8's algebraic inequality is verified. Thus no mathematical flaw was found. The concern is verifiability: the most intricate part of the proof is partly illegible, and the paper has no formal verification. That warrants a CONDITIONAL rather than ACCEPT, exactly as the reader concluded. The ChatGPT transparency note is not itself a flaw; the relevant evidence (the smoothing lemma) has an elementary proof that I also checked. I therefore see no reason to move the verdict, and I agree with the reader's identification of the load-bearing premise.","tokens_in":50784,"tokens_out":29546,"duration_ms":244882,"concrete_test":"Independently re-derive Lemma 5.6(18) from (17) and Lemma 5.1(12), verifying the cross-term coefficient 1/(2(1+η)) and the positive sign; then run a small numerical experiment (n≤12): sample random monotone subadditive value functions, compute the smoothed v~ by enumeration, identify S* maximizing the potential, take the tail T*, and across many random partitions check inequality (17) and the tail-branch expected potential bound of Lemma 5.7. If either bound fails on any instance, Theorem 5.2's constant approximation is false; if all pass, the reconstructed lemma is empirically supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Main Result 3) rests on the polynomial-time potential allocator of Theorem 5.2, whose tail branch is justified by Lemma 5.6 (concentration of random-partition estimates) and Lemma 5.7 (uniform thinning), with Lemma D.3 supplying the variance bound. This is the least secure link: the typeset display of Lemma 5.6(18) and parts of Lemma D.3 contain corrupted symbols (e.g., '⌟roo⟪⟪op'), so the exact inequality cannot be read from the manuscript. Reconstructing from the proof text, (18) should read E[ν] ≥ (1/(2(1+η)))Φ(T*) − (1/(2(1+η)))√(max_{|S|≤ℓ} Φ(S)·Φ(T*)). The derivation is consistent: (17) gives E[min(v~(T0),v~(T1))] ≥ v~(T*)/2 − 0.5√(M_{T*} v~(T*)); multiplying by Π_{i∈T*}(1−x_i) and invoking Lemma 5.1(12) yields exactly this cross-term. Lemma D.3's Efron–Stein argument also checks out. However, because the displayed statements are corrupted, a wrong coefficient or sign in the cross-term would silently break the constant approximation of Theorem 5.2, and no independent formal verification accompanies the paper. This is the single most load-bearing premise that could not be fully audited.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified framework, based on non-truthful compensation design, for constructing truthful budget-feasible mechanisms. It establishes constant price-of-stability bounds for marginal-contribution payment rules over self-bounding proxies, proves a new smoothing lemma showing that every monotone subadditive function admits a self-bounding 2-approximation, and translates these results into universally truthful mechanisms. The information-theoretic results improve the state of the art for monotone submodular (3), nonmonotone submodular (e+1), XOS (e+1), and subadditive (2e+1) valuations, with deterministic large-market improvements. The main result is a universally truthful, individually rational, budget-feasible mechanism for subadditive valuations that runs in polynomial time using demand queries and achieves approximation factor C+epsilon with C<86.399, resolving the Dobzinski–Papadimitriou–Singer conjecture. The polynomial-time implementation is based on a core-tail decomposition, a nonbossy potential allocator, empirical estimation of the smoothed value, and a filtering step that restores budget feasibility.","tokens_in":51127,"tokens_out":6105,"duration_ms":56465,"significance":"If the central claims are correct, the paper resolves a long-standing open problem in budget-feasible mechanism design and substantially advances the state of the art for submodular, XOS, and subadditive valuations. The smoothing lemma, showing that every subadditive function is 2-approximated by a self-bounding function, is an elegant structural result with independent applications, including the multiwinner-elections core question. The proof strategy, moving from compensation design to truthful direct mechanisms through potential arguments, is conceptually novel and well explained. The information-theoretic theorems are supported by clean, largely self-contained proofs, and the paper provides explicit constants and query bounds for the polynomial-time mechanism. The main caveat is that the most intricate part of the polynomial-time analysis, specifically the concentration lemma that underlies the tail approximation, cannot be fully audited from the typeset text due to corrupted displayed formulas.","major_comments":[{"comment":"Equation (18) is the load-bearing bridge between the concentration estimate (17), the grid estimator H-hat_b, and the constant-factor tail approximation in Theorem 5.2, but the displayed formula contains unreadable glyphs (for example '⌟roo⟪⟪op') in the cross-term. The proof text suggests the intended inequality is E[ν] ≥ (1/(2(1+η))) Φ(T*) − (1/(2(1+η))) sqrt( max_{|S|≤ℓ} Φ(S) · Φ(T*) ), but this is a reconstruction rather than a reading of the manuscript. A wrong coefficient or sign in the cross-term would change the constant and potentially invalidate the claimed polynomial-time approximation. This corruption must be repaired and the exact inequality stated cleanly before the central result can be certified.","section":"§5.1.2, Lemma 5.6, equation (18)"},{"comment":"The same corrupted square-root notation reappears in the lower bound for the expected potential of the tail branch and in the proof of Theorem 5.2. Since the randomization between the core and tail branches (Lemma 5.8) is applied to this expression, the entire constant-factor computation for the potential allocator depends on the exact algebraic form of the cross-term. The authors should re-typeset these displays and include the intermediate algebra explicitly.","section":"§5.1.3, display (19), and Theorem 5.2"},{"comment":"The variance bound Var(v-tilde(T*_0)) ≤ (M/2) E[v-tilde(T*_0)] is a crucial step: it produces the square-root cross-term in Lemma 5.6. Although the Efron–Stein argument is plausible and the final bound is stated without corruption, the surrounding proof of Lemma 5.6 contains corrupted symbols in the passage using that variance estimate. Given that this is the least secure link in the polynomial-time analysis, the derivation should be rewritten with every step displayed, including the monotonicity argument for the function z ↦ z − sqrt(M z)/2 on [v-tilde(T*)/2,∞).","section":"§D.3, Lemma D.3 and proof of Lemma 5.6"}],"minor_comments":[{"comment":"The monotonicity definition contains a corrupted arrow symbol 'b_i' ≤ b_i /Leftr⫯g⊸tl⫯ne⇒'; this should be typeset as a standard logical implication.","section":"Definition 2.1"},{"comment":"The sampling trick is described as drawing a random permutation of 'N ∪ {/⊙◇⊞}', but the marker symbol appears corrupted; the intended construction is a random permutation with a separator, and the notation should be cleaned up.","section":"§5.2.1"},{"comment":"The entry for β-self-bounding valuations in the general column reads 'unbounded(((β≥2)))', which appears to be a formatting artifact; the statement that the approximation is unbounded for β≥2 should be presented normally.","section":"Table 1"},{"comment":"The threshold formulas use the notation 'Φ F_i,in' and 'Φ F_i,out' in a way that is understandable but visually cluttered; adding a short explanatory sentence or a displayed definition would improve readability.","section":"Mechanism 4.1"}],"recommendation":"major_revision","confidential_remarks":"This is a strong and important paper, and I found no concrete mathematical error in the reconstructed argument. The reason for major revision is auditability: the corrupted displays in Lemma 5.6, equation (18), display (19), and Theorem 5.2 concern the exact inequality that carries the polynomial-time approximation guarantee. Once those displays are repaired and the derivation is fully written out, the paper should be re-evaluated, but I would then expect it to be a strong accept candidate if the restored formulas match the proof text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the smoothing lemma (Theorem 3.5) is the real result. No one had a constant-distortion self-bounding approximation for arbitrary subadditive functions; the prior subadditive-to-XOS approximation is Theta(log n) (Bhawalkar–Roughgarden). The proof via the smoothed value function v-tilde, the marginal identity sum_i (v-tilde(S)-v-tilde(S\\{i})) = v(S)-v-tilde(S), and the 2-approximation argument is clean and checkable. That lemma alone justifies the paper.\n\nFrom there the PoS-to-truthful conversion is standard but executed well: potential maximizers are Nash equilibria under marginal-contribution payments, and the self-bounding property gives budget-feasible threshold payments. The improved ratios (3 for monotone submodular, e+1 for XOS, 2e+1 for subadditive) follow naturally. Those are real advances over 3.798, 28, and 33.\n\nThe soft spot is the polynomial-time mechanism (Theorem 5.1). The core-tail decomposition is reasonable, but the tail analysis rests on concentration bounds—Lemma 5.6 and Lemma D.3—that are the least secure links. The displayed inequality (18) contains corrupted symbols ('⌟roo⟪⟪op...') so the exact statement can't be read from the manuscript. The accompanying proof text suggests the intended inequality is E[nu] >= (1/(2(1+eta))) Phi(T*) minus a cross-term involving sqrt(max_{|S|<=ell} Phi(S) * Phi(T*)). The reconstruction is consistent with (17) and Lemma 5.1, and the Efron–Stein argument in Lemma D.3 checks out, but a wrong coefficient or sign in that cross-term would break the constant approximation. This needs a careful referee with the actual source file.\n\nAlso worth noting: the authors acknowledge ChatGPT Pro 5.6 generated a draft proof of Theorem 3.5. They say it was rewritten and verified; the proof in the text is short enough to verify by hand, so I don't see this as a red flag, just a small extra verification burden.\n\nCitation pattern is fine. The companion paper (compensation design, Anagnostides et al. 2026) is self-cited heavily, but the new results here are derived from first principles in the text; the reuse is transparent.\n\nBottom line: this deserves a serious referee. If the tail analysis survives scrutiny, it resolves a 15-year-old open problem. Even if the polynomial-time mechanism has issues, the smoothing lemma and the information-theoretic ratios are worth publishing on their own. I'd accept for peer review and would cite the smoothing lemma.","headline":"A strong paper with a genuinely new structural lemma; the polynomial-time mechanism's tail analysis has a corrupted display that needs a careful referee, but the math appears to hold.","tokens_in":51709,"tokens_out":2331,"would_cite":true,"duration_ms":20818,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","68W25","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For subadditive valuations, a universally truthful budget-feasible mechanism achieves a constant approximation (factor C+ε, C below 86.399) in polynomial time via demand queries, refuting the conjecture that constant approximation…","keywords":["budget-feasible mechanism design","compensation design","subadditive valuations","self-bounding functions","smoothing lemma","demand queries","price of stability","universal truthfulness"],"falsifier":"On a small subadditive example such as $v(\\emptyset)=0$, $v(T)=1$ for every nonempty proper $T$, and $v(N)=2$, compute the smoothed value exactly from $\\widetilde{v}(S)=\\sum_{T\\subseteq S}v(T)\\,\\frac{k!(|S|-k)!}{(|S|+1)!}$ and check the identity $\\sum_{i\\in S}(\\widetilde{v}(S)-\\widetilde{v}(S\\setminus\\{i\\}))=v(S)-\\widetilde{v}(S)$ and the variance bound $\\mathrm{Var}(\\widetilde{v}(T^*_0))\\le(\\widetilde{M}_{T^*}/2)\\,\\mathbb{E}[\\widetilde{v}(T^*_0)]$ for the random half $T^*_0$ of any budget-feasible tail $T^*$. A single violated instance of either inequality refutes the factor-2 smoothing claim or the tail concentration (Lemma D.3), and with them the constant-factor potential allocator of Theorem 5.2 and the $C+\\epsilon$ mechanism.","tokens_in":50469,"feed_emoji":"💰","tokens_out":28588,"duration_ms":217518,"temperature":0.7,"pith_summary":"Budget-feasible mechanism design asks how much of the optimal value a buyer can secure from strategic sellers while staying within a hard budget and keeping truthful reporting dominant. The paper's central claim is that for subadditive valuations — the most general complement-free class — a constant factor is achievable, and even computable: for every fixed $\\epsilon>0$, a universally truthful, individually rational, budget-feasible mechanism runs in polynomial time via demand queries and approximates the optimum within a factor $C+\\epsilon$, with $C<86.399$. The engine is an indirect, non-truthful game called compensation design with marginal-contribution payments, whose equilibrium analysis (a constant price of stability) is converted into truthful direct mechanisms. The load-bearing structural discovery is a smoothing lemma: every monotone subadditive valuation is $2$-approximated by a self-bounding function. If the paper is right, the 2011 conjecture that constant approximation requires exponentially many demand queries is false, and the best-known approximation ratios for submodular, XOS, and subadditive valuations all improve.","feed_headline":"Constant-factor truthful procurement runs in polynomial time","feed_subtitle":"First such mechanism for subadditive valuations; it refutes the exponential-query conjecture.","key_machinery":"The argument is carried by the potential function $\\Phi^F_b(S)=F(S)\\prod_{i\\in S}(1-b_i/B)_+$ for a normalized monotone proxy $F$ that is self-bounding, meaning the sum of the final marginal contributions $\\sum_{i\\in S}(F(S)-F(S\\setminus\\{i\\}))$ is at most $F(S)$. A global maximizer of $\\Phi^F_b$ is a pure Nash equilibrium of the game induced by the marginal-contribution payment rule $p^F_i(S)=B\\,(F(S)-F(S\\setminus\\{i\\}))/F(S)$, and the same maximizer, endowed with Myerson threshold payments, becomes a truthful and budget-feasible direct mechanism: an agent whose bid exceeded its marginal payment would break the equilibrium, so thresholds are bounded by marginals, and the self-bounding property bounds the sum of thresholds by the budget. Because subadditive functions need not be self-bounding, the smoothing operator $\\widetilde{v}(S)=\\int_0^1\\mathbb{E}[v(R_q(S))]\\,dq$, which keeps each element of $S$ with probability $q$ and averages over $q$, produces a self-bounding $\\widetilde{v}$ with $\\frac{1}{2}v(S)\\le\\widetilde{v}(S)\\le v(S)$, via the identity $\\sum_{i\\in S}(\\widetilde{v}(S)-\\widetilde{v}(S\\setminus\\{i\\}))=v(S)-\\widetilde{v}(S)$. The polynomial-time implementation approximates the potential by a core-tail decomposition (enumerating the $\\ell$ most expensive agents and handling the light tail through random partitioning, one demand query, and uniform thinning at rate $q=\\nu/v(D)$), an empirically sampled proxy $\\widehat{v}_m$, and a filtering step that certifies budget feasibility of the final threshold payments.","core_discovery":"The paper claims three main results. Without computational constraints, universally truthful budget-feasible mechanisms achieve approximation ratios of $3$ for monotone submodular valuations, $e+1\\approx 3.718$ for nonmonotone submodular and for XOS valuations, and $2e+1\\approx 6.436$ for subadditive valuations, with deterministic large-market versions approaching $2$, $e$, and $2e$; these improve the previous best of $3.798$, $9.742$, $28$, and $33$. For subadditive valuations, a new mechanism (PolyRMC) runs in polynomial time via demand queries and achieves factor $C+\\epsilon$ with $C=1+2e\\rho_0<86.399$, where $\\rho_0\\approx 15.7083$ comes from the potential-approximation analysis; this resolves the long-standing question attached to the Dobzinski–Papadimitriou–Singer conjecture, which asserted that a constant approximation requires exponentially many demand queries. Beyond the complement-free hierarchy, the paper claims an $e\\beta+o_\\lambda(1)$ deterministic approximation for $\\beta$-self-bounding valuations in large markets, and an impossibility result: without the large-market assumption, no universally truthful mechanism achieves a bounded approximation even for $\\beta=2$. The same smoothing lemma yields a $2e$-approximate restrained core for multiwinner elections under subadditive utilities, answering an open question in that literature.","pith_inferences":["The paper says no attempt was made to optimize the constant; since $C=1+2e\\rho_0$ with $\\rho_0\\approx 15.7083$ determined by a single quadratic-combination lemma, tightening that lemma or the core-tail mixing would lower $C$ directly, so the true gap between polynomial-query and exponential-query mechanisms may be far smaller than the distance from $86.4$ to $6.436$.","The smoothing lemma replaces the classical $\\Theta(\\log n)$-distortion embedding of subadditive functions into XOS with a constant-distortion embedding into self-bounding functions; other algorithmic-game-theory problems whose bottleneck is subadditive-to-XOS conversion could inherit this factor-2 substitute, an application the paper only gestures at in its conclusions.","The $\\beta=2$ impossibility rests on an extreme two-agent complementarity instance, so it marks a clean dividing line: constant-factor universal truthfulness lives exactly within the complement-free hierarchy, and any positive result for complements must come from large markets, different solution concepts, or weaker incentive guarantees.","The query count for fixed $\\epsilon$ is a high-degree polynomial — enumerating $O(n^\\ell)$ subsets with $\\ell=\\ell(\\epsilon)$ plus $m=O(n^4(n+\\log(1/\\epsilon))/\\epsilon^2)$ empirical evaluations — so 'polynomial time' here carries parameter dependence the paper does not optimize."],"forward_implications":["The Dobzinski–Papadimitriou–Singer conjecture is false: a constant approximation for subadditive valuations uses only polynomially many demand queries, not exponentially many.","Without computational constraints, universally truthful mechanisms achieve ratios of $3$ (monotone submodular), $e+1$ (XOS and nonmonotone submodular), and $2e+1$ (subadditive), and these become deterministic near-$2$, near-$e$, and near-$2e$ in large markets.","Fair multiwinner elections gain a $2e$-approximate restrained core for subadditive voter utilities, settling an open question about proportionality under general valuations.","For $\\beta$-self-bounding valuations, the paper proves an $e\\beta$ large-market approximation; for $\\beta\\ge 2$, outside large markets, no universally truthful mechanism has a bounded approximation, so the frontier of universal truthfulness runs through the complement-free hierarchy as far as these results go.","Through the monotone closure — whose optimal value equals the original optimum — the XOS and subadditive guarantees extend to nonmonotone valuations, so the improved ratios apply to the full classes claimed."],"supporting_citations":[{"why":"the open problem and conjecture the paper refutes; also the O(log² n) demand-query mechanisms that set the baseline to beat","marker":"Dobzinski, Papadimitriou, and Singer [2011]"},{"why":"introduced the budget-feasible mechanism design model with its full-information benchmark OPT and the truthfulness/budget tension","marker":"Singer [2010]"},{"why":"introduced compensation design, the marginal-contribution payment rule, and the potential function whose maximizer is a pure equilibrium","marker":"Anagnostides et al. [2026]"},{"why":"the source of the self-bounding definition and the concentration machinery (Efron–Stein) behind the tail variance bound","marker":"Boucheron, Lugosi, and Massart [2000]"},{"why":"establishes the Θ(log n) subadditive-to-XOS approximation gap that the factor-2 smoothing lemma bypasses","marker":"Bhawalkar and Roughgarden [2011]"},{"why":"the previous demand-query upper bound (O(log n / log log n)) and the random-partitioning technique the tail branch reuses","marker":"Bei, Chen, Gravin, and Lu [2012]"},{"why":"the previous best explicit mechanisms (28 XOS, 33 subadditive) plus the nonbossy threshold-payment analysis the polynomial implementation adapts","marker":"Neogi, Pashkovich, and Swamy [2024]"},{"why":"the O(log log n) query-efficient mechanism that PolyRMC improves to a constant","marker":"Neogi, Pashkovich, and Swamy [2025]"},{"why":"the threshold-payment characterization that converts monotone allocation rules into dominant-strategy truthful mechanisms","marker":"Myerson [1981]"},{"why":"defined the large-market regime (λ→0) and its tight benchmarks, which the deterministic large-market results target","marker":"Anari, Goel, and Nikzad [2014]"}],"fun_headline_variants":["Constant approximation for subadditive valuations in poly time","Refuting conjecture: constant approximation for subadditive","First poly-time constant-factor mechanism for subadditive","Subadditive valuations: constant approximation, resolves conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polynomial-time mechanism collapses if the smoothed value of a random half of the optimal tail does not concentrate as claimed: the proof needs the variance of that random half to be at most half its typical value times the largest single-item smoothed value (Lemma D.3), and the displayed statement of the lemma that converts this into a usable lower bound (Lemma 5.6) appears corrupted in the provided text, making this the hardest premise to verify.","fun_headline_variants_meta":{"raw":{"variants":["Constant approximation for subadditive valuations in poly time","Refuting conjecture: constant approximation for subadditive","First poly-time constant-factor mechanism for subadditive","Subadditive valuations: constant approximation, resolves conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2983,"prompt_tokens":1210,"completion_tokens":1773,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":826,"completion_tokens_details":{"reasoning_tokens":1710}},"tokens_in":826,"tokens_out":1773,"duration_ms":13887,"temperature":1.0,"reasoning_tokens":1710,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:40:30.771770+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small subadditive example such as $v(\\emptyset)=0$, $v(T)=1$ for every nonempty proper $T$, and $v(N)=2$, compute the smoothed value exactly from $\\widetilde{v}(S)=\\sum_{T\\subseteq S}v(T)\\,\\frac{k!(|S|-k)!}{(|S|+1)!}$ and check the identity $\\sum_{i\\in S}(\\widetilde{v}(S)-\\widetilde{v}(S\\setminus\\{i\\}))=v(S)-\\widetilde{v}(S)$ and the variance bound $\\mathrm{Var}(\\widetilde{v}(T^*_0))\\le(\\widetilde{M}_{T^*}/2)\\,\\mathbb{E}[\\widetilde{v}(T^*_0)]$ for the random half $T^*_0$ of any budget-feasible tail $T^*$. A single violated instance of either inequality refutes the factor-2 smoothing claim or the tail concentration (Lemma D.3), and with them the constant-factor potential allocator of Theorem 5.2 and the $C+\\epsilon$ mechanism.","supporting_citations":[],"review_version":3}