2023/02/01 by Hummel, Halvard · 2 citations
#91B32 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2302.00264
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 nc such that an MMS allocation exists for any instance with n ≥ nc agents and at most n + c items, where nc ≤ \lfloor 0.6597c ⋅ c!\rfloor for allocation of goods and nc ≤ \lfloor 0.7838c ⋅ c!\rfloor for chores. Furthermore, we show that for n ≠ 3 agents, all instances with n + 6 goods have an MMS allocation.