Consider an abstract resource $X$ and $n$ players who want to divide it among themselves.

For each possible division of $X$ each player has their favorite piece(s).

The logic which the players use to choose the piece they like may be arbitrary complicated.

Can we always find an envy-free division, i.e., match players with pieces so that everyone gets a piece they like?

Modeling $X$ as a line segment and making some natural continuity assumption plus an additional assumption that "something is better than nothing", i.e., that players never like an empty piece, Gale (1984) proved

that an envy-free division exists for any $n$.

Later it turned out that "something is better than nothing" assumption is not necessarily essential. Without it, Segal-Halevi (2018) and later Meunier and Zerbib (2018) proved that an envy-free segment division exist for $n=3$ and $n=4$ or $n$ prime, respectively.

We prove that an envy-free segment division exist for $n$ prime power. For every $n$ not a prime power we construct an example where no envy-free division is possible. This completely solves the problem.

We also discuss what happens if $X$ is not assumed to be a line segment.

Joint work with Roman Karasev.

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria www.ist.ac.at © IST 2020