Fair and Efficient Online Allocations
研究在线分配问题中公平与效率的权衡，指出在对抗性到达下无法同时保证两者，但在物品价值服从分布时存在同时公平高效的算法。
Trade-Offs in Dynamic Allocation Problems Food rescue organizations often receive donations to allocate to food pantries or families. Donations are unpredictable, and goods are often perishable; as a result, allocations have to be made within a short time frame after arrival without knowledge of future arrivals. It is important that donations go to organizations that are able to use them; at the same time, organizations that serve different communities should be treated equitably. In “Fair and Efficient Online Allocations,” Benadè, Kazachkov, Procaccia, Psomas, and Zeng study fairness-efficiency trade-offs in such online allocation problems. Against adversarial arrivals, no algorithm can provide nontrivial guarantees for both these objectives simultaneously. When item values are drawn from (potentially correlated) distributions, there is no trade-off, and a simultaneously fair and efficient algorithm is presented.