• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Prophet Secretary Through Blind Strategies

Correa, José; Saona, Raimundo; Ziliotto, Bruno (2019), Prophet Secretary Through Blind Strategies, in Timothy M. Chan, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, p. 1946-1961. 10.1137/1.9781611975482.118

View/Open
1807.07483.pdf (273.0Kb)
Type
Communication / Conférence
Date
2019
Conference title
Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Conference date
2019-01
Conference city
San Diego
Conference country
United States
Book title
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Book author
Timothy M. Chan
Publisher
Society for Industrial and Applied Mathematics
ISBN
978-1-61197-548-2
Number of pages
IX-2972
Pages
1946-1961
Publication identifier
10.1137/1.9781611975482.118
Metadata
Show full item record
Author(s)
Correa, José
University of Santiago, Chile
Saona, Raimundo

Ziliotto, Bruno
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)
In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no nonadaptive algorithm for the gambler can achieve better than 0.732.
Subjects / Keywords
Prophet Secretary

Related items

Showing items related by title and author.

  • Thumbnail
    Streaming Algorithms for Online Selection Problems 
    Correa, José; Dütting, Paul; Fischer, Felix; Schewior, Kevin; Ziliotto, Bruno (2021) Communication / Conférence
  • Thumbnail
    Finite-Memory Strategies in POMDPs with Long-Run Average Objectives 
    Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2021) Article accepté pour publication ou publié
  • Thumbnail
    Managing Impatriate Adjustment as a Core Human Resource Management Challenge 
    Al-Rajhi, Ibrahim; Altman, Yochanan; Metcalfe, Beverly; Roussel, Josse (2006) Article accepté pour publication ou publié
  • Thumbnail
    Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core 
    Mavrotas, George; Figueira, José; Florios, Kostas (2009) Article accepté pour publication ou publié
  • Thumbnail
    Tauberian theorems for general iterations of operators: Applications to zero-sum stochastic games 
    Ziliotto, Bruno (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo