  The existence of EFX allocations is a major open problem in fair division,
even for additive valuations. The current state of the art is that no setting
where EFX allocations are impossible is known, and EFX is known to exist for
($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with
additive valuations, ($iv$) agents with one of two additive valuations and
($v$) agents with two-valued instances. It is also known that EFX exists if one
can leave $n-1$ items unallocated, where $n$ is the number of agents.
  We develop new techniques that allow us to push the boundaries of the
enigmatic EFX problem beyond these known results, and, arguably, to simplify
proofs of earlier results. Our main results are ($i$) every setting with 4
additive agents admits an EFX allocation that leaves at most a single item
unallocated, ($ii$) every setting with $n$ additive valuations has an EFX
allocation with at most $n-2$ unallocated items.
  Moreover, all of our results extend beyond additive valuations to all nice
cancelable valuations (a new class, including additive, unit-demand,
budget-additive and multiplicative valuations, among others). Furthermore,
using our new techniques, we show that previous results for additive valuations
extend to nice cancelable valuations.

Computer Science and Game Theory