Rémi Castera

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.