Pith. sign in

REVIEW 4 major objections 4 minor 37 references

Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics

T0 review · 4 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read The optimal online k-selection policy in large i.i.d. markets has an asymptotic competitive ratio that depends only on k and the reward distribution's extreme value index γ.

desk verdict Main formula is probably right, but the proof of the central theorem has a real fixed-point gap; the CE-heuristic analysis is the most novel part and worth engaging. read the letter →

arxiv 2602.18756 v2 pith:O4SDSROX submitted 2026-02-21 math.OC

Jieming Kong , Karthyek Murthy This is my paper · ORCID
classification math.OC MSC 60G4060G7090C4062G32
keywords prophetinequalitiesmulti-secretaryproblemextremevalueindexasymptoticcompetitiveratiocertainty-equivalentheuristicfixed-thresholdpolicyregularvariationcompetitioncomplexity
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

This paper tries to prove an instance-dependent answer to the classic k-unit prophet inequality for i.i.d. nonnegative rewards when the number of offers n is large. It claims that for any distribution satisfying the extreme value condition, the optimal online policy's asymptotic competitive ratio depends on the distribution only via its extreme value index γ, and it gives an explicit closed form for that ratio. Since the worst case over γ occurs at γ=1/2, this yields a uniform guarantee of at least 1−(log k)/(8k)(1+ε) for all sufficiently large k, improving on the tight 1−1/√(2πk) guarantee of fixed-threshold policies. The paper further characterizes the certainty-equivalent heuristic, finds that its leading-order competitive ratio matches the optimum for large k, but shows that its additive regret relative to the optimal dynamic program diverges when k=o(n).

What carries the argument

The central object is the one-step dynamic-programming recursion for the optimal value V^dp(n,k), together with its analogue for the certainty-equivalent heuristic. The proof normalizes V^dp(n,k) by U(n)=F^{-1}(1−1/n), the high quantile of the reward distribution; regular variation of U with index γ converts the update into a difference equation in the normalized values. The threshold τ_{n,k}=V^dp(n−1,k)−V^dp(n−1,k−1) enters the tail integral ∫_τ^∞ (1−F(u)) du, and the standard tail-integration result for regularly varying tails rewrites that integral as a power of the normalized threshold. Passing to limits yields the deterministic recursion solved by v_k. The whole reduction replaces the u

What would settle it

For a distribution with power-law tail 1−F(x)=x^{-1/γ} (γ=0.7), evaluate the exact dynamic-program recursion for fixed k across n=10^2,…,10^7. If V^dp(n,k)/F^{-1}(1−1/n) does not converge to the claimed v_k/(1−γ)^γ, or converges to a different constant for some k, the closed-form formula fails; the power-law tail makes the recursion exact for every n.

Watch

Extended reading notes

Core claim

Theorem 3.1 asserts that for F with extreme value index γ∈(0,1), ACR_k(F) = (1−γ)^{1−γ} v_k Γ(k)/Γ(k+1−γ), and that ACR_k(F)=1 for γ∉(0,1); here v_1=1 and for k>1, v_k−v_{k−1} is the unique positive root of x^{1/γ}+v_{k−1}x^{1/γ−1}−1=0. The argument normalizes the optimal dynamic-program values by the high quantile F^{-1}(1−1/n), which is regularly varying with index γ, and shows that the normalized values satisfy a deterministic recursion in the limit. The same machinery yields a closed form for the certainty-equivalent heuristic's ratio and, by Stirling-type expansions, the large-k expansion 1−γ(1−γ) log k/(2k)+O(1/k) for both policies. This expansion is what produces the tight worst-case

Load-bearing premise

The load-bearing premise is that the normalized dynamic-program value functions actually converge as n grows, so one may pass to the limit inside the nonlinear recursion; the proof establishes this only for subsequences, not for every heavy-tailed distribution it covers.

Editorial extensions

