Almost and Approximate EFX for Few Types of Agents
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915454942969856 |
|---|---|
| author | HV, Vishwa Prakash Mehta, Ruta Nimbhorkar, Prajakta |
| author_facet | HV, Vishwa Prakash Mehta, Ruta Nimbhorkar, Prajakta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15380 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Almost and Approximate EFX for Few Types of Agents HV, Vishwa Prakash Mehta, Ruta Nimbhorkar, Prajakta Computer Science and Game Theory Data Structures and Algorithms 91B32, 91B10, 68W25 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. |
| title | Almost and Approximate EFX for Few Types of Agents |
| topic | Computer Science and Game Theory Data Structures and Algorithms 91B32, 91B10, 68W25 |
| url | https://arxiv.org/abs/2508.15380 |