forgot password?
register here
Research articles
  search articles
  reviews guidelines
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
Members: 3652
Articles: 2'545'386
Articles rated: 2609

24 June 2024
  » arxiv » 2302.00264

 Article overview

On Lower Bounds for Maximin Share Guarantees
Halvard Hummel ;
Date 1 Feb 2023
AbstractWe 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   
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
of broad interest:
Global appreciation:

  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.
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica