Near-Optimal Best-of-Both-Worlds Fairness for Few Agents
This work provides the first near-optimal BoBW fairness guarantees for three agents, addressing a gap in the literature for few-agent settings.
The paper addresses fair allocation of indivisible goods among few agents, achieving near-optimal Best-of-Both-Worlds fairness. For three agents, they provide a poly-time algorithm guaranteeing ex-ante proportionality and ex-post EEFX with at least 9/10 MMS, and for two agents, an FPTAS achieving ex-ante envy-free, ex-post EFX, and (1-ε) MMS.
We consider the problem of fair allocation of indivisible goods among agents with additive valuations, aiming for Best-of-Both-Worlds (BoBW) fairness: a distribution over allocations that is ex-ante fair, and additionally, it is supported only on deterministic allocations that are ex-post fair. Existing BoBW algorithms are far from achieving the best possible ex-post fairness guarantees, even in the well studied special case when there are only few agents. We focus on BoBW for few agents, and our main result is the design of the first poly-time BoBW algorithms achieving near-optimal fairness for three agents. We also present optimal poly-time BoBW results for two agents. For three agents, we prove that there exists an ex-ante proportional distribution over at most six allocations, each of which is Epistemic EFX (EEFX) and gives every agent at least $\tfrac{9}{10}$ of her maximin share (MMS). Since MMS allocations need not exist, some agent may fall below her MMS; we guarantee that any such agent is EFX-satisfied -- a new criterion we call "Individually MMS-satisfying or EFX-satisfying (IMMX)". We complement this with an FPTAS preserving all envy-based guarantees, and also preserving all value-based guarantees up to $(1-\varepsilon)$. Furthermore, we present an FPTAS which guarantees exact ex-ante proportionality, while guaranteeing each agent receives $(1-\varepsilon)$ of her MMS or is EFX-satisfied ex-post -- notable, as computing EFX allocations in polynomial time is open even without BoBW constraints. For two agents, we give an FPTAS that is ex-ante envy-free, ex-post EFX, and guarantees each agent $(1-\varepsilon)$ of her MMS, matching the strongest guarantees achievable in polynomial time.