Fair Division and Allocation: New Developments

The field of fair division and allocation is moving towards addressing complex scenarios and providing more robust guarantees. Researchers are exploring new models and algorithms to achieve fair and efficient allocations in various settings, including online and networked environments. Recent work has focused on developing strategyproof mechanisms, characterizing the existence of fair allocations, and providing best-of-both-worlds guarantees. Notably, innovative results have been obtained in the study of EFX and PMMS allocations, as well as in the development of residual prophet inequalities. Some highlights include the provision of online algorithms for fair division of indivisible chores, the identification of monotone allocation rules in network auctions, and the development of algorithms for achieving ex-post EFX and ex-ante fairness guarantees. Noteworthy papers include: Online MMS Allocation for Chores, which closes the gap on the negative side by proving a strong impossibility result and presents an online algorithm with a reasonable bound. Probing EFX via PMMS, which establishes a formal separation between EFX and PMMS and proves existence of fair allocations for important special cases. Best-of-Both-Worlds Guarantees with Fairer Endings, which achieves stronger ex-post fairness guarantees along with meaningful ex-ante guarantees.

Sources

Online MMS Allocation for Chores

Strategyproofness and Monotone Allocation of Auction in Social Networks

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

Best-of-Both-Worlds Guarantees with Fairer Endings

Residual Prophet Inequalities

On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities

Built with on top of