This talk is about the problem of fairly allocating indivisible goods among multiple agents. Envy-freeness up to any item (EFX) and maximin share fairness (MMS) are arguably the most compelling fairness concepts proposed till now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, and MMS allocations are not always guaranteed to exist. We propose two alternative fairness concepts—called epistemic EFX (EEFX) and minimum EFX value fairness (MXS)—inspired by EFX and MMS. We explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations.

We also consider the problem of finding approximate MMS allocations. The Garg-Taki algorithm gives an approximation factor of (3/4 + 1/12n). We significantly simplify the analysis of their algorithm and improve the existence guarantee to a factor of (3/4 + min(1/36, 3/(16n-4))). Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with these techniques.