Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations

Daniel Halpern, Alexandros Psomas, Paritosh Verma +1

We consider the fundamental problem of allocating $T$ indivisible items that arrive over time to $n$ agents with additive preferences, with the goal of minimizing envy. This proble…