A central problem in fair division involves allocating a set of M indivisible goods among N agents in a
fair and
efficient manner. The quintessential fairness notion is "envy freeness" (EF) where every agent prefers their own assignment over that of any other agent's. In the deterministic setting, EF allocations may not always exist, motivating the study of relaxations such as envy-freeness up to any good (EFX). While deciding the existence of EFX allocations remains unresolved even for just four agents with additive valuations, interestingly,
Hosseini et al. showed that EFX allocations always exist and can be computed efficiently when agents have
lexicographic preferences.
Traditional approaches in the literature focus either on randomized allocations that are fair in expectation or deterministic allocations that are "approximately" fair. Recently, these two approaches have been reconciled in the form of "
best-of-both-worlds" guarantees [
AFSV '24], wherein one seeks a randomized allocation that is fair in expectation (i.e., ex-ante fairness) while also being supported on approximately fair allocations (i.e., ex-post fairness).
In this talk, I will discuss some of our approaches at achieving best-of-both-worlds guarantees for agents with lexicographic preferences. I will first introduce some of the techniques we use in our methods, and then present an algorithm that achieves ex-ante 6/7-EF and ex-post (EFX + PO). Following this (if time permits), we shall see a refinement that strengthens the ex-ante ratio to 9/10-EF while preserving the ex-post guarantees.
The talk is based on joint work with Telikepalli Kavitha, Vignesh Viswanathan, Rohit Vaish and Jatin Yadav.
