On Interim Envy-Free Allocation Lotteries

• 成果类型: Article; Early Access
• 署名作者: Caragiannis, Ioannis; Kanellopoulos, Panagiotis; Kyropoulou, Maria
• 署名单位: Aarhus University; University of Essex
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0203
• 发表日期: 2025
• 关键词: Indivisible goods; fair-division; equilibrium

摘要

With very few exceptions, recent research in fair division has mostly focused on deterministic allocations. Deviating from this trend, we study the fairness notion of interim envy-freeness (iEF) for lotteries over allocations, which serves as a sweet spot between the too-stringent notion of ex post envy-freeness and the very weak notion of ex ante envy freeness. Our analysis relates iEF to other fairness notions as well and reveals trade-offs between iEF and efficiency. Even though several of our results apply to general fair division problems, we are particularly interested in instances with equal numbers of agents and items where allocations are perfect matchings of the items to the agents. We show how to compute iEF allocations in matching allocation instances in polynomial time while also maximizing several efficiency objectives, even though this proves to be considerably more challenging than computing envy-free allocations. Our algorithms use efficient solutions to a novel variant of the bipartite matching problem. We also study the extension of iEF when payments to or from the agents are allowed. We present a series of results on two optimization problems, including a generalization of the classical rent division problem to random allocations.