We study fair allocation of indivisible goods among agents. Prior research focuses on additive agent preferences, which leads to an impossibility when seeking truthfulness, fairness, and efficiency. We show that when agents have binary additive preferences, a compelling rule -- maximum Nash welfare (MNW) -- provides all three guarantees. Specifically, we show that deterministic MNW with lexicographic tie-breaking is group strategyproof in addition to being envy-free up to one good and Pareto optimal. We also prove that fractional MNW -- known to be group strategyproof, envy-free, and Pareto optimal -- can be implemented as a distribution over deterministic MNW allocations, which are envy-free up to one good. Our work establishes maximum Nash welfare as the ultimate allocation rule in the realm of binary additive preferences.
翻译:我们研究的是代理商之间不可分割货物的公平分配。 先前的研究侧重于添加剂偏好,这导致在寻求真实性、公平性和效率时不可能实现。 我们证明,当代理商有二进制添加剂偏好时,一个令人信服的规则 -- -- 最大纳什福利(MNW) -- -- 提供所有三项保障。 具体地说,我们证明,具有确定性、具有确定性、具有断层线的MNW不仅可以避免嫉妒,还可以消除一种好和最佳的Pareto策略。 我们还证明,分数的MNW -- -- 已知为集体战略防妒忌、无嫉妒和Pareto最佳 -- -- 可以作为确定性MNW分配的分发,而这种分配是无嫉妒的,只有一种好处。 我们的工作将最大的NAW福利确定为二进制添加剂偏好的最终分配规则。