# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Improving Approximation Guarantees for 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.12916.pdf

(Preprint), 9KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Akrami, H., Garg, J., Sharma, E., & Taki, S. (2023). Improving Approximation Guarantees for Maximin Share. Retrieved from https://arxiv.org/abs/2307.12916.

Cite as: https://hdl.handle.net/21.11116/0000-000F-143C-8

##### Abstract

We consider fair division of a set of indivisible goods among $n$ agents with

additive valuations using the 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 ($1$-out-of-$n$) MMS value. An

allocation is called MMS if all agents receive their MMS values. However, since

MMS allocations do not always exist, the focus shifted to investigating its

ordinal and multiplicative approximations.

In the ordinal approximation, the goal is to show the existence of

$1$-out-of-$d$ MMS allocations (for the smallest possible $d>n$). A series of

works led to the state-of-the-art factor of $d=\lfloor3n/2\rfloor$ [Hosseini et

al.'21]. We show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always

exist, thereby improving the state-of-the-art of ordinal approximation.

In the multiplicative approximation, the goal is to show the existence of

$\alpha$-MMS allocations (for the largest possible $\alpha < 1$), which

guarantees each agent at least $\alpha$ times her MMS value. We introduce a

general framework of "approximate MMS with agent priority ranking". An

allocation is said to be $T$-MMS, for a non-increasing sequence $T = (\tau_1,

\ldots, \tau_n)$ of numbers, if the agent at rank $i$ in the order gets a

bundle of value at least $\tau_i$ times her MMS value. This framework captures

both ordinal approximation and multiplicative approximation as special cases.

We show the existence of $T$-MMS allocations where $\tau_i \ge \max(\frac{3}{4}

+ \frac{1}{12n}, \frac{2n}{2n+i-1})$ for all $i$. Furthermore, we can get

allocations that are $(\frac{3}{4} + \frac{1}{12n})$-MMS ex-post and $(0.8253 +

\frac{1}{36n})$-MMS ex-ante. We also prove that our algorithm does not give

better than $(0.8631 + \frac{1}{2n})$-MMS ex-ante.

additive valuations using the 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 ($1$-out-of-$n$) MMS value. An

allocation is called MMS if all agents receive their MMS values. However, since

MMS allocations do not always exist, the focus shifted to investigating its

ordinal and multiplicative approximations.

In the ordinal approximation, the goal is to show the existence of

$1$-out-of-$d$ MMS allocations (for the smallest possible $d>n$). A series of

works led to the state-of-the-art factor of $d=\lfloor3n/2\rfloor$ [Hosseini et

al.'21]. We show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always

exist, thereby improving the state-of-the-art of ordinal approximation.

In the multiplicative approximation, the goal is to show the existence of

$\alpha$-MMS allocations (for the largest possible $\alpha < 1$), which

guarantees each agent at least $\alpha$ times her MMS value. We introduce a

general framework of "approximate MMS with agent priority ranking". An

allocation is said to be $T$-MMS, for a non-increasing sequence $T = (\tau_1,

\ldots, \tau_n)$ of numbers, if the agent at rank $i$ in the order gets a

bundle of value at least $\tau_i$ times her MMS value. This framework captures

both ordinal approximation and multiplicative approximation as special cases.

We show the existence of $T$-MMS allocations where $\tau_i \ge \max(\frac{3}{4}

+ \frac{1}{12n}, \frac{2n}{2n+i-1})$ for all $i$. Furthermore, we can get

allocations that are $(\frac{3}{4} + \frac{1}{12n})$-MMS ex-post and $(0.8253 +

\frac{1}{36n})$-MMS ex-ante. We also prove that our algorithm does not give

better than $(0.8631 + \frac{1}{2n})$-MMS ex-ante.