# Envy-free division
via configuration spaces

Gaiane Panina  and  Rade Živaljević  St. Petersburg State University; St.
Petersburg Department of Steklov Mathematical Institute  Mathematical
Institute of the Serbian Academy of Sciences and Arts (SASA), Belgrade

###### Abstract.

The classical approach to envy-free division and equilibrium problems arising
in mathematical economics typically relies on Knaster-Kuratowski-Mazurkiewicz
theorem, Sperner’s lemma or some extension involving mapping degree. We
propose a different and relatively novel approach where the emphasis is on
configuration spaces and equivariant topology, originally developed for
applications in discrete and computational geometry (Tverberg type problems,
necklace splitting problem in the sense of N.Alon and D. West, etc.). We
illustrate the method by proving several relatives (extensions) of the
classical envy-free division theorem of David Gale, where the emphasis is on
preferences allowing the players to choose degenerate pieces of the cake.

###### Key words and phrases:

envy-free division, configuration space/test map scheme

##  1\. Overview and an informal introduction

Given some resource and a set of agents (players), one of the goals of
_welfare economics_ is to divide the resource among the agents in an _envy-
free_ manner. Envy-freeness, as a criterion of fair division, is the principle
where every player feels that their share is at least as good as the share of
any other agent, and thus no player feels envy.

In a mathematical simplification a group of $r$ players want to divide among
themselves a commodity, commonly referred to as the “cake”. The simplest model
of the cake is the interval $I=[0,1]$, which should be cut into $r$ pieces by
$r-1$ cuts. Therefore a partition (cut) of the cake (in this model) is a
sequence $x=(x_{1},\dots,x_{r-1})$ where

(1) $0\leqslant x_{1}\leqslant x_{2}\leqslant\dots\leqslant x_{r-1}\leqslant
1\,.$

The pieces of the cake arising from this division are the closed intervals
(tiles) $I_{i}=[x_{i-1},x_{i}]\,(i=1,\dots,r)$, where $x_{0}=0$ and $x_{r}=1$.

It would seem plausible that in actual applications all inequalities in (1)
should be strict. Indeed the non-degeneracy of tiles is a salient feature of
some classical results such as Gale’s theorem (Theorem 2.5). However, as
noticed by several authors in more recent publications [1, 2, 8, 9], this
condition may be too restrictive in some situations.

For example if the cake is partially burnt, the players are not hungry or
there is some other reason which could make some large pieces less desirable,
then a degenerate piece may be preferred by some players.

One of our goals is to demonstrate that methods based on equivariant topology
and new configuration spaces is well suited for the study of envy-free
division where _degenerate tiles_ may be preferred.

###  1.1. Preferences

After a partition (1) is chosen, each of the players expresses his/her own
individual _preferences_ , over the tiles arising from this particular cut, by
pointing to one (or more) intervals which they like more than the rest.

The nature of the preferences may be unknown or hidden (black box
preferences). For instance we do not assume the monotonicity of preferences,
where a player satisfied by an interval $I$ is automatically satisfied with
any $J\supseteq I$.

Actually the preferences may be quite arbitrary, even irrational (from our
point of view) as illustrated by the following example.

######  Example 1.1.

Assume that two cuts are given

$C_{1}=(1/4,1/3,2/3,3/4)\quad\mbox{\rm and}\quad C_{2}=(1/4,1/3,3/4,5/6)\,,$

where the two initial tiles $I_{1}=[0,1/4]$ and $I_{2}=[1/4,1/3]$ are the
same. A player may prefer the tile $I_{1}$ in the cut $C_{1}$, and the tile
$I_{2}$ for the cut $C_{2}$. So, although the tiles $I_{1}$ and $I_{2}$ are
identical in both cuts, for some mysterious reason a player may prefer one
over the other depending on the rest of the tiles.

###  1.2. Conditions satisfied by all preferences

We emphasized that preferences can be quite arbitrary. There are however some
conditions which are natural (intrinsic) or even unavoidable in the sense that
they must be satisfied by all preferences.

######  Example 1.2.

(Baguette’s gorbushka example) Suppose that each of the players prefers either
the first or the last tile. This is a real-life preference in some countries
(for instance Russia), where some people prefer the “gorbushka” (the “heel” or
the end slice of the baguette). If $r>2$ then envy-free division is clearly
impossible since a loaf of bread has only two end pieces.

The following two conditions may not be “unavoidable”. However they are quite
natural (reasonable) and they are not very restrictive so they are assumed
throughout the paper as default conditions satisfied by all preferences.

  * $\mathbf{(P_{cl})}$

(The preferences are _closed_) If a sequence of cuts converges to a limit cut
and if in this sequence a player always prefers the tile labeled by $i$, then
in the limit cut the player also prefers the tile labeled by $i$.

  * $\mathbf{(P_{cov})}$

(The preferences form a covering) Each player in each cut is expected to find
an acceptable tile. In other words each player prefers at least one of the
offered pieces.

###  1.3. The role of degenerate tiles

A classical theorem, found independently by Stromquist [10] and by Woodall
[13] in 1980 states that, under the conditions _“no player prefers a tile
which degenerates to a single point”_ , it is possible to divide the cake into
$r$ connected tiles and distribute these shares to $r$ players in an _envy-
free manner_ (see Theorem 2.5 for a formal statement). This result is referred
to as Gale’s theorem by some authors (after D. Gale who introduced important
new ideas).

Remark. The conditions _“no player prefers a tile which degenerates to a
single point”_ together with closeness condition implies, in particular, that
“no player prefers an arbitrarily small tile”. That is, for a fixed system of
preferences, there exists $\varepsilon>0$ such that a tile shorter than
$\varepsilon$ is never preferred.

The “gorbushka example” (Example 1.2) shows that if the players are allowed to
choose degenerate pieces then an envy-free division may not be possible
without some restrictions.

###  1.4. Preferences where the choice of degenerate tiles is permitted

In the present paper we want to understand how one can generalize or alter
Gale’s theorem by allowing players to choose degenerate tiles. The following
two types of conditions have already appeared in the literature.

  * $\mathbf{(P_{dte})}$

(All degenerate tiles are equal) In this type of preferences all degenerate
tiles are equal from the viewpoint of the players. Moreover each of them is
informally equal to the empty set.

Example: Assume that the cut-points are $(1/4,1/3,1/3,2/3,2/3)$. The condition
$\mathbf{P_{dte}}$ says that if a player prefers the degenerate segment
$[1/3,1/3]$, then he also prefers the degenerate segment $[2/3,2/3]$.

$\mathbf{P_{dte}}$ is the most important property used in the present paper.
We shall see that this condition is essential for the construction of the new-
style configuration spaces.

  * $\mathbf{(P_{pe})}$

(Preferences satisfying partition equivalence) If two cuts produce one and the
same collection of non-degenerate tiles, the preferences for these two cuts
should define each other. That is,

    1. (1)

A player prefers a non-degenerate tile for the first cut iff he prefers the
same tile for the second cut.

    2. (2)

A player prefers a degenerate tile for the first cut iff he prefers any of the
degenerate tiles for the second cut, and vice versa.

Note that $\mathbf{P_{dte}}$ is a consequence of (2).

Example: Assume that the cut-points are $(1/4,1/3,1/3,2/3)$. The non-
degenerate tiles are $[0,1/4],\ [1/4,1/3],\ [1/3,2/3],[2/3,1]$. The following
cuts $(1/4,1/3,2/3,2/3)$ and $(1/4,1/3,2/3,1)$ are formally different although
they have the same non-degenerate tiles. The $\mathbf{(P_{pe})}$ condition
states that if a player prefers the segment $[1/4,1/3]$ in the first cut, he
keeps preferring the segment $[1/4,1/3]$ for the other cut.

The condition $\mathbf{P_{pe}}$ is used only once in the paper (in Theorem
2.6).

An easy exercise shows that with the Baguette’s gorbushka preferences the
$\mathbf{P_{dte}}$ condition makes fair division possible. Indeed, if the
“gorbushka” degenerates to a point, it becomes equivalent to any other
degenerate segment. So if the cake master makes all the cuts at the end-point
$0$, and so creates $r-1$ degenerate tiles, every player becomes happy.

###  1.5. What kind of divisions are allowed

A division of the cake is called _full_ if each non-degenerate tile is
allocated to one of the players, or in other words _no tiles are dropped_.

Other divisions may be possible. For example some non-degenerate tiles may be
dropped because some players prefer not to choose any of the available non-
degenerate tiles (we say that they prefer an empty piece).

Sometimes it may be necessary to allow exceptions (see Theorem 3.1) when one
player (in a very exceptional situation) is allowed to have two pieces of the
cake.

###  1.6. What is known

  1. (1)

If $r$ is a prime power then a full, envy-free division always exists if the
preferences satisfy the $\mathbf{P_{pe}}$ condition. See [1] and [2], and
Theorem 2.6 in the present paper. This result of Avvakumov and Karasev [1,
Theorem 3.3] was established earlier by Meunier and Zerbib [8, Theorem 1] in
the cases when $r$ is a prime or $r=4$, see also Segal-Halevi [9] where the
result was conjectured and proved in the case $r=3$.

  2. (2)

As shown in [1] if $r$ is not a prime power the theorem of Avvakumov and
Karasev is no longer true.

  3. (3)

Assume that we are allowed to drop some of the tiles. Then without
restrictions on $r$ a not necessarily full envy-free division always exists
under the condition $\mathbf{P_{dte}}$, see Theorem 2.7 and [1, 8] for a
proof.

###  1.7. What is new in the paper

  1. (1)

We modify the rules of the game. As before there are $r-1$ cuts which
partition the interval $[0,1]$ into $r$ tiles (possibly degenerate). In the
presence of degenerate tiles only one of the guests may be given two tiles
(instead of one) in which case one of them must be the rightmost tile (the
right gorbushka). Then, if either $r$ is a prime number or $r=4$, under the
condition $\mathbf{P_{dte}}$, a full envy-free division always exists with no
other restrictions (Theorem 3.1).

  2. (2)

If $r$ is neither a prime nor equal to $4$, the statement above is no longer
true (Theorem 3.3).

  3. (3)

Let $r$ be a prime number or $r=4$. Assume that in the division we are allowed
to drop _at most one of the non-degenerate tiles_ and the condition “no player
prefers an arbitrarily small tile number $r$, unless it degenerates to a
point”. That is, for a fixed system of preferences, there exists
$\varepsilon>0$ such that a non-degenerate tile $r$ shorter than $\varepsilon$
is never preferred. Then an envy-free division always exist under the
condition $\mathbf{P_{dte}}$ (Corollary 3.2).

  4. (4)

We give an alternative proof of the result of Avvakumov and Karasev: If $r$ is
a prime power then an envy-free full partition always exist under the
condition $\mathbf{P_{pe}}$.

  5. (5)

Consider $r-1$ cuts which partition the interval $[0,1]$ into $r$ possibly
degenerate tiles. We assume that the tiles may be distributed among the
players without any restrictions, in particular a player may receive several
tiles at a time. Then under the condition $\mathbf{P_{dte}}$, a full envy-free
division always exists if $r=p^{a}$ is a prime power (Theorem 5.1).

###  1.8. New narrative and the novelty of the method.

We approach the cake division problem from a slightly different point of view
by offering a new narrative which is, in our opinion, helpful for the
formalization and construction of configuration spaces.

We assume that the cake division supervisor (cake master) cuts the cake into
tiles, and then puts them on display in (transparent) cake boxes, prepared in
advance and numbered from $1$ to $r$. This is called a partition/allocation of
the cake because it involves both a cut (partition) of the cake and (an
arbitrary) allocation of the tiles in boxes.

After that the players approach the boxes and point to some of them,
expressing their preferences.

The condition $\mathbf{P_{dte}}$ allows the cake master to ignore the
degenerate tiles, meaning that they are not allocated at all. Instead, the
degenerate tiles are put in the trash, and as a result after a
partition/allocation some of the boxes may be empty.

A quite natural assumption in this setting is the _equivariance of the
preferences_. It says that the players pay attention only on the content,
disregarding the numbers (labels) on the boxes. In other words each player
prefers one and the same piece of the cake, ignoring the numbering of the box
where it is placed in the current allocation.

An example of a non-equivariant preference arises if a (superstitious) thief
always avoids the box no. 13, regardless of its content.

##  2\. Comparison of the old and the new setting

The classical or the “old” approach to envy-free division typically relies on
Knaster-Kuratowski-Mazurkiewicz theorem, Sperner’s lemma, Brouwer fixed-point
theorem, or some extension involving mapping degree. Our approach, where the
emphasis is on configuration spaces and equivariant topology, is (informally)
referred to as the “new” approach.

###  2.1. Configuration spaces, old and new

A _cut_ of the segment $I=[0,1]$ by $r-1$ cut-points is (as in Section 1)
recorded as $x=(x_{1},...,x_{r-1})\in I^{r-1}$, where the individual cut-
points $x_{i}$ are listed in the increasing order. The tiles
$I_{i}=[x_{i-1},x_{i}]$ are automatically labeled by $[r]=\\{1,2,...,r\\}$,
also from left to the right. The cut $x$ can be uniquely reconstructed from
the vector $z=(z_{1},\dots,z_{r})\in\Delta^{r-1}:={\rm
conv}\\{e_{i}\\}_{i=1}^{r}\subset\mathbb{R}^{r}$, where $z_{i}\in[0,1]$ is the
length of the tile $I_{i}$.

Therefore, in the traditional setting, the _configuration space of all
possible cuts_ is the standard simplex $\Delta^{r-1}$. Its boundary
corresponds to degenerations of some of the tiles.

Assuming that there are $r$ different boxes, also labeled by
$[r]=\\{1,2,...,r\\}$, let us consider an _allocation map_
$\alpha:[r]\rightarrow[r]$ whose function is to distribute the tiles in the
boxes. To this end, there are no restrictions on $\alpha$: some of the boxes
may contain more than one tile.

######  Definition 2.1.

Two allocations with one and the same cut are called _equivalent_ if they
differ only by allocations of degenerate tiles.

This definition formalizes (on the level of configuration spaces) the property
$\mathbf{P_{dte}}$ which says that “all degenerate tiles are equal from the
viewpoint of the players”.

Example: Assume that the cut-points are $(1/4,1/3,1/3,2/3,2/3)$, which means
that the tiles $I_{3}$ and $I_{5}$ are degenerate. All tiles $I_{i}$, labeled
by $i\in[6]$, should be allocated to six boxes $B_{j}$, labeled by $j\in[6]$.
The allocation
$B_{1}=\\{1,2,3\\},B_{2}=\emptyset,B_{3}=\emptyset,B_{4}=\\{4\\},B_{5}=\\{5\\},B_{6}=\\{6\\}$
is equivalent to
$B_{1}=\\{1,2\\},B_{2}=\emptyset,B_{3}=\emptyset,B_{4}=\\{4\\},B_{5}=\\{5,3\\},B_{6}=\\{6\\}$,
and also to
$B_{1}=\\{1,2\\},B_{2}=\\{3\\},B_{3}=\emptyset,B_{4}=\\{4\\},B_{5}=\\{5\\},B_{6}=\\{6\\}$.

It is instructive to think that for an equivalence class only non-degenerate
tiles are allocated, whereas degenerate ones are put in the trash. So the
equivalence class of the above three allocation is recorded as
$B_{1}=\\{1,2\\},B_{2}=\emptyset,B_{3}=\emptyset,B_{4}=\\{4\\},B_{5}=\emptyset,B_{6}=\\{6\\}$.

The space of all possible equivalence classes of cuts and allocations forms a
configuration space. This configuration space can be described as a simplicial
complex obtained by gluing together different copies $\Delta_{\alpha}$ of the
standard simplex $\Delta^{r-1}$, one copy for each allocation function
$\alpha:[6]\rightarrow[6]$.

This construction has many variations and modifications, for example one can
put some restrictions on the mapping $\alpha$. Different restrictions yield
different configuration spaces and the design of a proper configuration space
is guided and motivated by the envy-free division problem we are interested
in.

All these configuration spaces form a _species_ which is closely tied to the
class of _chessboard complexes_ (Section 6).

Summarizing the main difference between the new and the old approach we
observe that the configuration spaces are respectively of the following two
types:

  * •

The old-style configuration space is the simplex $\Delta^{r-1}$, whose points
record cuts of the interval $I=[0,1]$.

  * •

Characteristic for the new approach is a configuration space $\mathcal{C}$,
whose points record both the cuts of $I$ and allocations of non-degenerate
tiles into boxes.

###  2.2. Preferences, old and new

######  Definition 2.2.

The old-style preferences of $r$ players is a matrix of subsets
$(A^{j}_{i})_{i,j=1}^{r}$ of the standard simplex $\Delta^{r-1}$. The subsets
are interpreted as preferences in the usual sense as follows:

(2) $x\in A^{j}_{i}\ \ \Leftrightarrow\,\mbox{ {\rm in the cut} }x\mbox{ {\rm
the player} }j\mbox{ {\rm prefers the tile} }i\,.$

The new-style preferences of $r$ players is a matrix of subsets
$(B^{j}_{i})_{i,j=1}^{r}$ of the configuration space $\mathcal{C}$.
Analogously, they are interpreted as:

(3) $\begin{split}(x,\alpha)\in B^{j}_{i}\ \ \Leftrightarrow\,&\mbox{ {\rm in
the cut} }x\mbox{ {\rm and the allocation} }\alpha\mbox{ {\rm the player}
}j\\\ &\mbox{ {\rm prefers the content of the box } }i\,.\end{split}$

We assume throughout the paper that:

  * $\mathbf{(P_{cl})}$

The preferences are _closed_ , meaning that they are represented by closed
subsets of the configuration space.

  * $\mathbf{(P_{cov})}$

The preferences are _covering_ , in the sense that for each $j$ the union of
the sets $A_{i}^{j},\,(i=1,\dots,r)$ is equal to the whole configuration
space.

The symmetric group $S_{r}$ acts on $\mathcal{C}$ by renumbering the boxes:

$\sigma(x,\alpha):=(x,\sigma\circ\alpha)\,.$

We assume throughout the paper that the new-style preferences are
_equivariant_ in the sense that for the action of each $\sigma\in S_{r}$,

(4) $(x,\alpha)\in B_{i}^{j}\Leftrightarrow\sigma(x,\alpha)\in
B_{\sigma(i)}^{j}\,.$

The justification of (4) is quite obvious. In light of (3)
$(x,\sigma\circ\alpha)\in B^{j}_{\sigma(i)}$ if and only if in the cut $x$ and
the allocation $\sigma\circ\alpha$ the player $j$ prefers the content of the
box $\sigma(i)$. Since $(\sigma\circ\alpha)^{-1}(\sigma(i))=\alpha^{-1}(i)$
the condition (4) expresses the idea that players make their decisions solely
on the content of the boxes, not on their current labels.

###  2.3. Preferences $\mathbf{P_{pe}}$

Here we formalize the property $\mathbf{P_{pe}}$ ”The preferences are
determined by non-degenerate tiles” (introduced in Section 1.4). For this
purpose we provide a dictionary of some of the relevant terms and definitions
(used here and elsewhere in the paper).

Degenerate tiles for a cut $x\in\Delta^{r-1}$:
$Deg(x)=\\{i\in[r]\mid|I_{i}|=x_{i}-x_{i-1}=0\\}$

Essential tiles for a cut $x$: $Ess(x)=\\{I_{i}\mid x_{i}-x_{i-1}>0\\}$

Labeling of essential tiles: For $I\in Ess(x)\quad\nu(I,x)=i\Leftrightarrow
I=I_{i}=I_{i}(x)$

Partition equivalent cuts: $x\sim_{pe}x^{\prime}\Leftrightarrow
Ess(x)=Ess(x^{\prime})$

We say that the preferences $(A_{i}^{j})$ are $\mathbf{(P_{pe})}$ if whenever
$x\sim_{pe}x^{\prime}$, we have

  1. (1)

$\quad x\in A_{\nu(I,x)}^{j}\Leftrightarrow x^{\prime}\in
A_{\nu(I,x^{\prime})}^{j}$, and

  2. (2)

$(\exists i_{1}\in Deg(x))\,x\in A_{i_{1}}^{j}\,\,\Rightarrow\,\,(\forall
i_{2}\in Deg(x^{\prime}))\,x^{\prime}\in A_{i_{2}}^{j}.$

The partition equivalence condition is closely related to pseudo-equivariance
assumptions from [1, Section 4.1]. Indeed, $x$ and $x^{\prime}$ are in the
same partition equivalence class if and only if one can be obtained from the
other by an identification of the form $\sigma_{FGZ}$, described in [1].

###  2.4. Envy-free division, old and new

######  Definition 2.3.

Let $(A^{j}_{i})_{i,j=1}^{r}$ be a matrix of old-style preferences. A point
$x\in\Delta^{r-1}$ describes an _envy-free division_ for preferences
$(A^{j}_{i})_{i,j=1}^{r}$ if there exists a permutation $\pi\in S_{r}$ such
that

$x\in\bigcap_{j=1}^{r}A_{\pi(j)}^{j}\,.$

Here is the counterpart of this definition for the new-style preferences.

######  Definition 2.4.

Let $(B^{j}_{i})_{i,j=1}^{r}$ be a matrix of new-style preferences. A point
$\hat{x}=(x,\alpha)\in\mathcal{C}$ provides an _envy-free division_ for
preferences $(B^{j}_{i})_{i,j=1}^{r}$ if

(5) $(x,\alpha)\in\bigcap_{j=1}^{r}B_{j}^{j}\,.$

By the equivariance of preferences (4) we immediately observe that if an envy-
free division $(x,\alpha)$ exists then for each permutation $\pi\in S_{r}$

(6) $(x,\pi\circ\alpha)\in\bigcap_{j=1}^{r}B_{\pi(j)}^{j}\,.$

For the same reason if (6) holds for one permutation than it holds for all of
them and (5) is an immediate consequence.

In the terminology of this section the envy-free division theorems of Gale and
Avvakumov-Karasev can be formulated as follows.

######  Theorem 2.5.

(Gale’s theorem [4]) Let $(A_{i}^{j})_{i,j=1}^{r},\
A_{i}^{j}\subset\Delta^{r-1}$ be a matrix of the old-style closed covering
preferences. Assume that nobody prefers a degenerate tile, that is,
$A_{i}^{j}\cap\Delta_{i}^{r-1}=\emptyset$ for each $i$ and $j$, where
$\Delta_{i}^{r-1}$ is the face of $\Delta^{r-1}$ opposite to the vertex
labeled by $i$. Then there exists an envy-free division, that is, a
permutation $\sigma\in S_{r}$ such that

$\bigcap_{i\in[r]}A_{\sigma(j)}^{j}\neq\emptyset\,.$

######  Theorem 2.6.

([1, Theorem 4.1]) Assume that $r$ is a prime power. Assume we have the old-
style closed, covering preferences $(A_{i}^{j})_{i,j=1}^{r},\ \
A_{i}^{j}\subset\Delta^{r-1}$ satisfying the $\mathbf{P_{pe}}$ condition.

Then there exists a permutation $\pi\in S_{r}$ such that

$\bigcap_{j\in[r]}A^{j}_{\pi(j)}\neq\emptyset\,.$

