非表示:
キーワード:
Computer Science, Computer Science and Game Theory, cs.GT
要旨:
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.
