On best of both worlds allocations with subadditive valuations

Abstract

We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0<\rho \le 1$, given any algorithm that produces $\rho$-MMS allocations, transforms it into a randomized allocation algorithm that offers $\rho$-MMS ex-post simultaneously with $\eta$-MES ex-ante. We prove several new properties of MES, and use them to show that $\eta \ge \min [\frac{\rho }{2+\rho },\frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $\eta$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $\Omega (\frac{1}{\log \log n})$-MES ex-ante and $\Omega (\frac{1}{\log \log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.