Threshold Dynamics and Correlated Prophet Inequalities

José Correa, Maximilian Fichtl, Reda Jlibene, Rida Laraki, Vasilis Livanos, Kevin Schewior, Victor Verdugo

arXivarxiv/2607.09887Jul 10, 2026cs.GTscore 0

Prophet inequalities have become a central tool for analyzing the performance of online algorithms. However, most existing results assume that input random variables are independent, which limits their applicability. Motivated by this gap, we study prophet inequalities under two correlation models induced by a latent state of the world variable $Z$. In the common-base model, the algorithm observes the sequence $Z+X_1,\dots,Z+X_n$. We analyze single-threshold algorithms with the constraint that they always accept the final item, guaranteeing a reward of at least $Z$. When $Z$ is chosen…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.09887
curl -X POST /api/v1/records/arxiv/2607.09887/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09887/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'