The problem of finding envy-free allocations of indivisible goods can not always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1). Another property of interest for efficiency of an allocation is the Pareto Optimality (PO). Under additive utility functions, it is possible to find allocations EF1 and PO using Nash social welfare. However, to find an allocation that maximizes the Nash social welfare is a computationally hard problem. In this work we propose a polynomial time algorithm which maximizes the utilitarian social welfare and at the same time produces an allocation which is EF1 and PO in a special case of additive utility functions called buyer utility functions. Moreover, a slight modification of our algorithm produces an allocation which is envy-free up to any positively valued good (EFX).
翻译:寻找不可分割商品的无嫉妒分配问题并非总能得到解决;因此,研究某种放松,如无嫉妒可达一种商品(EF1),是常见现象,研究某些放松,例如无嫉妒可达一种商品(EF1),也是有利于分配效率的另一种财产。在附加公用事业功能下,有可能找到分配EF1和PO,使用纳什社会福利;然而,找到使纳什社会福利最大化的分配是一个计算上的困难问题。在这项工作中,我们建议采用多时算法,使功利主义的社会福利最大化,同时产生EF1和PO,在称为买方效用功能的附加公用事业功能的特殊情况下,这种分配是EF1和PO。此外,对我们的算法稍作修改后,就会产生一种分配,不会羡慕任何具有积极价值的商品(EFX)。