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 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.

References in corpus (8)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Picking Sequences and Monotonicity in Weighted Fair Division
• Closing Gaps in Asymptotic Fair Division
• Asymptotic Existence of Proportionally Fair Allocations
• When Do Envy-Free Allocations Exist?
• Fairly Allocating Many Goods with Few Queries
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
• On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature