Best-of-Both-Worlds Fairness and Pareto Optimality
2026-08-10 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors studied how to fairly share indivisible items between people who value them differently. They found a way to create a random method of giving out items so that, on average, nobody envies another person’s share, and every actual outcome is almost envy-free and efficient for two people. They also showed a stronger version of this idea that can be computed for whole number valuations. However, for three people and a few items, such a perfect fair and efficient random method may not exist. This work explores the limits of fair division under these conditions.
fair allocationindivisible itemsenvy-freeenvy-free up to one item (EF1)envy-free up to any item (EFX)Pareto optimalityadditive valuationslottery over allocationspseudo-polynomial timeex-ante fairness
Authors
Haris Aziz
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.