EUVIMEDEUVIMED entdecken
Crossref

Uniformly Bounded Regret in the Multisecretary Problem

Alessandro Arlotto, Itai Gurvich

Stochastic Systems · 2019-09 · 9 (3) · 231-260

DOI: 10.1287/stsy.2018.0028 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Stochastic Systems, 2019-09. Verfasst von Alessandro Arlotto und 1 weiteren Autor:innen. Die Arbeit wurde bisher 71-mal zitiert (Crossref) und nennt 19 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the secretary problem of Cayley [Cayley A (1875) Mathematical questions with their solutions. Ed. Times 23:18–19.] and Moser [Moser L (1956) On a problem of Cayley. Scripta Mathematica 22(3/4):289–292.], n nonnegative, independent, random variables with common distribution are sequentially presented to a decision maker who decides when to stop and collect the most recent realization. The goal is to maximize the expected value of the collected element. In the k-choice variant, the decision maker is allowed to make k ≤ n selections to maximize the expected total value of the selected elements. Assuming that the values are drawn from a known distribution with finite support, we prove that the best regret—the expected gap between the optimal online policy and its offline counterpart in which all n values are made visible at time 0—is uniformly bounded in the number of candidates n and the budget k. Our proof is constructive: we develop an adaptive budget-ratio policy that achieves this performance. The policy selects or skips values depending on where the ratio of the residual budget to the remaining time stands relative to multiple thresholds that correspond to middle points of the distribution. We also prove that being adaptive is crucial: in general, the minimal regret among nonadaptive policies grows like the square root of n. The difference is the value of adaptiveness.

Zitieren

APA

Arlotto, A., & Gurvich, I. (2019). Uniformly Bounded Regret in the Multisecretary Problem. Stochastic Systems, 9(3), 231-260. https://doi.org/10.1287/stsy.2018.0028

Vancouver

Arlotto A, Gurvich I. Uniformly Bounded Regret in the Multisecretary Problem. Stochastic Systems. 2019;9(3):231-260. doi:10.1287/stsy.2018.0028

BibTeX
@article{Arlotto2019,
  author = {Arlotto, Alessandro and Gurvich, Itai},
  title = {Uniformly Bounded Regret in the Multisecretary Problem},
  journal = {Stochastic Systems},
  year = {2019},
  volume = {9},
  number = {3},
  pages = {231--260},
  doi = {10.1287/stsy.2018.0028}
}
Kostenlos starten →