SHAMS Parham

Docteur
Équipe : SMA
Date de départ : 31/12/2023
https://lip6.fr/Parham.Shams

Direction de recherche : Aurélie BEYNIER, Nicolas MAUDET

Co-encadrement : BOUVERET Sylvain

Procédures basées sur des échanges entre agents et nouvelles relaxations d'envy-freeness dans le partage équitable de ressources indivisibles

Cette thèse s'inscrit dans le contexte du Choix Social Computationnel. Il s'agit d'un domaine à l'intersection du Choix Social, de l'Informatique et de l'Intelligence Artificielle. Nous nous intéressons plus particulièrement au problème partage équitable de ressources indivisibles qui consiste à trouver une allocation équitable et efficace d'un ensemble d'objets à un ensemble d'agents. Tandis que la notion d'efficacité est communément traduite par l'exigence minimale de complétude (tous les objets doivent être alloués dans le but de ne gâcher aucun objet) ou la notion plus exigeante de Pareto-Optimalité (une allocation est dite Pareto-Optimale s'il n'existe pas une autre allocation telle que tous les agents sont au moins aussi contents et un agent est strictement plus content), plusieurs notions ont été proposées pour définir l'équité. Une des mesures d'équité la plus importante est l'absence d'envie. Une allocation est dite sans envie ou envy-free si aucun agent n'avait envie de changer ses objets contre ceux d'un autre agent. Cependant, il n'existe pas forcément d'allocation envy-free quand on est dans le cadre de ressources indivisibles. Afin de surmonter cette limitation, des relaxations ont été récemment proposées dans la littérature.
Dans cette thèse, nous étudions tout d'abord une famille de procédures décentralisées basée sur des échanges d'objets entre agents. Nous analysons en particulier comment ces procédures se comportent et les propriétés désirables qu'elles montrent. Plus précisément, on étudie les séquences de choix sincères et les cycles d'échanges de ressources. Dans un second temps, nous proposons de nouvelles relaxations de la notion d'absence d'envie (et d'autres mesures d'équité) et les étudions en profondeur. La première relaxation a pour but d'équilibrer l'envie entre les agents (quand elle ne peut être évitée) et se base sur l'Ordered Weighted Average (OWA), un agrégateur habituellement utilisé dans le domaine de l'optimisation multicritère pour traduire l'équité. La deuxième relaxation se concentre sur l'approbation sociale de l'envie et se rapproche plus de la théorie du vote étant donné que les agents votent sur l'envie des autres agents. Nous examinons les aspects computationnels liés à ces nouvelles relaxations, leurs liens avec des notions d'équité et d'efficacité existantes avant de les tester expérimentalement.

Soutenance : 21/12/2023

Membres du jury :

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é

Date de départ : 31/12/2023

Publications 2019-2023

Mentions légales
Carte du site