Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912401394237440 |
|---|---|
| author | Verma, Arun Saha, Indrajit Yokoo, Makoto Low, Bryan Kian Hsiang |
| author_facet | Verma, Arun Saha, Indrajit Yokoo, Makoto Low, Bryan Kian Hsiang |
| contents | This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that has to be irrevocably allocated to one of the agents while satisfying a fairness and efficiency constraint. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy bandit feedback. However, this assumption may not hold in many real-life applications, for example, an online platform that has a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), which makes it difficult to accurately estimate utilities for all item-agent pairs. To address this, we assume utility is an unknown function of item-agent features. We then propose algorithms that model online fair division as a contextual bandit problem, with sub-linear regret guarantees. Our experimental results further validate the effectiveness of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12845 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies Verma, Arun Saha, Indrajit Yokoo, Makoto Low, Bryan Kian Hsiang Machine Learning Artificial Intelligence This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that has to be irrevocably allocated to one of the agents while satisfying a fairness and efficiency constraint. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy bandit feedback. However, this assumption may not hold in many real-life applications, for example, an online platform that has a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), which makes it difficult to accurately estimate utilities for all item-agent pairs. To address this, we assume utility is an unknown function of item-agent features. We then propose algorithms that model online fair division as a contextual bandit problem, with sub-linear regret guarantees. Our experimental results further validate the effectiveness of the proposed algorithms. |
| title | Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2408.12845 |