On Lower Bounds for Maximin Share Guarantees

On Lower Bounds for Maximin Share Guarantees

Halvard Hummel

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2747-2755. https://doi.org/10.24963/ijcai.2023/306

We study the problem of fairly allocating a set of indivisible items to a set of agents with additive valuations. Recently, Feige et al. (WINE'21) proved that a maximin share (MMS) allocation exists for all instances with n agents and no more than n + 5 items. Moreover, they proved that an MMS allocation is not guaranteed to exist for instances with 3 agents and at least 9 items, or n ≥ 4 agents and at least 3n + 3 items. In this work, we shrink the gap between these upper and lower bounds for guaranteed existence of MMS allocations. We prove that for any integer c > 0, there exists a number of agents n_c such that an MMS allocation exists for any instance with n ≥ n_c agents and at most n + c items, where n_c ≤ ⌊0.6597^c · c!⌋ for allocation of goods and n_c ≤ ⌊0.7838^c · c!⌋ for chores. Furthermore, we show that for n ≠ 3 agents, all instances with n + 6 goods have an MMS allocation.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division