Abstract
We study the problem of allocating T indivisible
items that arrive online to agents with additive valuations. The allocation must satisfy a prominent
fairness notion, envy-freeness up to one item (EF1),
at each round. To make this possible, we allow
the reallocation of previously allocated items, but
aim to minimize these so-called adjustments. For
the case of two agents, we show that algorithms
that are informed about the values of future items
can get by without any adjustments, whereas uninformed algorithms require ?(T) adjustments. For
the general case of three or more agents, we prove
that even informed algorithms must use ?(T) adjustments, and design an uninformed algorithm that
requires only O(T3/2).