Thèse Popularity In Matching Under Preferences H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Sciences de l'ingénierie et des systèmes École doctorale : Interfaces : matériaux, systèmes, usages Laboratoire de recherche : Mathématiques et Informatique pour la Complexité et les Systèmes - EA 4037 Direction de la thèse : Wassila OUERDANE ORCID 0000000245157461 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-23T23:59:59 De nombreuses applications concrètes concernent les appariements sous préférences [Klaus et al., 2016], où des agents doivent être affectés à des éléments selon leurs préférences. On peut citer, par exemple, l'affectation d'étudiants à des universités ou de résidents à des hôpitaux, le marché de l'emploi ou du logement, ou encore la formation de groupes de travail.
Une propriété importante recherchée pour les appariements est la popularité [Cseh, 2017], un concept bien établi qui vise à sélectionner des appariements pour lesquels il n'existe pas d'autre appariement préféré par un plus grand nombre d'agents. Un appariement populaire est l'équivalent d'un gagnant de Condorcet faible en théorie du vote (c'est-à-dire un candidat qui n'est jamais battu par un autre lors de comparaisons par paires), lorsque tous les appariements possibles sont considérés comme des candidats.
Cependant, comme en théorie du vote, un appariement populaire n'existe pas toujours. Plusieurs relaxations ont donc été proposées dans la littérature, par exemple en considérant des solutions aléatoires [Kavitha et al., 2011], ou en minimisant le nombre d'agents envieux [Kondratev et Nesterov, 2022]. Une autre possibilité consiste à adapter au contexte des appariements les généralisations du gagnant de Condorcet, largement étudiées en théorie du vote (voir, par exemple, les solutions de tournoi [Brandt et al., 2016]). À notre connaissance, cette piste de recherche n'a commencé à être explorée que très récemment [Brandt et al., 2026].
La majorité des travaux sur les appariements populaires ont été menés dans le cadre de préférences unilatérales (c'est-à-dire lorsque des agents sont affectés à des objets sans préférences propres), où une caractérisation élégante de la popularité a été obtenue [Abraham et al., 2007]. Cette caractérisation permet notamment de résoudre en temps polynomial le problème de l'existence d'un appariement populaire.
En revanche, lorsque les agents sont appariés avec d'autres agents, le problème de l'existence a été montré comme étant NP-complet [Gupta et al., 2021 ; Faenza et al., 2019], et seule une caractérisation technique - relativement directe - de la popularité a été établie jusqu'à présent [Huang et Kavitha, 2013]. De plus, à notre connaissance, aucune relaxation de la popularité reposant sur la relation majoritaire entre appariements n'a encore été proposée. L'objectif de cette thèse est d'étudier des relaxations de la popularité qui adaptent les généralisations des gagnants de Condorcet, dans la continuité des travaux de Brandt et al. [2026]. Alors que la plupart des recherches ont proposé des relaxations dans le cadre de préférences unilatérales, nous prévoyons d'explorer davantage le cas où les agents sont appariés avec d'autres agents. En parallèle, nous souhaitons apporter une compréhension plus approfondie de la structure des appariements populaires dans ce contexte. De nombreuses applications concrètes concernent les appariements sous préférences [Klaus et al., 2016], où des agents doivent être affectés à des éléments selon leurs préférences. On peut citer, par exemple, l'affectation d'étudiants à des universités ou de résidents à des hôpitaux, le marché de l'emploi ou du logement, ou encore la formation de groupes de travail.
Une propriété importante recherchée pour les appariements est la popularité [Cseh, 2017], un concept bien établi qui vise à sélectionner des appariements pour lesquels il n'existe pas d'autre appariement préféré par un plus grand nombre d'agents. Un appariement populaire est l'équivalent d'un gagnant de Condorcet faible en théorie du vote (c'est-à-dire un candidat qui n'est jamais battu par un autre lors de comparaisons par paires), lorsque tous les appariements possibles sont considérés comme des candidats.
Cependant, comme en théorie du vote, un appariement populaire n'existe pas toujours. Plusieurs relaxations ont donc été proposées dans la littérature, par exemple en considérant des solutions aléatoires [Kavitha et al., 2011], ou en minimisant le nombre d'agents envieux [Kondratev et Nesterov, 2022]. Une autre possibilité consiste à adapter au contexte des appariements les généralisations du gagnant de Condorcet, largement étudiées en théorie du vote (voir, par exemple, les solutions de tournoi [Brandt et al., 2016]). À notre connaissance, cette piste de recherche n'a commencé à être explorée que très récemment [Brandt et al., 2026].
La majorité des travaux sur les appariements populaires ont été menés dans le cadre de préférences unilatérales (c'est-à-dire lorsque des agents sont affectés à des objets sans préférences propres), où une caractérisation élégante de la popularité a été obtenue [Abraham et al., 2007]. Cette caractérisation permet notamment de résoudre en temps polynomial le problème de l'existence d'un appariement populaire.
En revanche, lorsque les agents sont appariés avec d'autres agents, le problème de l'existence a été montré comme étant NP-complet [Gupta et al., 2021 ; Faenza et al., 2019], et seule une caractérisation technique - relativement directe - de la popularité a été établie jusqu'à présent [Huang et Kavitha, 2013]. De plus, à notre connaissance, aucune relaxation de la popularité reposant sur la relation majoritaire entre appariements n'a encore été proposée. The goal of this PhD is to investigate relaxations of popularity that adapt generalized Condorcet winners
in the line of the work of Brandt et al. [2026]. While most works have proposed relaxations in the setting
of one-sided preferences, we plan to further investigate the case where agents are matched with other
agents. In the same time, we plan to provide deeper insights on the structure of popular matchings in
that setting. he work will be mainly axiomatic but an algorithmic point of view will also be used via the design of
polynomial-time algorithms to construct solutions or complexity proofs. A deeper understanding of the structure of popular matchings could also be done via algebraic tools.

Master 2 recherche, diplôme d'ingénieur ou formation équivalente en informatique, mathématiques appliquées ou intelligence artificielle. Un bon niveau académique en algorithmic game theory et/ou en choix social computationnel est attendu.