(This is an update on my Ethereum Protocol Fellowship. More updates can be found here ).


Last week, I analysed the BigPlayer rule for cake-cutting using the Open Game engine, and found equilibria at proportional distributions for $n \in [2, 3, 4]$. Here follows a handwavy proof of general fairness.


Notation Let $n\in \mathbb{N}$ be the total number of players, and let $P_i$ be the name of player $i$. Let $C\in \mathbb{R}^+$ be the total size of the cake to be shared among all players.


Definition The BigPlayer rule is defined by the following rules:

  1. $P_1$ cuts the pie in two pieces, resulting in two pieces of sizes $(\alpha C, (1-\alpha )C)$, where $\alpha \in [0, 1]$.
  2. $P_2$ chooses one of the two pieces.
  3. If there are any players left who did not play yet: Let the last cutter and the chooser be $(P_a, P_b)$, respectively, and the size of their pieces $(a, b)$, respectively. Then, let $P_\text{BP}=P_a$ if $a\geq b$, and $P_\text{BP}=P_b$ otherwise. $P_\text{BP}$ then has to cut their piece in two.
  4. A player that did not play yet chooses one of $P_\text{BP}$’s pieces.
  5. Move to 3 if there are any players that have not played yet.


Theorem Cutting a cake of size $C$ with the BigPlayer rule has a Nash equilibrium at a proportional distribution with $n-1$ cuts where each of $n$ players gets a contiguous piece of size $C/n$.


(proof) The $n=1$ case is trivial. The $n=2$ case reduces to the game ‘I cut you choose’, so inherits the proportional equilibrium. The proof then follows by induction: Assume that the $n$-player implementation has a proportional equilibrium, then consider the game with $n+1$ players. In this game, a proportional first cut would result in two pieces of respective sizes $(\frac{C}{n+1}, \frac{Cn}{n+1})$. Each of the two players then ends up with either a piece of size $\frac{C}{n+1}$, or a piece of size $\frac{Cn}{n+1}$ that then has to be shared with $n$ other players. Since the $n$-player game has a proportional equilibrium, whoever ends up with the piece of size $\frac{Cn}{n+1}$, and all remaining players, will thus also get a proportional piece of size $\frac{C}{n+1}$.

However, consider possible deviations from an initial proportional cut. If $P_1$ chooses to deviate by an $\epsilon$ such that $0<\epsilon<\frac{C(n-1)}{2(n+1)}$, then the resulting pieces are of size $(\frac{C}{n+1} + \epsilon, \frac{Cn}{n+1} - \epsilon)$, the first piece being the smallest. $P_\text{BP}$ ends up with a piece of size $\frac{Cn}{n+1} - \epsilon$, to be shared among $n$ players. The proportional equilibrium of the $n$-player game would then give $P_\text{BP}$ and each remaining player a piece of size $\frac{C}{n+1} - \epsilon/n$, which is smaller than true proportionality among $n+1$ players. Since $P_2$ profits from choosing the first piece they will do so, making this deviation not profitable for $P_1$. If $\epsilon > \frac{C(n-1)}{2(n+1)}$, then the first piece is the biggest, but this simply corresponds to choosing a new deviation $\delta = \frac{C(n-2)}{n+1} - \epsilon$ to which the same reasoning applies. If $\epsilon<0$, then $P_2$ can choose the bigger piece and end up with more than $\frac{C}{n+1}$ by playing the proportional $n$-player game with the remaining players, so this deviation is also not profitable to $P_1$.

The only special case is a cut that leaves two pieces of equal size. In this case, the cutting player is always at a disadvantage, as they have to proportionally share their piece with all remaining players. As long as there are remaining players, this deviation from proportional cutting is thus strictly loss-inducing.

Therefore, the equilibrium of proportional distribution holds for $n+1$ players as long as it holds for $n$ players. Since it holds for $n=2$, it holds in general. $\square$


Note that this rule does not easily generalise to situations where players have different valuation functions, since the choice of $P_\text{BP}$ then depends on the valuation used. Another limiting factor is that the reasoning each player needs to do in order to decide on the cut that maximises their payoff grows quickly with the number of players involved.


A variation One could consider a variation of this rule in which the choice of $P_\text{BP}$ is randomised when the two pieces are of equal size. However, each player can then gamble and try to win the half piece for themselves by making the perfect $(\frac{1}{2}, \frac{1}{2})$ cut of their piece. When the randomisation is a 50/50 coin toss, the cutter’s expected payoff from cutting a piece of size $s$ perfectly in half is $\mathbb{E}_{(\frac{1}{2}, \frac{1}{2})}[p] = \frac{1}{2} \frac{s}{2} + \frac{1}{2} \frac{s}{2m}$, where $m$ is the number of players that still have to play. In contrast, if they decide on a fair strategy, their expected payoff would be simply $\mathbb{E}[p] = \frac{s}{m}$. Whenever $m>3.5$, the expected payoff from a perfect half-cut is thus bigger, so all players, except for the last four, will take their chances on a half-cut, which is probably not desirable behaviour.


One might wonder what the point of this is. If the cake is homogeneous, the fair distribution is trivially known, and this could be enforced in a game by punishing anyone who takes more than $\frac{1}{n}$ of the cake by an arbitrarily large amount. However, some tolerance has to be allowed, since cuts are never perfect. This, however, creates a new problem: if a player ends up with slightly more than $\frac{1}{n}$, it is not clear to the other players if this player is lucky or malicious. By implementing the BigPlayer rule, there is no longer space for maliciousness, so there is no need to distinguish luck from maliciousness.


NB: A previous version of this proof excluded the possibility of half-cuts. Thanks to Rein for pointing this out and suggesting a fix. Thanks also to Matteo Capucci for useful comments.