If this is right

  • Large-market optimal competitive ratio becomes computable for any heavy-tailed distribution: evaluate a one-dimensional recursion and gamma functions.
  • The worst-case guarantee over distributions satisfying the extreme value condition is asymptotically 1−(log k)/(8k), beating the tight 1−1/√(2πk) bound of static thresholds; the worst case sits at γ=1/2.
  • The certainty-equivalent heuristic asymptotically matches the optimal policy's leading-order performance ratio for large k, even without the fluid-scaling assumption k∝n.
  • When k=o(n), the CE heuristic's additive regret relative to the optimal DP diverges like a positive power of n/k, so a near-1 competitive ratio can coexist with unbounded additive loss.
  • In heavy-tailed domains, both DP and CE need only a (1+O(log k/k)) inflation of market size to compensate their multiplicative loss.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: if the convergence and compactness step for normalized value functions can be supplied, the same tail-index reduction should extend to broader tail classes, suggesting a general principle that only the tail index governs large-market online allocation.
  • Editorial inference: because the worst case occurs at γ=1/2, the hard instances are heavy-tailed with finite mean but infinite variance; practical policies that know only γ, not the full distribution, may inherit near-optimality.
  • Editorial inference: the divergent-regret result warns that fluid-scaling conclusions about the CE heuristic do not transfer to fixed instances with k much smaller than n; in such cases additive regret, not just the competitive ratio, should be tracked.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper studies the i.i.d. k-unit prophet inequality in the large-market regime, aiming to characterize the instance-dependent asymptotic competitive ratio ACR_k(F) under the extreme value condition. Theorem 3.1 asserts that ACR_k(F) depends on F only through its extreme value index gamma, with an explicit formula for gamma in (0,1) involving a recursively defined sequence v_k, and equals 1 otherwise. From this the authors derive a large-k worst-case guarantee 1 - (log k)/(8k)(1+epsilon), improving on the fixed-threshold guarantee 1 - 1/sqrt(2 pi k). The second half analyzes the Certainty-Equivalent (CE) heuristic, showing that its asymptotic ratio has the same leading-order large-k expansion as the optimal DP, but that its additive regret can diverge when k = o(n), via Theorem 4.4 and Proposition 4.5. The paper also discusses competition complexity.

Significance. If the main results are correct, this is a substantial contribution: an explicit, distribution-dependent asymptotic characterization for the multi-unit prophet inequality, a new large-k worst-case guarantee, and the first systematic analysis of the CE heuristic outside the fluid-scaling regime. The extreme-value reduction is elegant and the DP-recursion approach is natural. The paper is also commendable for focusing on instance-dependent rather than worst-case guarantees, and for making sharp distinctions between ratio and additive-regret performance. However, the proof of the central DP asymptotic, Proposition 6.2, contains a significant convergence gap, and the divergence result for the CE heuristic relies on an unproved positivity assertion backed only by a missing numerical figure. These issues must be repaired before the paper's main claims can be accepted.

major comments (4)
  1. [Proposition 6.2, Eqs. (13)–(19)] The central fixed-point step is not justified. Writing g_k(n)=V^dp(n,k)/U(n), the exact expansion of V^dp(n,k)-V^dp(n-1,k) contains the term U(n)(g_k(n)-g_k(n-1)) in addition to (gamma/n)U(n)g_k(n-1)+o(U(n)/n). After dividing by U(n)/n, this yields gamma g_k(n-1) + n(g_k(n)-g_k(n-1)) + o(1). The proof drops the term n(g_k(n)-g_k(n-1)) without showing it is o(1); convergence of g_k(n) does not imply this. Consequently, Eqs. (18)-(19) identify only a necessary condition for subsequential limits, and the claimed convergence of the full sequence g_k(n) to v_k/(1-gamma)^gamma is not established. No boundedness, compactness, or convergence-rate argument is supplied, and the [1+o(1)] factors are commuted with the nonlinear power Delta_k^{-(1-gamma)/gamma}. Since Theorem 3.1, Corollary 3.3, and Proposition 3.2 all rest on Proposition 6.2, the gamma-in-(0,1) ACR formula is currently unproven.
  2. [Theorem 3.1, Eq. (6), gamma >= 1] The line '1, otherwise' is not meaningful for gamma >= 1. As the paper itself notes, gamma >= 1 occurs only when E[X] = infinity. In that case both V^dp(n,k) and the prophet value mu_{n,k} are infinite for every n, so the ratio V^dp(n,k)/mu_{n,k} is not defined in the usual sense. The statement needs either an explicit extended-real convention, a normalization, or a restriction of the theorem to the cases where the ratio is well-defined. This is not merely cosmetic, because the theorem is claimed for all extreme-value distributions on R_+.
  3. [Theorem 4.4 and proof (Section B.4)] The theorem's divergence conclusion depends on the positivity of c_gamma, but positivity is not proved. The proof states: 'by numerical validation, we can further know c_gamma > 0. See Figure 3.' Figure 3 is absent from the manuscript, and numerical validation cannot serve as a proof in a mathematical paper. Moreover, the proof's final step writes V^dp(n,k)-V^ce(n,k)=Theta((n/k)^gamma), which would require U(n) to be comparable to n^gamma; for a general regularly varying quantile U with index gamma, only divergence of the gap follows from c_gamma>0, not this exact order. The overclaim should be corrected or proved.
  4. [Proposition 4.5 and proof (Section B.5)] The proposition asserts a joint limit behavior V^dp(n,k)-V^ce(n,k)=Omega((n/k)^gamma) whenever k=o(n), but its proof relies on the claim that 'the large-k expansions for the competitive ratios remain valid along any sequence with k=o(n)' and on a statement that the recursions simplify 'in a way that is uniform.' No uniformity estimates or verification of the interchange of limits are provided. Since Theorem 3.1 and Theorem 4.1 are fixed-k asymptotic results, applying them along k=k(n)->infinity requires additional uniform control that is not established. As stated, the lower bound is not proven.
