تقرير
Existence of MMS Allocations with Mixed Manna
| العنوان: | Existence of MMS Allocations with Mixed Manna |
|---|---|
| المؤلفون: | Hsu, Kevin |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory |
| الوصف: | Maximin share (MMS) allocations are a popular relaxation of envy-free allocations that have received wide attention in the context of the fair division of indivisible items. Although MMS allocations can fail to exist [1], previous work has found conditions under which they exist. Specifically, MMS allocations exist whenever $m \leq n+5$ in the context of goods allocation, and this bound is tight in the sense that MMS allocations can fail to exist when $m = n+6$ [2]. Unfortunately, the technique used to establish this result does not generalize readily to the chores and mixed manna settings. This paper generalizes this result to the chores setting and provides a partial solution for the mixed manna setting. Our results depend on the presence of certain types of agents. Specifically, an agent $i$ is a goods agent (resp. chores agent) if every item is a good (resp. chore) to $i$, and a non-negative mixed agent if $i$ is neither a goods nor a chores agent and the MMS guarantee of $i$ is non-negative. In this paper, we prove that an MMS allocation exists if $m \leq n+5$ and there exists a goods agent, a non-negative mixed agent, or only chores agents. [1] David Kurokawa, Ariel D Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? In Thirtieth AAAI Conference on Artificial Intelligence, 2016. [2] Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for mms fair allocations. In International Conference on Web and Internet Economics, pages 355-372. Springer, 2021. Comment: 11 pages. A mistake in the previous version has been fixed, and a new reference has been added |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2401.07490Test |
| رقم الانضمام: | edsarx.2401.07490 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |