---
_id: '12677'
abstract:
- lang: eng
  text: "In modern sample-driven Prophet Inequality, an adversary chooses a sequence
    of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The
    process follows in two phases. In the first phase (sampling phase), some items,
    possibly selected at random, are revealed to the DM, but she can never accept
    them. In the second phase, the DM is presented with the other items in a random
    order and online fashion. For each item, she must make an irrevocable decision
    to either accept the item and stop the process or reject the item forever and
    proceed to the next item. The goal of the DM is to maximize the expected value
    as compared to a Prophet (or offline algorithm) that has access to all information.
    In this setting, the sampling phase has no cost and is not part of the optimization
    process. However, in many scenarios, the samples are obtained as part of the decision-making
    process.\r\nWe model this aspect as a two-phase Prophet Inequality where an adversary
    chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly
    ordered. Finally, there are two phases of the Prophet Inequality problem with
    the first n-items and the rest of the items, respectively. We show that some basic
    algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves
    a ratio of at least 0.495. Finally, we show that for every algorithm the ratio
    it can achieve is at most 0.502. Hence our algorithm is near-optimal."
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
  grant.
article_number: '2209.14368'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Mona
  full_name: Mohammadi, Mona
  id: 4363614d-b686-11ed-a7d5-ac9e4a24bc2e
  last_name: Mohammadi
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
citation:
  ama: Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with
    near-optimal bounds. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/ARXIV.2209.14368">10.48550/ARXIV.2209.14368</a>
  apa: Chatterjee, K., Mohammadi, M., &#38; Saona Urmeneta, R. J. (n.d.). Repeated
    prophet inequality with near-optimal bounds. <i>arXiv</i>. <a href="https://doi.org/10.48550/ARXIV.2209.14368">https://doi.org/10.48550/ARXIV.2209.14368</a>
  chicago: Chatterjee, Krishnendu, Mona Mohammadi, and Raimundo J Saona Urmeneta.
    “Repeated Prophet Inequality with Near-Optimal Bounds.” <i>ArXiv</i>, n.d. <a
    href="https://doi.org/10.48550/ARXIV.2209.14368">https://doi.org/10.48550/ARXIV.2209.14368</a>.
  ieee: K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality
    with near-optimal bounds,” <i>arXiv</i>. .
  ista: Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality
    with near-optimal bounds. arXiv, 2209.14368.
  mla: Chatterjee, Krishnendu, et al. “Repeated Prophet Inequality with Near-Optimal
    Bounds.” <i>ArXiv</i>, 2209.14368, doi:<a href="https://doi.org/10.48550/ARXIV.2209.14368">10.48550/ARXIV.2209.14368</a>.
  short: K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.).
corr_author: '1'
date_created: 2023-02-24T12:21:40Z
date_published: 2022-09-28T00:00:00Z
date_updated: 2025-04-14T07:52:48Z
day: '28'
department:
- _id: GradSch
- _id: KrCh
doi: 10.48550/ARXIV.2209.14368
ec_funded: 1
external_id:
  arxiv:
  - '2209.14368'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2209.14368'
month: '09'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: arXiv
publication_status: submitted
status: public
title: Repeated prophet inequality with near-optimal bounds
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...