Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Breaking the 3/4 Barrier for Approximate Maximin Share


Akrami,  Hannaneh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 394KB

Supplementary Material (public)
There is no public supplementary material available

Akrami, H., & Garg, J. (2023). Breaking the 3/4 Barrier for Approximate Maximin Share. Retrieved from https://arxiv.org/abs/2307.07304.

Cite as: https://hdl.handle.net/21.11116/0000-000F-1439-B
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. 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 $\frac34 + O(\frac{1}{n})$. However, a simple example in [DFL82,
BEF21, AGST23] showed the limitations of existing approaches and proved that
they cannot improve this factor to $3/4 + \Omega(1)$. In this paper, we bypass
these barriers to show the existence of $(\frac{3}{4} + \frac{3}{3836})$-MMS
allocations by developing new reduction rules and analysis techniques.