AAAIJul, 2018

使用少量查询合理分配多种货物

TL;DR研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足 envy-freeness 最多一个 good (EF1) 的分配,并且这个 logarithmic 查询复杂性界限也适用于具有可加性效用的三个代理人,但是需要使用 polylogarithmic 界限来满足单增效用的情况。同时,证明即使只有两个代理人具有相同可加效用时,计算满足 envy-freeness 和 EFX(envy-freeness up to any good)之一的分配需要线性数量的查询。