{"id":"055d4aec-9d32-4b2a-a073-eb250e18fc73","arxiv_id":"2505.16054","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For XOS buyers with k copies per item, supply-based posted pricing obtains a 1-(k/(k+1))^k competitive ratio, and dynamic pricing obtains 1-O(sqrt(log k/k)).","lead":"This paper analyzes sequential posted-price mechanisms in multi-unit combinatorial auctions where buyers have XOS valuations, deriving welfare guarantees that improve with the number k of copies of each item. It shows supply-based prices achieve a 1-(k/(k+1))^k competitive ratio and dynamic prices match the single-item benchmark asymptotically.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's 'strictly harder' claim is explicitly conjectural in §5, and Corollary 2's equality is not supported by Theorem 3.","rationale":"The reader's verdict was CONDITIONAL, with the weakest assumption focusing on the need for exact SW_j and the lack of a complexity argument for computing it. My stress-test identifies a different but equally serious issue: the manuscript itself concedes in Section 5 that the 'strictly harder' claim is only a conjecture, directly contradicting the abstract and introduction, which present it as a proven result. Additionally, Corollary 2's equality claim lacks a valid upper-bound proof: Theorem 3 only shows an information-restricted lower bound against mechanisms that know only ExAnteOpt, not the full competitive-ratio bound against all supply-based pricings. Both issues are explicitly locatable in the text and do not require external assumptions. They do not change the overall verdict, which remains CONDITIONAL: the paper contains a novel and plausibly correct supply-based pricing construction, but the advertised exact tightness and the strict separation result are not established by the current proofs. The concrete tests would settle whether the strict separation holds numerically and whether the Theorem 3 family can be strengthened to a true upper bound.","tokens_in":33611,"tokens_out":26991,"duration_ms":238837,"concrete_test":"Numerically compute τ_k and τ̂_k for k=2,...,1000 with high-precision arithmetic using the definitions in Theorems 9 and 10, verifying the claimed strict inequality; if it holds, the inequality remains a conjecture unless a formal proof is supplied. Separately, for k=2, enumerate the family F of instances constructed in the proof of Theorem 3 (Appendix B) and compute, for each instance, the optimal supply-based pricing and its welfare; if any instance's optimal welfare exceeds (1-(2/3)^2)·2k, then that family does not establish the upper bound in Corollary 2, confirming the proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline claim that the multi-unit combinatorial setting is strictly harder than the single-item setting (stated as 'We show...' in the abstract and Introduction) is not a theorem. Section 5 defines τ_k and τ̂_k and then states: 'We conjecture that τ̂_k < τ_k for every k ≥ 2, but were not able to prove this formally.' The provided Theorem 10 gives only an upper bound τ̂_k for the two-item unit-demand static-pricing ratio; the strict inequality is verified numerically for k up to 1000, not proven. Likewise, Corollary 2 claims CompRatio(SuppIP,k) = 1-(k/(k+1))^k, but the proof of the upper bound (Theorem 3) only shows that for each supply-based pricing vector p there exists an instance D_p where p performs poorly. It does not exhibit a single instance where every supply-based pricing performs poorly, which is what the competitive-ratio definition requires. Thus the abstract overstates a conjecture as a theorem, and the claimed exact ratio for supply-based pricing is unsupported by the supplied proofs.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies multi-unit combinatorial prophet inequalities for XOS buyers. It distinguishes static item pricing, supply-based static pricing, dynamic item pricing, and general online allocation, and derives competitive-ratio guarantees against the ex-ante LP benchmark. The main positive result (Theorem 1) constructs a supply-based static pricing, using only per-item welfare contributions of a feasible ex-ante solution, with expected welfare at least 1 - (k/(k+1))^k times the LP objective; Theorem 4 gives a dynamic pricing with ratio 1 - O(sqrt(log k / k)); Appendix A gives an online allocation matching the single-item rate 1 - 1/sqrt(k+3). The paper also claims, in Corollary 2, that the supply-based ratio is exactly 1 - (k/(k+1))^k, and claims in the abstract and introduction that the multi-unit combinatorial setting is strictly harder than the single-item setting for static pricing, with a two-item unit-demand construction in Section 5.","tokens_in":33748,"tokens_out":14348,"duration_ms":140545,"significance":"If the positive results are correct, they materially advance the multi-unit combinatorial prophet-inequality literature: Theorem 1 beats the 1/2 barrier for static-type pricing in XOS settings, and Theorem 4 shows that dynamic item pricing can recover the single-item asymptotic rate. Theorem 1's derivation is elegant and self-contained, and the paper is careful to prove guarantees against the stronger ex-ante benchmark rather than only the prophet benchmark. The reduction in Appendix A and the martingale concentration argument in Section 4 are also useful contributions. However, two headline claims currently exceed what the proofs establish: the exact competitive ratio for supply-based pricing is not proved under the paper's own definition, and the strict-hardness gap is explicitly left as a conjecture in Section 5. These overclaims affect the framing of the paper and must be corrected before publication.","major_comments":[{"comment":"The claimed equality CompRatio(SuppIP,k) = 1 - (k/(k+1))^k is not supported by the supplied proofs. Theorem 1 gives a lower bound, but the upper-bound direction in Theorem 3 has the wrong quantifier structure: it shows that for every supply-based pricing vector p there exists an instance D_p in a family F with low welfare for that p. The competitive-ratio definition in Section 2.4 instead requires a single instance (or a minimax argument) on which every supply-based pricing performs poorly. Moreover, the 'knows only the value of ExAnteOpt' information model in Theorem 3 is not the model of Section 2.4, where the mechanism knows the full distribution D. Corollary 2 should be weakened to an achievability statement, or the upper bound must be proved under the Section 2.4 definition.","section":"Section 3, Corollary 2 and Theorem 3"},{"comment":"The abstract and Introduction item 1 state as a theorem that static item pricing in the multi-unit combinatorial setting is strictly harder than in the single-item setting. Section 5 explicitly says: 'We conjecture that tau-hat_k < tau_k for every k >= 2, but were not able to prove this formally.' Theorem 10 only establishes an upper bound tau-hat_k for two-item unit-demand instances, Table 1 gives values for k <= 11, and the text reports numerical verification up to k = 1000. None of these constitutes a proof of the strict gap. Please rephrase these statements as a conjecture supported by numerical evidence, or provide a formal proof of the inequality for all k.","section":"Abstract, Section 1, and Section 5"},{"comment":"The theorem as stated assumes exact knowledge of SW_j for every item j, and the proof's per-copy balance identity after Eq. (2) uses the exact SW_j and the exact coefficients alpha_{j,c}. The abstract and Introduction, however, promise that merely an estimate of the per-item welfare contribution suffices, and no theorem states or proves robustness to estimation error. In addition, the claim that the pricing is 'efficiently computable' is not backed by a complexity argument: the EA-Opt LP has exponentially many variables over bundles, and the XOS support can be exponentially large. Please provide a precise computational model (oracle model or explicitly given feasible solution x), and either add a formal estimation-robustness result or remove the estimate claim from the abstract and introduction.","section":"Section 3, Theorem 1 and the abstract's information claim"}],"minor_comments":[{"comment":"The sentence that the difference between tau_k and tau-hat_k 'appears within the first four decimal digits' is vague; since these are numerical evaluations, please state explicitly which quantities are rigorously proved and which are computed, and describe the numerical method and error bounds used.","section":"Section 5, Table 1"},{"comment":"The notation for prices is inconsistent across the paper: in Section 3, alpha_{j,c} is a unitless fraction and the actual price is alpha_{j,c} * SW_j, while in Appendix B the symbol p_c appears to be an absolute price normalized against the per-unit welfare 2k. Please state the normalization of SW_j and of the prices p_c explicitly so that the inequalities in Appendix B can be checked.","section":"Section 3 and Appendix B"},{"comment":"Lemma 5 asserts that there exist prices and a tie-breaking rule such that the buyer chooses S with probability y*_{v,S}. The proof claims strict inequality v_i(S') - sum rho_j < psi_{v_i} for all S' with y*_{v_i,S'}=0, but complementary slackness and dual feasibility give only <=. Please clarify how ties among utility-maximizing sets are handled without changing the distributional guarantee.","section":"Section 4, Lemma 5 and Algorithm 1"},{"comment":"Lemma 6 is stated for the final remaining set R_{n+1}, but Lemma 8 needs the bound for the remaining set R_i at buyer i's arrival. The implication Pr[j in R_i] >= Pr[j in R_{n+1}] is true by monotonicity but is not stated; adding it would make the proof easier to follow.","section":"Section 4, Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The paper's core positive results are worth publishing if the overclaims are fixed. The authors should either prove the exact competitive-ratio upper bound under the standard full-distribution model or clearly restate Corollary 2 as an achievability result, and they should present the strict-hardness gap as a conjecture rather than a theorem. I would also ask the authors to double-check the construction in Appendix B, since the relationship between the claimed value ExAnteOpt = 2k and the described fractional solution requires clarification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The supply-based pricing result is the real contribution: Theorem 1's per-copy price schedule giving 1-(k/(k+1))^k against the ex-ante benchmark is a clean generalization of Feldman et al.'s balancing argument, and the proof checks out. The dynamic pricing and online-allocation results are also new and plausible. But the paper's headline claims overshoot the proofs.\n\nThe abstract's statement that the multi-unit setting is strictly harder than single-item is a conjecture, not a theorem: Section 5 says 'We conjecture that \\hat{\\tau}_k < \\tau_k for every k \\ge 2, but were not able to prove this formally.' The construction and numerical evidence are legitimate, but 'we show' in the abstract is too strong. Also Corollary 2's equality CompRatio(SuppIP,k) = 1-(k/(k+1))^k is not supported. Theorem 1 gives the lower bound. The upper bound (Theorem 3) only shows that for each supply-based pricing vector p there exists an instance D_p in F where p does poorly; it does not exhibit a single instance where every supply-based pricing does poorly, which is what the competitive ratio of the class requires. So the equality should be dialed back to a lower bound plus a separate information-restricted tightness statement.\n\nThird, the abstract says merely an estimate of SW_j suffices, but no theorem analyzes approximate SW_j; the proof uses exact values. That should be fixed or retracted. The 'efficiently compute' claim in Theorem 1 also lacks a complexity argument, since EA-Opt has exponentially many variables; presumably one needs implicit representation, and that is not discussed.\n\nWhat the paper does well: the per-copy balancing idea is genuinely new and should work; the dynamic pricing result removes restrictive assumptions of Chawla et al. 2017; and the online reduction to single-item prophet inequalities via item-wise marginals is elegant. The numerical support for \\hat{\\tau}_k < \\tau_k is suggestive, but it is not a proof.\n\nBottom line: this deserves a serious referee. The core theorem is likely correct and useful to the prophet-inequality community. But the abstract and Corollary 2 need to be rewritten so that conjectures and information-restricted lower bounds are labeled as such. I'd send it to a suitably careful venue and ask for a revision.","headline":"Solid supply-based pricing theorem, but the abstract and Corollary 2 overstate what is proven: the 'strictly harder' gap is a conjecture and the competitive-ratio equality lacks support.","tokens_in":34353,"tokens_out":2722,"would_cite":true,"duration_ms":24573,"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":"This paper shows that supply-based static pricing—prices fixed in advance but increasing with each copy sold—achieves a $1-(k/(k+1))^k$ competitive ratio against the ex-ante optimal social welfare in multi-unit combinatorial auctions with…","keywords":["prophet inequalities","combinatorial auctions","XOS valuations","multi-unit supply","posted pricing","social welfare","competitive ratio","ex-ante optimal"],"falsifier":"On a small enumerated instance with two items and $k=2$, compute the Theorem 1 prices from the optimal ex-ante LP, simulate every arrival order, and compare welfare with the LP value; a ratio below $5/9$ would refute the main theorem. For the asserted exactness, compare against the best supply-based pricing chosen with full distribution knowledge on the same instances: exceeding $5/9$ would refute the equality in Corollary 2.","tokens_in":33369,"feed_emoji":"🛒","tokens_out":11030,"duration_ms":95446,"temperature":0.7,"pith_summary":"Multi-unit combinatorial auctions with fractionally subadditive (XOS) buyers have a known 1/2 barrier for posted prices when each item has one copy. This paper establishes that the barrier breaks once each item has k copies: a non-adaptive supply-based price list, with prices that increase per copy sold, attains at least $1-(k/(k+1))^k$ of the ex-ante optimal social welfare, and this ratio increases with k toward $1-1/e$. The prices depend only on each item's expected welfare contribution in an optimal ex-ante allocation, not on full value distributions. The paper also shows dynamic prices reach $1-O(\\sqrt{\\log k/k})$, matching single-item static pricing asymptotically, while fully static prices are strictly weaker in the combinatorial setting.","feed_headline":"Supply-based prices beat the 1/2 welfare barrier as k grows","feed_subtitle":"Non-adaptive posted prices with k copies of each item guarantee a 1-(k/(k+1))^k share of optimal welfare.","key_machinery":"The carrying object is the copy-dependent price schedule $\\alpha_{j,c} = (1/k_j)(k_j/(k_j+1))^{k_j+1-c}$ applied to $SW_j$, the contribution of item j to the ex-ante LP objective via supporting additive functions of XOS valuations. The analysis splits per-item welfare into seller revenue and buyer utility; the schedule makes the sum flat across the number of copies sold, so every trajectory contributes the same fraction $1-(k/(k+1))^k$. The dynamic-pricing result replaces this with a scaled-down ex-ante LP and per-round dual prices, with a martingale concentration inequality controlling the probability that any single item sells out.","core_discovery":"The central discovery is a per-copy balancing identity for supply-based posted pricing. Given any feasible solution x to the ex-ante LP, define SW_j as item j's contribution to the LP objective using the additive support of XOS valuations, and price the c-th copy at $\\alpha_{j,c} SW_j$ where $\\alpha_{j,c}=(1/k_j)(k_j/(k_j+1))^{k_j+1-c}$. Revenue from sold copies grows convexly while buyer utility falls concavely in the number of copies sold; the schedule makes each copy contribute the same fraction of SW_j, so every arrival order gets at least $1-(k/(k+1))^k$ of the LP value. The paper claims this ratio is exactly the competitive ratio of supply-based pricing, and that dynamic item pricing attains $1-O(\\sqrt{\\log k/k})$, while general online allocation attains $1-1/\\sqrt{k+3}$.","pith_inferences":["The paper's abstract says an estimate of $SW_j$ suffices, but Theorem 1 is proved only for exact values; quantifying how pricing error degrades the ratio is a natural next step and would make the mechanism practical.","The static-pricing gap already appears with two items, suggesting the obstruction is substitution between items rather than market size; testing whether the formula for $\\hat\\tau_k$ extends to more items would show whether the two-item bound is universal.","The per-copy balance construction is stated for welfare and XOS valuations; the same revenue/utility splitting may transfer to revenue objectives or to subadditive valuations that admit additive certificates, though the paper does not claim this.","Corollary 2's exact equality is supported on one side by an information-limited lower bound; a full-information lower bound would be needed to rule out better supply-based prices that use the whole distribution."],"forward_implications":["For k copies of each item, the supply-based schedule gives a $1-(k/(k+1))^k$ approximation to the ex-ante optimum, hence to the prophet benchmark.","As $k\\to\\infty$ the ratio tends to $1-1/e$, so additional supply translates into a concrete welfare guarantee above the single-copy 1/2.","Dynamic item pricing reaches $1-O(\\sqrt{\\log k/k})$, asymptotically matching the best static pricing for a single item with k units.","General online allocation reaches $1-1/\\sqrt{k+3}$, matching the single-item benchmark, so allowing arbitrary online decisions removes the combinatorial hardness.","When buyers can demand multiple units, capped at $k_j/\\ell$ of each item, the same construction gives $1-(\\ell/(\\ell+1))^\\ell$."],"supporting_citations":[{"why":"Establishes the 1/2-competitive static item pricing for XOS buyers via revenue/utility splitting, which the supply-based construction refines per copy.","marker":"Feldman et al. (2014)"},{"why":"Provides the single-item multi-unit rounding bound used as a black box for the online allocation result.","marker":"Alaei (2014)"},{"why":"Gives the tight single-item static pricing framework and the minimax technique used to construct the two-item gap.","marker":"Jiang et al. (2023)"},{"why":"Supplies the single-item static pricing ratio that the combinatorial static pricing bound is compared against.","marker":"Chawla et al. (2024)"},{"why":"Introduces the scaled-down ex-ante LP and dual-price approach underlying the dynamic pricing algorithm.","marker":"Chawla et al. (2017)"},{"why":"Contributes the martingale concentration inequality used to bound the probability any item sells out.","marker":"Fan et al. (2015)"},{"why":"Initiates k-unit single-item prophet inequalities and motivates the supply-dependent pricing question.","marker":"Hajiaghayi et al. (2007)"}],"fun_headline_variants":["Supply-based pricing hits 1-(k/(k+1))^k welfare ratio","Non-adaptive pricing improves with more copies of each item","Copy-count pricing beats the static single-item barrier","Pricing per copy yields tight prophet inequality for XOS","More copies, better welfare: supply-based prices work"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem requires exact knowledge of each item's expected welfare contribution $SW_j$ in an optimal ex-ante allocation; the advertised use of mere estimates is not analyzed, and without exact values the per-copy balance that produces the ratio can break.","fun_headline_variants_meta":{"raw":{"variants":["Supply-based pricing hits 1-(k/(k+1))^k welfare ratio","Non-adaptive pricing improves with more copies of each item","Copy-count pricing beats the static single-item barrier","Pricing per copy yields tight prophet inequality for XOS","More copies, better welfare: supply-based prices work"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000646,"raw_usage":{"total_tokens":2972,"prompt_tokens":953,"completion_tokens":2019,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":1935}},"tokens_in":569,"tokens_out":2019,"duration_ms":12240,"temperature":1.0,"reasoning_tokens":1935,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:09:19.720240+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small enumerated instance with two items and $k=2$, compute the Theorem 1 prices from the optimal ex-ante LP, simulate every arrival order, and compare welfare with the LP value; a ratio below $5/9$ would refute the main theorem. For the asserted exactness, compare against the best supply-based pricing chosen with full distribution knowledge on the same instances: exceeding $5/9$ would refute the equality in Corollary 2.","supporting_citations":[],"review_version":1}