# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Breaking the 3/4 Barrier for Approximate Maximin Share

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2307.07304.pdf

(Preprint), 394KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.