تقرير
For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods
| العنوان: | For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods |
|---|---|
| المؤلفون: | Scarlett, Jonathan, Teh, Nicholas, Zick, Yair |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory, Economics - Theoretical Economics |
| الوصف: | Fair allocation of indivisible goods is a well-explored problem. Traditionally, research focused on individual fairness - are individual agents satisfied with their allotted share? - and group fairness - are groups of agents treated fairly? In this paper, we explore the coexistence of individual envy-freeness (i-EF) and its group counterpart, group weighted envy-freeness (g-WEF), in the allocation of indivisible goods. We propose several polynomial-time algorithms that provably achieve i-EF and g-WEF simultaneously in various degrees of approximation under three different conditions on the agents' (i) when agents have identical additive valuation functions, i-EFX and i-WEF1 can be achieved simultaneously; (ii) when agents within a group share a common valuation function, an allocation satisfying both i-EF1 and g-WEF1 exists; and (iii) when agents' valuations for goods within a group differ, we show that while maintaining i-EF1, we can achieve a 1/3-approximation to ex-ante g-WEF1. Our results thus provide a first step towards connecting individual and group fairness in the allocation of indivisible goods, in hopes of its useful application to domains requiring the reconciliation of diversity with individual demands. Comment: Appears in the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2023 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2302.06958 |
| رقم الأكسشن: | edsarx.2302.06958 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |