Fair division is a fundamental problem raised in many real word problems such as multi-robot task allocation, allocation of schools, courses
or rooms to students, division of goods ininheritance or divorce settlement… A multi agent fair division problem consists in dividing a set of resources among a set of agents while respecting a fairness notion.
Various fairness notions have been proposed and studied in economics and computer science.
The absence of envy is one of the most studied fairness notion. An agent i would envy another agent j if she prefers the share of j to her own share. A completely fair allocation would thus be an envy-free allocation i.e. an allocation where no agent is envious. However, as soon as it is required to allocate all the resources of the system, an envy-free allocation may not exist.
An alternative objective may then consist in minimizing the envy or requiring that the allocation is supported by a majority of agents against any other allocation. Such an allocation is called a popular allocation.
When each agent holds at most one resource and each resource is hold by at ost one agent, we turn to one-sided assignment problems. In this context, Kondratev et al. showed that a popular matching, when it exists, can be reached by a sequence of popular exchanges involving at most 3 agents. When a popular matching does not exist, Kondratev et al. generalised the algorithm of Abraham et al. and showed that a minimal envy matching can be obtained through a sequence of popular exchanges.
The internship proposal consists in studying how the therorectical results and algorithms proposed by Kondratev et al. extend to more general settings. We can first study whether popular matchings can be obtained by other types of local exchanges involving more agents or different voting rules that the strict majority rule. Another line of research consists in exploring the notion of popular allocations where each agent can hold several items.
References :
Aleksei Y. Kondratev, Alexander S. Nesterov, Minimal envy and popular matchings, European Journal of Operational Research, Volume 296, Issue 3, 2022
Abraham, D. J. , Irving, R. W. , Kavitha, T. , & Mehlhorn, K. (2007). Popular matchings. SIAM Journal on Computing, 37 (4), 1030–1045 .