{"ID":2856662,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.10423","arxiv_id":"2510.10423","title":"Improved Maximin Share Guarantee for Additive Valuations","abstract":"The maximin share ($\\textsf{MMS}$) is the most prominent share-based fairness notion in the fair allocation of indivisible goods. Recent years have seen significant efforts to improve the approximation guarantees for $\\textsf{MMS}$ for different valuation classes, particularly for additive valuations. For the additive setting, it has been shown that for some instances, no allocation can guarantee a factor better than $1-\\tfrac{1}{n^4}$ of maximin share value to all agents. However, the best currently known algorithm achieves an approximation guarantee of $\\tfrac{3}{4} + \\tfrac{3}{3836}$ for $\\textsf{MMS}$. In this work, we narrow this gap and improve the best-known approximation guarantee for $\\textsf{MMS}$ to $\\tfrac{10}{13}$.","short_abstract":"The maximin share ($\\textsf{MMS}$) is the most prominent share-based fairness notion in the fair allocation of indivisible goods. Recent years have seen significant efforts to improve the approximation guarantees for $\\textsf{MMS}$ for different valuation classes, particularly for additive valuations. For the additive...","url_abs":"https://arxiv.org/abs/2510.10423","url_pdf":"https://arxiv.org/pdf/2510.10423v1","authors":"[\"Ehsan Heidari\",\"Alireza Kaviani\",\"Masoud Seddighin\",\"AmirMohammad Shahrezaei\"]","published":"2025-10-12T03:14:32Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}