  Envy-freeness is a standard benchmark of fairness in resource allocation.
Since it cannot always be satisfied when the resource consists of indivisible
items even when there are two agents, the relaxations envy-freeness up to one
item (EF1) and envy-freeness up to any item (EFX) are often considered. We
establish tight lower bounds on the number of allocations satisfying each of
these benchmarks in the case of two agents. In particular, while there can be
as few as two EFX allocations for any number of items, the number of EF1
allocations is always exponential in the number of items. Our results apply a
version of the vertex isoperimetric inequality on the hypercube and help
explain the large gap in terms of robustness between the two notions.
