Breaking the 3/4 Barrier for Approximate Maximin Share

Hannaneh Akrami, Jugal Garg

Research output: Contribution to conferencePaperpeer-review


We study the fundamental problem of fairly allocating a set of indivisible goods among n agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her MMS value. An allocation is called MMS if all agents receive at least their MMS value. However, since MMS allocations need not exist when n > 2, a series of works showed the existence of approximate MMS allocations with the current best factor of (Equation presented). The recent work [3] showed the limitations of existing approaches and proved that they cannot improve this factor to 3/4 + Ω(1). In this paper, we bypass these barriers to show the existence of (Equation presented)-MMS allocations by developing new reduction rules and analysis techniques.

Original languageEnglish (US)
Number of pages18
StatePublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024


Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Breaking the 3/4 Barrier for Approximate Maximin Share'. Together they form a unique fingerprint.

Cite this