Thèse Mécanismes Véridiques pour la Localisation Fiable d'Installations H/F doctorat.gouv.fr

  • Paris - 75
  • CDD
  • Service public d'état
Lire dans l'app

Détail du poste

É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 : 2027-10-01 Date limite de candidature : 2027-01-07T23:59:59 Les problèmes de localisation d'installations étudient le choix de sites de service à partir des positions déclarées par des agents. Un mécanisme doit concilier l'efficacité collective et la véracité des déclarations : aucun agent ne doit pouvoir réduire son coût en mentant sur sa position. Les modèles classiques supposent que les installations restent disponibles. Cette hypothèse ne convient pas toujours aux services vulnérables aux pannes, tels que les bornes de recharge ou les dispensaires. Lorsqu'une installation est indisponible, l'usager doit rejoindre la plus proche installation encore opérationnelle. Cette thèse étudiera comment cette incertitude modifie la conception des mécanismes et leurs garanties d'efficacité.

Le modèle de départ comporte n agents et k installations dans un espace métrique. Chaque installation tombe en panne indépendamment avec une probabilité q, identique pour toutes. Un agent est servi par l'installation opérationnelle la plus proche. Pour définir un coût fini, l'analyse sera conditionnée à la disponibilité d'au moins une installation. Si les installations sont ordonnées par distance à l'agent, le poids de la j-ième installation est alors (1-q)q^(j-1)/(1-q^k), avec une règle de départage fixée en cas d'égalité. Cette définition rend explicite l'hypothèse de survie déjà utilisée dans la proposition. La véracité signifie que, quels que soient les rapports des autres agents, chaque agent minimise son coût espéré en déclarant sa position réelle.

La localisation fiable a été étudiée comme problème d'optimisation : les travaux de Snyder et Daskin portent notamment sur les modèles p-médiane et à coûts fixes; Berman, Krass et Menezes étudient les effets de centralisation et de colocalisation; Cui et al. puis Shen et al. analysent les perturbations, la réaffectation des usagers et les algorithmes d'approximation [5-8]. De leur côté, les travaux sur la conception de mécanismes étudient les incitations stratégiques en l'absence de ces pannes [1-4]. La question centrale est donc l'interaction entre ces deux cadres : quelles garanties de véracité et d'efficacité résistent lorsque les installations peuvent être indisponibles, et lesquelles doivent être repensées ?

Nous comparerons chaque mécanisme à une solution optimale soumise au même budget k et au même modèle de panne. Deux objectifs seront étudiés séparément : le coût social espéré, égal à la somme des coûts espérés des agents, et le coût individuel espéré maximal, max_i E[C_i]. Le travail cherchera à caractériser l'existence de mécanismes véridiques, à établir des garanties d'approximation, et à construire des bornes supérieures et inférieures serrées ou des résultats d'impossibilité. Une attention particulière sera portée à la dépendance des garanties vis-à-vis de q et de k. L'analyse distinguera le surcoût associé aux contraintes d'incitation de celui lié aux pannes, en comparant mécanismes et optimum sous les mêmes hypothèses de fiabilité. Elle précisera pour quels paramètres une garantie à facteur constant est possible ou si des instances adverses imposent des bornes plus faibles.

Le projet examinera ensuite dans quelle mesure les résultats obtenus s'étendent aux espaces de dimension supérieure et à différentes normes. Ces sujets font déjà l'objet de travaux récents en conception de mécanismes [9-11]; leur intérêt ici devra donc provenir de l'interaction avec la fiabilité, et non de la seule géométrie. La contribution attendue est une analyse théorique qui relie explicitement les probabilités de panne, les incitations des agents et la qualité du service mesurée par le coût espéré.
This project lies at the intersection of algorithmic game theory, mechanism design, and reliable facility location. Optimization research studies how to maintain service under facility disruptions, while mechanism-design research studies how to make location decisions when agents may misreport their positions. The central question is how facility failures affect truthful incentives and approximation guarantees. Recent work on high-dimensional and norm-based strategic facility location [9-11] makes it necessary to state precisely which reliability-dependent results are new; dimension and norm extensions will therefore be treated as a scoped research question, not as a novelty claim on their own. The thesis aims to formalize the trade-off between truthful reporting and efficiency when service facilities may fail. It will characterize strategyproof mechanisms under a specified reliability model and quantify their worst-case performance against an optimum subject to the same facility budget and failure assumptions. The main parameters are the failure probability q and the number k of facilities. We will first formalize the failure process, the conditional expected-cost model, the agents' incentives, and the benchmark optimum. We will then analyze strategyproof mechanisms for the baseline setting, derive approximation upper bounds, and construct lower-bound instances to assess their tightness. The analysis will track the dependence on q and k and distinguish the social-cost objective from maximum expected individual cost. A final comparative study will examine extensions to selected geometries or norms where the literature review identifies a precise open question. Results will be established through mathematical proofs.

Le profil recherché

Le candidat sélectionné doit :
- Avoir obtenu avec succès une offre formelle de doctorat de l'Université de la ville de Hong Kong dans le cadre de l'accord de cotutelle.
- Etre titulaire d'une maîtrise en recherche opérationnelle, en informatique, en mathématiques appliquées ou dans tout autre domaine connexe.
- Avoir une solide connaissance des algorithmes (optimisation combinatoire, algorithmes exacts et approximatifs et analyse d'algorithmes).

Publiée le 29/10/2026 - Réf : 238392c6c6f9eef6f4506869871ee7ff

Postuler
Créez votre compte
Hellowork et postulez

sur le site du partenaire !

Ces offres pourraient aussi
vous intéresser

AIRCOS recrutement
AIRCOS recrutement
Clichy - 92
CDI
35 000 - 50 000 € / an
Voir l’offre
il y a 24 jours
Safran recrutement
Voir l’offre
il y a 19 jours
Acadomia recrutement
Acadomia recrutement
Dampmart - 77
CDD
Temps partiel
20 - 23 € / heure
Voir l’offre
il y a 9 jours
Voir plus d'offres
Les sites
L'emploi
  • Offres d'emploi par métier
  • Offres d'emploi par ville
  • Offres d'emploi par entreprise
  • Offres d'emploi par mots clés
L'entreprise
  • Qui sommes-nous ?
  • On recrute
  • Accès client
Les apps
Nous suivre sur :
Informations légales CGU Politique de confidentialité Gérer les traceurs Accessibilité : non conforme Aide et contact