Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.09869 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913988653088768 |
|---|---|
| author | Kyropoulou, Maria Voudouris, Alexandros A. |
| author_facet | Kyropoulou, Maria Voudouris, Alexandros A. |
| contents | We consider a resource allocation problem with agents that have additive ternary valuations for a set of indivisible items, and bound the price of envy-free up to one item (EF1) allocations. For a large number $n$ of agents, we show a lower bound of $Ω(\sqrt{n})$, implying that the price of EF1 is no better than when the agents have general subadditive valuations. We then focus on instances with few agents and show that the price of EF1 is $12/11$ for $n=2$, and between $1.2$ and $1.256$ for $n=3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Price of EF1 for Few Agents with Additive Ternary Valuations Kyropoulou, Maria Voudouris, Alexandros A. Computer Science and Game Theory We consider a resource allocation problem with agents that have additive ternary valuations for a set of indivisible items, and bound the price of envy-free up to one item (EF1) allocations. For a large number $n$ of agents, we show a lower bound of $Ω(\sqrt{n})$, implying that the price of EF1 is no better than when the agents have general subadditive valuations. We then focus on instances with few agents and show that the price of EF1 is $12/11$ for $n=2$, and between $1.2$ and $1.256$ for $n=3$. |
| title | The Price of EF1 for Few Agents with Additive Ternary Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.09869 |