The Price of EF1 for Few Agents with Additive Ternary Valuations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |