Fair and Efficient Online Allocations

• 成果类型: Article
• 署名作者: Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Alexandros; Zeng, David
• 署名单位: Boston University; State University System of Florida; University of Florida; Harvard University; Purdue University System; Purdue University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0332
• 发表日期: 2024
• 页码: 1438-1452
• 关键词: Equity

摘要

We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions, it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy free up to one good or envy free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto-efficient fractional allocation that is strongly envy free with respect to pairs of agents with substantially different utilities while allocating identical bundles to agents with identical utilities (up to multiplicative factors).