In other words there exists a partition of $[0,1]$ into at most $r$ non-
degenerate intervals such that each non-degenerate interval is given to a
different player, the remaining players are not given anything (they are given
“empty pieces”), and this distribution is envy-free from the viewpoint of each
of the players.

######  Theorem 2.7.

([1]) Let $(A_{i}^{j})_{i,j=1}^{r}$ be the old-style closed, covering
preferences. Degenerate tiles may be preferred but the condition
$\mathbf{P_{dte}}$ is satisfied. Then there exists an envy-free division where
some tiles may be dropped.

##  3\. Configuration space $\Delta_{r,r-1}\ast[r]$

In this section we consider the configuration space of partitions and
allocations with the following restrictions on the allocation function
$\alpha$:

  1. (1)

At most two non-degenerate tiles are allocated to the same box.

  2. (2)

If two non-degenerate tiles appear in the same box than one of the tiles is
necessarily the last tile $r$ (the right “gorbushka” tile).

So, the tiles are allocated one tile per box with the unique exception: the
tile $r$ can be put with some other tile in one and the same box.

Denote the associated configuration space by $\mathcal{C}_{1}$. This space,
which appeared in the literature in the framework of the _colored Tverberg
theorem_ , is known as the _chessboard complex_ $\Delta_{r,r-1}*[r]$. We need
some special topological properties of this space, however the reader can
safely take them for granted (at least for the first reading). For a more
detailed exposition and the original references we refer the reader to the
Appendix (Section 6).

The configuration space $\mathcal{C}_{1}$ is used in the proof of the
following Gale-type theorem which we informally call the “right gorbushka”
theorem.

######  Theorem 3.1.

Suppose that either $r$ is a prime number or $r=4$. Let

$(B_{i}^{j})_{i,j=1}^{r},\ \ B_{i}^{j}\subseteq\mathcal{C}_{1}$

be a matrix of the new-style preferences which are _closed, covering and
equivariant_. Then there exists an envy-free division:

(7) $\bigcap_{i\in[r]}B_{i}^{i}\neq\emptyset\,.$

In other words, there exists a cut and an allocation (of the type described
above) such that the player $j$ prefers the content of the box $j$ for all
$j$. More explicitly, each player obtains not more than one non-degenerate
tile, possibly with only one exception, when a player gets two tiles. In that
case one of these tiles is labeled by $r$.

###### Proof.

Assuming the contrary, suppose that the intersection (7) is empty. It follows
from the equivariance of the preferences that the intersection (5) is also
empty for each permutation $\pi\in S_{r}$.

Let us construct an _equivariant_ test map
$F:\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}$ which records the preferences of
the players. We begin by replacing closed preferences $B_{i}^{j}$ by slightly
larger open equivariant preferences $O_{i}^{j}$, so that the corresponding
intersection is also empty for each permutation $\sigma\in S_{r}$

(8) $\bigcap_{j\in[r]}O_{\sigma(j)}^{j}=\emptyset\,.$

Next, choose (for each $j\in[r]$) an equivariant partition of unity
$\\{f_{i}^{j}\\}_{i=1}^{r}$ subordinated to the cover
$\\{O_{i}^{j}\\}_{i=1}^{r}$. Since the preferences are equivariant, we can
make these functions also equivariant:

(9) $f_{\sigma(i)}(\sigma(x,\alpha))=f_{i}^{j}(x,\alpha)\,.$

By construction $f_{i}^{j}(x,\alpha)>0$ implies $(x,\alpha)\in O_{i}^{j}$.

By averaging $F_{i}=\frac{1}{r}\sum_{j=1}^{r}f^{j}_{i}$ we obtain a vector-
valued $S_{r}$-equivariant function

$F=(F_{1},F_{2},\dots,F_{r}):\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}.$

Let $\widehat{F}:\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}/D$ be the
(equivariant) map obtained by composing the map $F$ with the projection
$\mathbb{R}^{r}\rightarrow\mathbb{R}^{r}/D_{\mathbb{R}^{r}}$, where
$D_{V^{r}}$ stands for the diagonal $D_{V^{r}}\subset V^{r}$. We claim that
the map $\widehat{F}$ must have a zero.

Otherwise there arises an equivariant map $\mathcal{C}_{1}\rightarrow
S^{r-2}$. However this is a contradiction, see [3, Proposition 4.2] and [12,
Proposition 3]. Note that in these papers the configuration space
$\mathcal{C}_{1}$ served as the key building block for the configuration space
used in the colored Tverberg theorem.

It remains to apply D. Gale’s original argument [4] (see also [1]). We have
proven the existence of $(x,\alpha)\in\mathcal{C}_{1}$ such that the matrix
$(f_{i}^{j}(x,\alpha))$ is doubly stochastic. By the Birkhoff-von Neumann
theorem it lies in the convex hull of permutation matrices.

It follows that there exists a permutation $\sigma\in S_{r}$ such that
$f_{\sigma}(j)^{j}(x,\alpha)>0$ for all $j$. As a consequence the intersection
(8) is also empty which is a contradiction. ∎

Here is a corollary which refines Theorem 2.7 about not necessarily full
divisions, which means that some of the tiles may not be distributed at all.

######  Corollary 3.2.

Assume that $r$ is prime or $r=4$, and let
$(A_{i}^{j})_{i,j=1}^{r}\,(A_{i}^{j}\subseteq\Delta^{r-1})$ be a matrix of
old-style (covering, closed, $\mathbf{P_{dte}}$) preferences. We do not
exclude that a degenerate tile is preferred by some players. We also assume
that there exists $\varepsilon>0$ such that a non-degenerate tile $r$ shorter
than $\varepsilon$ is never preferred.

Then there always exists an envy-free division such that each player gets a
preferred tile (or nothing, if he prefers so), and at most one tile is
dropped.

###### Proof.

