Thèse Jeux de Localisation d'Équipement en Dimensions Multiples H/F - Université Paris-Saclay GS Informatique et sciences du numérique

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique
École doctorale : Sciences et Technologies de l'Information et de la Communication
Laboratoire de recherche : IBISC - Informatique, BioInformatique, Systèmes Complexes
Direction de la thèse : Eric ANGEL ORCID 000000026759809X
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-03-22T23:59:59

Les jeux de localisation d'équipements constituent une classe fondamentale de problèmes en informatique théorique et en théorie des jeux algorithmique, dans lesquels des agents stratégiques déclarent leurs positions préférées au sein d'un espace métrique abstrait. L'objectif est de concevoir des mécanismes qui sélectionnent les emplacements des équipements afin de minimiser des objectifs sociaux formels, tels que le coût social (la somme des distances des agents à l'équipement le plus proche) ou le coût maximum, tout en garantissant la strategyproofness (propriété selon laquelle les agents n'ont aucune incitation à déclarer de fausses préférences). Historiquement, la littérature a été dominée par des analyses dans des espaces unidimensionnels, où les agents et les équipements sont situés sur une ligne. Ce cadre largement exploré a donné lieu à des recherches approfondies sur diverses extensions théoriques, notamment le placement discret d'équipements [1,2], les jeux à localisations multiples [3,4], et les agents dotés de structures de préférences complexes [5-8].

Dans cette thèse, nous nous concentrons sur l'extension de cette théorie aux espaces multidimensionnels, plus précisément à l'espace métrique général L\_p (R^d), l'espace à d dimensions muni de la norme L\_p. Cette généralisation est motivée par l'objectif de développer un cadre théorique plus complet pour les problèmes d'allocation spatiale, dépassant ainsi le cas unidimensionnel analytiquement restrictif.

Une avancée récente [10] a radicalement changé la perspective. Elle a établi que le mécanisme naturel de la médiane coordonnée par coordonnée, pour un équipement, obtient un ratio d'approximation constant (3) en toute dimension, invalidant la conjecture ancienne d'une dégradation en d [9].

S'appuyant directement sur ce changement conceptuel, cette thèse vise à entreprendre une investigation théorique complète des mécanismes strategyproof pour les jeux de localisation d'équipements en haute dimension. Notre objectif est de réexaminer et de généraliser systématiquement le riche corpus de résultats unidimensionnels au sein de ce cadre mathématique plus général et expressif, afin d'en tirer des enseignements fondamentaux sur la conception et les limites des mécanismes d'allocation robustes dans des domaines complexes.

Dans cette thèse, nous visons à relever des défis théoriques fondamentaux dans la conception de mécanismes en haute dimension à travers trois axes clés :

1. Mécanismes randomisés dans des espaces métriques abstraits. Bien que des mécanismes déterministes comme la médiane coordonnée par coordonnée atteignent un ratio d'approximation constant en théorie, les limites fondamentales des mécanismes strategyproof randomisés restent floues. Nous étudierons le potentiel mathématique de la randomisation pour améliorer les bornes d'approximation connues ou pour surpasser des résultats d'impossibilité établis dans des contextes de haute dimension.
2. Localisation d'équipements dans un domaine discret. L'analyse des mécanismes strategyproof lorsque les équipements doivent être placés dans un ensemble discret et abstrait d'emplacements réalisables est incomplète pour les espaces de haute dimension. Nous visons à établir des ratios d'approximation serrés, déterminant à la fois des bornes supérieures et inférieures, pour les mécanismes déterministes et randomisés dans ce cadre. Cela implique d'étendre des techniques abstraites unidimensionnelles pour gérer la complexité combinatoire et géométrique des dimensions supérieures.

This thesis falls within the field of algorithmic game theory, and more specifically within the subdomain of mechanism design. The central objective is to design decision rules (the mechanisms) that, when faced with strategic and self-interested agents, produce an efficient collective outcome while incentivizing those agents to honestly reveal their preferences.

We aim to define mechanisms that incentivize agents to reveal their true information, while minimizing the efficiency gap relative to the theoretical optimal solution. This involves establishing the optimal achievable trade-off between truthful reporting (strategyproofness) and the economic efficiency of the system.
The thesis is anchored in the core disciplines of algorithmic game theory, combinatorial optimization. It falls within the domain of learning-augmented algorithms and aims to address decision-making problems in uncertain environments, developing mathematically robust theoretical frameworks for incentive-compatible system design.

Le candidat sélectionné doit :

- Avoir obtenu avec succès une offre formelle de doctorat de la City University of Hong Kong dans le cadre de l'accord de cotutelle.
- Être titulaire d'un master en recherche opérationnelle, en informatique, en mathématiques appliquées ou dans un domaine étroitement connexe. Les candidats titulaires d'une licence et justifiant d'une expérience avérée en recherche dans l'un de ces domaines seront également considérés.
- Posséder de solides connaissances en algorithmique (optimisation combinatoire, algorithmes exacts et approchés, analyse d'algorithmes).