GeomTop Seminar: Envy-free division and degrees of equivariant maps.
Date
Wednesday, September 4, 2019 13:00 - 14:15
Speaker
Sergey AVVAKUMOV
Location
Mondi Seminar Room 3, Central Building
Series
Seminar/Talk
Tags
Mathematics and CS Seminar, mathematical_seminar_ics
Host
Uli Wagner
Contact
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.