Envy-free Relaxations for Goods, Chores, and Mixed Items

Understand

In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair.

• There are several established fairness concepts and envy-freeness is one of the most extensively studied ones.
• However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations.
• We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting.