Abstract
We consider a fair division setting in which items
arrive one by one and are allocated to agents via
two existing mechanisms: LIKE and BALANCED
LIKE. The LIKE mechanism is strategy-proof
whereas the BALANCED LIKE mechanism is not.
Whilst LIKE is strategy-proof, we show that it is
not group strategy-proof. Indeed, our first main result is that no online mechanism is group strategyproof. We then focus on pure Nash equilibria of
these two mechanisms. Our second main result is
that computing a pure Nash equilibrium is tractable
for LIKE and intractable for BALANCED LIKE. Our
third main result is that there could be multiple such
profiles and counting them is also intractable even
when we restrict our attention to equilibria with a
specific property (e.g. envy-freeness).