minor comments (4)
  1. [Section 6.2, Eq. (8)] The notation for the CE value function alternates between V^ce, V^{CE}, and V CE. Please standardize.
  2. [Theorem 6.9, gamma=0 formula] In the definition of a_n = F^{-1}(1-1/(en)) - F^{-1}(1-1/n), the suffix 'x>1' appears to be a typo; presumably it should be n>1 or e>1.
  3. [Proof of Proposition 6.6] The proof says 'existence follows from boundedness of hat g_j(.)' but boundedness is not established. A short argument or a citation to a uniform bound is needed.
  4. [Theorem 4.4 proof] The proof refers to 'Figure 3' for the numerical positivity check, but no Figure 3 is included in the manuscript. If the authors intend to retain the numerical check as supporting evidence, the figure must be included; ideally the positivity of c_gamma should be proved analytically.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the ACR derivation is self-contained, with no fitted parameters or author self-citations carrying the argument.

full rationale

The central derivation of Theorem 3.1 is not circular. The asymptotic value-function expansion in Proposition 6.2 is obtained from the Bellman recursion (4), Lemma 6.1, and standard extreme-value/regular-variation tools (Karamata, quantile asymptotics), and the prophet expectation in Theorem 6.9 is computed independently from extreme-value theory for order statistics. The constant v_k is not fitted to the target ratio; it is determined by the fixed-point equation that emerges from the normalized DP recursion, and gamma is an external EVT parameter. The large-k bound in Corollary 3.3 uses only the universal inequality gamma(1-gamma) <= 1/4 together with Proposition 3.2, which in turn rests on Stirling/gamma-ratio expansions. The paper contains no load-bearing self-citations: the cited works are external (e.g., [21], [31]) and the authors do not invoke a prior uniqueness theorem of their own to force the form of the result. Section 7's competition-complexity formula is a direct reformulation of Definition 7.1 using the already-proved asymptotic ratios and regular variation; it is not a hidden prediction. The main genuine weakness is a proof gap, not circularity: in Proposition 6.2, the passage from equation (18) to the convergence of g_k(n) assumes that subsequential limits exist and that the dropped n(g_k(n)-g_k(n-1)) term is negligible; compactness of the normalized value functions is not established, so the fixed-point step identifies at most a necessary condition for subsequential limits. This is a correctness risk in the proof of Theorem 3.1, but it does not make the derivation circular, because the claimed formula is not assumed as an input anywhere in the derivation chain.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim is parameter-free: gamma is an input describing the distribution, and v_k/w_k are determined by exact recursions, not fitted to data. The main unstated loads are the compactness/limit-exchange in the DP fixed-point proof, the gamma >= 1 interpretation, and the uniformity of large-k expansions in the joint limit.

