# Item

ITEM ACTIONSEXPORT

Released

Paper

#### EFX Allocations: Simplifications and Improvements

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2205.07638.pdf

(Preprint), 464KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Akrami, H., Alon, N., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX Allocations: Simplifications and Improvements. Retrieved from https://arxiv.org/abs/2205.07638.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1FEB-A

##### Abstract

The existence of EFX allocations is a fundamental open problem in discrete

fair division. Given a set of agents and indivisible goods, the goal is to

determine the existence of an allocation where no agent envies another

following the removal of any single good from the other agent's bundle. Since

the general problem has been illusive, progress is made on two fronts: $(i)$

proving existence when the number of agents is small, $(ii)$ proving existence

of relaxations of EFX. In this paper, we improve results on both fronts (and

simplify in one of the cases).

We prove the existence of EFX allocations with three agents, restricting only

one agent to have an MMS-feasible valuation function (a strict generalization

of nice-cancelable valuation functions introduced by Berger et al. which

subsumes additive, budget-additive and unit demand valuation functions). The

other agents may have any monotone valuation functions. Our proof technique is

significantly simpler and shorter than the proof by Chaudhury et al. on

existence of EFX allocations when there are three agents with additive

valuation functions and therefore more accessible.

Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX

allocations and EFX allocations with few unallocated goods (charity). Chaudhury

et al. showed the existence of $(1-\epsilon)$-EFX allocation with

$O((n/\epsilon)^{\frac{4}{5}})$ charity by establishing a connection to a

problem in extremal combinatorics. We improve their result and prove the

existence of $(1-\epsilon)$-EFX allocations with $\tilde{O}((n/

\epsilon)^{\frac{1}{2}})$ charity. In fact, some of our techniques can be used

to prove improved upper-bounds on a problem in zero-sum combinatorics

introduced by Alon and Krivelevich.

fair division. Given a set of agents and indivisible goods, the goal is to

determine the existence of an allocation where no agent envies another

following the removal of any single good from the other agent's bundle. Since

the general problem has been illusive, progress is made on two fronts: $(i)$

proving existence when the number of agents is small, $(ii)$ proving existence

of relaxations of EFX. In this paper, we improve results on both fronts (and

simplify in one of the cases).

We prove the existence of EFX allocations with three agents, restricting only

one agent to have an MMS-feasible valuation function (a strict generalization

of nice-cancelable valuation functions introduced by Berger et al. which

subsumes additive, budget-additive and unit demand valuation functions). The

other agents may have any monotone valuation functions. Our proof technique is

significantly simpler and shorter than the proof by Chaudhury et al. on

existence of EFX allocations when there are three agents with additive

valuation functions and therefore more accessible.

Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX

allocations and EFX allocations with few unallocated goods (charity). Chaudhury

et al. showed the existence of $(1-\epsilon)$-EFX allocation with

$O((n/\epsilon)^{\frac{4}{5}})$ charity by establishing a connection to a

problem in extremal combinatorics. We improve their result and prove the

existence of $(1-\epsilon)$-EFX allocations with $\tilde{O}((n/

\epsilon)^{\frac{1}{2}})$ charity. In fact, some of our techniques can be used

to prove improved upper-bounds on a problem in zero-sum combinatorics

introduced by Alon and Krivelevich.