Complexity of Round-Robin Allocation with Potentially Noisy Queries
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912522359013376 |
|---|---|
| author | Li, Zihan Manurangsi, Pasin Scarlett, Jonathan Suksompong, Warut |
| author_facet | Li, Zihan Manurangsi, Pasin Scarlett, Jonathan Suksompong, Warut |
| contents | 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 $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19402 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of Round-Robin Allocation with Potentially Noisy Queries Li, Zihan Manurangsi, Pasin Scarlett, Jonathan Suksompong, Warut Computer Science and Game Theory Computational Complexity Information Theory 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 $Ω(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. |
| title | Complexity of Round-Robin Allocation with Potentially Noisy Queries |
| topic | Computer Science and Game Theory Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2404.19402 |