Document detail
ID
oai:arXiv.org:2404.19402
Topic
Computer Science - Computer Scienc... Computer Science - Computational C... Computer Science - Information The...Author
Li, Zihan Manurangsi, Pasin Scarlett, Jonathan Suksompong, WarutCategory
Computer Science
Year
2024
listing date
5/8/2024
Keywords
items theory $ complexity computer scienceAbstract
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 be implemented in time $O(nm\log(m/n))$ in the worst case.
If the agents' preferences are uniformly random, we establish an improved (expected) running time of $O(nm + m\log m)$.
On the other hand, assuming comparison queries between items, we prove that $\Omega(nm + m\log m)$ queries are necessary to implement the algorithm, even when randomization is allowed.
We also derive bounds in noise models where the answers to queries are incorrect with some probability.
Our proofs involve novel applications of tools from multi-armed bandit, information theory, as well as posets and linear extensions.
Li, Zihan,Manurangsi, Pasin,Scarlett, Jonathan,Suksompong, Warut, 2024, Complexity of Round-Robin Allocation with Potentially Noisy Queries
