Pith. sign in

REVIEW 5 minor 28 references

Sequential Pricing with Deadlines and Correlated Buyers

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sequential posted-price sales with deadlines admit the first constant-factor revenue approximations, even with correlated buyers.

desk verdict Clean first map of deadline-constrained sequential pricing: tight 1-1/e for known-horizon correlated values, solid constants elsewhere, and matching hardness. read the letter →

arxiv 2607.04027 v1 pith:6YBSQ2OM submitted 2026-07-04 math.OC

Shruti Penumatsa , Rajan Udwani This is my paper · ORCID
classification math.OC MSC 90C2768W2591B26
keywords sequentialpostedpricingdeadlinescorrelatedvaluationssubmodularmaximizationmatroidcontentionresolutionrandomhorizonapproximationalgorithms
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

The seller never gains by changing future offers after seeing earlier rejections; fixed sequences are already optimal.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: approximation guarantees are derived from structural lemmas plus standard black-box combinatorial optimization, not from self-definitional or fitted constructions.

full rationale

The paper’s load-bearing claims are algorithmic approximation ratios for sequential posted pricing under deadlines. The central known-horizon result (Theorems 1–2, Corollary 1) is self-contained: Lemma 1 proves decreasing-price order is pointwise optimal for any valuation realization; Lemma 9 shows the induced set function equals the max accepted price and is therefore monotone and submodular; feasibility is a matroid; continuous greedy + pipage rounding (Calinescu et al.) yields 1−1/e; hardness is reduced from Feige’s weighted Max-k-Coverage. For unknown horizons, the 1/4-approximation proves that a pruned evaluator G is monotone, subadditive, and reverse-time submodular-ordered (Lemmas 2, 10–12), then invokes the directed local-search black box of Udwani (2025)—a general algorithmic result, not a uniqueness theorem that forces the present ratios. The (1/2−ε) result builds an explicit MILP upper bound, solves it via breakpoint guessing + EPTAS for budgeted matroid intersection, and attenuates with a unit-capacity OCRS argument (Alaei); tightness is shown by an explicit gap example, not by construction of the claim. Geometric and IFR special cases similarly reduce to monotone submodularity or median scaling with independent proofs. There are no fitted parameters, no self-definitional identities equating outputs to inputs, and no load-bearing uniqueness imported from overlapping authors. Self-citation to Udwani (2025) is ordinary use of a prior algorithmic framework and does not make the claimed ratios circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The results rest on standard combinatorial-optimization primitives plus a small set of modeling axioms that isolate the computational problem (non-adaptivity WLOG, threshold acceptance, known distributions, single-call restriction). No free parameters are fitted; the invented technical objects (pruned evaluator G, density breakpoint, reverse-time order) are definitional tools with independent combinatorial meaning.

assumptions (5)
  • domain assumption Non-adaptivity is without loss: fixed sequences achieve the same revenue as adaptive policies (Remark 1).
    Used to restrict the search space to non-adaptive plans throughout Sections 3-6.
  • domain assumption Buyers accept if and only if valuation ≥ posted price (threshold rule), even under multi-call (Remark 2).
    Isolates the computational problem from strategic delay; stated explicitly for multi-call special case.
  • domain assumption Value and horizon distributions are known and mutually independent; oracle access to expected revenue under correlation.
    Standard Bayesian assumption; oracle model for correlated case is treated as exact (Section 3).
  • standard math Continuous greedy + pipage rounding yields (1-1/e) for monotone submodular maximization under matroid (Calinescu et al. 2011).
    Black-box used for known-horizon and geometric-horizon results (Corollary 1, Theorem 5).
  • standard math Weighted Max-k-Coverage is NP-hard to approximate better than 1-1/e (Feige 1998).
    Imported for tightness of the known-horizon correlated result (Theorem 2).
invented entities (2)
  • Pruned evaluator G on time-indexed ground set
    purpose: Restores monotonicity and reverse-time submodular order for independent unknown-horizon case.
    Defined in Section 5.1.2; purely algorithmic construct with no external physical claim.
  • Density-threshold MILP with breakpoint element
    purpose: Upper-bounds OPT under independent unknown horizons and enables EPTAS + half-attenuation rounding.
    Formulated in Section 5.2.1; combinatorial relaxation, not a new physical object.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sequential Pricing with Deadlines and Correlated Buyers." pith.science (2026). https://pith.science/paper/6YBSQ2OM

@misc{pith2026260704027,
  author       = {Pith},
  title        = {Pith review of: Sequential Pricing with Deadlines and Correlated Buyers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6YBSQ2OM}},
  note         = {Machine review of arXiv:2607.04027}
}
read the original abstract

