{"id":"486bc914-e5e5-45b0-8ff0-2b1d58678392","arxiv_id":"2607.04027","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"First poly-time approximation algorithms for sequential posted pricing under known/random deadlines with independent or correlated valuations, including a tight (1-1/e) for known-horizon correlated values.","lead":"This paper gives the first approximation algorithms for maximizing revenue when a seller posts sequential take-it-or-leave-it prices under a hard deadline, allowing both random deadlines and arbitrarily correlated buyer values. The results map a practically common sales process (housing pre-market, ad mediation) onto tractable combinatorial optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader's identification of the strongest claim is accurate, and the supporting lemmas (1, 9) and theorems (1-2) form a self-contained combinatorial reduction that does not rely on independence or special horizon structure. The non-adaptivity remark is correctly flagged as an assumption used throughout, but it is standard and does not create a correctness risk for the known-horizon claim: once earlier calls have failed, the remaining problem is again a fixed-horizon sequential pricing instance on the residual set, so fixed sequences suffice. The hardness reduction is approximation-preserving and standard. Weaker regimes (unknown horizons) receive matching upper/lower bounds that are carefully scoped; none of those weaker results is needed for the strongest claim. No free parameters, no circularity, and the full proofs are present. Therefore the ACCEPT verdict stands without adjustment.","tokens_in":37448,"tokens_out":458,"duration_ms":4827,"concrete_test":"Independently re-derive the pointwise characterization in the proof of Lemma 9: confirm that for every valuation realization v, Rev_infty(pi_d(S);v) equals max_{e in S} r_e * 1{v_{i_e} >= r_e} (empty max = 0), and that this max function is monotone submodular; if either step fails for some v or S, the reduction collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim (known-horizon correlated valuations reduce to monotone submodular maximization under a matroid via decreasing-price order, yielding tight 1-1/e) is supported by a clean argument. Lemma 1 shows decreasing-price is pointwise optimal for any realization; Lemma 9 shows the induced set function is pointwise max of accepted prices, hence monotone and submodular; the horizon and single-call constraints form a matroid (Theorem 1). Hardness via weighted Max-k-Coverage (Theorem 2) matches. Remark 1 (non-adaptivity) is standard for probe-and-commit models and does not undermine the reduction. No hidden assumption or gap appears load-bearing for this claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies revenue-maximizing sequential posted pricing of a single item under an exogenous deadline (known or random horizon) with buyer valuations that may be independent or arbitrarily correlated. The central technical contribution is a suite of polynomial-time approximation algorithms: a tight (1-1/e)-approximation for known horizons under arbitrary correlation via a decreasing-price reduction to monotone submodular maximization under a matroid (Theorems 1–2, Corollary 1); a deterministic 1/4-approximation and a randomized (1/2-ε)-approximation for unknown horizons with independent valuations (Theorems 3–4); a (1-1/e) guarantee for geometric horizons with independent valuations (Theorem 5); a 1/4(1-1/e) guarantee for IFR horizons under correlation (Theorem 6); and a tight Θ(1/log M) guarantee for fully general horizons under correlation (Theorem 7). Supporting structure includes a pruned evaluator with reverse-time submodular order, a density-threshold MILP with OCRS-style attenuation, and matching hardness/tightness examples.","tokens_in":37612,"tokens_out":797,"duration_ms":7434,"significance":"If the claims hold, the paper supplies the first systematic approximation landscape for deadline-constrained sequential pricing beyond the independent known-horizon special cases already treated by stochastic-probing PTAS/EPTAS results. The known-horizon correlated reduction is particularly clean: decreasing-price order is pointwise optimal (Lemma 1), the induced set function is pointwise the maximum accepted price and therefore monotone submodular (Lemma 9), and hardness matches via weighted Max-k-Coverage (Theorem 2). The independent unknown-horizon algorithms recover constant factors via a pruned submodular-order objective and a carefully designed MILP+attenuation scheme whose 1/2 gap is shown tight (Example 3). The logarithmic result for general correlated unknown horizons is likewise tight for the natural multi-scale greedy (Example 7). These are standard, black-box combinatorial-optimization reductions with complete appendix proofs; they constitute a solid contribution to algorithmic mechanism design and stochastic selection.","major_comments":[],"minor_comments":[{"comment":"Tables 1–2 are helpful but the footnote on Brubach et al. (2025) could more explicitly flag that their 1/2 result is for weighted Bernoulli valuations only, so the present (1/2-ε) for general independent valuations is a genuine extension.","section":null},{"comment":"Remark 1 (non-adaptivity WLOG) is standard for probe-and-commit models; a one-sentence pointer to the analogous argument in the stochastic-probing literature would help readers less familiar with that literature.","section":null},{"comment":"In §5.2.2 the density-threshold structure (Lemma 3) and the subsequent EPTAS invocation for budgeted matroid intersection are correct, but the dummy-call augmentation and the “distinct densities by perturbation” argument could be stated more formally in the main text rather than only in the appendix.","section":null},{"comment":"Example 1 (non-monotonicity/non-submodularity of the raw time-indexed objective) is useful; placing a short pointer to it earlier in §4 would clarify why the order-first reduction is necessary.","section":null},{"comment":"Minor typographical issues: “amulti-call auction” (p. 1), occasional missing spaces around math operators, and a few long sentences in the introduction that could be broken for readability.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and the approximation landscape is cleanly mapped. Fit for a strong math.OC / algorithmic-economics venue is good. No novelty or citation concerns; the relation to Brubach et al., Segev–Singla, and the classic SPM literature is accurately described."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper fills a real gap. For sequential take-it-or-leave-it offers with an exogenous deadline, it gives the first poly-time approximations across the full matrix of known/random horizons and independent/correlated values, with matching hardness where it claims tightness.\n\nThe cleanest result is the known-horizon correlated case. Decreasing-price order is pointwise optimal (Lemma 1); under that order the revenue set function is just the max accepted price, so monotone and submodular (Lemma 9); feasibility is a matroid. Continuous greedy + pipage therefore gives 1-1/e, and the Max-k-Cover reduction shows you cannot do better unless P=NP. That argument is transparent and the hardness matches. Non-adaptivity (Remark 1) is standard for probe-and-commit and does not undercut the reduction.\n\nBeyond that, the independent unknown-horizon work is careful: pruning restores a reverse-time submodular order for a deterministic 1/4, and a density-threshold MILP plus half-attenuation gives 1/2-eps with a matching gap example. Geometric horizons recover full 1-1/e via the score order; IFR correlated gets a constant via the median; arbitrary correlated horizons get Theta(1/log M) by best-of-greedy, again with a matching lower-bound family. The tables make the landscape easy to read.\n\nSoft spots are minor and mostly flagged. The multi-call reduction and oracle model are standard; the open constant-factor question for fully general correlated + arbitrary horizons is stated honestly. No free parameters, no circularity, proofs and tightness examples are in the appendices.\n\nThis is for people who work on sequential posted pricing, stochastic probing, or revenue management under deadlines. It deserves a serious referee. I would engage with it and cite the known-horizon reduction and the independent-horizon algorithms.","headline":"Clean first map of deadline-constrained sequential pricing: tight 1-1/e for known-horizon correlated values, solid constants elsewhere, and matching hardness.","tokens_in":38191,"tokens_out":488,"would_cite":true,"duration_ms":5717,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","68W25","91B26"],"pacs":[],"model":"grok-4.5","headline":"Sequential posted-price sales with deadlines admit the first constant-factor revenue approximations, even with correlated buyers.","keywords":["sequential posted pricing","deadlines","correlated valuations","submodular maximization","matroid","contention resolution","random horizon","approximation algorithms"],"falsifier":"Exhibit a known-horizon correlated instance whose optimal adaptive policy earns more than a (1-1/e+ε) fraction of the decreasing-price optimum, or a random-horizon independent instance whose optimum exceeds twice the mixed-integer relaxation, contradicting the claimed tightness and gap results.","tokens_in":38350,"feed_emoji":"⏱️","tokens_out":590,"duration_ms":5847,"temperature":0.7,"pith_summary":"A seller must sell one item by making take-it-or-leave-it price offers one buyer at a time before an exogenous deadline ends the opportunity. Deadlines may be fixed or random, and buyer values may be independent or arbitrarily correlated. The paper shows that, despite NP-hardness, polynomial-time algorithms can still guarantee a constant fraction of optimal expected revenue in every regime. The key insight for known deadlines is that offering selected prices in decreasing order turns the revenue objective into a monotone submodular function under a simple matroid constraint, immediately giving a tight (1-1/e) guarantee. For random deadlines the same ordering no longer works universally, so the authors develop new pruning, mixed-integer relaxation, and multi-scale greedy methods that recover constant or logarithmic factors depending on independence and horizon structure. The results supply the first systematic approximation landscape for this practically common sales process.","feed_headline":"Deadlines and correlated buyers still allow constant-factor pricing","feed_subtitle":"First approximation algorithms cover fixed or random horizons and independent or correlated values","key_machinery":"Decreasing-price order-induced set function: once every feasible set of offers is evaluated only under nonincreasing prices, expected revenue becomes a monotone submodular set function under a matroid, reducing known-horizon revenue maximization to a classical combinatorial optimization problem.","core_discovery":"When the number of allowed offers is known in advance, any set of buyer-price pairs should be executed in decreasing-price order; under that canonical order the expected-revenue objective becomes monotone and submodular subject to a partition matroid, so continuous greedy plus pipage rounding yields a (1-1/e)-approximation that is optimal unless P=NP. Parallel constant-factor and logarithmic-factor algorithms are obtained for random horizons by imposing reverse-time submodular order, solving a mixed-integer upper bound and attenuating it, or taking the best of many deterministic greedy solutions.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Fixed deadlines yield (1-1/e) sequential pricing even with buyer correlations","Decreasing-price order makes revenue monotone submodular under matroid constraints","First approx algorithms for sequential prices with fixed or random deadlines","Random horizons admit constant/log factors via reverse-time submodular order","Correlated values and deadlines still allow constant-factor revenue maximization"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The seller never gains by changing future offers after seeing earlier rejections; fixed sequences are already optimal.","fun_headline_variants_meta":{"raw":{"variants":["Fixed deadlines yield (1-1/e) sequential pricing even with buyer correlations","Decreasing-price order makes revenue monotone submodular under matroid constraints","First approx algorithms for sequential prices with fixed or random deadlines","Random horizons admit constant/log factors via reverse-time submodular order","Correlated values and deadlines still allow constant-factor revenue maximization"]},"model":"grok-4.5","effort":"low","cost_usd":0.0059,"raw_usage":{"total_tokens":1490,"prompt_tokens":664,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":59000000,"prompt_tokens_details":{"text_tokens":664,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":750,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":664,"tokens_out":76,"duration_ms":5663,"temperature":1.0,"reasoning_tokens":750,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T22:12:35.590880+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a known-horizon correlated instance whose optimal adaptive policy earns more than a (1-1/e+ε) fraction of the decreasing-price optimum, or a random-horizon independent instance whose optimum exceeds twice the mixed-integer relaxation, contradicting the claimed tightness and gap results.","supporting_citations":[],"review_version":1}