SHAMS Parham

PhD student at Sorbonne University
Team : SMA
https://lip6.fr/Parham.Shams

Supervision : Aurélie BEYNIER, Nicolas MAUDET

Co-supervision : BOUVERET Sylvain

Procedures based on Exchanges and new Relaxations of Envy-Freeness in Fair Division of Indivisible Goods

The work of this thesis is in the scope of Computational Social Choice. It is a field at the intersection of Social Choice, Computer Science and Artificial Intelligence. In particular, we study the problem of Fair Division of Indivisible Goods where the objective is to find a fair and efficient allocation of a set of (valuable) objects among a set of agents. While efficiency is usually brought by the minimal requirement of completeness (all the objects have to be allocated in order not to waste anything), or the more demanding notion of Pareto-Optimality (an allocation is Pareto-Optimal if there is no allocation such that all the agents are not worse off and one agent is strictly better off), several notions have been proposed to define the fairness of an allocation. One of the most prominent fairness measures is called envy-freeness. An allocation is said to be envy-free if no agent would like to exchange her bundle of resources with another agent. However, envy-freeness is not guaranteed to exist when considering indivisible goods so various relaxation has been proposed recently in the literature to overcome this limitation.
In this thesis, we first thoroughly study a family of decentralized allocation procedures related to exchanges of goods. We analyze how these procedures behave and the desirable properties they exhibit. More specifically, we study sequence of sincere choices and cycle exchanges of resources. We then propose new relaxation of the envy-freeness notion (and also of other fairness measures) and thoroughly study them. Our first relaxation aims at balancing the envy among the agents (when it cannot be avoided) and is based on the Order Weighted Average (OWA) aggregator usually used in multi-criterion optimization to bring fairness. The second relaxation focuses on the social approval of the envy and is more related to voting theory, as it lets agents vote about the envy of the other agents. We investigate computational issues related to these new relaxation, their link with existing fairness and efficiency notions and we experimentally test them.

Defence : 12/21/2023

Jury members :

Gauthier Picard, Directeur de Recherche, ONERA, Université de Toulouse [Rapporteur]
Agnieszka Rusinowska, Directrice de Recherche, Centre d'Economie de la Sorbonne, Université Paris 1 Panthéon Sorbonne [Rapporteur]
Bruno Escoffier, Professeur, LIP6, Sorbonne Université
Laurent Gourves, Directeur de Recherche, LAMSADE, Université Paris Dauphine
Aurélie Beynier, Maître de conférences HDR, LIP6, Sorbonne Université
Sylvain Bouveret, Maître de conférences, LIG, Université Grenoble-Alpes
Nicolas Maudet, Professeur, LIP6, Sorbonne Université

Departure date : 12/31/2023

2019-2023 Publications