2024/04/30 by Zihan Li, Pasin Manurangsi, Li, Zihan +5 · 4 citations
Computer Science · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT) #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2404.19402
openalex publication_date 2024/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nmlog(m/n)) in the worst case. If the agents' preferences are uniformly random, we establish an improved (expected) running time of O(nm + mlog m). On the other hand, assuming comparison queries between items, we prove that Ω(nm + mlog 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.