Given $(A_{i}^{j})$, let us create new-style preferences
$(B_{i}^{j})=\psi(A_{i}^{j}),\ B_{i}^{j}\subseteq\mathcal{C}_{1}$ by the
following rule.

Imagine you are a player $j$, the segment $I$ is cut into $r$ tiles by a cut
$x$, and you know which tiles you prefer according to $(A_{i}^{j})_{i=1}^{r}$.
These tiles are allocated to $r$ boxes by an allocation function
$\alpha:[r]\rightarrow[r]$, and you need to specify which boxes you prefer.

An empty box is preferred whenever a degenerate tile is preferred according to
$(A_{i}^{j})$. A non-empty box is preferred whenever one of the tiles
contained in the box is preferred according to $(A_{i}^{j})$. We add one
exceptional rule: If the box contains the tile $r$ and no other tiles, the box
is preferred not only if the tile $r$ is preferred, but also if a degenerate
tile is preferred according to $(A_{i}^{j})$.

More formally,

  1. (1)

If the box $i$ is empty, then $(x,\alpha)\in B_{i}^{j}$ iff

    1. (a)

There is a degenerate tile $m$ in the cut $x$, and

    2. (b)

$x\in A_{m}^{j}$.

  2. (2)

If the box $i$ has exactly one non-degenerate tile $m\neq r$, then

$(x,\alpha)\in B^{j}_{i}\Leftrightarrow x\in A_{m}^{j}.$

  3. (3)

If the box $i$ contains two non-degenerate tiles, $r$ and some $m\neq r$, then

$(x,\alpha)\in B^{j}_{i}\Leftrightarrow\hbox{either \ \ }x\in A_{r}^{j}\hbox{\
or\ }x\in A_{m}^{j}.$

  4. (4)

If the box $i$ has exactly one non-degenerate tile $r$, then

    1. (a)

If there are no degenerate tiles in the cut $x$,

$(x,\alpha)\in B^{j}_{i}\Leftrightarrow x\in A_{r}^{j}.$

    2. (b)

If there is a degenerate tile $m$ in the cut $x$,

$(x,\alpha)\in B^{j}_{i}\Leftrightarrow\hbox{either \ \ }x\in A_{r}^{j}\hbox{\
or\ }x\in A_{m}^{j}.$

The new-style preferences $(B_{i}^{j})$ are clearly equivariant and covering.
They are also closed – this is where the condition “short tile $r$ is never
preferred unless it degenerates to a point” is used. Let us briefly comment on
how closeness fails without this condition. Assume there is a sequence of cuts
$(x^{(n)})_{n\in\mathbb{N}}$ such that the length of the tile $r$ tends to
zero, and the tile $r$ is preferred according to $(A_{i}^{j})$. Consider an
allocation function $\alpha_{k},\ (k=1,\dots,r-1)$ which places the tile $r$
in the same box with the tile $k$, assuming that the tile $k$ is non-
degenerate. For $(x^{(n)},\alpha_{k})$ the box with the tiles $r$ and $k$ is
preferred. Therefore, in the limit, when $r$ degenerates, the box with the
tile $k$ must be preferred, which is leads to a contradiction.

Remark. For the above defined preferences $(B_{i}^{j})=\psi(A_{i}^{j})$, if
there are no degenerate tiles, an empty box may exist, but an empty box is
never preferred.

Now let us apply Theorem 3.1 to $(B_{i}^{j})=\psi(A_{i}^{j})$. There exists an
envy-free division such that each player $j$ prefers the box $j$ for all $j$.
If the box $j$ is empty, the player $j$ prefers a degenerate tile. It exists
by the above remark, so let the player $j$ take the degenerate tile.

If the box $j$ contains a unique tile which is not $r$, then the player
prefers the tile.

If the box $j$ contains two tiles (this might happen for one box only), one of
these tiles is preferred. Drop the other one.

If the box $j$ contain a unique tile which is $r$, then the player either
prefers the tile (then there is no need to drop the tile), or he prefers the
degenerate tile. In this case drop the tile $r$.∎

######  Theorem 3.3.

Assume that $r$ is neither a prime number nor equal to $4$. Then there exist
$(B_{i}^{j})_{i,j=1}^{r},\,B_{i}^{j}\subseteq\mathcal{C}_{1}$, the new-style
(closed, covering, equivariant) preferences such that

$\bigcap_{i\in[r]}B_{i}^{i}=\emptyset\,.$

In other words, there exists no envy-free division if empty pieces may be
preferred, and one of the players may be satisfied by getting a disconnected
share consisting of two tiles one of which is $r$.

###### Proof.

Construct an equivariant function
$F=(F_{1},F_{2},\dots,F_{r}):\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}$ whose
image belongs to the hyperplane $x_{1}+\dots+x_{r}=1$ and misses the diagonal
$x_{1}=\dots=x_{r}$. If $r$ is not a prime the existence of such function
follows from [3, Proposition 4.2].

Let $\widetilde{B}_{i}^{j}$ be the preferences not depending on $j$ (meaning
that all the players have the same preferences) where

$\widetilde{B}_{i}^{j}=\widetilde{B}_{i}:=F^{-1}\\{x_{i}\neq 0\\}\,.$

They are covering and equivariant, however they are open, rather than closed
(as required). Still $\widetilde{B}_{i}$ can be replaced by a slightly smaller
closed sets $B_{i}$ with all the necessary properties. It remains to observe
that $\bigcap_{i\in[r]}B_{i}^{i}=\emptyset$. ∎

##  4\. Configuration space $\Delta_{r,2r-1}$

In this section we use our method to give a new proof of the envy-free theorem
of Avvakumov and Karasev [1, Theorem 4.1]. Recall that this result was
established earlier by Meunier and Zerbib [8, Theorem 1] in the cases when $r$
is a prime or $r=4$, see also Segal-Halevi [9] where the result was
conjectured and proved in the case $r=3$.

