Fair division with subsidies ensures balanced outcomes for indivisible items
Best-of-Both-Worlds Fair Division via Subsidies
Computer Science and Game Theory
Summary
Fairly dividing things that can't be split, like toys or chores, is tricky because some people might feel left out or unfairly treated. The authors found a way to use subsidies—extra help like money or tokens—to make these divisions feel fair both before and after the items are assigned. They proved that if subsidies can fix envy after dividing, then it's possible to create a fair random lottery over different fair divisions. Their work connects complicated fairness rules and shows which combinations work well or not, depending on the number of people and item types.
What this means in practice
- •For resource allocation teams: Design incentive schemes that use subsidies to guarantee fair and efficient allocation of indivisible goods or tasks among multiple agents.
- •For market designers: Develop allocation lotteries for indivisible items ensuring fairness on average while allowing flexibility in agent preferences and valuations.
A theory result. No direct application yet.
Authors
Surya Panchapakesan, Rohit Vaish
Abstract
We study the relationship between fair division with $\textit{subsidies}$ and $\textit{best-of-both-worlds}$ (BoBW) fairness for indivisible items. We prove a general reduction of BoBW existence to envy-freeability. Specifically, for any scale-free ex-post property $P$ (e.g., EF1, EFX, PO) and any scale-free valuation class $\mathcal{V}$ (e.g, additive, submodular, subadditive, monotone), if every instance in $\mathcal{V}$ admits a $P$-allocation that can be made envy-free using subsidies, then every such instance admits an ex-ante envy-free lottery supported on $P$-allocations. The proof uses linear programming duality. As applications, the reduction gives alternative proofs of BoBW existence results for additive goods, chores, and mixtures of goods and chores. The converse of our general reduction holds for two agents but fails for three: We provide a four-good counterexample with monotone submodular valuations where an ex-ante envy-free and ex-post EF1 lottery exists, but no allocation is simultaneously EF1 and envy-freeable. For lexicographic valuations, we prove simultaneous EFX, Pareto optimality, and envy-freeability (and hence BoBW guarantees for EFX+PO) for three agents, and show that even EFX and envy-freeability can be incompatible for four agents.