Item

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.