IID prophet inequality with a single data point

DOI10.1016/J.ARTINT.2025.104296MaRDI QIDQ6995442zbMATH OpenFDO

Authors Yilong Feng, Bo Li, Haolong Li, Xiaowei Wu, Y. T. Wu

Publication date 22 April 2025

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ARTINT.2025.104296

zbMATH Keywords

data pointobserve-and-accept algorithmsprophet inequality

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Online algorithms; streaming algorithms (68W27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites work

• An O( m) prophet inequality for subadditive combinatorial auctions
• Bayesian auctions with efficient queries
• Beating \(1-\frac{1}{e}\) for ordered prophets
• Combinatorial prophet inequalities
• Comparison of threshold stop rules and maximum for independent nonnegative random variables
• Comparisons of stop rule and supremum expectations of i.i.d. random variables
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• scientific article; zbMATH DE number 7650408 (Why is no real title available?)
• Matroid prophet inequalities
• Multi-parameter mechanism design and sequential posted pricing
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Order selection prophet inequality: from threshold optimization to arrival time design
• Polymatroid Prophet Inequalities
• Pricing query complexity of revenue maximization
• Prior independent mechanisms via prophet inequalities with limited information
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Prophet secretary
• Prophet secretary for combinatorial auctions and matroids
• Prophet secretary through blind strategies
• Secretary Problems: The Power of a Single Sample
• Semiamarts and finite values
• Settling the sample complexity of single-parameter revenue maximization
• Single-sample prophet inequalities via greedy-ordered selection
• Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality
• The I.I.D. prophet inequality with limited flexibility
• The sample complexity of auctions with side information
• The sample complexity of revenue maximization
• The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization

This page was built for publication: IID prophet inequality with a single data point

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6995442)