Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Trading Prophets
 
research article

Trading Prophets

Correa, José
•
Cristi, Andrés  orcid-logo
•
Dütting, Paul
Show more
October 27, 2025
Operations Research

The prophet inequality is a cornerstone of online decision making, comparing a sequential decision maker to a prophet who knows all outcomes in advance. In “Trading Prophets,” J. Correa, A. Cristi, P. Dütting, M. Hajiaghayi, J. Olkowski, and K. Schewior initiate the study of buy-and-sell prophet inequalities. Here, an online algorithm observes a sequence of prices, one after the other, to trade an item. At each time step, the algorithm can decide to buy and pay the current price if it does not already hold the item, or it can decide to sell and collect the current price as a reward if it holds the item. The authors identify settings where a constant-factor approximation to the all-knowing prophet benchmark can be achieved. Interestingly, these conditions differ from those required for standard prophet inequalities. Specifically, they show that no constant-factor inequality exists for arbitrary independent prices. In contrast, they prove that a constant factor is achievable when independent prices arrive in a random order.

  • Details
  • Metrics
Type
research article
DOI
10.1287/opre.2023.0593
Author(s)
Correa, José

University of Chile

Cristi, Andrés  orcid-logo

École Polytechnique Fédérale de Lausanne

Dütting, Paul

Google (Switzerland)

Hajiaghayi, Mohammad Taghi

University of Maryland, College Park

Olkowski, Jan

University of Maryland, College Park

Schewior, Kevin

University of Southern Denmark

Date Issued

2025-10-27

Publisher

Institute for Operations Research and the Management Sciences (INFORMS)

Published in
Operations Research
Article Number

opre.2023.0593

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
GO  
Available on Infoscience
October 31, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255441
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés