Description du sujet de thèse

"Prophet inequality (mathematical optimisation problem) and their applications in computer science and economics"

Prophet inequalities provide a fundamental framework in online decision-making, where a decision-maker sequentially observes random values and must decide when to stop and accept a value, aiming to maximize the expected reward. Classic results guarantee that even without knowing future values, one can achieve at least a constant fraction of the expected maximum value, assuming the values are drawn independently from known distributions. These results have been widely applied in areas such as auction theory, resource allocation, and stochastic optimization.

The interdependent value model, introduced by Milgrom and Weber (1982), describes settings where an agent's valuation depends not only on their own private signal but also on signals held by others. This interdependence makes decision-making more complex, as an agent's expected value is affected by information that is held by others, which is at odds with the independence assumption. In a recent paper [1], we bridge the gap between prophet inequalities and interdependent values, proving the first constant-factor approximations in online selection problems where agent values are interdependent.

Building on this result, a natural next step is to extend the incorporation to the following generalizations:
- Extend results to settings where distributions are identical across agents or where the arrival order is random [2]
- Explore cases where only a single sample is available per distribution [3], limiting prior knowledge and requiring more robust selection strategies.
- Generalize results to the "philosopher inequality" setting [4], where the benchmark is the optimal online algorithm rather than the expected maximum, making the competition more dynamic.
- Study settings where multiple items are allocated to buyers, such as combinatorial auctions or matroid selection problems [5].
Extending these results could lead to new insights in mechanism design, online auctions, and stochastic decision processes, where interdependence plays a crucial role.

[1] Mauras, Simon, et al. "Optimal Stopping with Interdependent Values." Proceedings of the 25th ACM Conference on Economics and Computation. 2024.
[2] Correa, José, et al. "Prophet inequalities for iid random variables from an unknown distribution." Proceedings of the 2019 ACM Conference on Economics and Computation. 2019.
[3] Rubinstein, Aviad, et al. "Optimal Single-Choice Prophet Inequalities from Samples." Innovations in Theoretical Computer Science (2020).
[4] Papadimitriou, Christos, et al. "Online stochastic max-weight bipartite matching: Beyond prophet inequalities." Proceedings of the 22nd ACM Conference on Economics and Computation. 2021.
[5] Kleinberg, Robert, et al. "Matroid prophet inequalities." Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 2012.

Contexte de travail

The PhD will be carried out under the supervision of Vianney Perchet and Simon Mauras, within the FairPlay team based in the Statistics Department at CREST, and in collaboration with Jose Correa at the University of Chile. We propose to study "prophet inequalities (a mathematical optimization problem) and their applications in computer science and economics."

Contraintes et risques

none