| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
09 February 2025 |
|
| | | |
|
Article overview
| |
|
On Lower Bounds for Maximin Share Guarantees | Halvard Hummel
; | Date: |
1 Feb 2023 | 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 ge 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 ge
n_c$ agents and at most $n + c$ items, where $n_c le lfloor 0.6597^c cdot
c!
floor$ for allocation of goods and $n_c le lfloor 0.7838^c cdot
c!
floor$ for chores. Furthermore, we show that for $n
eq 3$ agents, all
instances with $n + 6$ goods have an MMS allocation. | Source: | arXiv, 2302.00264 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|