{"ID":3050103,"CreatedAt":"2026-06-04T02:13:16.786527022Z","UpdatedAt":"2026-06-06T11:11:21.995702784Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04731","arxiv_id":"2606.04731","title":"Improved Approximation Guarantees for Groupwise Maximin Share Fairness","abstract":"We study the problem of fairly allocating a set of indivisible goods to a set of $n$ agents with additive valuation functions. We focus on the very demanding notion of \\textit{groupwise maximin share fairness} (GMMS), which requires that each agent $i$ receives value comparable to their maximin share, where the latter is computed \\textit{with respect to any subset of agents that contains $i$}. We show that it is possible to compute $(φ-1)$-approximate GMMS allocations in polynomial time, where $φ\\approx 1.618$ is the golden ratio). This improves on the previously known guarantee of $4/7$ of Chaudhury et al. [SICOMP; 2021] and Amanatidis et al. [TCS; 2020]. We propose a simple algorithm that maintains the same main properties as the Draft-and-Eliminate algorithm of Amanatidis et al. [TCS, 2020] and we improve on the approximation guarantee analysis by carefully bounding the relevant value within any subinstance induced by the restriction of our allocation to a subset of agents. Our analysis is asymptotically tight for algorithms that share these properties and has the additional benefit of giving improved guarantees for restricted settings; in particular, when the agents agree on the top $n$ goods or when the number of agents is small. To illustrate the challenges of going beyond the guarantees of our algorithm, we also present a variant with an improved approximation of $(\\sqrt{10}-1)/3 \\approx 0.72$ for the case of three agents. To achieve this improvement we partially characterize the maximin share guarantees of short picking sequences for a small number of goods.","short_abstract":"We study the problem of fairly allocating a set of indivisible goods to a set of $n$ agents with additive valuation functions. We focus on the very demanding notion of \\textit{groupwise maximin share fairness} (GMMS), which requires that each agent $i$ receives value comparable to their maximin share, where the latter...","url_abs":"https://arxiv.org/abs/2606.04731","url_pdf":"https://arxiv.org/pdf/2606.04731v1","authors":"[\"Georgios Amanatidis\",\"Anna Korfiati\",\"Evangelos Markakis\",\"Christodoulos Santorinaios\"]","published":"2026-06-03T11:15:24Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}