Equivalence of Models of Cake-Cutting Protocols¹¹1This paper is based on the second author’s final year project.

The Robertson-Webb query model, first introduced by Robertson & Webb, [11] and formalised by Woeginger & Sgall, [14], which is the standard model for discrete cake-cutting protocols in the literature, involves a referee who can ask the agents two types of queries related to their valuation functions (see Introduction), and divides the cake accordingly. A natural question is whether there is an incentive for the agents to report their valuation functions truthfully, i.e. whether there exist any strategy-proof protocols in the Robertson-Webb model. Here, strategy-proofness means truthful reporting is a dominant strategy for every agent, regardless of their valuation function.

Brânzei & Miltersen, [4] show this is impossible for any “interesting” protocols in the Robertson-Webb model: any strategy-proof protocol for two agents is dictatorial (there is a fixed agent who always gets the entire cake), and, more generally, in any strategy-proof protocol for $n$ agents, at least one agent gets an empty piece. There are some other papers that deal with strategy-proofness and the closely related concept of truthfulness.

Notably, Chen et al. , [7] design a cake-cutting protocol that is truthful, proportional, and envy-free for piecewise-uniform valuation functions, but which uses a direct-revelation mechanism (i.e. the agents reveal their entire valuation function to the referee), rather than the standard query model. A recent paper by Tao, [13] proves that no such protocol can exist for the more general case of strictly positive piecewise-constant valuations, and designs a mechanism that satisfies a weaker notion of truthfulness.

Brânzei et al. , [5, 6] introduce the GCC protocols model described above, and use it as a framework to design a protocol for which a contiguous allocation is envy-free if and only if it is the outcome of a Nash equilibrium.

The BC protocols model introduced in this paper is different from the GCC model in that instead of having agents choose which pieces of the cake they receive, they choose which branch of the protocol to proceed to. In addition, the agents’ actions are more restrictive, so that the ordering of the cuts is encoded in the tree structure, which eliminates the need for if-else statements.

Furthermore, our work does not focus on game-theoretic aspects like strategy-proofness, though this would be an interesting topic to address in the future, but rather on results related to the expressive power of the model, which is a topic that Brânzei et al. , [5, 6] only touch on briefly, and considerations such as the space complexity of implementing common protocols in this format.

For a readable introduction to the better-known cake-cutting protocols, including algorithmic and strategic issues, see Procaccia, [10].

The cake, which is represented as the interval $[0,1]$, must be divided between $n$ agents. Each agent must be allocated a piece of cake (i.e. a finite union of disjoint intervals). The pieces of cake allocated to different agents must be disjoint. We allow for an individual agent to be given no cake (or an empty piece $[x,x]$), but every piece of cake must be allocated to some agent.

The agents’ preferences are given by private valuation functions $V_{1},V_{2},...,V_{n}$ that assign a value $V_{i}(a,b)$ to every subinterval $[a,b]\subseteq[0,1]$. We extend the $V_{i}$ additively to pieces of cake, writing $V_{i}(X)$ for the value of a piece of cake X. The valuation functions are assumed to have the following properties:

• •

  Normalization: $V_{i}(0,1)=1$

• •

  Additivity: For any two disjoint intervals $I_{1}$ and $I_{2}$, $V_{i}(I_{1}\cup I_{2})=V_{i}(I_{1})+V_{i}(I_{2})$

• •

  Divisibility: For every interval $[a,b]\subseteq[0,1]$ and $0\leq\lambda\leq 1$ there exists $c\in[a,b]$ such that $V_{i}(a,c)=\lambda V_{i}(a,b)$. In particular, this implies the valuation functions are non-atomic: $V_{i}(a,a)=0$ for every $a\in[0,1]$.

• •

  Non-negativity: $V_{i}(a,b)\geq 0$ for any $a,b\in[0,1]$.

For an allocation $A=(X_{1},...,X_{n})$, where $X_{i}$ is the piece of cake assigned to agent $i$, we define the envy of agent $i$ towards agent $j$ as:

A generalised cut and choose (GCC) protocol [5, 6], is represented as a tree in which each node corresponds to the action of an agent. There are three types of nodes:

• •

  cut nodes: an agent makes a cut between two existing cuts. More specifically, agent $i$ is given a set $S=\{[x_{1},y_{1}],...,[x_{m},y_{m}]\}$ of intervals representing contiguous piece of cake, such that the endpoints of every piece are either 0,1, or cuts made at a previous step. The agent picks an interval $[x_{j},y_{j}]$ and makes a cut at some point $z$ in it.

• •

  choose nodes: an agent chooses between a set of pieces induced by the existing cuts. Agent $i$ is given a set $S$ as above. They choose an interval $[x_{j},y_{j}]$ from $S$, and this interval then gets allocated to them. In the special case $|S|=1$, the agent is essentially assigned a piece and there is no actual “choice”.

• •

  if-else nodes: These nodes can have multiple branches. The protocol progresses to one of the branches based on an if-else statement. The conditions in the if-else statement depend on the order of the cut points made in the previous steps, and the execution history of the protocol (Equivalently, the conditions depend on which pieces the agents cut or chose at each of the previous steps).

Note that cut and choose nodes have at most one child each, so the protocol only branches out at if-else nodes.

In the original paper by Brânzei et al. , [5], the if-else statements are not explicitly included in the tree structure. Instead, the cut/choose nodes have multiple children and progression to one of the children is based on an if-else statement. We view if-else statements as separate nodes for simplicity. It is easy to see that our interpretation and the original one have the same expressive power.

Algorithm 1 shows how the Selfridge-Conway protocol [11], a classic envy-free protocol for three agents, can be represented as a GCC protocol. Algorithm 2 shows the original protocol, for comparison.

Since we are working with multiple models for representing cake-cutting protocols, we need to define what it means for two protocols (possibly represented in different models) to be “the same”. We will present multiple possible notions of equivalence between cake-cutting protocols, which are all based on various bounds agents can guarantee for themselves in terms of value/envy, regardless of the other agents’ strategies, so they are independent of the model used to represent a protocol.

Let $\mathcal{P}$ and $\mathcal{P^{\prime}}$ be two cake-cutting protocols.

1. 1.

   Value equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent if the minimum value that each agent can guarantee for themselves is the same. That is, if in the worst case for protocol $\mathcal{P}$ agent $i$ gets a piece of value $\lambda$, then in the worst case for protocol $\mathcal{P^{\prime}}$ the piece agent $i$ gets must have the same value $\lambda$.

2. 2.

   Total envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent if the maximum total amount of envy $\sum_{j=1,j\neq i}^{n}envy(i,j)$ an agent can guarantee for themselves is the same in both protocols.

3. 3.

   Pair-wise envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent if, for any two agents $i$ and $j$, if in one of the protocols agent $i$ can guarantee $envy(i,j)\leq M$, for some $M\in[0,1]$, then they can guarantee the same bound holds in the other protocol.

4. 4.

   Strong envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent if, for any agent $i$ and any set $S$ of agents not containing $i$, if in one of the protocols agent $i$ can guarantee simultaneous bounds $envy(i,j)\leq M_{j},\forall j\in S$, for some $M_{j}\in[0,1]$, then they can guarantee the same bounds hold in the other protocol. This is the notion of equivalence we will be using the most throughout the paper. Note this is still quite broad, since, in particular, any two envy-free protocols will be strongly envy-equivalent. A lot of our results involve protocols that appear “similar” in a stronger sense (for example, some of our conversion algorithms involve mimicking the actions in a given protocol in a different model), but this is difficult to formalise and since, in practice, most protocols aim to guarantee certain bounds on envy, our definition is good enough.

   Note also that strong envy equivalence implies pair-wise envy equivalence (taking $S=\{j\}$).

Consider the following alternative representation of cake-cutting protocols. As before, we represent the protocols as trees, but this time we divide the nodes into:

