3 papers
cs.GT2024
Planning Against a Prophet: A Graph-Theoretic Framework for Making Sequential Decisions
Andrés Cristi, Sigal Oren
We devise a general graph-theoretic framework for studying prophet inequalities. In this framework, an agent traverses a directed acyclic graph from a starting node to a target…
cs.DS2023
Prophet Inequalities Require Only a Constant Number of Samples
Andrés Cristi, Bruno Ziliotto
In a prophet inequality problem, independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent v…
cs.DS2023
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…