Description du sujet de thèse

**Inégalités de prophète (problème d’optimisation mathématique) et leurs applications en informatique et en économie**

Les inégalités de prophète offrent un cadre fondamental pour la prise de décision en ligne, où un décideur observe successivement des valeurs aléatoires et doit décider à quel moment s’arrêter et accepter une valeur, dans le but de maximiser la récompense espérée. Des résultats classiques garantissent que, même sans connaître les valeurs futures, on peut obtenir au moins une fraction constante de la valeur maximale espérée, à condition que les valeurs soient tirées indépendamment de distributions connues. Ces résultats ont été largement appliqués dans des domaines tels que la théorie des enchères, l’allocation de ressources et l’optimisation stochastique.

Le modèle à valeurs interdépendantes, introduit par Milgrom et Weber (1982), décrit des situations où la valorisation d’un agent dépend non seulement de son propre signal privé, mais aussi des signaux détenus par les autres. Cette interdépendance complexifie la prise de décision, car la valeur espérée d’un agent est influencée par des informations détenues par d’autres, ce qui contredit l’hypothèse d’indépendance. Dans un article récent \[1], nous comblons le fossé entre les inégalités de prophète et les valeurs interdépendantes, en prouvant les premières approximations à facteur constant pour des problèmes de sélection en ligne où les valeurs des agents sont interdépendantes.

À partir de ce résultat, il est naturel d’envisager les généralisations suivantes :

* Étendre les résultats à des contextes où les distributions sont identiques entre agents, ou bien où l’ordre d’arrivée est aléatoire \[2] ;
* Explorer les cas où un seul échantillon est disponible par distribution \[3], ce qui limite les connaissances a priori et nécessite des stratégies de sélection plus robustes ;
* Généraliser les résultats au cadre des « inégalités du philosophe » \[4], où le critère de comparaison est l’algorithme en ligne optimal plutôt que la valeur maximale espérée, rendant la compétition plus dynamique ;
* Étudier les contextes où plusieurs objets sont alloués à des acheteurs, comme dans les enchères combinatoires ou les problèmes de sélection sur matroïdes \[5].

Étendre ces résultats pourrait offrir de nouvelles perspectives en conception de mécanismes, en enchères en ligne et en processus décisionnels stochastiques, où l’interdépendance joue un rôle central.

---

**Références :**

[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 44th ACM Symposium on Theory of Computing.* 2012.

Contexte de travail

La thèse sera réalisée sous la supervision de Vianney Perchet et Simon Mauras, dans l’équipe FairPlay basée au département de Statistique du CREST, et en collaboration avec Jose Correa à l’université du Chili. Nous proposons l’étude des "inégalités de prophète (problème d’optimisation mathématiques) et leurs applications en informatique et économie"

Contraintes et risques

RAS