- FR
- EN
Thursday December 15, 2022 at 11am. (room Espace One, Paris Dauphine)
Ioannis Caragiannis (Aarhus University, Denmark)
Title: New Fairness Concepts for Allocating Indivisible Items
Absract:
In a fair division model that has recently received much attention, a set of indivisible items has to be allocated to a set of agents who have values for the items. Fairness of allocations is usually interpreted in two ways. The first interpretation is comparative; to evaluate an allocation as fair, each agent compares the bundle of items allocated to her to bundles of items allocated to other agents. The concept of envy-freeness up to any item (abbreviated as EFX) is the most compelling comparative fairness criterion. An allocation is EFX if every agent prefers her bundle to the bundle allocated to any other agent after removing any single item from the latter. The second interpretation is in more absolute terms. In this category, each agent defines a threshold value based on her view of the allocation instance (the set of items, the number of agents, her valuation function, etc.) and evaluates as fair those allocations in which she gets a bundle of value that exceeds the threshold. Variations of proportionality are the typical examples here, with max-min fair share (MMS) being the fairness concept that has attracted the lion’s share of attention.
Despite intensive research efforts, it is still unknown whether EFX allocations always exist for sufficiently broad valuation functions and instances with more than three agents. Actually, even if such allocations always exist, polynomial-time algorithms to find them do not seem to be within reach. Furthermore, today we know that MMS allocations may not exist, and the research has focused on finding the best possible “fairness approximation”.
In this talk, we will present two new fairness notions inspired by envy-freeness up to any item (EFX). The first one, called epistemic EFX (EEFX), is comparative and is defined as follows. An allocation is EEFX if, for every agent, there is a redistribution of the items not allocated to the agent so that the EFX conditions for her are satisfied. The second one, called minimum EFX value (MXS), is absolute and requires that each agent gets a value that is at least as high as the minimum value the agent gets among all allocations where the EFX conditions for her are satisfied. We argue about the importance of these fairness concepts as alternatives to EFX and MMS, showing that allocations that satisfy them always exist and can be computed efficiently.
The talk is based on joint work with Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio.
