Wednesday the 16th of October 2024
- Share
- Share on Facebook
- Share on X
- Share on LinkedIn
Efficiency and Fairness in Matching Problems
Abstract:
Matching problems are ubiquitous, as they arise in school choice, college admission, job markets, and even refugee resettlement. The literature about matching historically focuses on efficiency and stability, but recently interest has been growing around questions on fairness. This thesis aims to contribute to this emergent work. Assume that a population is divided into groups, representing different demographics, and the aim is to treat all groups fairly when choosing a matching. I consider various definitions of fairness towards those groups (a concept called group fairness), and which parameters of each studied model play a role in the existence or the optimality of a fair matching. In particular, I study the trade-off between fairness and efficiency, defined as the size of the matching when there are no preferences, or the satisfaction of agents when there are preferences. In the setting with no preferences, I propose an original geometric representation of the problem that allows me to give conditions for the existence of a matching that is maximal and fair, and when it does not exist, I provide tight bounds on the ratio between the size of the largest matching and the size of the largest fair matching (I call this ratio the Price of Fairness). In the setting with preferences, that I model as a college admission problem with students on one side and colleges on the other side, I study the role of the correlation between colleges’ rankings of students. I show that correlation improves the efficiency of the stable matching. Moreover, when different groups have different levels of correlation in their rankings by the colleges, it creates disparities in each group’s rate of students that remain unassigned, even when each college’s individual ranking is completely fair towards each group. I also show that when colleges’ rankings are fair, there is no trade-off between efficiency and fairness, in the sense that both can be achieved simultaneously.
Date and place
Wednesday the 16th of October 2024 at 15:00
Amphitéatre, Maison du doctorat Jean Kuntzmann
Supervisors
Patrick Loiseau
Directeur de recherche, INRIA/Fairplay, directeur de thèse
Directeur de recherche, INRIA/Fairplay, directeur de thèse
Bary Pradelski
Chargé de recherche, CNRS/LIG/Maison française d'Oxford, co-encadrant
Chargé de recherche, CNRS/LIG/Maison française d'Oxford, co-encadrant
Jury members
Utku Unver
Professor, Boston College - Reviewer
Bruno Escoffier
Professeur des universités, Sorbonne Université/LIP6- Reviewer
Professeur des universités, Sorbonne Université/LIP6- Reviewer
Claire Mathieu
Directrice de recherche, CNRS/IRIF - Examiner
Directrice de recherche, CNRS/IRIF - Examiner
Rida Laraki
Directeur de recherche, UM6P/CNRS - Examiner
Directeur de recherche, UM6P/CNRS - Examiner
Bettina Klaus
Professor, Université de Lausanne - Examiner
Professor, Université de Lausanne - Examiner
Kim Thang Nguyen
Professeur des universités, UGA/LIG - Examiner
Professeur des universités, UGA/LIG - Examiner
- Share
- Share on Facebook
- Share on X
- Share on LinkedIn