Kyropoulou, Maria and Voudouris, Alexandros (2025) The Price of EF1 for Few Agents with Additive Ternary Valuations. Operations Research Letters, 63. p. 107351. DOI https://doi.org/10.1016/j.orl.2025.107351
Kyropoulou, Maria and Voudouris, Alexandros (2025) The Price of EF1 for Few Agents with Additive Ternary Valuations. Operations Research Letters, 63. p. 107351. DOI https://doi.org/10.1016/j.orl.2025.107351
Kyropoulou, Maria and Voudouris, Alexandros (2025) The Price of EF1 for Few Agents with Additive Ternary Valuations. Operations Research Letters, 63. p. 107351. DOI https://doi.org/10.1016/j.orl.2025.107351
Abstract
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 Ω(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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Fair division; EF1 allocations; Price of EF1 |
| Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 30 Jul 2025 15:00 |
| Last Modified: | 20 Aug 2025 23:15 |
| URI: | http://repository.essex.ac.uk/id/eprint/41352 |
Available files
Filename: 1-s2.0-S0167637725001129-main.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 4.0