دورية أكاديمية
Existence of MMS Allocations with Mixed Manna ...
| العنوان: | Existence of MMS Allocations with Mixed Manna ... |
|---|---|
| المؤلفون: | Hsu, Kevin |
| بيانات النشر: | arXiv |
| سنة النشر: | 2024 |
| المجموعة: | DataCite Metadata Store (German National Library of Science and Technology) |
| مصطلحات موضوعية: | Computer Science and Game Theory cs.GT, FOS Computer and information sciences |
| الوصف: | 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 ... : 11 pages. A mistake in the previous version has been fixed, and a new reference has been added ... |
| نوع الوثيقة: | article in journal/newspaper report |
| اللغة: | unknown |
| DOI: | 10.48550/arxiv.2401.07490 |
| الإتاحة: | https://doi.org/10.48550/arxiv.2401.07490Test https://arxiv.org/abs/2401.07490Test |
| حقوق: | arXiv.org perpetual, non-exclusive license ; http://arxiv.org/licenses/nonexclusive-distrib/1.0Test/ |
| رقم الانضمام: | edsbas.CCA8E457 |
| قاعدة البيانات: | BASE |
| DOI: | 10.48550/arxiv.2401.07490 |
|---|