论文标题
改进了对三个代理的不可分割项目的最大值公平分配
Improved maximin fair allocation of indivisible items to three agents
论文作者
论文摘要
我们考虑了具有添加估值功能的三种代理中不可分割的项目的近似最大值共享（MMS）分配的问题。对于货物，我们表明$ \ frac {11} {12} $ -MMS分配始终存在，比以前已知的$ \ frac {8} {9} $改进。此外，在我们的分配中，我们可以预先指定一个代理，该代理人将获得她的全部比例份额（PS）；我们还介绍了示例，表明对于这种分配，最好的可能是$ \ frac {11} {12} $的比率。对于琐事，我们表明$ \ frac {19} {18} $ -MMS分配始终存在。同样，在这种情况下，我们可以预先指定一个不超过她的PS的代理，并且我们提出的例子表明，对于这种分配，$ \ frac {19} {18} $的比率最好是最好的。
We consider the problem of approximate maximin share (MMS) allocation of indivisible items among three agents with additive valuation functions. For goods, we show that an $\frac{11}{12}$ - MMS allocation always exists, improving over the previously known bound of $\frac{8}{9}$ . Moreover, in our allocation, we can prespecify an agent that is to receive her full proportional share (PS); we also present examples showing that for such allocations the ratio of $\frac{11}{12}$ is best possible. For chores, we show that a $\frac{19}{18}$-MMS allocation always exists. Also in this case, we can prespecify an agent that is to receive no more than her PS, and we present examples showing that for such allocations the ratio of $\frac{19}{18}$ is best possible.
