Approximate EFX Under Limited Agent Heterogeneity

摘要

We study EFX and approximate EFX allocations of indivisible goods among agents with at most k distinct valuations (i.e., k types of agents). For exact EFX, it is known that an EFX allocation always exists when there are at most three types of agents. For approximate EFX, the best known guarantee is a 0.618-EFX allocation, and this has been improved recently to a φ-EFX allocation when the number of agents is at most seven. We settle another natural case in this landscape by showing that a φ-EFX allocation exists for any number of agents whenever there are at most four distinct valuations. We then consider a relaxation, EFX with charity, where some goods may remain unallocated and no agent envies the set of unallocated goods. It is known that, for n agents and any ε ∈ (0, 1/2], there exists an EFXε allocation with at most Õ((n/ε)^(1/2)) goods allocated to charity. We prove that when there are at most k distinct valuation types, there exists an EFXε allocation with only Õ((k/ε)^(1/2)) goods allocated to charity; in particular, the required amount of charity is sublinear in the number of distinct valuations rather than in the number of agents. We show that any EFX guarantee for k types of agents can be extended, with an additional (1 − 2ε) approximation factor, to a more general setting where the valuations can be partitioned into k clusters such that the maximum heterogeneity of valuations within each cluster is at most ε.