Complexity of Round-Robin Allocation with Potentially Noisy Queries
Abstract
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 O(nm log(m/n)) time 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 Ω(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 may be incorrect with certain probabilities.
implemented in O(nm log(m/n)) time 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 Ω(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 may be incorrect with certain probabilities.
