Towards Envy-Freeness Relaxations for General Nonmonotone Valuations

In the fair division of items among interested agents, envy-freeness is possibly the most favoured and widely studied formalization of fairness. For indivisible items, envy-free allocations may not exist in trivial cases, and hence research and practice focus on relaxations, particularly envy-freeness up to one item (EF1) and up to any item (EFX). Though EFX is a tighter relaxation, a significant reason for the popularity of EF1 is the simple fact of its existence. This raises the question if in fact EF1 allocations exist for all valuations. Towards this objective, we present three results. We show that for all valuations, there exists an EFX allocation with charity, when some non-envied subset of items can remain unallocated. Secondly, we consider two new but natural classes of valuations: (i) Trilean valuations-an extension of Boolean valuations-when the value of any subset is 0, 𝑎, or 𝑏 for any integers 𝑎 and 𝑏, and (ii) Separable single-peaked valuations, when the set of items is partitioned into types. For each type, an agent's value is a singlepeaked function of the number of items of the type. The value for a set of items is the sum of values for the different types. We prove the existence of complete EF1 allocations for identical trilean valuations for any number of agents and for separable single-peaked valuations for three agents. For both classes of valuations, we also show that complete EFX allocations do not exist.