dc.contributor.author | Hummel, Halvard | |
dc.date.accessioned | 2024-02-26T08:25:45Z | |
dc.date.available | 2024-02-26T08:25:45Z | |
dc.date.created | 2024-01-09T13:36:13Z | |
dc.date.issued | 2023 | |
dc.identifier.isbn | 978-1-956792-03-4 | |
dc.identifier.uri | https://hdl.handle.net/11250/3119792 | |
dc.description.abstract | 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. | |
dc.description.abstract | On Lower Bounds for Maximin Share Guarantees | |
dc.language.iso | eng | en_US |
dc.publisher | AAAI Press | en_US |
dc.relation.ispartof | Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence | |
dc.relation.uri | https://www.ijcai.org/proceedings/2023/0306.pdf | |
dc.title | On Lower Bounds for Maximin Share Guarantees | en_US |
dc.title.alternative | On Lower Bounds for Maximin Share Guarantees | en_US |
dc.type | Chapter | en_US |
dc.description.version | publishedVersion | |
dc.source.pagenumber | 2747-2755 | en_US |
dc.identifier.doi | 10.24963/ijcai.2023/306 | |
dc.identifier.cristin | 2223180 | |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |