Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items
Ying Wang, Jiaqian Li, Tianze Wei, Hau Chan, Minming Li
我们研究从代理人和集中分配者的角度为代理人群体公平分配不可分割的物品。 在我们的设置中,集中分配器有兴趣确保分配在组之间和代理之间是公平的。 这种设置适用于许多现实世界的场景,包括当学校管理员希望向各部门的工作人员分配资源(例如办公空间和用品)时,以及当市议会将有限的住房单元分配给不同社区的各种有需要的家庭时。 为了确保代理人之间的公平分配,我们考虑了经典的嫉妒自由(EF)概念。 为了确保各群体之间的公平性,我们定义了集中群体公平性(CGEQ)的概念,以从分配者的角度捕捉群体的公平性。 由于EF或CGEQ分配并不总是普遍存在,所以我们考虑他们对一个项目(EF1)和集中组公平性(CGEQ1)的相应自然放松。 对于代理和集中分配器的不同类别的估值函数,我们表明满足 EF1 和 CGEQ1 的分配始终存在,并设计高效的算法来计算这些分配。 我们还认为,从集中分配器的角度来看,集中式组最大份额(CGMMS)是EF1的团体级公平目标,并提出了几项结果。
We study the fair allocation of indivisible items for groups of agents from the perspectives of the agents and a centralized allocator. In our setting, the centralized allocator is interested in ensuring the allocation is fair among the groups and between agents. This setting applies to many real-world scenarios, including when a school administrator wants to allocate resources (e.g., office spaces and supplies) to staff members in departments and when a city council allocates limited housing un...