We modify the configuration space. Let us consider $2r-2$ cuts of the interval
$I=[0,1]$, so altogether there are $2r-1$ tiles. Allocate the tiles to $r$
boxes by _“admissible”_ allocation functions $\alpha:[2r-1]\rightarrow[r]$,
permitting at most one non-degenerate tile in each of the boxes.

As a consequence, in the associated configuration space $\mathcal{C}_{2}$ only
those cuts that create at least $r-1$ degenerate tiles are permitted.

The configuration space $\mathcal{C}_{2}$ is again a chessboard complex
$\Delta_{r,2r-1}$, see the Appendix (Section 6). Its elements are (equivalent
classes of) pairs $(x,\alpha)$ where $x$ is a cut with at least $r-1$
degenerate tiles and $\alpha$ is an associated admissible allocation function.

######  Theorem 4.1.

Let $r$ be a prime power. Let

$(C_{i}^{j})_{i,j=1}^{r},\ \ C_{i}^{j}\subseteq\mathcal{C}_{2}$

be a matrix of the new-style (closed, covering, equivariant) preferences. Then
there exists an envy-free division:

(10) $\bigcap_{i\in[r]}C_{i}^{i}\neq\emptyset\,.$

In other words there exists a cut and an _admissible allocation_ of non-
degenerate tiles into the boxes, such that the player $j$ prefers the box $j$
for all $j$.

###### Proof.

The proof follows the pattern of the proof of Theorem 3.1. Assume, for the
sake of contradiction, that the intersection (10) is empty. As before we
construct an (equivariant) test map
$F:\mathcal{C}_{2}\rightarrow\mathbb{R}^{r}$ which records the information
provided by the preferences $C_{i}^{j}$.

Initially we replace $C_{i}^{j}$ with slightly larger open preferences
$O_{i}^{j}$ and choose (for each $j\in[r]$) an equivariant partition of unity
$\\{f_{i}^{j}\\}_{i=1}^{r}$ subordinated to the cover
$\\{O_{i}^{j}\\}_{i=1}^{r}$. Since the preferences are equivariant, we can
make these functions also equivariant:

(11) $f_{\sigma(i)}^{j}(\sigma(x,\alpha))=f_{i}^{j}(x,\alpha)\,.$

By averaging $F_{i}=\frac{1}{r}\sum_{j=1}^{r}f^{j}_{i}$ we obtain a vector-
valued $S_{r}$-equivariant function

$F=(F_{1},F_{2},\dots,F_{r}):\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}.$

Let $\widehat{F}:\mathcal{C}_{1}\rightarrow\mathbb{R}^{r}/D$ be the
(equivariant) map obtained by composing the map $F$ with the projection
$\mathbb{R}^{r}\rightarrow\mathbb{R}^{r}/D_{\mathbb{R}^{r}}$, where
$D_{V^{r}}$ stands for the diagonal $D_{V^{r}}\subset V^{r}$. This map must
have a zero.

In the opposite case there arises an equivariant map
$\mathcal{C}_{2}\rightarrow S^{r-2}$. This is, in light of the
$(r-2)$-connectivity of $\mathcal{C}_{2}$ [15], a contradiction with either
Dold’s theorem [7] or (more general) Volovikov’s Theorem [11].

It remains to apply D. Gale’s original trick [4], already described in the
proof of Theorem 3.1. ∎

_New proof of Theorem 2.6._ Based on preferences $(A_{i}^{j})$, let us
construct new preferences $(C_{i}^{j})=(\phi(A_{i}^{j}))$ defined on the
configuration space $\mathcal{C}_{2}$.

The map $\phi$ can be described in a form of an algorithm:

  1. (1)

We are given a cut $x$ of the segment $I$ with $2r-2$ cut points. Create an
induced cut $y$ of $I$ with $r-1$ cut points ($y\in\Delta^{r-1}$), preserving
the same collection of non-degenerate intervals $\\{I^{\nu}_{k}\\}_{k=1}^{s}$.
In other words we eliminate $r-1$ superfluous (multiple) cuts. Note that this
step can be performed in many different ways.

  2. (2)

If the preferences $\\{A_{i}^{j}\\}$ of a player dictate the choice of some
non-degenerate tile $i$, add the box $\alpha(i)$ to the preferences of the
player. Note that the property $\mathbf{P_{pe}}$ of $(A_{i}^{j})$) implies
that no matter how the superfluous cuts are eliminated, the result will be one
and the same.

  3. (3)

If the preferences $(A_{i}^{j})$ dictate a player to choose a degenerate
interval (which occurred after $r-1$ cuts), observe that there necessarily
exists an empty box, since in this case the number of non-degenerate tiles is
at most $r-1$. Add all empty boxes to the preferences of the player.

We emphasize once again that the condition $\mathbf{P_{pe}}$ is used in the
proof that the preferences $C_{i}^{j}$ are well-defined.

It is not difficult to check that the preferences
$(C_{i}^{j})=(\phi(A_{i}^{j}))$ satisfy all conditions of Theorem 4.1. So
there exist an envy-free division with $(C_{i}^{j})$, and, by construction, a
full envy-free division for $(A_{i}^{j})$. ∎

##  5\. Configuration space $[r]^{*r}$

We illustrate the versatility of the method of configuration spaces by one
more example. As in Section 3 we consider partitions of the interval $I=[0,1]$
into $r$ tiles by $r-1$ cuts. However in this section we put no restriction on
the allocation functions $\alpha:[r]\rightarrow[r]$ and consider all possible
ways to allocate $r$ tiles to $r$ boxes. In particular, a box may be empty or
contain several tiles.

The corresponding configuration space $\mathcal{C}_{3}=[r]^{*r}$ is the
$r$-fold join of the $0$-dimensional simplicial complex $[r]$. Recall [7, 14]
that this configuration space naturally arises in the topological Tverberg
problem (a monochromatic predecessor of the colored Tverberg problem).

######  Theorem 5.1.

Let $r$ be a prime power. Let

$(D_{i}^{j})_{i,j=1}^{r},\ \ D_{i}^{j}\subseteq\mathcal{C}_{3}$

