مقاله وجود تخصیص های MMS با مانا ترکیبی

چکیده

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.

چکیده به فارسی (ترجمه ماشینی)

تخصیص Maximin Share (MMS) یک آرامش محبوب از تخصیص عاری از حسادت است که در زمینه تقسیم منصفانه موارد غیرقابل تفکیک مورد توجه گسترده ای قرار گرفته است.اگرچه تخصیص MMS نمی تواند وجود نداشته باشد [1] ، کار قبلی شرایطی را پیدا کرده است که تحت آن وجود دارد.به طور خاص ، تخصیص MMS در هر زمان $ m \ leq n+5 $ در زمینه تخصیص کالا وجود دارد ، و این محدودیت به این معناست که تخصیص MMS می تواند در صورت وجود $ m = n+6 $ [2] وجود نداشته باشد.متأسفانه ، تکنیکی که برای ایجاد این نتیجه استفاده می شود ، به راحتی در کارها و تنظیمات مانا مخلوط نمی شود.این مقاله این نتیجه را در تنظیمات کارها تعمیم داده و یک راه حل جزئی برای تنظیم مانا مخلوط ارائه می دهد.نتایج ما به وجود انواع خاصی از عوامل بستگی دارد.به طور خاص ، یک عامل $ i $ یک عامل کالا (به ترتیب نماینده CHORES) است اگر هر مورد خوب باشد (به ترتیب کاری) به $ i $ ، و یک عامل مختلط غیر منفی اگر $ i $ نه کالا باشد و نه یکAgent Agent و ضمانت MMS $ I $ غیر منفی است.در این مقاله ، ما ثابت می کنیم که اگر یک $ m \ leq n+5 $ $ $ mms وجود داشته باشد و یک عامل کالا ، یک عامل مخلوط غیر منفی یا فقط مأمورین کارها وجود داشته باشد.[1] دیوید کوروکاوا ، آریل دی پروچیا ، و جونکسنگ وانگ.چه زمانی می توان ضمانت سهم حداکثر را تضمین کرد؟در سی و یکم کنفرانس AAAI در مورد هوش مصنوعی ، 2016. [2] اوریل فیگ ، آریل ساپیر و لالیو تابر.یک مثال منفی محکم برای تخصیص منصفانه MMS.در کنفرانس بین المللی اقتصاد وب و اینترنت ، صفحات 355-372.اسپرینگر ، 2021.