Best of Both World Fairness under Entitlements
H. Aziz, A. Ganguly, E. Micha. Best of Both Worlds Fairness under Entitlements. Working Paper. Aug 2022. [ P DF ] We consider probabilistic allocation of indivisible items to agents with additive valuations and weighted entitlements. We explore how far ex-ante and ex-post fairness properties can be achieved simultaneously. Our first result is that in contrast to the case of same entitlements, well-established adaptations of ex-ante envy-freeness and ex-post envy-freeness up to one item (EF1) to the case of entitlements are not compatible. We then present a polynomial-time algorithm that achieves weighted ex-ante envy-freeness and ex-post weighted envy-freeness up to 1 transfer. The outcome is ex-ante weighted envy-free for all utilities consistent with the underlying ordinal preferences but it is not Pareto optimal. We then present an alternative polynomial-time algorithm that satisfies Pareto optimality, ex-ante weighted envy-freeness and ex-post weighted proportionality up to one ...