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.

},\n}\n'