Dipartimento di Ingegneria informatica, automatica e gestionale

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a (ϕ−1)-approximation of envy-freeness up to any good ([Formula presented]) and a [Formula Presented]-approximation of groupwise maximin share fairness ([Formula presented]), where ϕ is the golden ratio (ϕ≈1.618). The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good ([Formula presented]) and a 2/3-approximation of pairwise maximin share fairness ([Formula presented]). While [Formula presented] is our primary focus, we also exhibit how to fine-tune our algorithm and further improve the guarantees for [Formula presented] or [Formula presented]. Finally, we show that [Formula presented]—and thus [Formula presented] and [Formula presented]—allocations always exist when the number of goods does not exceed the number of agents by more than two.