{"ID":2879770,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.15380","arxiv_id":"2508.15380","title":"Almost and Approximate EFX for Few Types of Agents","abstract":"We study the problem of fair allocation of a set of indivisible goods among $n$ agents with $k$ distinct additive valuations, with the goal of achieving approximate envy-freeness up to any good ($α-\\mathrm{EFX}$). It is known that EFX allocations exist for $n$ agents when there are at most three distinct valuations due to HV et al. Furthermore, Amanatidis et al. showed that a $\\frac{2}{3}-\\mathrm{EFX}$ allocation is guaranteed to exist when number of agents is at most seven. In this paper, we show that a $\\frac{2}{3}-\\mathrm{EFX}$ allocation exists for any number of agents when there are at most four distinct valuations. Secondly, we consider a relaxation called $\\mathrm{EFX}$ with charity, where some goods remain unallocated such that no agent envies the set of unallocated goods. Akrami et al. showed that for $n$ agents and any $\\varepsilon \\in \\left(0, \\frac{1}{2}\\right]$, there exists a $(1-\\varepsilon)-\\mathrm{EFX}$ allocation with at most $\\tilde{\\mathcal{O}}((n/\\varepsilon)^{\\frac{1}{2}})$ goods to charity. In this paper, we show that a $(1-\\varepsilon)-\\mathrm{EFX}$ allocation with a $\\tilde{\\mathcal{O}}(k/\\varepsilon)^{\\frac{1}{2}}$ charity exists for any number of agents when there are at most $k$ distinct valuations.","short_abstract":"We study the problem of fair allocation of a set of indivisible goods among $n$ agents with $k$ distinct additive valuations, with the goal of achieving approximate envy-freeness up to any good ($α-\\mathrm{EFX}$). It is known that EFX allocations exist for $n$ agents when there are at most three distinct valuations due...","url_abs":"https://arxiv.org/abs/2508.15380","url_pdf":"https://arxiv.org/pdf/2508.15380v1","authors":"[\"Vishwa Prakash HV\",\"Ruta Mehta\",\"Prajakta Nimbhorkar\"]","published":"2025-08-21T09:20:06Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\"]","methods":"[]","has_code":false}