Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.00943 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909372944220160 |
|---|---|
| author | Fitzsimmons, Zack Viswanathan, Vignesh Zick, Yair |
| author_facet | Fitzsimmons, Zack Viswanathan, Vignesh Zick, Yair |
| contents | We study the problem of fair allocation of indivisible items when agents have ternary additive valuations -- each agent values each item at some fixed integer values $a$, $b$, or $c$ that are common to all agents. The notions of fairness we consider are max Nash welfare (MNW), when $a$, $b$, and $c$ are non-negative, and max egalitarian welfare (MEW). We show that for any distinct non-negative $a$, $b$, and $c$, maximizing Nash welfare is APX-hard -- i.e., the problem does not admit a PTAS unless P = NP. We also show that for any distinct $a$, $b$, and $c$, maximizing egalitarian welfare is APX-hard except for a few cases when $b = 0$ that admit efficient algorithms. These results make significant progress towards completely characterizing the complexity of computing exact MNW allocations and MEW allocations. En route, we resolve open questions left by prior work regarding the complexity of computing MNW allocations under bivalued valuations, and MEW allocations under ternary mixed manna. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00943 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Hardness of Fair Allocation under Ternary Valuations Fitzsimmons, Zack Viswanathan, Vignesh Zick, Yair Computer Science and Game Theory We study the problem of fair allocation of indivisible items when agents have ternary additive valuations -- each agent values each item at some fixed integer values $a$, $b$, or $c$ that are common to all agents. The notions of fairness we consider are max Nash welfare (MNW), when $a$, $b$, and $c$ are non-negative, and max egalitarian welfare (MEW). We show that for any distinct non-negative $a$, $b$, and $c$, maximizing Nash welfare is APX-hard -- i.e., the problem does not admit a PTAS unless P = NP. We also show that for any distinct $a$, $b$, and $c$, maximizing egalitarian welfare is APX-hard except for a few cases when $b = 0$ that admit efficient algorithms. These results make significant progress towards completely characterizing the complexity of computing exact MNW allocations and MEW allocations. En route, we resolve open questions left by prior work regarding the complexity of computing MNW allocations under bivalued valuations, and MEW allocations under ternary mixed manna. |
| title | On the Hardness of Fair Allocation under Ternary Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2403.00943 |