Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores
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_ | 1866912074479697920 |
|---|---|
| author | Qiu, Jiawei Wu, Xiaowei Zhang, Cong Zhou, Shengwei |
| author_facet | Qiu, Jiawei Wu, Xiaowei Zhang, Cong Zhou, Shengwei |
| contents | We study the problem of allocating $m$ indivisible chores to $n$ agents with additive cost functions under the fairness notion of maximin share (MMS). In this work, we propose a notion called $α$-approximate all-but-one maximin share ($α$-AMMS) which is a stronger version of $α$-approximate MMS. An allocation is called $α$-AMMS if $n-1$ agents are guaranteed their MMS values and the remaining agent is guaranteed $α$-approximation of her MMS value. We show that there exist $α$-AMMS allocations, with $α= 9/8$ for three agents; $α= 4/3$ for four agents; and $α= (n+1)^2/4n$ for $n\geq 5$ agents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12347 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores Qiu, Jiawei Wu, Xiaowei Zhang, Cong Zhou, Shengwei Computer Science and Game Theory We study the problem of allocating $m$ indivisible chores to $n$ agents with additive cost functions under the fairness notion of maximin share (MMS). In this work, we propose a notion called $α$-approximate all-but-one maximin share ($α$-AMMS) which is a stronger version of $α$-approximate MMS. An allocation is called $α$-AMMS if $n-1$ agents are guaranteed their MMS values and the remaining agent is guaranteed $α$-approximation of her MMS value. We show that there exist $α$-AMMS allocations, with $α= 9/8$ for three agents; $α= 4/3$ for four agents; and $α= (n+1)^2/4n$ for $n\geq 5$ agents. |
| title | Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.12347 |