• •

  non-leaf nodes, which are further divided into:

  • –

    cut nodes: We have a partition of the cake into $m$ contiguous pieces, ordered from left to right. Agent $i$ subdivides a piece $j$ by making one cut. Trivial cuts (i.e. cutting at one of the ends of the piece) are allowed. For convenience, we consider that for a piece $[x,y]$, cutting at one of the ends, WLOG $x$, divides it into $[x,y]$ and a new piece $[x,x]$. Such “empty” pieces will have value $0$ to any agent, but they allow us to keep track of the number of pieces throughout the tree. Note $i$ and $j$ are both fixed, unlike in the previous section.

  • –

    choose nodes: Given a partition of the cake as above, agent $i$ is allowed to choose which child of the current node to proceed to, based on the position of the cuts.

• •

  leaf nodes: Given a partition of the cake, each piece in the partition is allocated to an agent. The allocation is represented as a mapping $\{1,...,m\}\rightarrow\{1,...,n\}$ where $n$ is the number of agents, and $m$ is the number of pieces in the partition. Note that for a given leaf, the number $m$ of pieces the cake has been divided into by the time we reach that leaf is one plus the number of cut nodes above the leaf, which does not depend on the execution history, so the mapping is well-defined.

We say a cut/choose node corresponding to an action of agent $i$ is controlled by agent $i$.

We will refer to the class of protocols that can be represented in the above form as branch choice (BC) protocols to reflect the fact that at choose nodes, an agent chooses which branch of the tree is executed.

Note we need to keep track of the execution history at every node (i.e. how the cake is partitioned before the action corresponding to the current node). We can either store this information at every node (requiring extra space), or recover it from the unique path between the current node and the root (no extra space). Both take linear time in the number of nodes to read, so we will use the latter option and store no extra information at the nodes.

In figure 1:

* - agent $2$ trims the largest piece according to them (as per the original protocol). In our representation of the protocol, they have to choose the largest piece to minimise their envy.

** - agent $3$ chooses which of the three “big” pieces $[0,y],[x_{0},x_{1}]$ and $[x_{1},1]$ they get.

*** - agent $2$ chooses which of the remaining two “big” pieces they get. In the two branches we have left out, where agent $1$ hasn’t chosen $[0,y]$, agent $2$ is assigned $[0,y]$ by default and does not get a choice here.

****, ***** - agents $3$ and $1$ choose which of the “trimmings” they are assigned.

It can be shown that all other conditions in the original protocol (e.g. agent $1$ cutting the piece into thirds at the beginning, agent $2$ trimming the largest piece to be the same size as the second largest, etc.) can be recovered by analysing where the agents need to cut to minimise their envy.

As a generalisation, we can instead consider the class of cake-cutting protocols that can be represented as directed acyclic graphs (DAGs) using the same types of nodes as BC protocols.

A DAG representing a cake-cutting protocol will have a designated root node that corresponds to the first action in the protocol. We will also assume that every node is reachable from the root, as nodes that are not reachable will not be relevant to the protocol. To ensure the DAG represents a valid protocol, we must also require that if there are multiple paths from the root to a node, all of them result in the same number of cuts, so that the number of pre-existing cuts at a given node is well-defined and we can describe actions like “agent $i$ cuts into the $j$-th piece”. This can provide a more compact representation for certain protocols, but we will see that it is no more “powerful” than the tree representation, that is, given a DAG representing some protocol, we can represent the same protocol as a tree.

We will now consider a modified definition of BC protocols, which allows an agent to choose which piece of cake to cut from a sequence of consecutive pieces, and allows for allocating a sequence of pieces to some agent at once by only specifying the endpoints of the sequence.

The advantage of this more flexible definition is that we can ignore some extraneous cuts in the execution of the protocol, as we will see, for example, in the proof of theorem 4. We will show that, in fact, this extended definition has the same expressive power as the original one.

• •

  Instead of having some agent $i$ cut into a single piece $[x,y]$ with no other cuts inside it, we allow for cut nodes that ask agent $i$ to make a cut between two existing cuts $x$ and $y$ (which might not be consecutive).

