Fair Randomized Allocations under Lexicographic Valuations

Abstract

In this thesis, we study the problem of fairly dividing a set of indivisible items among a group of agents. Envy-free (EF) allocations might fail to exist in this setting, motivating the study of relaxed notions such as EF1 and EFX. While EF1 allocations can always be computed e fficiently, the existence of EFX (even for n >= 4 additive agents) remains one of fair division’s largest unresolved problems to date. However, upon restricting our domain to lexicographic valuations - a subclass of additive functions - EFX allocations are known to always exist. When randomization is allowed, it is possible to achieve EF in expectation (ex-ante). However, preserving ex-ante fairness while ensuring that every deterministic allocation in the support also satisfies strong fairness guarantees (ex-post) is a far more non-trivial problem. In this thesis, we detail our attempts to compute randomized allocations that are simultaneously ex-ante EF and ex-post EFX, for agents with lexicographic valuations. Our main result is a polynomial time algorithm which computes an ex-ante 6/7 -EF and ex-post EFX+PO allocation for lexicographic goods. For the chores setting, we provide an algorithm that gives ex-ante EF and ex-post EFX, but fails ex-post PO. Finally, we show that by relaxing ex-ante EF to ex-ante PROP, it is possible to obtain ex-post EFX + PO for both goods and chores. We also discuss some of our alternative approaches and study their guarantees and limitations.