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

In this work, we study the single-choice prophet inequality problem, where agambler faces a sequence of~$n$ online i.i.d. random variables drawn from anunknown distribution. When a variable reveals its value, the gambler needs todecide irrevocably whether or not to accept the value. The goal is to maximizethe competitive ratio between the expected gain of the gambler and that of themaximum variable. It is shown by Correa et al. that when the distribution isunknown or only $o(n)$ uniform samples from the distribution are given, thebest an algorithm can do is $1/e$-competitive. In contrast, when thedistribution is known or $\Omega(n)$ uniform samples are given, the optimalcompetitive ratio of 0.7451 can be achieved. In this paper, we study a newmodel in which the algorithm has access to an oracle that answers quantilequeries about the distribution and investigate to what extent we can use asmall number of queries to achieve good competitive ratios. We first use theanswers from the queries to implement the threshold-based algorithms and showthat with two thresholds our algorithm achieves a competitive ratio of$0.6786$. Motivated by the two-threshold algorithm, we design theobserve-and-accept algorithm that requires only a single query.  This algorithm sets a threshold in the first phase by making a query and usesthe maximum realization from the first phase as the threshold for the secondphase. It can be viewed as a natural combination of the single-thresholdalgorithm and the algorithm for the secretary problem. By properly choosing thequantile to query and the break-point between the two phases, we achieve acompetitive ratio of $0.6718$, beating the benchmark of $1-1/e$.

Prophet Inequality on I.I.D. Distributions: Beating 1-1/e with a Single Query