assumptions (6)
  • domain assumption The reward distribution F satisfies the extreme value condition with gamma in (0,1) in the nontrivial regime.
    Theorem 3.1's main case rests on F being in the Frechet domain, which is used to justify regular variation of the quantile function and Karamata tail-integral asymptotics in Propositions 6.2 and 6.6.
  • domain assumption The Bellman recursion (4) exactly characterizes the optimal online value function.
    Lemma 6.1, the starting point of the DP analysis, follows from the standard accept/reject dynamic program. This is a model-level assumption inherited from the prophet inequality problem.
  • standard math Karamata's theorem and standard regular-variation calculus apply to the tail and quantile functions.
    Used in equations (12)-(16) and (22)-(24) to convert tail integrals and quantile ratios into powers of n and k.
  • standard math The sequence v_k defined by v_1=1 and the positive-root recursion is uniquely defined and has the asymptotic expansion used in Lemma A.2.
    The theorem states uniqueness of the positive root; the large-k expansion is proved from the exact identity sk-1 = sk(1-(1-gamma)/sk)^(1/(1-gamma)) in Appendix A.2.
  • ad hoc to paper For gamma not in (0,1), ACR=1 is meaningful even when E[X]=infinity and the prophet's expected top-k sum is infinite.
    Theorems 3.1 and 4.1 assert ACR=1 for gamma >= 1, but the text gives no definition of the ratio of infinite expectations; this is a gap in the stated theorem.
  • ad hoc to paper The fixed-k large-k expansions used for ACR and apx remain valid uniformly when k=k(n)=o(n).
    Proposition 4.5 relies on these expansions in the joint limit n->infty, k=o(n), but only fixed-k asymptotics are proved in Propositions 3.2 and 4.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics." pith.science (2026). https://pith.science/paper/O4SDSROX

@misc{pith2026260218756,
  author       = {Pith},
  title        = {Pith review of: Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O4SDSROX}},
  note         = {Machine review of arXiv:2602.18756}
}
abstract

We study the i.i.d. $k$-selection prophet inequality problem, where a decision-maker sequentially observes $n$ independent nonnegative rewards and may accept at most $k$ of them without knowledge of future realizations. The objective is to maximize the expected total reward relative to that of a prophet who observes all rewards in advance. This problem captures the performance limits achievable in online resource allocation and underlies posted-price mechanisms in online marketplaces. We characterize the optimal welfare achievable relative to the prophet in terms of $k$ and the extreme value index of the reward distribution, in the asymptotic regime where the number of offers $n$ grows large. This optimal performance ratio turns out to be at least $1-\frac{\log k}{8k}[1+\epsilon]$ for any $\epsilon > 0$ and sufficiently large $k$, improving upon the respective, tight $1 - \frac{1}{\sqrt{2\pi k}}$ guarantee of static-threshold algorithms. We additionally analyze the certainty-equivalent (CE) heuristic, a widely used online allocation algorithm known to yield optimal regret growth in $n$ when evaluated under the fluid scaling assumption. Even in the absence of the fluid scaling, the CE heuristics's performance improves with $k$ to eventually match the leading order terms of the optimal dynamic program's performance ratio. A finer analysis nevertheless reveals that regret can be divergent and large relative to the optimal dynamic program when $n/k \to \infty$. This highlights the sensitivity in viewing the CE heuristic's performance under the commonly adopted, though subjective, fluid scaling assumption.

Figures

Figures reproduced from arXiv: 2602.18756 by the authors.

Figure 1
Figure 1. Heatmaps of the asymptotic ratios as a function of k and γ. 5.2. Worst-case ratios of ACRk(F) and apxk (F) over γ. To quantify the worst-case behavior, define ACRDP k := inf γ∈(0,1) ACRk(F), ACRCE k := inf γ∈(0,1) apxk (F), ρk := inf γ∈(0,1) apxk (F) ACRk(F) , and let γ ∗ DP, γ∗ CE, γ∗ CE/DP denote points attaining these infima on the numerical grid [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Finer Comparison between DP and CE of Pareto Distribution 6. Key Ingredients in the Proofs of Main Results In this section, we provide proofs for the key results, namely, characterizations of the solutions to the 2-dimensional recursions capturing the value functions V dp(n, k) and V ce(n, k), for the case γ > 0. Their application in proving the main results in the paper, and all other proofs not furnished here are … view at source ↗
Figure 3
Figure 3. Finer Comparison between DP and CE When γ = 0, the DP and CE fixed-k asymptotics are governed by the same limiting recursion (and the same initial condition), hence αk = βk for every fixed k and therefore c0 = 0. If γ ∈ (0, 1), then U(n) → ∞ as n → ∞. Moreover, the previous steps imply that for large k, limn→∞ V dp(n, k) − V ce(n, k) U(n) = αk − βk = Θ(k −γ ), so as n → ∞, V dp(n, k) − V ce(n, k) = Θ n k γ , and… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 2 linked inside Pith

  1. [1]

    Abdallah and J

    T. Abdallah and J. Reed. Regime dependent approximations for the single-item dynamic pricing problem. 2024

    2024

  2. [2]

    Abdallah and J

    T. Abdallah and J. Reed. Dynamic pricing in the large market regime.Available at SSRN 5223633, 2025

    2025

  3. [3]

    S. Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.SIAM Journal on Computing, 43(2):930–972, 2014

    2014

  4. [4]

    Arlotto and I

    A. Arlotto and I. Gurvich. Uniformly bounded regret in the multisecretary problem.Stochastic Systems, 9(3):231–260, 2019

    2019

  5. [5]

    Arnosti and W

    N. Arnosti and W. Ma. Tight guarantees for static threshold policies in the prophet secretary problem.Operations Research, 71(5):1777–1788, September 2023

    2023

  6. [6]

    Arsenis, O

    M. Arsenis, O. Drosis, and R. Kleinberg. Constrained-order prophet inequalities. InProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 2034–2046, USA, 2021. Society for Industrial and Applied Mathematics

  7. [7]

    Balseiro, O

    S. Balseiro, O. Besbes, and D. Pizarro. Survey of dynamic resource constrained reward collection problems: Unified model and analysis.SSRN Electronic Journal, 01 2021

    2021

  8. [8]

    Beyhaghi, N

    H. Beyhaghi, N. Golrezaei, R. P. Leme, M. Pal, and B. Sivan. Improved approximations for free-order prophets and second-price auctions.CoRR, abs/1807.03435, 2018

    arXiv 2018

Show all 37 references
  1. [9]

    Beyhaghi, N

    H. Beyhaghi, N. Golrezaei, R. P. Leme, M. P´ al, and B. Sivan. Improved revenue bounds for posted-price and second- price mechanisms.Oper. Res., 69(6):1805–1822, Nov. 2021

    2021

  2. [10]

    Beyhaghi and S

    H. Beyhaghi and S. M. Weinberg. Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 686–696, 2019

    2019

  3. [11]

    R. L. Bray. Logarithmic regret in multisecretary and online linear programs with continuous valuations.Operations Research, 73(4):2188–2203, 2025

    2025

  4. [12]

    Brustle, J

    J. Brustle, J. Correa, P. Duetting, and V. Verdugo. The competition complexity of dynamic pricing.Mathematics of Operations Research, 49(3):1986–2008, 2024

    1986

  5. [13]

    Brustle, S

    J. Brustle, S. Perez-Salazar, and V. Verdugo. Splitting guarantees for prophet inequalities via nonlinear systems. Mathematics of Operations Research, 04 2025

    2025

  6. [14]

    Bumpensanti and H

    P. Bumpensanti and H. Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66(7):2993–3009, 2020

    2020

  7. [15]

    Cai and C

    Y. Cai and C. Daskalakis. Extreme value theorems for optimal multidimensional pricing.Games and Economic Be- havior, 92(C):266–305, None 2015

    2015

  8. [16]

    A. Cayley. Mathematical questions with their solutions.The Educational Times, 23:18–19, 1875. 18

  9. [17]

    Chakraborty, E

    T. Chakraborty, E. Even-Dar, S. Guha, Y. Mansour, and S. Muthukrishnan. Approximation schemes for sequential posted pricing in multi-unit auctions. InProceedings of the 6th International Conference on Internet and Network Economics, WINE’10, page 158–169, Berlin, Heidelberg, 2...

    2010

  10. [18]

    Chawla, J

    S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan. Multi-parameter mechanism design and sequential posted pricing. InProceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 311–320, New York, NY, USA, 2010. Association for Computing Machinery

    2010

  11. [19]

    Correa, P

    J. Correa, P. Foncea, D. Pizarro, and V. Verdugo. From pricing to prophets, and back!Operations Research Letters, 47(1):25–29, 2019

    2019

  12. [20]

    Correa, V

    J. Correa, V. Livanos, D. Pizarro, and V. Verdugo. Posted pricing and competition in large markets, 2025

    2025

  13. [21]

    Correa, D

    J. Correa, D. Pizarro, and V. Verdugo. Optimal revenue guarantees for pricing in large markets. InAlgorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021, Proceedings, page 221–235, Berlin, Heidelberg, 2021. Springer-Verlag

    2021

  14. [22]

    De Haan and A

    L. De Haan and A. Ferreira.Extreme value theory: an introduction. Springer, 2006

    2006

  15. [23]

    D¨ utting, F

    P. D¨ utting, F. Fischer, and M. Klimm. Revenue gaps for static and dynamic posted pricing of homogeneous goods, 2019

    2019

  16. [24]

    Feng and Y

    Y. Feng and Y. Jin. Beyond regularity: Simple versus optimal mechanisms, revisited. Papers 2411.03583, arXiv.org, Nov 2024

    2024 arXiv

  17. [25]

    R. A. Fisher and L. H. C. Tippett. Limiting forms of the frequency distribution of the largest or smallest member of a sample.Mathematical Proceedings of the Cambridge Philosophical Society, 24(2):180–190, 1928

    1928

  18. [26]

    B. V. Gnedenko. Sur la distribution limite du terme maximum d’une serie aleatoire.Annals of Mathematics, 44:423, 1943

    1943

  19. [27]

    M. T. Hajiaghayi, R. Kleinberg, and T. Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 1, AAAI’07, page 58–65. AAAI Press, 2007

    2007

  20. [28]

    T. P. Hill and R. P. Kertz. Comparisons of Stop Rule and Supremum Expectations of I.I.D. Random Variables.The Annals of Probability, 10(2):336 – 345, 1982

    1982

  21. [29]

    Jasin and A

    S. Jasin and A. Sinha. An lp-based correlated rounding scheme for multi-item ecommerce order fulfillment.Operations Research, 63(6):1336–1351, 2015

    2015

  22. [30]

    Jiang, W

    J. Jiang, W. Ma, and J. Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack, 2023

    2023

  23. [31]

    D. P. Kennedy and R. P. Kertz. The Asymptotic Behavior of the Reward Sequence in the Optimal Stopping of I.I.D. Random Variables.The Annals of Probability, 19(1):329 – 341, 1991

    1991

  24. [32]

    A. J. Kleywegt and J. D. Papastavrou. The dynamic and stochastic knapsack problem.Operations Research, 46(1):17– 35, 1998

    1998

  25. [33]

    Livanos and R

    V. Livanos and R. Mehta. Minimization i.i.d. prophet inequality via extreme value theory: A unified approach. In Proceedings of the 26th ACM Conference on Economics and Computation, EC ’25, page 1157–1179, New York, NY, USA, 2025. Association for Computing Machinery

    2025

  26. [34]

    Molina, N

    M. Molina, N. Gast, P. Loiseau, and V. Perchet.Prophet Inequalities: Competing with the TopℓItems is Easy, pages 1270–1307. 01 2025

    2025

  27. [35]

    L. Moser. On a problem of cayley.Scripta Math, 22:289–292, 1956

    1956

  28. [36]

    S. I. Resnick.Extreme values, regular variation, and point processes, volume 4. Springer Science & Business Media, 2008

    2008

  29. [37]

    Q. Yan. Mechanism design via correlation gap. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 710–719, USA, 2011. Society for Industrial and Applied Mathematics. 1 Appendices AppendixA.Proofs of results in Section 3 A.1.Proof...

    2011

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.