In the fair division of items among interested agents, envy-freeness is possibly the most favoured
and widely studied formalisation 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), which allows the removal of an item to resolve envy. A significant reason
for the popularity of EF1 allocations is its simple fact of existence, which supports research into
combining EF1 with other properties such as efficiency, or research into stronger properties such as
ex-ante envy-freeness. It is known that EF1 allocations exist for two agents with arbitrary valuations;
agents with doubly-monotone valuations; agents with Boolean valuations; and identical agents with
negative Boolean valuations. In fact the last two results were shown for the more stringent EFX
fairness requirement.
We consider two new but natural classes of valuations, and partly extend results on the existence
of EF1 allocations to these valuations. Firstly, we consider trilean valuations — an extension of
Boolean valuations — when the value of any subset is 0, a, or b for any integers a and b. Secondly,
we define separable single-peaked valuations, when the set of items is partitioned into types. For
each type, an agent’s value is a single-peaked 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 EF1 existence 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 EFX allocations do not exist.
