Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

• 成果类型: Article
• 署名作者: Aziz, Haris; Freeman, Rupert; Shah, Nisarg; Vaish, Rohit
• 署名单位: University of New South Wales Sydney; University of Virginia; University of Toronto; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2432
• 发表日期: 2024
• 页码: 1674-1688
• 关键词: fair resource allocation; indivisible goods; randomization and approximation

摘要

We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex ante (before the randomness is realized) and approximately fair ex post (after the randomness is realized). The key question we address is whether ex ante envy-freeness can be achieved in combination with ex post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. The algorithm can be viewed as a desirable way to instantiate a lottery for the probabilistic serial rule. If we additionally require economic efficiency, we obtain three impossibility results that show that ex post or ex ante Pareto optimality is impossible to achieve in conjunction with combinations of fairness properties. Hence, we slightly relax our ex post fairness guarantees and present a different algorithm that can be viewed as a fair way to instantiate a lottery for the maximum Nash welfare allocation rule.