Aller au contenu principal

Rémi Castera

Mercredi 16 Octobre 2024

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 et lieu

Mercredi 16 Octobre à 15:00
Amphitéatre, Maison du doctorat Jean Kuntzmann

Supervision

Patrick Loiseau
Directeur de recherche, INRIA/Fairplay, directeur de thèse
Bary Pradelski
Chargé de recherche, CNRS/LIG/Maison française d'Oxford, co-encadrant

Composition du Jury

Utku Unver
Professor, Boston College  - Reviewer
Bruno Escoffier
Professeur des universités, Sorbonne Université/LIP6- Reviewer
Claire Mathieu
Directrice de recherche, CNRS/IRIF - Examiner
Rida Laraki
Directeur de recherche, UM6P/CNRS - Examiner
Bettina Klaus
Professor, Université de Lausanne - Examiner
Kim Thang Nguyen
Professeur des universités, UGA/LIG - Examiner

Publié le 27 septembre 2024

Mis à jour le 7 novembre 2024