Best-of-Both-Worlds Fairness and Pareto Optimality

Abstract

We consider fair allocation of indivisible items among agents with non-negative and additive valuations. The goal is to construct a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up to one item and Pareto optimal. We show that this is always possible for two agents. We then prove a stronger result that there always exists a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up each one item (EFX) and Pareto optimal. For non-negative integral additive valuations, such a lottery can be computed in pseudo-polynomial time. We also prove that for three agents and four items, there may be no ex-ante envy-free lottery that can be supported on allocations that are simultaneously EFX and Pareto optimal.