Complexity of Round-Robin Allocation with Potentially Noisy Queries

Zihan Li, Pasin Manurangsi, Jonathan Scarlett +1

We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For $n$ agents and $m$ items, we show that the algorithm can…