Ordinal Maximin Guarantees for Group Fair Division

Ordinal Maximin Guarantees for Group Fair Division

Pasin Manurangsi, Warut Suksompong

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2922-2930. https://doi.org/10.24963/ijcai.2024/324

We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if n agents are distributed equally across g groups, there exists a 1-out-of-k MMS allocation for k = O(g log(n/g)), while if all but a constant number of agents are in the same group, we obtain k = O(log n / log log n). We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Computational social choice