Prophet inequalities for independent and identically distributed random variables from an unknown distribution

DOI10.1287/MOOR.2021.1167MaRDI QIDQ5085141zbMATH OpenOpenAlexFDO

Authors José R. Correa, Paul Dütting, Felix Fischer, Kevin Schewior

Publication date 27 June 2022

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.2021.1167

zbMATH Keywords

online algorithmsoptimal stoppingprophet inequalitiesposted pricing

Mathematics Subject Classification ID

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

Recommendations

• Optimal stopping of independent random variables and maximizing prophets
• Prophet secretary through blind strategies
• Prophet secretary
• Prophet secretary through blind strategies
• Prophet Inequalities with Limited Information

Cites work

• scientific article; zbMATH DE number 3928135 (Why is no real title available?)
• scientific article; zbMATH DE number 67295 (Why is no real title available?)
• scientific article; zbMATH DE number 7650408 (Why is no real title available?)
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers
• Beating \(1-\frac{1}{e}\) for ordered prophets
• Beyond matroids: secretary problem and prophet inequality with general constraints
• Combinatorial auctions via posted prices
• 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
• Competitive Analysis with a Sample and the Secretary Problem
• Matroid prophet inequalities
• Multi-parameter mechanism design and sequential posted pricing
• Online contention resolution schemes
• Polymatroid Prophet Inequalities
• Pricing for Online Resource Allocation: Intervals and Paths
• 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
• Robust monopoly pricing
• Semiamarts and finite values
• Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality
• The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
• Who solved the secretary problem? With comments and a rejoinder by the author

Cited in

(6)

• Optimal prophet inequality with less than one sample
• Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality
• Secretary and online matching problems with machine learned advice
• Expectation inequalities associated with prophet problems¹
• Knapsack secretary through boosting
• A statistical version of prophet inequalities

This page was built for publication: Prophet inequalities for independent and identically distributed random variables from an unknown distribution

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