Improved Maximin Share Approximations for Chores by Bin Packing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916471195566080 |
|---|---|
| author | Garg, Jugal Huang, Xin Segal-Halevi, Erel |
| author_facet | Garg, Jugal Huang, Xin Segal-Halevi, Erel |
| contents | We study fair division of indivisible chores among $n$ agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more than two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exists. We show the existence of
1) 1-out-of-$\lfloor \frac{9}{11}n\rfloor$ MMS allocations, which improves the state-of-the-art factor of 1-out-of-$\lfloor \frac{3}{4}n\rfloor$.
2) MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021).
3) $15/13$-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of $13/11$.
We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a $15/13$-MMS allocation for personalized bivalued instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04391 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Maximin Share Approximations for Chores by Bin Packing Garg, Jugal Huang, Xin Segal-Halevi, Erel Computer Science and Game Theory We study fair division of indivisible chores among $n$ agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more than two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exists. We show the existence of 1) 1-out-of-$\lfloor \frac{9}{11}n\rfloor$ MMS allocations, which improves the state-of-the-art factor of 1-out-of-$\lfloor \frac{3}{4}n\rfloor$. 2) MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021). 3) $15/13$-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of $13/11$. We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a $15/13$-MMS allocation for personalized bivalued instances. |
| title | Improved Maximin Share Approximations for Chores by Bin Packing |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2411.04391 |