GROSS-HUMBERT Nathanaël

PhD student at Sorbonne University
Team : SMA
https://sites.google.com/view/gross--humbertnathanael/accueil

Supervision : Aurélie BEYNIER

Co-supervision : BENABBOU Nawal, MAUDET Nicolas

Study of the notion of diversity in the context of allocation problems with groups of agents

The purpose of this thesis is to study the notions of fairness and diversity in resource allocation problems where the agent set is partitioned into types. These concepts have numerous applications, first among them being the Singapour housing allocation problem, which inspired our model. Other applications include allocating students to schools or medical resources to hospital.
This work follows to the main axis, the first one is about allocation mechanism within the context of a model with diversity constraints, while the second one is about equity between types of agents using the notion in envy.
In the first part, we study a model for which, just as the agent set is partitioned into a set of types, the item set is partitioned into a set of blocks, and there are diversity quotas between these types and these blocks. We introduce a dynamic of individual improvement in which agents are allowed to improve their allocation by swapping their item with another (willing) agent. This dynamic create a notion of stability, for which an allocation is stable if no pair of agent wish to swap their item. We then study the theoretical property of this notion of stability, before considering two different methods for generating allocation. The first one, the lottery mechanism, consists of ordering the set of agents, then allowing each one in turn to pick their favorite item. The second one relies on the dynamic we just introduced: we start from a random allocation, and we apply improving swap between agents until we reach a stable allocation. We then describe several series of experiments made using these mechanisms, and discuss their results.
The second main contribution is about the notion of equity, which we consider through the lens of envy and envy-freeness. We define 4 axioms which stands for properties we consider to be critical to a relevant definition of envy. We then list the definitions of envy commonly used in the literature, and we check whether or not they satisfy the axioms. We then define our own notions of envy, which relies on comparison using subgroups. We first study whether or not they satisfy the axioms, then their computational aspects. We then discuss the different possible interpretations of the concept of monotony.
We then relax our notions of envy by defining the degree of envy. However, we show that it is hard to compute, we thus bring forward two ways to approximate its computation. The first and most efficient one relies on a reduction to a variant of the knapsack problem, while the second one uses a succession of samples made using a Markov chain. While the theoretical complexity of this second method is very high, experimental results suggest convergence is in practice much faster.

Defence : 09/04/2024

Jury members :

Umberto GRANDI, Professeur, Université Toulouse Capitole [Rapporteur]
Ramón PINO PÉREZ, Professeur, Universidad de Los Andes [Rapporteur]
Jérôme LANG, Directeur de recherche, Université Paris Dauphine - PSL
Anaëlle WILCZYNSKI, Maîtresse de conférences, CentraleSupélec
Nawal BENABBOU, Maîtresse de conférences, Sorbonne Université
Nicolas MAUDET, Professeur, Sorbonne Université
Aurélie BEYNIER, Maîtresse de conférences, Sorbonne Université

Departure date : 09/30/2024

2021-2024 Publications