  Envy-freeness up to one good (EF1) is a well-studied fairness notion for
indivisible goods that addresses pairwise envy by the removal of at most one
good. In the worst case, each pair of agents might require the (hypothetical)
removal of a different good, resulting in a weak aggregate guarantee. We study
allocations that are nearly envy-free in aggregate, and define a novel fairness
notion based on information withholding. Under this notion, an agent can
withhold (or hide) some of the goods in its bundle and reveal the remaining
goods to the other agents. We observe that in practice, envy-freeness can be
achieved by withholding only a small number of goods overall. We show that
finding allocations that withhold an optimal number of goods is computationally
hard even for highly restricted classes of valuations. In contrast to the
worst-case results, our experiments on synthetic and real-world preference data
show that existing algorithms for finding EF1 allocations withhold
close-to-optimal number of goods.

Computer Science and Game Theory