We consider the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The current best approximation factor, for which the existence is known, is $(\frac{3}{4} + \frac{1}{12n})$ [Garg and Taki, 2021]. Most of these results are based on complicated analyses, especially those providing better than $2/3$ factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of $(\frac{3}{4} + \min(\frac{1}{36}, \frac{3}{16n-4}))$. For small $n$, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques.
翻译:我們考慮將一組不可分割物品按加法估值分配給 $n$ 個代理人的公平分配問題,使用廣受歡迎的最大最小分享 (MMS) 公平概念。由於 MMS 分配並不總是存在,一系列的論文提供了存在和近似 MMS 分配的算法。目前已知的最佳近似因數為 $(\frac{3}{4} + \frac{1}{12n})$ [Garg and Taki,2021]。大多數這些結果基於複雜的分析,尤其是那些提供 $2/3$ 以上因數的算法。此外,由於缺乏 Garg-Taki 算法的最佳例子,現時不清楚這是否是該方法的最佳因數。在本論文中,我們顯著簡化了該算法的分析,並將存在保證改進為因數 $(\frac{3}{4} + \min(\frac{1}{36}, \frac{3}{16n-4}))$。對於小的 $n$,這提供了明顯的改進。此外,我們提供了該算法的最佳例子,表明在當前技術下,這可能是人們可以期望的最佳因數。