be a matrix of the new-style (closed, covering, equivariant) preferences. Then
there exists an envy-free division:

(12) $\bigcap_{i\in[r]}D_{i}^{i}\neq\emptyset\,.$

In other words there exists a cut and an allocation of non-degenerate tiles
into the boxes, such that the player $j$ prefers the box $j$ for all $j$.

###### Proof.

The proof follows the pattern of the proof of Theorem 3.1. Assuming the
contrary, we again arrive at an equivariant map $\mathcal{C}_{3}\rightarrow
S^{r-2}$ from the configuration space to the sphere. The non-existence of such
a map is a well-known fact [7, 14], as one of the key ingredients in the proof
of the topological Tverberg theorem. ∎

##  6\. Appendix. Chessboard complexes

The _Chessboard complex_ $\Delta_{m,n}$ is the simplicial complex of all non-
attacking placements of rooks on a $[m]\times[n]$ chessboard. More precisely
the vertex-set of $\Delta_{m,n}$ is the set $[m]\times[n]$ (interpreted as a
$(m\times n)$-chessboard) and $S\subset[m]\times[n]$ is a simplex if $S$ has
at most one element in each row or column of $[m]\times[n]$.

Similarly the join $\Delta_{r,r-1}*[r]$, introduced in Section 3, is the
simplicial complex whose vertices $v_{ij}$ correspond to the cells of the
chessboard $r\times r$, and a set of vertices corresponds to a simplex
whenever (1) there is at most one vertex in each column, and (2) there is at
most one vertex in each row, with a unique possible exception, when there are
two vertices in a row, and one of these two vertices belongs to the column
$r$. From this description it is clear that the rows of the chessboard
correspond to the boxes, whereas the columns correspond to the tiles of a cut.

If a column of the chessboard $[r]\times[r]$ is empty, the corresponding tile
degenerates. Each point $\hat{z}\in\Delta_{r,r-1}*[r]$ is in (the interior of)
some simplex, and has a (unique) representation
$\hat{z}=\sum_{i=1}^{r}z_{i}v_{i,\alpha(i)}$, in terms of the corresponding
barycentric coordinates. This point is associated to (1) the cut whose
$z$-representation (Section 2.1) is $(z_{1},...,z_{r})$, and (2) the
allocation function $\alpha$ which allocates the tile $i$ to the corresponding
box $\alpha(i)$.

In other words, the join $\Delta_{r,r-1}*[r]$ is precisely the configuration
space which parameterizes all partitions/allocations described in Section 3.

Analogously, the complex $\Delta_{r,2r-1}$ is isomorphic to the configuration
space from Section 4 which records partitions into $2r-1$ tiles with at most
$r$ non-degenerate ones and the corresponding allocation functions.

The $(r-2)$-connectedness of the complex $\Delta_{r,2r-1}$ was used in [15]
for the proof of the original colored Tverberg theorem. The complex
$\Delta_{r,r-1}$ is always a pseudomanifold and its properties were used in
the proof of the _optimal colored Tverberg theorem_ [3] (see also [12, 6]).
The role of chessboard complexes and other configuration spaces used in
combinatorics and discrete geometry is discussed in [7, 14].

### Acknowledgements

We are grateful to the anonymous referee of the paper [5] who pointed out that
our methods imply Theorem 2.6. R. Živaljević was supported by the Serbian
Ministry of Education, Science and Technological Development through
Mathematical Institute of the Serbian Academy of Sciences and Arts. Sections 3
and 5 are supported by the Russian Science Foundation under grant 21-11-00040.

## References

  * [1] S. Avvakumov, R. Karasev, Envy-free division using mapping degree. Mathematika, Vol. 67, Issue 1, 36–53 (2021).
  * [2] S. Avvakumov, R. Karasev, Equipartition of a segment, arXiv:2009.09862
  * [3] P.V.M. Blagojević, B. Matschke, G. M. Ziegler, Optimal bounds for the colored Tverberg problem, J. Eur. Math. Soc. (JEMS), 2015, 17:4, 739–754.
  * [4] D. Gale. Equilibrium in a discrete exchange economy with money. International Journal of Game Theory, 13(1):61–64, 1984.
  * [5] D. Jojić, G. Panina, R.T. Živaljević. Splitting necklaces, with constraints. arXiv:1907.09740v4 [math.CO]
  * [6] D. Jojić, G. Panina, R.T. Živaljević. Optimal colored Tverberg theorems for prime powers, arXiv:2005.11913 [math.MG]
  * [7] J. Matoušek. Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry. Universitext, Springer-Verlag, Heidelberg, 2003 (Corrected 2nd printing 2008).
  * [8] F. Meunier, S. Zerbib. Envy-free cake division without assuming the players prefer nonempty pieces. Israel J. Math. (to appear), 2019. arXiv:1804.00449v2.
  * [9] E. Segal-Halevi. Fairly dividing a cake after some parts were burnt in the oven. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), 1276–1284, 2018.
  * [10] W. Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640–644, 1980.
  * [11] A.Y. Volovikov.Volovikov, A.Yu.  On a topological generalization of the Tverberg theorem.  Math. Notes, 59:324–32, 1996.
  * [12] S. Vrećica, R. Živaljević. Chessboard complexes indomitable. Journal of Combinatorial Theory, Series A 118 (2011) 2157–2166.
  * [13] D.R. Woodall. Dividing a cake fairly. Journal of Mathematical Analysis and Applications, 78(1):233–247, 1980.
  * [14] R.T. Živaljević. _Topological methods in discrete geometry_ , Chapter 21 in Handbook of Discrete and Computational Geometry (third edition), CRC Press LLC, (2017) 551–580. J.E. Goodman, J. O’Rourke, and C. D. Tóth (Editors).
  * [15] R.T. Živaljević and S.T. Vrećica. The colored Tverberg’s problem and complexes of injective functions. _J. Combin. Theory Ser. A_ 61 (1992), 309–318.