English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The setting of the classic prophet inequality is as follows: a gambler isshown the probability distributions of $n$ independent, non-negative randomvariables with finite expectations. In their indexed order, a value is drawnfrom each distribution, and after every draw the gambler may choose to acceptthe value and end the game, or discard the value permanently and continue thegame. What is the best performance that the gambler can achieve in comparisonto a prophet who can always choose the highest value? Krengel, Sucheston, andGarling solved this problem in 1978, showing that there exists a strategy forwhich the gambler can achieve half as much reward as the prophet inexpectation. Furthermore, this result is tight.  In this work, we consider a setting in which the gambler is allowed much lessinformation. Suppose that the gambler can only take one sample from each of thedistributions before playing the game, instead of knowing the fulldistributions. We provide a simple and intuitive algorithm that recovers theoriginal approximation of $\frac{1}{2}$. Our algorithm works against even analmighty adversary who always chooses a worst-case ordering, rather than thestandard offline adversary. The result also has implications for mechanismdesign -- there is much interest in designing competitive auctions with afinite number of samples from value distributions rather than fulldistributional knowledge.

The Prophet Inequality Can Be Solved Optimally with a Single Set of Samples