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

A prophet inequality states, for some $\alpha\in[0,1]$, that the expectedvalue achievable by a gambler who sequentially observes random variables$X_1,\dots,X_n$ and selects one of them is at least an $\alpha$ fraction of themaximum value in the sequence. We obtain three distinct improvements for asetting that was first studied by Correa et al. (EC, 2019) and is particularlyrelevant to modern applications in algorithmic pricing. In this setting, therandom variables are i.i.d. from an unknown distribution and the gambler hasaccess to an additional $\beta n$ samples for some $\beta\geq 0$. We first giveimproved lower bounds on $\alpha$ for a wide range of values of $\beta$;specifically, $\alpha\geq(1+\beta)/e$ when $\beta\leq 1/(e-1)$, which is tight,and $\alpha\geq 0.648$ when $\beta=1$, which improves on a bound of around$0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal,specifically in the context of algorithmic pricing, we then show that the newbounds can be obtained even in a streaming model of computation and thus insituations where the use of relevant data is complicated by the sheer amount ofdata available. We finally establish that the upper bound of $1/e$ for the casewithout samples is robust to additional information about the distribution, andapplies also to sequences of i.i.d. random variables whose distribution isitself drawn, according to a known distribution, from a finite set of knowncandidate distributions. This implies a tight prophet inequality forexchangeable sequences of random variables, answering a question of Hill andKertz (Contemporary Mathematics, 1992), but leaves open the possibility ofbetter guarantees when the number of candidate distributions is small, asetting we believe is of strong interest to applications.

Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility