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 (α-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 2/3-EFX allocation is guaranteed to exist when number of agents is at most seven. In this paper, we show that a 2/3-EFX allocation exists for any number of agents when there are at most four distinct valuations. Secondly, we consider a relaxation called 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 ε ∈ (0, 1/2], there exists a (1-ε)-EFX allocation with at most O((n/ε)^1/2) goods to charity. In this paper, we show that a (1-ε)-EFX allocation with a O(k/ε)^1/2 charity exists for any number of agents when there are at most k distinct valuations.