• •

  At leaves, instead of allocating each interval, we allow for allocating the piece of cake between two (potentially non-consecutive) cuts $x$ and $y$ to some agent, with the constraint that $x<y$ (so if the ordering of $x$ and $y$ cannot be determined solely from the structure of the protocol, and depends on the decisions of the agents, this is not a valid allocation). Note this is essentially the same as BC protocol allocation, except the allocation can be written more concisely, ignoring intermediate cuts if consecutive intervals are allocated to the same agent.

  Example.

  If agent $1$ makes a cut at $x\in[0,1]$ and agent $2$ then makes a cut at $y\in[0,1]$, we cannot have an allocation $[0,x]\mapsto 1$, $[x,y]\mapsto 2$, $[y,1]\mapsto 1$, because it might be the case that $y<x$. But if instead we restrict the second cut to $y\in[x,1]$, the allocation is valid. In both cases, $[0,x]\mapsto 1$, $[x,1]\mapsto 2$ is also a valid allocation.

We will refer to protocols covered by this definition as extended BC protocols. Note that indeed any protocol covered by the original definition of BC protocols is covered by the modified definition, with no changes needed.

In this section, we will prove that any BC protocol can be converted to a “nice” form in which all the cut nodes come before all the choose nodes, so, intuitively, the agents first cut up the cake, and then they make choices between branches leading to various allocations.

In this section, we will prove that GCC and BC protocols can express the same class of protocols, up to strong envy-equivalence.

Note this argument does not work for the reverse conversion (GCC to BC) given by theorem 7, because there we specifically make use of the more restrictive classes of protocols when converting, for example, GCC if-else nodes.

A cake-cutting protocol for $n$ agents is said to be proportional if each agent is guaranteed to receive a piece of cake with value at least $\frac{1}{n}$ according to their own valuation function. There are a number of well-known proportional cake-cutting protocols, such as the Dubins-Spanier protocol [8] and the Even-Paz protocol [9].

In this section, we look at how these can be represented as GCC and BC protocols.

The discrete Dubins-Spanier protocol works as follows: each agent $i$ makes a cut at a point $a_{i}$ such that $V_{i}([0,a_{i}])=\frac{1}{n}$. The agent who made the leftmost cut $a_{j}$ gets the piece $[0,a_{j}]$. That agent is then removed and we repeat the protocol on the remaining cake $[a_{j},1]$ with the other $n-1$ agents. The last agent gets the remaining piece of cake.

Brânzei, [3] describes how the Dubins-Spanier protocol can be implemented as a GCC protocol. Each agent is asked to make a cut in $[0,1]$ at some point $a_{i}$. The leftmost cut $a_{j}$ is then determined using an If-Else node with $n$ branches, then, in the $j$-th branch, agent $j$ “chooses” a piece from the singleton set $\{[0,a_{j}]\}$, and we repeat the procedure for the other $n-1$ agents on the remaining cake, ignoring the cuts made at previous steps. This protocol clearly respects the proportionality condition, so, in our language, it is value-equivalent to the original protocol. Any bounds on envy from the original protocol would also clearly carry over, so they are strongly envy-equivalent. Note that the size of the resulting GCC tree is $\Theta(n!)$, because there are $n$ branches on the first if-else node, then $n-1$ branches for each of those, etc. The runtime of the protocol is $\Theta(n^{2})$ if we just count the queries/nodes, as in the original protocol, and $\Theta(n^{3})$ if we also consider the comparisons inside each if-else node, since to find the leftmost cut we need to compare the position of each cut to the other $n-1$.

We can implement this as a BC protocol either by converting the GCC implementation using theorem 7, or as an extended BC protocol as follows: agent $1$ makes a cut in $[0,1]$ at $a_{1}$, agent $2$ chooses between two branches (one for cutting in $[0,a_{1}]$ and the other one for $[a_{1},1]$), the next agent chooses between two branches corresponding to cutting left or right of the current leftmost node. After this, we know who made the leftmost cut $a_{j}$ in a specific branch. At the end of the protocol agent $j$ will get allocated the piece $[0,a_{j}]$. We repeat the algorithm for the other $n-1$ agents on the remaining cake, ignoring the cuts made at previous steps. There are $2^{n-1}$ branches in the first step, then for each of those there are $2^{n-2}$ branches in the second step, etc. So the size of the tree is $2^{n-1}2^{n-2}...2^{1}=2^{\frac{n(n-1)}{2}}$, so the size of the protocol is $\Theta(2^{n^{2}})$.