We study sequential posted pricing for selling a single item under an exogenous deadline: a seller makes take-it-or-leave-it price offers to buyers one at a time, stopping when some buyer accepts or the selling opportunity expires. We consider both deterministic deadlines and random deadlines drawn from a known distribution, and allow buyer valuations to be either independent or arbitrarily correlated. Despite its practical relevance, this collection of deadline-constrained sequential pricing models has received limited algorithmic study beyond special cases. We develop the first approximation algorithms for revenue maximization across these settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references

  1. [1]

    SIAM Journal on Computing , volume =

    Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers , author =. SIAM Journal on Computing , volume =. 2014 , doi =

    2014

  2. [2]

    Budgeted matching and budgeted matroid intersection via the gasoline puzzle , journal =

    Berger, Andr. Budgeted matching and budgeted matroid intersection via the gasoline puzzle , journal =. 2011 , doi =

    2011

  3. [3]

    Operations Research , volume =

    Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience , author =. Operations Research , volume =. 2025 , doi =

    2025

  4. [4]

    SIAM Journal on Computing , volume =

    Maximizing a monotone submodular function subject to a matroid constraint , author =. SIAM Journal on Computing , volume =. 2011 , publisher =

    2011

  5. [5]

    International Workshop on Internet and Network Economics (WINE) , pages =

    Approximation schemes for sequential posted pricing in multi-unit auctions , author =. International Workshop on Internet and Network Economics (WINE) , pages =. 2010 , organization =

    2010

  6. [6]

    Proceedings of the forty-second ACM symposium on Theory of computing (STOC) , pages =

    Multi-parameter mechanism design and sequential posted pricing , author =. Proceedings of the forty-second ACM symposium on Theory of computing (STOC) , pages =. 2010 , publisher =

    2010

  7. [7]

    Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures , booktitle =

    Chekuri, Chandra and Vondr. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures , booktitle =. 2010 , pages =

    2010

  8. [8]

    Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding , booktitle =

    Chekuri, Chandra and Vondr. Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding , booktitle =. 2011 , publisher =

    2011

Show all 28 references
  1. [9]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Combinatorial multi-armed bandit with general reward functions , author =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  2. [10]

    50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , series =

    Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas , title =. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , series =. 2023 , publisher =

    2023

  3. [11]

    Operations Research , volume =

    Selection and Ordering Policies for Hiring Pipelines via Linear Programming , author =. Operations Research , volume =. 2024 , doi =

    2024

  4. [12]

    Journal of the ACM , volume =

    A threshold of ln n for approximating set cover , author =. Journal of the ACM , volume =. 1998 , publisher =

    1998

  5. [13]

    Fu, Hao and Li, Jian and Xu, Pan , booktitle =. A. 2018 , publisher =

    2018

  6. [14]

    Game-Theoretic Models of Bargaining , chapter =

    Infinite-horizon models of bargaining with one-sided incomplete information , author =. Game-Theoretic Models of Bargaining , chapter =

  7. [15]

    Adaptivity gaps for stochastic probing: Submodular and

    Gupta, Anupam and Nagarajan, Viswanath and Singla, Sahil , booktitle =. Adaptivity gaps for stochastic probing: Submodular and. 2017 , organization =

    2017

  8. [16]

    Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC '15) , pages =

    Team Performance with Test Scores , author =. Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC '15) , pages =. 2015 , doi =

    2015

  9. [17]

    Mathematical Programming , volume =

    An analysis of approximations for maximizing submodular set functions , author =. Mathematical Programming , volume =. 1978 , publisher =

    1978

  10. [18]

    Proceedings of the 36th International Conference on Machine Learning (ICML) , pages =

    Hiring Under Uncertainty , author =. Proceedings of the 36th International Conference on Machine Learning (ICML) , pages =. 2019 , publisher =

    2019

  11. [19]

    Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =

    Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation , author =. Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =. 2006 , doi =

    2006

  12. [20]

    Mathematics of Operations Research , year =

    Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems , author =. Mathematics of Operations Research , year =

  13. [21]

    Management Science , volume =

    Submodular Order Functions and Assortment Optimization , author =. Management Science , volume =. 2025 , publisher =

    2025

  14. [22]

    Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020) , pages =

    On the Complexity of Sequential Posted Pricing , author =. Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020) , pages =

    2020

  15. [23]

    2025 , month = feb, day =

    Off-. 2025 , month = feb, day =

    2025

  16. [24]

    2019 , url =

    Sivan, Balasubramanian , title =. 2019 , url =

    2019

  17. [25]

    Bargaining Theory , author =

  18. [26]

    Econometrica , volume =

    Perfect Equilibrium in a Bargaining Model , author =. Econometrica , volume =

  19. [27]

    Review of Economic Studies , volume =

    A Multistage Model of Bargaining , author =. Review of Economic Studies , volume =

  20. [28]

    The Review of Economic Studies , volume =

    Sequential Bargaining with Incomplete Information , author =. The Review of Economic Studies , volume =. 1983 , doi =

    1983

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.