论文标题
公平有效的在线分配，具有标准估值
Fair and Efficient Online Allocations with Normalized Valuations
论文作者
论文摘要
一系列可分配的资源可以通过一系列回合提供，需要立即和不可撤销地分配。我们的目标是分发这些资源，以最大程度地提高公平和效率。在对抗环境中实现任何非平凡的保证是不可能的。但是，我们表明，将代理值正常化，这是公平划分中非常普遍的假设，使我们能够摆脱这种不可能。我们的主要结果是针对两个代理商的在线算法，可确保结果无嫉妒，同时保证91.6％的最佳社会福利。我们还表明，这几乎是最佳的：没有嫉妒的算法可以保证超过93.3％的最佳社会福利。
A set of divisible resources becomes available over a sequence of rounds and needs to be allocated immediately and irrevocably. Our goal is to distribute these resources to maximize fairness and efficiency. Achieving any non-trivial guarantees in an adversarial setting is impossible. However, we show that normalizing the agent values, a very common assumption in fair division, allows us to escape this impossibility. Our main result is an online algorithm for the case of two agents that ensures the outcome is envy-free while guaranteeing 91.6% of the optimal social welfare. We also show that this is near-optimal: there is no envy-free algorithm that guarantees more than 93.3% of the optimal social welfare.