The Even-Paz protocol for $n$ agents, is as follows:

• •

  Each agent makes a cut at $z_{i}\in[0,1]$ such that $V_{i}([0,z_{i}])=\frac{1}{2}$.

• •

  The algorithm finds the $\lfloor\frac{n}{2}\rfloor$-th cut, which divides the cake into two “halves”.

• •

  Each half is divided recursively amongst the agents whose cuts were inside that half (with the agent who made the $\lfloor\frac{n}{2}\rfloor$-th cut going into the first half).

The runtime is $\Theta(n\log(n))$.

We can implement the Even-Paz protocol as a GCC protocol as follows: each agent makes a cut at $z_{i}\in[0,1]$, then in an if-else node with $n$ branches, we identify the $\lfloor\frac{n}{2}\rfloor$-th cut. We repeat the procedure for each half for the $n/2$ agents who cut into that half. There are $n$ branches in the first step, then in each of those we have $n/2$ branches for dividing the first half, each of which then splits into $n/2$ branches for dividing the second half, etc. Assuming $n=2^{k}$ for simplicity, the size of the tree is $n(\frac{n}{2})^{2}(\frac{n}{4})^{2}...=2^{k}2^{2(k-1)}2^{2(k-2)}...2^{2}=2^{k+2\frac{k(k-1)}{2}}=2^{k^{2}}$, so $\Theta(2^{k^{2}})=\Theta(n^{\log(n)})$, and the resulting protocol is value-equivalent (so, in particular, proportional) and strongly envy-equivalent to the original one.

For the extended BC protocol implementation, agent $1$ makes a cut at $a_{1}$ in $[0,1]$, agent $2$ chooses between two branches (for cutting in $[0,a_{1}]$ or $[a_{1},1]$ respectively), agent $3$ chooses between three branches (corresponding to cutting into each of the three existing pieces), etc. After this, we know the ordering of the cuts in a specific branch, so, in particular, the $\lfloor\frac{n}{2}\rfloor$-th cut. We recurse on the two halves of the cake. Assuming $n=2^{k}$, we get $n!$ branches in the first step, $((\frac{n}{2})!)^{2}=\Theta(n!)$ branches in the second step, etc, so the size of the tree is $n!((\frac{n}{2})!)^{2}((\frac{n}{4})!)^{2}...$

In this paper, we defined a new model for representing cake-cutting protocols as trees, called branch choice (BC) protocols, which differs from other models in that instead of choosing specific pieces of cake, the agents get to choose which branch of the tree to proceed to at a certain point, and then the cake is allocated at the end. We showed that various modifications to the model do not impact its expressive power. We also proved that any BC protocol can be converted to an equivalent protocol in which the cut nodes come before the choose nodes, so that, informally, the agents can first cut up the cake, and then choose between various branches that lead to different allocations.

The main benefit of BC protocols is that they form a rather bare-bones model, so that, for example, if the protocol reaches a given node, we can deduce the execution history of the protocol (the relative order of the cuts, as well as which branches the agents chose) just based on the path from the root to that node, with no ambiguity about what decisions the agents might have made at previous nodes. This makes it easier to reason about the protocols, particularly after putting them into the special “cuts before choices” form mentioned above, since in that case we also know a lot about the structure of the tree.

This comes at no cost to the expressive power of the model, since the class of protocols it covers is the same as generalised cut and choose protocols as described by Brânzei et al. , [5], up to strong envy equivalence (which we defined to mean that in both protocols, an agent can guarantee the same simultaneous bounds on their envy against any subset of the other agents).

However, as we have seen both in some of our conversion algorithms and in the case of representing some classic protocols as BC protocols, the simplicity of the model comes with a trade-off in space complexity, and in some cases the conversion seems to result in $\Theta(n!)$ or even worse blowups in the size of the tree representation compared to the original protocol.