Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.09869 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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$.