Fair division often faces a fundamental mathematical wall: when resources are indivisible, a perfectly fair deterministic allocation is frequently impossible. You cannot split a single house or a unique heirloom without destroying its value. The research direction across these papers addresses this by shifting the goal from ex-post fairness (fairness in the final outcome) to ex-ante fairness (fairness in expectation). By treating allocations as probability distributions over outcomes—often called lotteries—researchers can achieve rigorous fairness guarantees that are otherwise unattainable.
The Power of Randomization
The core intuition behind this direction is that while a single outcome might be unfair, a "fair" process can distribute the opportunity for value equally. As Ruben Becker, Bojana Kodric, and Cosimo Vinci demonstrate in Greedily Maximizing Ex-Ante Fairness, randomized strategies allow every participant to receive an equal expected utility, even when the actual items being assigned are inherently unequal.
This shift from discrete states to continuous probability distributions transforms the problem. In Reducing Leximin Fairness to Utilitarian Optimization, Eden Hartman, Yonatan Aumann, and Erel Segal-Halevi show that by using lotteries, complex fairness goals like leximin optimality (maximizing the welfare of the worst-off agent) can be solved using linear programming and duality. This makes computationally "hard" (NP-hard) deterministic problems solvable in polynomial time when relaxed to the ex-ante setting.
Balancing Fairness and Truthfulness
A recurring challenge in fair division is "strategic behavior," where agents lie about their preferences to get a better deal. Yiling Chen and Ariel D. Procaccia pioneered the first algorithms in Truth, Justice, and Cake Cutting that are both fair and "truthful." Their randomized mechanism works by finding a partition where every agent values every segment equally, then assigning those segments via random permutation. Because the assignment is random, no agent can gain an advantage by misrepresenting their preferences.
This "random priority" mechanism is a cornerstone of the field. Moshe Babaioff, Tomer Ezra, and Uriel Feige expanded this in Fair and Truthful Mechanisms for Dichotomous Valuations, proving that a random tie-breaking order combined with a deterministic selection process ensures "universal truthfulness." The system remains incentive-compatible regardless of the actual random outcome, while providing equal opportunities to all participants before the dice are rolled.
Improving Approximation Guarantees
Even when perfect fairness is impossible to guarantee ex-post, randomization can bridge the gap. In Improving Approximation Guarantees for Maximin Share, Hannaneh Akrami, Jugal Garg, and Setareh Taki demonstrate that assigning agent priority ranks uniformly at random significantly improves the expected fairness guarantees for indivisible goods. By focusing on the expected value (ex-ante) rather than the worst-case single run (ex-post), researchers can design mechanisms that are demonstrably fairer to all participants over time.