• 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

Streaming Algorithms for Online Selection Problems

Correa, José; Dütting, Paul; Fischer, Felix; Schewior, Kevin; Ziliotto, Bruno (2021), Streaming Algorithms for Online Selection Problems, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 10.4230/LIPIcs.ITCS.2021.86

View/Open
cdfo_streaming.pdf (556.9Kb)
Type
Communication / Conférence
Date
2021
Conference title
12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Conference date
2021
Conference city
virtual
Book title
12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Publication identifier
10.4230/LIPIcs.ITCS.2021.86
Metadata
Show full item record
Author(s)
Correa, José
Universidad de Chile = University of Chile [Santiago] [UCHILE]
Dütting, Paul
Fischer, Felix
Schewior, Kevin
Universidad de Santiago de Chile [Santiago] [USACH]
Ziliotto, Bruno
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)
A prophet inequality states, for some α∈[0,1], that the expected value achievable by a gambler who sequentially observes random variables X1,…,Xn and selects one of them is at least an α fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional βn samples for some β≥0. We first give improved lower bounds on α for a wide range of values of β; specifically, α≥(1+β)/e when β≤1/(e−1), which is tight, and α≥0.648 when β=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 new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of 1/e for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.
Subjects / Keywords
Prophet Inequalities; Stopping Theory; Unknown Distributions

Related items

Showing items related by title and author.

  • Thumbnail
    Parallel Algorithms are Good for Streaming 
    Demetrescu, Camil; Escoffier, Bruno; Moruz, Gabriel; Ribichini, Andrea (2006) Document de travail / Working paper
  • Thumbnail
    Possible and Necessary Winners of Partial Tournaments 
    Aziz, Haris; Brill, Markus; Fischer, Felix; Harrenstein, Paul; Lang, Jérôme; Seedig, Hans Georg (2015) Article accepté pour publication ou publié
  • Thumbnail
    Possible and necessary winners of partial tournaments 
    Aziz, Haris; Harrenstein, Paul; Brill, Markus; Lang, Jérôme; Fischer, Felix; Seedig, Hans Georg (2012) Communication / Conférence
  • Thumbnail
    On-line models and algorithms for max independent set 
    Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié
  • Thumbnail
    Greedy algorithms for on-line set-covering and related problems 
    Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Communication / Conférence
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