A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

Introduction

“Despite intense efforts over decades, up to this date no one has succeeded in finding a finite bounded cake cutting protocol that guarantees envy-freeness for any number of players.”— Lindner and Rothe .

The existence of a discrete and bounded envy-free cake cutting protocol has remained a major open problem for at least two decades. In this paper, we settle the problem by presenting a general discrete envy-free protocol for any number of agents. The protocol is for the cake cutting setting that is a versatile mathematical model for allocation of a heterogeneous divisible good among multiple agents with possibly different preferences over different parts of the cake. The main applications of cake cutting are fair scheduling, resource allocation, and conflict resolution . Cake cutting has been extensively studied within computer science and the social sciences . Since various important divisible resources such as time and land can be captured by cake cutting, the problem of fairly dividing the cake is a fundamental one within the area of fair division and multiagent resource allocation .

A cake is represented by an interval $$and each of the$n$agents has a valuation function over pieces of the cake that specifies how much that agent values a particular subinterval. The main goal is to divide the cake fairly. Among various fairness concepts proposed by social scientists, a prominent one is envy-freeness. An allocation is envy-free if no agent would prefer to take another agent’s allocation instead of his own. Although an envy-free allocation is guaranteed to exist even with$n-1$ cuts Su pointed out that the existence of an envy-free cake allocation can be shown via an interesting connection with Sperner’s Lemma., finding an envy-free allocation is a challenging problem which has been termed “one of the most important open problems in 20th century mathematics” by Garfunkel .

Since the valuations of agents over the cake can be complex, eliciting each agent’s complete valuations function over the cake is computationally infeasible. A natural approach in cake cutting protocols is to query agents about their valuations of different portions of the cake and based on these queries propose an allocation. A cake cutting protocol is envy-free if each agent is guaranteed to be non-envious if he reports his real valuations. If a protocol is envy-free, then an honest agent will not be envious even if other agents misreport their valuations. For the case of two agents, the problem has a well known solution in the form of the Divide and Choose protocol: one agent is asked to cut the cake into equally preferred pieces and the other agent is asked to choose the preferred piece. For the case of three agents, an elegant and bounded protocol was independently discovered by John L. Selfridge and John H. Conway around 1960 . Since then, an efficient general envy-free protocol for any number of agents has eluded mathematicians, economists, and computer scientists.

In 1995, Brams and Taylor made a breakthrough by presenting an envy-free protocol for any number of agents . Although the protocol is guaranteed to terminate in finite time, there is one drawback of the protocol: the running time or number of queries and even the number of cuts required is unbounded even for four agents. In other words, the number of queries required to identify an envy-free allocation can be arbitrarily large for certain valuations functions. Procaccia terms unboundedness as a “serious flaw”. Brams and Taylor were cognizant of their protocol’s drawback and explicitly mentioned the problem of proposing a bounded envy-free protocol even for $n=4$. Lindner and Rothe write that “the development of finite bounded envy-free cake cutting protocols still appears to be out of reach, and a big challenge for future research.” The problem has remained open and has been highlighted in several works . Saberi and Wang term the problem as “one of the most important open problems in the field”. Procaccia goes one step further and calls it an interesting challenge within theoretical computer science: “Since the 1940s, the computation of envy-free cake divisions has baffled many great minds across multiple disciplines. Settling this problem once and for all is an important challenge for theoretical computer science.” In recent work, Aziz and Mackenzie proposed a bounded and discrete envy-free protocol for $n=4$. Despite this progress, the general problem for any number of agents had remained unaddressed.

In this paper, we present a discrete envy-free protocol for any number of agents that requires a bounded number of queries and hence a bounded numbers of cuts of the cake thereby closing the central open problem in the field of cake cutting. The bound for the number of queries is $n^{n^{n^{n^{n^{n}}}}}$. Previously, no discrete protocol was known that even uses a bounded number of cuts. Apart from using some classic ideas in cake-cutting, our protocol requires some radically different techniques. Since only three general finite and discrete cake cutting protocols have been presented in the literature , our protocol is another addition to the list of finite envy-free protocols and is of interest even if boundedness is not a critical property. More generally, the protocol provides a new constructive argument for existence of envy-free allocations. Our result is surprising because leading experts in the area have conjectured that a bounded and discrete envy-free protocol does not exist: “It is natural to ask whether the envy-free cake cutting problem is inherently difficult: Is it provably impossible to design a bounded envy-free cake cutting algorithm?”. Previously, mathematician Ian Stewart had commented that “However, no discrete procedure with a bounded number cuts (however large) is known for four players, and such schemes probably don’t exist”.

We additionally show that even if we do not run our protocol to completion, it can find in at most $n^{3}{(n^{2})}^{n}$ queries a partial allocation of the cake that achieves proportionality (with respect to the whole cake) and envy-freeness. Finally, we show that even if we do not run our protocol to completion, it can be tweaked to find in at most $n^{3}{(n^{2})}^{n}$ queries an envy-free partial allocation of the cake in which each agent gets a connected piece that gives the agent $\nicefrac{{1}}{{3n}}$ of the value of the whole cake. For the additional two results, we only need one of our subprotocols called the SubCore Protocol that we define later.

Apart from introducing new techniques, our protocol relies on some ideas from previous protocols. At the heart of our protocol is the idea of domination or ‘irrevocable advantage’ . An agent $i$ dominates another agent $j$ if he is not envious of $j$ even if the unallocated cake is given to $j$. Note that if agents in subset $S\subset N$ dominate all the agents in $N\setminus S$, then agents in $S$ can simply let the agents in $N\setminus S$ worry about the remaining cake since they will not be envious if a single agent in $N\setminus S$ got all the remaining unallocated cake. Our protocol uses some high level ideas from our previous protocol for 4 agents: (i) We use a ‘Core Protocol’ over the unallocated cake (aka residue) with one agent as the specified cutter that results in an envy-free partial allocation and a smaller residue. The Core Protocol is called repeatedly on the latest residue so as to make the residue even smaller. As the new calls to the Core Protocol are made, the partial allocation remains envy-free. (ii) Every time agents make trims or evaluate pieces of cake, we do not lose such information and in fact keep track of it. (iii) We make agents exchange some parts of their already allocated pieces to obtain new dominations. The exchange was referred to as a permutation in . In some steps, our protocol also uses a simple fact: envy-freeness implies proportionality with respect to the allocated cake (i.e., each agent gets at least $\nicefrac{{1}}{{n}}$ value of the allocated cake).

Throughout the overall protocol, we have cake that has been allocated and some cake that is the unallocated residue. During the protocol, we ensure that the cake that has been allocated to the agents has been done so in an envy-free manner. Overall, our envy-free protocol (Main Protocol) takes as input the cake and a set of agents and returns an envy-free allocation of the whole cake. In order to obtain the envy-free allocation, the Main Protocol calls three other protocols. It repeatedly calls the Core Protocol a bounded number of times. The Core Protocol is the work-horse of the overall protocol that is called repeatedly to further allocate unallocated cake in any envy-free manner. The other protocols—GoLeft and Discrepancy are used to make one set of agents dominate the others so that the problem reduces to finding an envy-free allocation for fewer agents and the Main Protocol can be called again for this sub-problem.

After calling the Core Protocol many times, if there is still some unallocated cake and there is sufficient difference in the estimation of the value of a cake piece between some agents, then the Discrepancy Protocol is called by the Main Protocol. The goal of the Discrepancy Protocol is to either exploit the difference in valuations or else to ensure that on a very rough scale, agents have similar valuations. If after calling the Discrepancy Protocol, the cake still has not been allocated in an envy-free way, the GoLeft Protocol is called by the Main Protocol. The GoLeft Protocol is used to reallocate pieces of the cake among the agents after additionally adding some crumbs from the residue. The reallocation is useful to obtain new dominations until one set of agents dominate the remaining agents which means that we have reduced the problem to allocating the remainder of the cake among the dominated agents. The different protocols that we present are summarized in Figure 1.

Next, we informally summarize what input each protocol takes as a blackbox and then what it outputs.

Output: An envy-free allocation that completely allocates $R$ among agents in $N$.

Input: Specified cutter agent, agent set $N$ and unallocated cake $R$.

Output: An envy-free allocation of cake $R^{\prime}\subset R$ for agents in $N$ and updated unallocated cake $R\setminus R^{\prime}$.

Input: Cake $R$ cut into $n$ pieces to be allocated among agents in set $N^{\prime}\subset N$ with $n^{\prime}=|N^{\prime}|$. Additionally, each agent $i\in N^{\prime}$ has a benchmark value $b_{i}$.

Output: An envy-free partial allocation of $R$ for agents in $N^{\prime}$ in which each agent $j\in N^{\prime}$ gets a piece of value at least $b_{j}$.

Input: Residue $R$, a specific piece in $R$, a specific value given by agent $u$, a set of pieces of cake other than $R$, and a set of agents $N$.

Output: Possibly modified residue $R$, a Boolean value called DISCREPANCY, and a partition of $N$ into sets $D^{\prime}$ and $D^{\prime\prime}$.

Input: A set $N$, a set of ‘snapshots’ (disjoint envy-free allocation for the agents), a set of corresponding ‘extracted pieces’ for each piece in the disjoint allocations, and residue $R$.

Output: A set of agents $A\subset N$ such that all agents in $N\setminus A$ dominate all agents in $A$.

Despite some high level similarities with the approach of the recent protocol for four agents , our general protocol requires a number of new concepts and techniques. These concepts and techniques will be formalized and explained in the later sections but we mention them briefly and informally.

We define the notion of a significant advantage or bonus that informally means that an agent $i$ feels his absolute advantage over another agent is of a high enough fraction of his value of the unallocated cake. We then make use of our Core Protocol that not only reduces the size of the unallocated residue but also guarantees that a given agent has a significant advantage over someone else. The Core Protocol can be used to further allocate the residue so that an agent’s significant advantage over another agent translates into dominance in a bounded number steps. This approach is one of the key ideas for obtaining a bounded protocol rather than simply a finite protocol.

We rely on a notion of discrepancy that is based on the idea of how differently agents view a piece of cake. It is well known in fair division that the more different the agents’ valuations are, the easier it is to achieve fairness. We try to use the structure of agents that have similar valuations at a very coarse level. In case they have high enough discrepancy in valuations over two parts of the unallocated cake, then we simply break the problem into two subproblems where we divide each part in any envy-free manner among those agents who value it highly compared to the other part.

Another key idea to achieve a bounded protocol is that we run the Core Protocol enough times to ensure there are a sufficient number of Core Protocol allocation snapshots (allocation outcomes of various calls of the Core Protocol) that are isomorphic.The notion of isomorphic snapshots will be defined later. We will keep track of these snapshots to later make more agents dominate each other.

Further operations such as exchanges of allocated pieces are then implemented on such isomorphic Core snapshots by exploiting their structure. In order to achieve boundedness of the protocol, we also define and work with four carefully chosen bounds that are functions of the number of agents. The biggest of the four bounds is the maximal number of query operations required to complete the protocol.

We use a new technique called extraction whereby part of the residue is systematically trimmed off so that it can potentially be combined with some agent’s allocation in the Core Protocol. When a particular extracted piece of cake is given to an agent in addition to his allocated piece in a single snapshot of the Core Protocol, we refer to this as attachment. Attachment is helpful to systematically enable more agents to exchange each others’ pieces in snapshots of the Core Protocol without causing any agent to be envious. The exchange of pieces consequently allows for ‘permutations’ and helps achieve agents dominate each other.

In order to methodically track the possible permutations/exchanges, we keep track of a permutation graph in which nodes correspond to agents and an agent $i$ points to agent $j$ if $i$ is willing to replace his allocation in a subset of isomorphic snapshots of the Core Protocol with $j$’s allocated piece plus a tiny bit more cake without causing envy. The tiny bit more cake to attract agent $i$ can in principle cause agents to be envious so we have to compensate the other agents elsewhere so that envy is not introduced. The attachments and exchanges take place in the GoLeft Protocol. The interplay between the permutation graph and the working set of isomorphic Core snapshots is technically one of the most interesting parts of the overall protocol and is the central part of the GoLeft Protocol.

Cake cutting problems originated in the 1940’s when famous mathematicians such as Banach, Knaster, and Steinhaus initiated serious mathematical work on the topic of fair division.Hugo Steinhaus presented the cake cutting problems to the mathematical and social science communities on Sep. 17, 1947, at a meeting of the Econometric Society in Washington, D.C. . Since then, the theory of cake cutting algorithms has become a full-fledged field with at least three books written on the topic . The central problem within cake cutting is finding an envy-free allocation .

Since the earliest works, mathematicians have been interested in the complexity of cake cutting. Steinhaus wrote that “Interesting mathematical problems arise if we are to determine the minimal number of cuts necessary for fair division.” When formulating efficient cake cutting protocols, a typical goal is to minimize the number of cuts while ignoring the number of valuations queried from the agents. In principle, the actual complexity of a problem or a protocol depends on the number of queries. When considering how efficient a protocol is, it is useful to have a formal query model for cake cutting protocols. Robertson and Webb formalized a simple query model in which there are two kinds of queries: Evaluation and Cut. In an Evaluation query, an agent is asked how much he values a subinterval. In a Cut query, an agent is asked to identify an interval, with a fixed left endpoint, of a particular value. Although, the query model of Robertson and Webb is very simple, it is general enough to capture all known protocols in the literature. Note that if the number of queries is bounded, it implies that the number of cuts is bounded in the Robertson and Webb model. The protocol that we present in this paper uses a bounded number of queries in the Robertson and Webb model.

There are various notions of fairness in the cake-cutting literature. Two of the most prominent ones are envy-freeness and proportionality. Proportionality requires that each agent gets at least $\nicefrac{{1}}{{n}}$ value of the whole cake. An envy-free allocation of the whole cake also satisfies proportionality. Finding a proportional allocation is an easier task than finding an envy-free allocation. There exists a general discrete protocol for finding a proportional allocation with connected pieces that takes $O(n\log n)$ queries .

There is not too much known about the existence of a bounded envy-free protocol for general $n$ except that any envy-free cake cutting algorithm requires $\Omega(n^{2})$ queries in the Robertson-Webb model . Also, for $n\geq 3$, there exists no finite envy-free cake cutting algorithm that outputs contiguous allocations in which each agent gets a connected piece with no gaps . Brams et al. and Barbanel and Brams presented envy-free protocols for four agents that require 13 and 5 cuts respectively. However, the protocols are not only unbounded but also not finite since they are continuous protocols that require the notion of a moving knife. An alternative approach is to consider known bounded protocols and see how well they perform in terms of envy-freeness . Apart from the unbounded Brams and Taylor envy-free protocol for $n$ agents, there are other general envy-free protocols by Robertson and Webb and Pikhurko that are also unbounded. Gasarch compared the complexity of the three general unbounded envy-free protocols in the literature. Aziz and Mackenzie proposed a bounded and discrete envy-free protocol for $n=4$. We use similar ideas but generalizing to the case of any number of agents requires novel subroutines and significantly more abstract arguments.

There are positive algorithmic results concerning envy-free cake cutting when agents have restricted valuations functions or when some part of the cake is left unallocated . There has also been work on strategyproof cake cutting protocols for restricted valuation functions as well as strategic aspects of protocols .

Preliminaries

We consider a cake which is represented by the interval $$. A piece of cake is a finite union of disjoint subintervals of$$. We will assume the standard assumptions in cake cutting. Each agent in the set of agents $N=\{1,\ldots,n\}$ has his own valuation over subintervals of the interval $$. We denote by$V_{i}(x,y)$the value agent$i$has for interval$[x,y]$. The valuations are (i) non-negative:$V_{i}(Y)\geq 0$for any subinterval$Y$; (ii) additive: for all disjoint subintervals$Y,Y^{\prime}$,$V_{i}(Y\cup Y^{\prime})=V_{i}(Y)+V_{i}(Y^{\prime})$; and (iii) divisible, i.e., for every subinterval$Y$and$0\leq\lambda\leq 1$, there exists$Y^{\prime}\subseteq Y$with$V_{i}(Y^{\prime})=\lambda{V_{i}(Y)}$. It follows from the divisibility property that the valuations are non-atomic i.e.,$V_{i}(x,x)=0$.

We will typically denote an allocation by $X=(X_{1},\ldots,X_{n})$ where $X_{i}$ is the cake allocated to agent $i$. Two main criteria of fairness are envy-freeness and proportionality.

An allocation $X=(X_{1},\ldots,X_{n})$ is envy-free if $V_{i}(X_{i})\geq V_{i}(X_{j})$ for each $i,j\in N$.

An allocation $X=(X_{1},\ldots,X_{n})$ is proportional if $V_{i}(X_{i})\geq\frac{1}{n}V_{i}()$ for each $i\in N$.

We now define some terms and conventions that we will use in the paper. An allocation is partial if it does not necessarily allocate the whole cake. Given an envy-free partial allocation $X$ of the cake and an unallocated residue $R$, we say that agent $i$ dominates agent $j$ if $i$ does not become envious of $j$ even if all of $R$ were to be allocated to $j$:

We say that an agent gets a piece partially, if he does not necessarily get it completely. In the cake cutting protocols that we will describe, an agent may be asked to trim a piece of cake so that its value equals the value of a less valuable piece. Agents will be asked to trim various pieces of the cake to make a given piece equal to the value of another piece. In Figure 2, we outline the idea of trimming a piece to equal the value of another piece. When an agent trims a piece of cake, he will trim it from the left side: the main piece (albeit trimmed) will be on the right side. The piece minus the trim will be called the partial main piece. When we say that an agent is guaranteed to get his second/third/etc. most favoured piece, this guarantee is based on the ordinal preferences of the agents over the pieces. By ordinal, we mean that agents simply give a weak ordering over the pieces but do not tell the exact cardinal utility difference between two pieces. If an agent is indifferent between the top three pieces, then we will still say that the agent is guaranteed to get his third most valued piece.

The Protocol

The overall protocol we present is essentially the Main Protocol that calls other protocols. Some protocols such as the SubCore Protocol and the Main Protocol recursively call themselves. The overall idea of the protocol is as follows. We make an agent (the cutter) divide the cake into $n$ equally preferred pieces. The cake is then allocated to the agents with each agent getting a part of one of the pieces. The subroutine will be referred to as the Core Protocol. The Core Protocol itself relies on recursively applying the SubCore Protocol. When running the Core Protocol, if all the cake is already allocated, we are done. Otherwise, the Core Protocol is run repeatedly on the left-over cake. If some cake is still unallocated, we repeat it with another agent as cutter. After the Core Protocol has been run repeatedly, it is checked whether agents have discrepancy on a part of the cake. Discrepancy implies that agents have radically different valuations over two segments of the cake. This works to our advantage because we can run the Discrepancy Protocol in which we let the differing agents concentrate on the segments they prefer much more which reduces our problem to envy-free cake cutting for a smaller number of agents. Otherwise, we exchange some parts of the cake that certain agents hold using the GoLeft Protocol in a systematic way to obtain further dominations between agents. After the GoLeft Protocol has been implemented, some agents dominate all other agents. At this point, we have decomposed the problem into a smaller problem with less number of agents. Hence the envy-free algorithm can be called recursively on the unallocated cake to divide the cake among the specified subset of agents. We first present the Core Protocol that is the work-horse of the overall Main Protocol.

We first present the Core Protocol that calls the SubCore Protocol. The Core Protocol is helpful in allocating additional residue in an envy-free manner. The main challenge is that just by running the Core Protocol repeatedly on the residue, there is no guarantee that the cake will be allocated completely in a bounded or even finite number of steps. Hence, we will introduce other protocols in addition to the Core protocol that help us allocate the whole cake in an envy-free manner.

The Core Protocol asks a specified agent termed as the cutter to cut the unallocated cake into $n$ equally preferred pieces. It then calls the SubCore Protocol that allocates to each of the agents one of the pieces (possibly partially) in an envy-free manner. No agent is given cake from any other piece.

The name of the protocol is the same as the Core Protocol used by Aziz and Mackenzie for the case of 4 agents which returns an envy-free partial allocation in which one agent cuts the cake into four equally preferred pieces and the cutter as well as at least one other agent gets one of these four pieces. The new Core Protocol can be considered as a useful generalization of Core Protocol for the four-agent algorithm of Aziz and Mackenzie . Unlike the Core Protocol for the four-agent case, the new Core Protocol requires a more sophisticated recursive SubCore Protocol. The SubCore Protocol results in an allocation that satisfies some ‘neat’ properties.

Consider a cake divided into $n$ pieces and $m<n$ agents. An allocation of the cake into $m$ agents is neat if (i) each agent’s allocation is a (not necessarily whole) part of one of the pieces; (ii) at least one piece is unallocated; (iii) no agent prefers an unallocated piece over his allocation; and (iv) no agent prefers another agent’s allocation over his allocation.

We can prove that the Core Protocol results in an envy-free partial allocation in which the cutter cuts the cake into $n$ pieces, each agent gets a part of exactly one of the pieces, at least one non-cutter agent gets a complete piece and at least one piece is unallocated which no non-cutter agent envies over his allocation (Lemma 4.13). Since two agents get full pieces, from the cutter’s perspective, at least $2/n$ of the cake is allocated after an iteration of the Core Protocol.

Most of the technical work in the Core Protocol is done when it calls the SubCore Protocol. The SubCore Protocol takes as input agents and pieces of cake where the number of pieces is at least as much as the number of agents. Each agent is given a part of exactly one piece. The SubCore Protocol also takes as input the benchmark value for each agent. When we call SubCore for the first time during the Core Protocol, the benchmark value of each agent is zero. The benchmark value of an agent indicates the minimum value an agent expects in an envy-free allocation returned by the SubCore Protocol.

In the SubCore Protocol, the main idea is that we start from a single agent and gradually grow the number of agents in a specified order while making sure that a neat allocation exists for the growing set of agents $\{1,\ldots,m\}$ in which at least one agent gets a full piece. We denote $\{1,\ldots,m\}$ by $[m]$. All the allocations encountered during the course of the SubCore Protocol are considered tentative until the final step. If the next agent $m$ in the specified order most prefers a piece that is not currently (tentatively) allocated, we can easily handle the new agent as he can get the unallocated piece without causing envy for anyone. Otherwise, we have to do more work to ensure that the previously handled agents as well as the new agent can simultaneously get a neat allocation in which at least one agent gets a full piece. This includes calling the SubCore Protocol recursively for a smaller number of agents.

In the SubCore Protocol, if the $m$-th agent is also interested in one of the $m-1$ tentatively assigned pieces, we refer to the $m-1$ allocated pieces as the contested pieces. Each agent in $[m]$ is asked to trim pieces among the $m-1$ contested pieces that are of higher value than his most preferred piece outside the $m-1$ allocated pieces so that the value of the former is the same as the value of the latter. The value is referred to as the benchmark value of the agent. The rationale for asking all the $m$ agents to trim up to their benchmark value is as follows. If $m-1$ agents each get a part of a contested piece, then one of the $m$ agents who does not get a contested piece can get a most preferred uncontested piece. By asking all agents to place trims according to their benchmark values, the agent $j$ who is forced to get an uncontested piece will not be envious of other agents because each other agent gets a piece to the right of $j$’s trim on that piece. Note that in order to set the benchmark value of an agent we not only consider the uncontested pieces in that call of the SubCore but also implicitly consider other pieces that were part of the input of the root call to the SubCore. This ensures that agents are not envious or interested in pieces that are unallocated. The set of agents who have the rightmost trim in some piece is referred to as $W$. Note that $W$ is the set of agents who are guaranteed to have an envy-free allocation where each agent gets a piece that he trimmed most. If $|W|=m-1$, then if agents are given the piece they win up till their trim, then the corresponding allocation is envy-free for agents in $W$ and gives each agent in $W$ their benchmark value. Nonetheless, we call SubCore recursively on $W$ and the contested pieces with the left aside of trim the agent in $[m]\setminus W$ ignored. Doing this ensures that agents in $W$ get as much of the contested pieces as possible without causing envy. The remaining agent in $[m]\setminus W$ is considered to be ‘kicked out’ of the contested pieces and has to make do with a piece outside the contested pieces. He is given the most preferred uncontested piece.

We may not be lucky and the number of agents who win some piece may not be $m-1$, i.e., some agent may have the rightmost trim in multiple contested pieces. The protocol then increases the size of $W$ one by one. $W$ is expanded as follows. The previous trims of agents in $W$ are ignored. The SubCore Protocol is called recursively with $W$ as the target set of agents and for each piece, the left side of the right-most trim by an agent in $[m]\setminus W$ is ignored. Note that by ignoring the trims of agents in $W$, we have more cake that could potentially be allocated than the allocation where the trims of agents in $W$ are not ignored but each agent in $W$ gets the right hand side of the piece where he had the rightmost trim. In case $|W|<m-1$, we can continue increasing the size of $W$ while ensuring that agents in $W$ can get an envy-free allocation by getting a partial piece each from among the contested pieces. Take any unallocated contested piece $a$ for which the current left margin (beyond which the piece is ignored) is by agent $i\in[m]\setminus W$. We can add such an $i$ to $W$. As we increase the size of $W$, we are able to clear more space for some piece since the non-winner because of which we were ignoring the left part of some piece is now a winner, so we an ignore his previous trim. When $|W|=m-1$, we have ensured that all the contested pieces have been partially allocated to one agent each from $W$. In that case the remaining agent in $[m]\setminus W$ can then be given the most preferred uncontested piece.

Note that for $n=2$, the Core Protocol coincides with the well-known Divide and Choose protocol. Next, we further explain the SubCore Protocol with the help of an example.

In order to illustrate how the SubCore Protocol works, let us explain the SubCore Protocol when $n^{\prime}=3$ and there are $n=4$ pieces $a,b,c,d$.

In the for loop, when $m=2$, if agent $2$ has the same most preferred piece as agent $1$’s tentative piece $a$, then piece $a$ is the contested piece. Both agents place trim on that piece to equal the value of the second most preferred piece. Let us assume that 2’s trim is to the right of 1’s trim. In that case the cake in $a$ to the left of $1$’s trim is ignored temporarily as if the cake to the left did not exist. Agent $1$ can take a full unallocated piece $b$ that is at least as preferred by him as $2$’s tentative piece. Agent 1 is considered being kicked out of his piece and gets a piece of exactly his benchmark value. Since there is exactly one contested piece and the piece is ‘won’ by agent $2$, we call SubCore on piece $a$ and agent $2$ with the cake to the left of $a$’s trim ignored. Hence agent $2$ gets $a$ up till $1$’s trim.

We now increment $m$ to handle agent $3$. If agent $3$’s most preferred piece among the four pieces is not one currently held (even partially) by 1 and 2, then we can simply give 3 that piece. Otherwise, all agents $1,2,3$ are asked to place a trim over the contested pieces among $\{a,b\}$ to make the value equal to the most preferred piece among $c$ and $d$. Let us assume that $3$ places the rightmost trim over $b$ and over $a$. In that case, $W=\{3\}$. The fact that $3$ is in $W$ means that there exists a neat allocation for the agent in $W=\{3\}$ where he can get one of the pieces which are contested. We now ignore the trims of agent $3$ on pieces $a$ and $b$ and ignore the left side of the rightmost trim by agents in $\{1,2\}$. We call SubCore Protocol on the pieces $a,b$ with the left side of $1$ and $2$’s trims ignored and with agent $W=\{3\}$ as input. It returns a neat allocation (with respect to the current left margins on pieces beyond which they are ignored) for agent $3$ where $3$ will be assigned one of the pieces $a$ or $b$ up to the non-winner (not in $W$) agent’s rightmost trim. Let us say $3$ gets piece $a$. Since the allocation is neat (with respect to the current left margins), $3$ does not envy any of the other pieces up to the non-winner’s trims, meaning a new agent can be allocated a contested piece. Let us say this agent is agent $1$, and that $1$ is now the rightmost trimmer of piece $b$ and his trim coincided with the current left margin of $b$ beyond which $b$ is ignored. $1$ is added to $W$ and $1$ is allocated $b$ up till the current left margin. Since now $|W|=m-1$, we can make one last recursive call for agents $1$ and $3$ with the left part of the trims by agent 2 is ignored. This allocates piece $a$ to $3$ and piece $b$ to $1$. The uncontested pieces $c$ and $d$ are untrimmed. Agent $2$ can be seen as having been ‘kicked out’ of the contest, and therefore is left with his most preferred uncontested ‘benchmark’ piece, let us say $c$. Piece $d$ has remained unallocated and untrimmed. At this point the allocation of the SubCore Protocol is returned.

To avoid having to mention the special case of ties in each argument concerning the Core/SubCore protocol, we will deal with them in a modular way.

To this end we introduce what we will call imaginary values. Each agent has a list of such values. Each agent’s values are on a different scale (for example agent $2$’s values are much smaller than agent $1$’s). Our aim is to define those values so that no agent is indifferent between $2$ pieces, and so that agents never place trims on the exact same location (where locations with different imaginary values are distinct). We do so whilst ensuring that when agents equalise pieces of cake, they still prefer the pieces that were trimmed to the one they used as a benchmark to equalise.

To do so generate for each agent $j$ $E=n^{3}{(n^{2})}^{n}$ values $\epsilon^{j}_{1},\epsilon^{j}_{2}\ldots\epsilon^{j}_{E}$ with the properties that $\epsilon^{j}_{i}<<E\times\epsilon^{j}_{i+1}$ and $\epsilon^{j}_{E}<<E\times\epsilon^{j+1}_{1}$. Let $L_{j}$ be $j$’s list of these epsilon values ordered from largest to smallest.

The protocol now internally represents each piece of cake as a number with a physical part and imaginary part. All the cuts that are actually made on the cake are in reality only dependent on the physical part of the value. The imaginary part is used internally by the protocol to break ties in a consistent way. Agents only look at the imaginary value of a piece of cake when required to break a tie on the physical part. Agents do not disagree on the imaginary value of a piece. This means that if we query agent $l$ and $j$ on a piece, they might disagree on the physical value of the piece, but will agree on the imaginary value.

Let us now explain how those imaginary values are associated with the pieces generated by the protocol. When the Core protocol asks the cutter to cut $n$ equal pieces, the cutter will add the $\epsilon$ from the top of his list $L$ every-time he creates a new piece and then discard that $\epsilon$ from $L$. Every other agent also adds $\epsilon$ values to the pieces. In the SubCore protocol, agents generate new pieces of cake when placing trims on larger pieces to make them equal to a smaller piece. When an agent is asked to make larger pieces equal to a smaller piece $b$, he will add the epsilon value at the top of his list $L$ to the piece he least preferred before the trim (excluding $b$), then discard that value from $L$. He then proceeds to add the second value to the second least preferred piece, and so on until he reaches the most preferred piece that he trimmed. This ensures that while the physical value of the pieces becomes the same from the agent’s perspective, the actual order of the pieces remains unchanged.

Agents have a strict order on the pieces that were generated by the cutter. The order between two pieces $a>_{i}b$ can only change if $i$’s valuation of the physical part of $a$ becomes strictly less than his valuation of the physical part of $b$.

New pieces are generated in the SubCore protocol when an agent $j$ is asked to equalise pieces $c_{1}\ldots c_{l}$ to a piece $c_{z}$. The pieces will now have equal physical value from the perspective of agent $j$ but since the former larger pieces are allocated bigger imaginary values, the order is preserved.

When taking into account both the physical and imaginary part of the valuation of pieces an agent cannot have the same value for $2$ pieces. Moreover, $2$ agents cannot place a trim on the same point (they may place on the same physical point but the imaginary value breaks the tie). In other words, with imaginary values taken into account, ties do not happen in the protocol.

Each $\epsilon$ value is unique and cannot be obtained by recombining the others through addition and subtraction, which are the only operations available to the protocol.

Imagine that agent $j$ is asked to equalise piece $a$ to equal $b$. Let us have $v_{j}(a)=0.2$ and $v_{j}(a)=0.1+0.001i$ where $i$ just represents the fact that it is an imaginary value. $j$ will trim $a$ so that it is equal to $0.1+0.001i$, then add the next $\epsilon$ value $\epsilon_{l}$ on top of its list to piece $a$ so that $v_{j}(a)=0.1+(0.001+\epsilon_{l})i$.

When we run the Core Protocol we end up with an envy-free partial allocation of the cake and a residue. We call the partial allocation a snapshot or a core snapshot.

The algorithm will keep track of certain snapshots which we will label $p_{j}$ with $j\in\{1,\ldots,C^{\prime}\}$. The pieces allocated in each snapshot $p_{j}$ are labelled $c_{jk}$ where $k\in\{1,\ldots,n\}$ indicates which agent got the piece. Since the allocation in each snapshot is envy-free, each agent thinks he got at least as much value for his piece as any other allocated piece. Therefore each agent thinks he has some (possible zero or more) bonus value over another agent in the Core snapshot. Our protocol will make use of these bonuses. In our protocol, we repeatedly call the Core Protocol over the resultant residue thereby making the residue smaller until the set of snapshots have enough structure that we will exploit later.

2 Groundwork for the Main Protocol

We will use four parameters to represent the bounds we work with. These are

These are constant once $n$ is fixed, however they are dependent on $n$. Since the Main Protocol calls itself on a strict subset of the agents, we will use the notation $B^{\prime}_{n-1}$ to label the bound on the Main Protocol run on $n-1$ agents. The bounds correspond to the following concepts.

$C^{\prime}$ is the number of snapshots generated by the main algorithm that we label and keep track of. All subsequent partial allocations generated by runs of the Core Protocol simply serve the purpose of making the residue smaller from the cutter’s perspective. Once the main algorithm has extracted all the pieces it needs from the residue and if a discrepancy has not been successfully exploited, the GoLeft Protocol will be run.

When we run GoLeft we look at a subset of $C$ isomorphic snapshots from the $C^{\prime}$ total snapshots.

The value $B^{\prime}$ corresponds to the total number of queries required to run the whole protocol.

$B$ is used to define what we call significant pieces or values. Running the Core Protocol guarantees that a piece of cake is made smaller from the perspective of the cutter. The value $B$ is a bound on the number of times the algorithm allows us to run the Core Protocol to make the residue smaller.

For the sake of achieving our boundedness results, the following values of the parameters work. (i) $C=n^{n^{n}}$ (ii) $C^{\prime}=n^{n^{n^{n}}}$ (iii) $B=n^{n^{n^{n^{n}}}}$ (iv) $B^{\prime}=n^{n^{n^{n^{n^{n}}}}}$. We have not optimized the values of the bounds so we expect that our general algorithmic approach works for better bounds.

In the protocol we often want to make a piece of cake (the residue) smaller. To do so we run the Core Protocol on it. To make descriptions more succinct we define a function which converts the number of times we run the Core Protocol on a piece of cake to how much smaller it is from the cutter’s perspective. Note that when the Core Protocol is run, at least $2/n$ value of the cake is allocated to the agents because the cutter cuts the cake into $n$ equally preferred pieces and at least two pieces are fully allocated. By running the Core Protocol $B$ times with the same cutter, the cutter thinks only $f(B)={(\frac{n-2}{n})}^{B}$ value of the cake is unallocated.

For any piece of cake $c$ in a given snapshot, each agent has a bonus value which corresponds to how much more cake he thinks he got in that snapshot than he would have got had he been allocated $c$ instead.

An agent $i$’s bonus value on piece of cake $c_{jk}$ in snapshot $p_{j}$ is the value $V_{i}(c_{ji})-V_{i}(c_{jk})$, where $c_{ji}$ is the piece that was allocated to agent $i$ in $p_{j}$ by the Core Protocol.

In a Core snapshot, a bonus value is significant for an agent if we can make the residue smaller than that value from the agent’s perspective in a bounded number of steps. Note that the significance of a piece of cake does not depend on the absolute value that an agent ascribes to it but it is relative to the value of the unallocated cake (residue).

An agent $i$ thinks a value is significant if the value is more than or equal to $V_{i}(R)f(B)$ where $R$ is the unallocated residue. A piece is significant for an agent if it has significant value for him.

Note that if an agent $i$ finds a piece of cake significant, he will still find it significant if the residue becomes smaller than before. We also observe the following about the Core Protocol and the cutter getting a significant advantage over at least one other agent.

Note that when the Core Protocol is run once, the cutter has a significant bonus over at least one agent (the agent who gets the smallest valued piece from the cutter’s perspective). This bonus results in a domination of the cutter over the agent in $k=({\log n})(\frac{n-2}{n})+1$ iterations of the Core Protocol on the residue with same cutter. The reason is that the cutter $i$ has advantage at least $V_{i}(R)/(n-2)$ over the agent who gets the smallest valued piece from $i$’s perspective. This is the worst case when equal value of residue comes from each of the maximum of $n-2$ trimmed off pieces. In $k$ iterations of the Core Protocol with $i$ as cutter, agent $i$’s value of the residue is $V_{i}(R){(\frac{n-2}{n})}^{k}$ which is less than $V_{i}(R)/(n-2)$.

If we run the Core Protocol repeatedly with the same agent as cutter and we are lucky that the cutter has a significant advantage over each agent in some snapshot, then in $({\log n})(\frac{n-2}{n})+1$ extra iterations of the Core Protocol with the same cutter, we can make the cutter dominate each agent. This simplifies our problem, because we now only need to allocate the remaining cake among the dominated agents in an envy-free manner. In general, we may not be so lucky that the cutter dominates all other agent due to which we have to do more work to ensure that a set of agents dominates the other agents. In this additional work, the process of extraction is crucial:

For each piece allocated in each of the Core snapshots and for each agent, the Main Protocol tries to associate a piece of the cake extracted from the residue. For the $C^{\prime}$ snapshots, there are $C^{\prime}n$ pieces allocated to the agents. For each of the pieces, other agents who do not get the piece extract corresponding pieces from the residue that is the unallocated cake. Take for example, a piece $c$ allocated to some agent (say agent $1$) in a snapshot. In the snapshot in which $c$ is allocated to $1$, each agent $i$ gets a piece that is of value (according to $i$) at least as much as $c$. In the residue, each agent $i$ is asked to put a trim so that the cake from the left extreme of the residue to the trim is of value equal to $i$’s value of his piece minus his value for $c$. The trims of the agents on the residue give rise to pieces of cake corresponding to the agents’ bonus value over piece $c$. These pieces are extracted (cut away from the residue) and associated with $c$ (kept in consideration with piece $c$). When agents make trim marks on the residue in accordance with their bonus (over a piece in a snapshot), each pair of successive trim marks gives rise to a separate piece that can be extracted. For piece $c_{jk}$ in snapshot $p_{j}$, we will denote by $e_{jk1},e_{jk2},\ldots,e_{jkl^{\prime}}$ the set of pieces that are extracted in the same order with $e_{jk1}$ extracted first (see Figure 3). We say that a piece $e_{jkl}$ is extracted by agent $i$ if the right hand extreme of the piece coincided with the trim of agent $i$ on the residue. Note that $l^{\prime}\leq n-1$ because for each allocated piece in a snapshot, at most $n-1$ other agents can put trim marks on the residue so as to obtain at most $n-1$ extracted pieces. Each extracted piece has a clear corresponding allocated piece in a Core snapshot with which it is associated. Note that it can be the case that not all $n-1$ agents place a trim we allow extraction only for agents whose bonus values are not significant.

In our protocol, pieces are extracted from the residue only if each agent finds the pieces not significant. The reason is that we want to keep sufficient residue to do further extractions on the residue as well as maintain structure.

Figure 4 illustrates the process of extraction and association. We focus on a single Core snapshot in which each of the four agents are allocated a piece. Since the Core allocation is envy-free, each of agents $2,3,4$ think they got at least as much value as the piece that 1 got. Now agents $2,3,$ and $4$ are asked to place a trim mark each on the residue to indicate that the residue to the left of their trim mark is equal to their advantage over agent 1. The trim marks result in three slices of cake that are extracted. Among the extractions, since 2 has the leftmost trim, his piece is extracted first, then $4$ and then $3$. The extracted pieces are associated with $1$’s allocated piece in the snapshot. In case the pieces will be added to $1$’s piece, the piece extracted by agent $2$ will be attached first, then the piece by agent $4$ and then $3$.

Later on, the extracted pieces may be attached to $c$ so that piece $c$ is now attractive to other agents because of the additional extracted pieces combined with $c$. We clarify that when pieces are extracted and associated with a given piece in a Core snapshot, such extracted pieces have not yet been allocated to any particular agent. Extracted pieces can only be allocated after they are officially attached to their associated piece.

For the protocol we need to restrict our focus on a subset of the snapshots where the same set of agents extracted pieces in the same order:

We call two snapshots $p_{j}$ and $p_{j^{\prime}}$ isomorphic to each other if for each agent $i\in N$ and for any two pieces $c_{ji}$ and $c_{j^{\prime}i}$ allocated to agent $i$ in the corresponding snapshots $p_{j}$ and $p_{j^{\prime}}$, the set of agents who extracted cake from the residue and associated to $c_{ji}$ and $c_{j^{\prime}i}$ is the same and the agents in the set extracted pieces in the same order.

We extend this notion to allocated pieces in snapshots. Two allocated pieces of cake belonging to two isomorphic snapshots are isomorphic if they were allocated to the same agent.

We also extend the notion of isomorphism to extracted pieces. We say that for two isomorphic snapshots $p_{j}$ and $p_{j^{\prime}}$, two extracted pieces $e_{jkl}$ and $e_{j^{\prime}kl}$ are isomorphic if they are associated respectively to isomorphic pieces $c_{jk}$ and $c_{j^{\prime}k}$ and that $e_{jkl}$ and $e_{j^{\prime}kl}$ were extracted by the same agent.

In Figure 5, we illustrate isomorphic snapshots.

Our protocol will keep track of a set of isomorphic snapshots, progressively discarding (not changing) some so that we can make manipulations on the ones we keep in an envy-free way. The pieces of cake we are working with are labelled $c_{jk}$ for allocated pieces or $e_{jkl}$ for extracted pieces. Suppose that the given set of snapshots is $S$. We use the notation $c_{k},S$ and $e_{kl},S$ to denote the set of pieces of cake $c_{jk}$ or $e_{jkl}$ in snapshots in $S$. Abusing the notation, we will simply say $c_{k}$ or $e_{kl}$ to mean the set of pieces which are in the snapshots we are working with. Note that we will generally use index $j$ for the snapshot number, $k$ for the piece number in a given snapshot, and $l$ for the $l$-th extracted piece.

3 The Main Protocol

The Main Protocol is the engine which runs our overall envy-free protocol. It is responsible for allocating the whole cake among all the agents in an envy-free manner. The Main Protocol works recursively. If the number of agents is four or less, a previously known bounded envy-free algorithm can directly be called. Otherwise, the Main Protocol divides part of the cake in an envy-free manner and identifies a set of agents $N\setminus A$ that all dominate agents in $A$ with respect to the cake that is unallocated. The Main Protocol then recursively calls itself to divide the remaining cake among agents in $A$.

If the number of agents is more than four, the Main Protocol (Algorithm 3) calls the Core Protocol sequentially on the updated residue so that the residue becomes smaller than before after each call of the Core Protocol. The repeated calls of the Core Protocol help generate a number of snapshots each containing $n$ pieces of cake. In each snapshot, each agent has been allocated a piece of cake. Envy-freeness is maintained throughout for the allocated cake, and in the Core Protocol each agent thinks he got the highest value piece.

When we call the Core Protocol $n$ times each time with a different cutter, we argue that we get an envy-free allocation in which agents get at least $\nicefrac{{1}}{{n}}$ value of the original cake.

Suppose an agent $i$ is the cutter is the $j\leq n$-th call of the Core Protocol. Then in the first $j-1$ calls of the Core Protocol, $i$ gets $1/n$ value of the allocated cake. This follows from the envy-freeness of the allocated cake. For the remaining cake, $i$ again gets $1/n$ value of the unallocated cake in the $j$-th call because $i$ is the cutter. Hence $i$ gets $1/n$ value of the original cake. Since the cake is always allocated via Core, it is allocated in an envy-free manner. Hence after the Main Protocol has made the first $n$ calls of the Core Protocol, we have an envy-free allocation in which agents get at least $\nicefrac{{1}}{{n}}$ value of the original cake.

After the first $n$ calls to the Core Protocol, the Main Protocol does not stop making calls to the Core Protocol if there is still some unallocated cake. After calling the Core Protocol $C^{\prime}$ times, $C^{\prime}$ Core snapshots are obtained. The Core Protocol may be further called (in the while loop in step 13) to make the residue even smaller. This ensures that each agent considers each piece in the first $C^{\prime}$ snapshots significant or smaller than significant by a large factor dependent on our bound $B$.

For each piece of cake $c$ in the $C^{\prime}$ snapshots, agents can ascribe what we refer to as a bonus value, which corresponds to how much more value they got in that snapshot than their value for piece $c$. In the Main Protocol, for each piece of cake $c$ in the snapshots, we ask all agents with a non-significant bonus value to make a cut on the residue equal to their bonus value. The pieces obtained from these cuts are then taken from the residue and associated (but not yet attached) to piece of cake $c$. We refer to this process as extraction. A piece is extracted only if all agents find it insignificant. The extracted pieces will potentially be attached to their associated piece of cake $c$ in the GoLeft Protocol. Most of them however will be sent back to the residue or shared amongst a subset of agents in an envy-free way. The process of attaching the extracted pieces to their associated piece in the GoLeft Protocol is designed to make that piece desirable to the agent whose bonus value was used to extract the piece from the residue. The Main Protocol also calls the Discrepancy Protocol in case there is some piece in consideration for extraction that some agents consider significant and others do not. The goal of the Discrepancy Protocol is to exploit any such discrepancy and to ensure that when the GoLeft Protocol is called by the Main Protocol, then there is no discrepancy in how the extracted pieces are viewed, i.e., no actually extracted piece is considered significant by some agent.

4 Discrepancy Protocol

When pieces are being extracted from the residue during the Main Protocol, it may be the case that one of the pieces $e_{jkl}$ in consideration for extraction is significant for some agent. In that case, the piece is not extracted and the Discrepancy Protocol (Algorithm 4) is called in line 40 that either exploits or ‘eliminates’ this discrepancy. The discrepant piece $e_{jkl}$ is kept aside from the residue. On the other hand, all previously extracted pieces are added back to the residue. Since the difference between a piece that is just above significant or just below significant can be arbitrarily small, the Core Protocol is used to create a gap so that the discrepant piece either has value at least $V_{i}(R)n$ or value at most $V_{i}(R)/n$. This gap is highly useful because the goal of the Discrepancy Protocol is to either ensure that (1) everyone thinks that the discrepant piece is significant or (2) the problem of finding an envy-free allocation can be broken into two sub-problems where some agents $D$ are allocated the discrepant piece and the rest $D^{\prime}$ are allocated the residue. In this, we use the fact mentioned earlier that envy-freeness implies proportionality.

In case of (1), the process of extraction in the Main Protocol is reset and the discrepant piece as well as all the pieces that had been extracted are sent back to the residue. This may appear to be a waste of work but when we do this, we have ensured that at least one agent has significant advantage over another’s piece for a given snapshot. This ‘setback’ can only happen $C^{\prime}n^{2}$ times before each agent dominates each other agent in which case the remaining cake can be allocated arbitrarily without causing envy.

We note that Discrepancy makes the residue smaller as it calls the Core Protocol. When the residue becomes smaller, it may be that a piece of cake that was not significant for an agent becomes significant because significance is defined with respect to the residue. Hence any agent $i$ who thinks that $\frac{V_{i}(R)}{n}\leq V_{i}(e_{jkl})\leq V_{i}(R)n$ will eventually think that $V_{i}(e_{jkl})\geq V_{i}(R)n$ when the Core Protocol has been run to reduce the residue.

5 Groundwork for the GoLeft Protocol

The GoLeft Protocol is the heart of our overall protocol and is crucial to allocate the cake that is still not allocated. All the other steps in the Main Protocol can be viewed as preparing the ground for the GoLeft Protocol to work. By calling the Core Protocol a sufficient number of times in the Main Protocol, enough $C^{\prime}$ Core snapshots are obtained that are helpful to identify $C$ isomorphic snapshots in the GoLeft Protocol (these isomorphic snapshots constitute the working set of snapshots over which the GoLeft Protocol operates). Moreover, by calling Discrepancy before GoLeft, it is ensured that all agents are on the same page: all agents consider all the extracted pieces as insignificant.

The GoLeft Protocol (Algorithm 5) is called by the Main Protocol. The goal of the GoLeft Protocol is to identify a set of agents $N\setminus A$ that dominate agents in $A$. This means that the remaining residue can be allocated among agents in $A$ in an envy-free manner without worrying about agents in $N\setminus A$ envying them. The goal of the GoLeft protocol is achieved by attaching extracted pieces to the pieces in the working set of snapshots in a methodical manner while maintaining envy-freeness of the allocated cake. In order to maintain envy-freeness, the working set of snapshots is modified in various ways. When all extracted pieces for the working set of snapshots have been attached, we will show that we obtain a set of agents that all dominate the other agents. For example, if we end up with Core snapshots in which for one isomorphic allocated piece, there are a total of less than $n-1$ extracted pieces that have all been attached and are held by a certain agent $i$, then agents who did not manage to extract pieces corresponding to the main piece have a significant advantage over $i$ as well as all other agents who extracted pieces before $i$ for that main piece. This significant advantage translates into dominance.

The GoLeft protocol operates on a working set of isomorphic snapshots. The main operations of the GoLeft Protocol are to attach extracted pieces to the Core snapshot allocation and to implement exchanges in which there is a sequence of agents $a_{o},a_{1},\ldots,a_{k-1}$ where each agent $a_{i}$ in the sequence gets the pieces of agent $a_{i+1\mod k}$. When operations such as attachments and exchanges happen, the isomorphic snapshots change but remain isomorphic nonetheless.

Before we give an overview of the steps of the GoLeft Protocol, we establish some concepts and mathematical structures we will work with. The two key structures are the working set $S$ of isomorphic snapshots and the permutation graph that is defined with respect to the working set of isomorphic snapshots. During the GoLeft Protocol, each structure gets updated based on the information on the other structure. The algorithm makes progress when agents exchange their pieces with each other.

During the course of the GoLeft Protocol, the isomorphic snapshots in $S$ get changed in the following way: (1) some subset of $S$ is removed from $S$ (2) agents exchange their pieces and (3) extracted pieces are attached to pieces in the snapshots in $S$.

When we update $S$, we maintain isomorphism and other invariant properties as follows. If an agent holds a piece $c_{jk}$, he holds the whole set $c_{k}$ of isomorphic pieces in set of snapshots $S$. Note that we are abusing notation here as $c_{k}$ refers to a set of pieces allocated to agent $k$ in the working set of snapshots $S$. If an agent holds an extracted piece $e_{jkl}$, he holds the whole set $e_{kl}$ of isomorphic extracted pieces associated with $S$ as well. When we implement an exchange, we are essentially making $|S|$ exchanges – one in each of the snapshots. These are exchanges that not only involve the pieces in the snapshots but also involve those extracted pieces that have been attached to the pieces. When we attach an extraction to a piece in a snapshot in $S$, we simultaneously attach isomorphic extractions to the corresponding isomorphic allocated piece in each of the snapshots.

We also ensure that the extracted pieces are attached in the appropriate order so that each associated piece gets attached after the previous associated pieces have been attached. For example, if we were focussing on snapshot in Figure 4, the extracted associated piece due to agent $3$ will get attached after the extracted associated piece due to agent $4$. Note that if we attach an extracted piece $e_{jkl}$ to an allocated piece $c_{jk}$ (along with its previously attached extracted pieces) in a snapshot in the working set $S$, we perform a similar attachment for all such isomorphic extracted pieces in the set $e_{kl}$ to their corresponding pieces in set $c_{k}$. Also, if an agent $i$ currently holds an extracted piece, he also holds all earlier extracted pieces as well.

We make a crucial point about a consistency condition that we enforce.

We enforce a consistency condition whereby an agent cannot hold extracted pieces beyond the extraction he himself made. Therefore, when we attach an extracted piece to agent $j$’s piece in a snapshot to attract agent $i$ to it, agent $j$ does not actually hold the latest attachment because it is beyond $j$’s extraction. However in an exchange, if $i$ were to get $j$’s piece along with its attachments, then $i$ will also get the latest attachments that were originally extracted by $i$ himself.

In the GoLeft Protocol, we operate on an increasingly small set of isomorphic snapshots. The goal is to reach a set of isomorphic snapshots that can be used to find a set of agents who all dominate other agents. As the GoLeft Protocol proceeds, we discard snapshots to allow us to focus on others where extracted pieces from $E$ have been ‘attached’ in an envy-free way to the allocated pieces in $C$ to which they were associated. The set of isomorphic snapshots $S$ becomes smaller when a set of isomorphic extractions $e_{k(l+1)}$ are attached to set of isomorphic pieces $c_{k}$ in the snapshots $S$ with each particular extracted piece in $e_{k(l+1)}$ getting attached to its corresponding piece in $e_{k}$. By discarding a set of Core snapshots, we mean that these snapshots and their allocations are not further worked upon and their associated unattached extracted pieces are sent back to the residue. Intuitively, the purpose of discarding snapshots will be to preserve the remaining advantages of agents over other agents.

The GoLeft procedure gradually attaches the extracted pieces to the allocated pieces in the working set of snapshots. The reason we call the protocol ‘go left’ is because we can visualize that for each piece in the set of snapshots we work with, we want to add the next extracted pieces to the isomorphic allocated pieces that are kept to the left of the isomorphic allocated pieces (see Figure 6). By attaching the next extracted pieces, we are ‘going left’.

How do we know which set of isomorphic pieces in $S$ can have their next extraction? Which set of agents can exchange their currently held isomorphic pieces along with their current attachments? For this we work in tandem with the permutation graph.

The permutation graph keeps track of which agent is willing to move to which piece in the snapshots. The high level idea is that nodes of the permutation graph correspond to the agents and an agent $i$ points to another agent $j$ if he will be as happy taking $j$’s allocated pieces along with the attachments on those pieces.

The permutation graph is a directed graph where the set of nodes correspond to the set of agents. Hence when we refer to the graph, we will use agents and nodes interchangeably. The arcs of the permutation graph depend on the current state of the working set of isomorphic snapshots $S$. In particular, they depend on which extracted pieces have been attached to the originally allocated pieces in the isomorphic snapshots in $S$. Agent $i$ points to agent $j$ if $j$ holds isomorphic pieces in $S$ that have had all attachments up till $i$’s extracted pieces. We build the initial permutation graph with each node pointing only to itself. Throughout the protocol, we ensure that each node in the permutation graph has in-degree at least one.

The permutation graph itself gets updated when isomorphic extractions are attached to a isomorphic pieces in $S$. The process of extracted pieces being attached to an allocated piece results in the aggregated piece becoming attractive to a new agent who then wants to point to the agent holding that piece (see Figures 7 and 8).

The permutation graph also suggests a natural way to exchange pieces. It has a similar idea as the trading graph used in top trading cycles algorithm for housing markets. If there is a cycle in the graph, we have the possibility of exchanging the allocations of agents in the cycle by giving an agent the piece of the agent he points to . The permutation graph is more intricate because updates on the permutation graph reflect simultaneous updates on the working set of isomorphic snapshots $S$. Also by Remark 3.14, an agent in an exchange does not offer what he holds but can offer more because of the additional attachments beyond his own extraction.

6 The GoLeft Protocol

Now that we have established the important ideas in the GoLeft Protocol, let us tie up the ideas and give an overview of how the protocol works. When the GoLeft Protocol starts, it first identifies a working set $S$ of $C$ Core snapshots from out of the $C^{\prime}$ Core snapshot that we focus on. The protocol then constructs a permutation graph corresponding to the working set of isomorphic snapshots.

In the permutation graph, each node $i$ corresponds to an agent $i$ who holds a set of isomorphic pieces along with their attached extracted pieces in the working set of isomorphic snapshots $S$. We divide the nodes of the permutation graph into sets $T$ and $T^{\prime}$. Set $T$ is the set of nodes/agents such that the isomorphic pieces held by them in $S$ have not had $n-1$ attachments). $T^{\prime}$ is the set of nodes/agents such that the isomorphic pieces held by them in $S$ have had $n-1$ attachments.

The protocol identifies a cycle in the permutation graph that includes at least one node $i$ from $T$. Such a cycle always exists. In each of the working set $S$ of isomorphic snapshots, we implement an exchange of pieces held by agents in the cycle: each agent in the cycle is given the piece corresponding to the node that the agent points to in the cycle. After implementing the exchange, the permutation graph is updated to reflect the exchange. If in the exchange, if an agent gets an inferior piece, he always gets the additional extracted pieces associated with the inferior piece up till the agent’s extractions. Hence in each snapshot in $S$, each agent’s value from his allocation in the snapshot is preserved even if he gets a different piece than in the original Core snapshot. For any agent $i$, as long as no agent gets extracted pieces beyond $i$’s extraction, $i$ will not be envious. In the GoLeft protocol, it can be the case that some agent $j$ gets extracted pieces beyond $i$’s extracted pieces but before any such attachments in the last part of the GoLeft protocol, we ensure that no envy arises.

After implementing the cycle, we focus on a node $i\in T$ that was in the cycle. For agent/node $i$ we know that for all snapshots in the working set $S$, agent $i$ has been allocated the original isomorphic pieces $c_{k}$ as well as all associated pieces up till $i$’s extracted piece. If the piece of cake agent $i$ is currently allocated in the snapshots $S$ has no more extracted pieces left to attach to it, but it has not had $n-1$ attachments, this means that all agents who have not had their corresponding piece extracted/attached have a significant advantage over agents who have had an extracted piece attached. In this case, the GoLeft Protocol returns the set of dominated agents to the Main Protocol and we are left with a smaller envy-free allocation problem because it involves less number of agents.

In case node $i$ does not lead to an exit from the GoLeft Protocol, we know that there are associated pieces that can still be attached to the isomorphic pieces held by $i$ in the working set of Core snapshots $S$. We focus on the next set of associated pieces $e_{k(l+1)}$ that we are interested to attach to the pieces $c_{k}$ that have already had associated pieces $e_{k2},e_{k_{3}},\ldots,e_{kl}$ attached in their corresponding main pieces $c_{k}$. Additionally attaching pieces $e_{k(l+1)}$ to pieces $c_{k}$ is useful in making the agent who extracted them, interested in the pieces $c_{k}$ because of the additional $e_{k(l+1)}$ as well as the previous attachments. However, naively attaching the pieces can be problematic and spoil the envy-freeness of the allocation that we maintain. We deal with the issue as follows.

The agents who did not extract pieces associated with the $c_{k}$ pieces as well as agents who extracted pieces that have not been attached are asked to ‘reserve’ a big enough subset $S^{\prime}\subset S$ of snapshots in which they value the difference between their bonus value for $c_{k}$ and the extracted pieces currently attached to $c_{k}$ the most. These snapshots $S^{\prime}$ are removed from $S$ and their remaining unattached associated pieces sent back to the residue. By maintaining the advantages in the snapshots $S^{\prime}$, such agents will not be envious even if some agent in $\{1,\ldots,l\}$ additionally gets all other extracted pieces $e_{k(l+1)}$ in the remaining snapshots in $S$. The advantages reserved due to the discarded snapshots in $S^{\prime}$ are crucial for the next phase where agents in $\{1,\ldots,l\}$ get extracted pieces $e_{k(l+1)}$ from subset $S^{\prime\prime}$ of the working set.

The agents indexed from 1 to $l$ who have all already had their extracted pieces attached to $c_{k}$ are asked to choose a high enough fraction of the snapshots in $S$ in which they value the $e_{k(l+1)}$ pieces. We call these snapshots $S^{\prime\prime}$. The $e_{k(l+1)}$ pieces from $S^{\prime\prime}$ are bunched together and the Main Protocol is called to divide this cake in an envy-free way among the agents indexed from $1$ to $l$ where $l$ is strictly less than $n$. Since envy-freeness implies proportionality, they derive enough value that they will not be envious if the agent indexed $l+1$ gets all other pieces in set $e_{k(l+1)}$. The corresponding set of snapshots $S^{\prime\prime}$ are then discarded.

Hence each time we attach isomorphic extracted pieces $e_{k(l+1)}$ to isomorphic pieces $c_{k}$, we discard snapshots $S^{\prime}\cup S^{\prime\prime}$ from the working set $S$ and still maintain an envy-free allocation. Note that in the snapshots that remain in $S$, agents may currently hold a different isomorphic piece than they previously did, but since they also hold the corresponding attachments associated with the isomorphic piece, each agent’s total value in each isomorphic snapshot in $S$ stays the same. In Figure 9, we show the states of the permutation graph and the corresponding representative Core snapshot as well as the corresponding extracted pieces.

When the protocol attaches extracted pieces $e_{k(l+1)}$ to allocated pieces $c_{k}$ currently held by agent $l$, it deletes the incoming edge of node/agent $l$ and replaces it by an edge coming from agent $l+1$ who extracted pieces in $e_{k(l+1)}$. Intuitively, $l+1$ is now willing to be allocated $c$ and its attached pieces instead of his current pieces in $S$. We delete previous edges to ensure that until termination, nodes in $T$ have in-degree strictly $1$ which guarantees that no matter the cycle involving a node in $T$ found by the protocol, we will make progress towards termination. By attaching enough extracted pieces in the appropriate order, the GoLeft Protocol finally arrives at a point, where there is some isomorphic set of pieces $c_{k}$ in the set $S$ for which all possible associate pieces have been attached but there is some set of agents $N\setminus A$ who do not have associated pieces. The reason agents in $N\setminus A$ could not extract such pieces is because they had a unanimous significant advantage over the agent indexed $1$ who got the pieces $c_{k}$. By gradually attaching (unanimously insignificant) associated piece to pieces $c_{k}$ and ensuring that all agents who did extract corresponding pieces do get some isomorphic piece in $c_{k}$ (along with the associated insignificant attachments), we make sure that agents in $N\setminus A$ now dominate agents in $A$. At this point, we can return from the GoLeft Protocol.

In Figure 9, we demonstrate how the permutation graph along with the working set of isomorphic snapshots changes in the GoLeft Protocol. Note that even when the representative snapshot changes, there still exist snapshots isomorphic to the previous representative snapshots but these snapshots have been discarded from the working set of snapshots. The coloured/shaded pieces represent the pieces given by the Core Protocol to each player. The small pieces on the left of the coloured pieces are extracted pieces, each labelled by the agent who extracted it. At first the extracted pieces are associated with a specific allocated piece. Then they are attached to it (represented by the dotted lines). Finally, when a coloured/shaded piece is reallocated to a new agent, the extracted pieces attached to it are also allocated to the new agent (in the diagram we now aggregate the extracted piece to the main piece). In the second state of the isomorphic snapshot, agent $2$ points to agent $1$ because the piece extracted by agent $2$ has been attached to $1$’s held piece. In the third state of the isomorphic snapshot, agent $3$ points to agent $2$ because the piece extracted by agent $3$ has been attached to $2$’s held piece. In the fourth state of the isomorphic snapshot, agent $1$ points to agent $3$ because the piece extracted by agent $1$ has been attached to $3$’s held piece. In the fifth state, the agents $1,2,3$ exchange their currently held piece and are allocated cake up to their extracted piece. In the fifth (last) state of the isomorphic snapshot, agent $1$ holds a piece up till his extraction but neither agent $2$ or $4$ extracted pieces for the piece that agent $1$ holds. This means that agents $2$ and $4$ have a significant advantage over agent $1$. Initially the piece was held by $3$ and still is in discarded isomorphic snapshots. This implies significant advantage of $2$ and $4$ over $3$. Therefore agent $2$ and $4$ can be made to dominate $1$ and $3$.

Argument for Boundedness and Envy-freeness

In the previous section, we presented the Main Protocol that relies on a few other protocols. We will now argue why it is bounded and envy-free.

We first show that the Main Protocol is bounded.

The Core Protocol is bounded by ${(n^{2})}^{n+1}$.

The protocol can execute each of the steps without encountering a problem. In the Core Protocol, the cutter makes $n-1$ trims, and the other agents are asked to make at most one trim on the pieces. This takes $n^{2}$ queries. The most costly procedure is having to call at most $2n$ times the SubCore Protocol for less than $n$ number of agents. The recursion tree has at most $n^{2}$ branches and a depth of $n$. Hence there are at most $n{(n^{2})}^{n}$ nodes in the tree with each node requiring $n^{2}$ steps. Hence the overall time of the Core Protocol is bounded by $n^{3}{(n^{2})}^{n}$.

The Discrepancy Protocol is bounded by $Bn\times n^{3}{(n^{2})}^{n}$.

The Discrepancy Protocol can execute each of its steps without encountering a problem. Since at least one agent finds the discrepant piece significant and since we call the Core Protocol $B$ times before the while loop with each agent as cutter, at least one agent $i$ thinks that the discrepant piece is of at least as much value as $R$. Hence after the while loop, such an agent $i$ thinks that the discrepant piece is of value at least $n$ times the value of $R$. The while loop from line 6 to line 8 will run at most once for each agent. If an agent values the piece within the gap delimited by the inequality, running the Core Protocol with the agent as cutter $B$ times will ensure that the residue is small enough for the piece to be on the right hand side of the inequality. Therefore the while loop is bounded by $Bn\times Core$ where $Core$ is the number of operations required to run the Core Protocol. The rest of the Discrepancy Protocol does not make any queries. The Discrepancy Protocol is therefore bounded by $Bn\times n^{3}{(n^{2})}^{n}$ where $n^{3}{(n^{2})}^{n}$ is the bound on the Core protocol as proved by Lemma 4.1.

The GoLeft Protocol is bounded by $B^{\prime}_{n-1}+2Cn^{3}+2n^{2}+C^{\prime}$.

First let us show that the GoLeft Protocol can execute all steps. The two steps which might be problematic are finding isomorphic snapshots in line 4 and finding a cycle in line 12. We handle the two cases by a couple of claims.

Out of the $C^{\prime}$ snapshots generated, the GoLeft procedure can find $C$ isomorphic snapshots in line 4.

For this we use a simple counting argument. The isomorphism is entirely dependent on the order and existence of the extracted pieces. For each allocated piece of cake , there could be up to $n-1$ extracted pieces. Each extracted piece might be extracted by any agent or not exist. This gives us $(n+1)^{n-1}$ possibilities for each allocated piece. Since a snapshot has $n$ allocated pieces, this gives $(n+1)^{n^{2}-n}$ different possible configurations. We are given $n^{n^{n^{n}}}$ snapshots and desire to find $n^{n^{n}}$ isomorphic snapshots. For $n>4$ we have $n^{n^{n^{n}}}>(n+1)^{n-1}n^{n^{n}}$, which implies we can find a set of isomorphic snapshots of size $C$.

Therefore isomorphic snapshots can always be found.

We now argue that a cycle in line 12 can be found.

In the permutation graph, at each step of the GoLeft Protocol, there exists a cycle containing at least one node from $T$.

We observe that the permutation graph always contains a cycle since each node has in-degree at least $1$. For each node $s$ we can travel to the node $t$ pointing to it. This process of backtracking can occur at most as many times as the number of nodes until we cycle.

We now show that it always contains a cycle with at least one node from $T$. Recall that each node in the graph points to nodes in $T^{\prime}$ if $T^{\prime}$ is non-empty. Each node in $T$ has in-degree exactly 1 whereas each node in $T^{\prime}$ has in-degree $n-1$. We start from any node in $T$ and backtrack according to the incoming arc. In case we only encounter nodes from $T$, we will eventually cycle so that we have found a cycle consisting of nodes only from $T$. Otherwise, we may reach a node $t^{\prime}$ from $T^{\prime}$. Since the node $t\in T$ from which we started backtracking points to each node in $T^{\prime}$ and hence to $t^{\prime}$, we have again found a cycle consisting of node $t\in T$.

Now that we handled the two possibly problematic parts of the GoLeft Protocol, let us go over the other steps. The isomorphic snapshots can be found in $C^{\prime}$ steps. The while loop from line 8 to line 54 runs until a node in $T$ is found such that it has had less than $n-1$ attachments but has no extracted pieces to be attached (the if condition in step 19 is true). To make sure this happens, we require that there always be a node in $T$ so that either we make progress in terms of attaching new sets of extractions or we already encounter the separation condition (Step 19). We prove this as follows:

A node being in $T^{\prime}$ means the agent associated with the node holds a piece of cake with no significant bonus. At least one piece of cake must have a significant bonus from the cutter’s perspective (see e.g., Remark 3.10).

Each time the loop runs, either we get a separation of the agents given that the if condition in step 19 is true or a new set of extracted pieces is attached to a set of allocated pieces. There are only $Cn^{2}$ extracted pieces in the isomorphic snapshots that we are considering.

The for loop ranging from line 32 to line 35 just goes through a subset of the agents and therefore cannot run more than $n$ times.

The for loop ranging from line 40 to line 43 also goes through a subset of the agents and therefore cannot run more than $n$ times.

The while loop contains the two for loops and therefore its overall complexity is $(Cn^{2}+n)\times 2n$.

Finally the call to the Main Protocol in line 46 calls the Main Protocol on a strict subset of the agents and is therefore bounded by $B^{\prime}_{n-1}$.

This gives an overall complexity of $(Cn^{2}+n)\times 2n+B^{\prime}_{n-1}+C^{\prime}$.∎

The Main Protocol is bounded by $B^{\prime}=n^{n^{n^{n^{n^{n}}}}}$ Robertson and Webb operations.

When the agents are asked to place a trim on the residue in line 28, they are always asked to delimit a value which is (much) smaller than their valuation of the residue.

For the first extractions this is straightforward, seeing as we only ask an agent to place a trim if he thinks his bonus value is not significant. However as we extract pieces, the residue could become much smaller. This does not happen due to the bounds set in place. A non-significant piece of cake is valued to be less than $(\frac{n-2}{n})^{B}$ of the residue. We extract for $C^{\prime}$ snapshots and there are only $C^{\prime}n^{2}$ pieces that could potentially be extracted. $C^{\prime}n^{2}(\frac{n-2}{n})^{B}\ll 1$, hence extracting the pieces barely affects the residue, and we can therefore always extract a non-significant value from it.

The protocol can therefore always execute line 28.

The initial statement in line 13 runs the Core Protocol $C^{\prime}$ times. It is therefore upper bounded by $C^{\prime}\times n^{3}{(n^{2})}^{n}$ where $n^{3}{(n^{2})}^{n}$ is the complexity of the Core Protocol, as proved by Lemma 4.1.

The while loop from line 13 to 15 checks that each agent values a piece outside a certain gap. The gap is based on the residue and if an agent values a piece within that gap, by running the Core Protocol $B$ times with the agent as cutter we can ensure that the piece will never be in that gap again. The while loop will therefore run a maximum of $BnC^{\prime}n$ times. Its complexity is therefore bounded by $BnC^{\prime}n\times n^{3}{(n^{2})}^{n}$.

The while loop from line 23 to 51 runs at most once for each bonus value piece since every time it repeats it labels a new bonus value as significant and a value can never be made to no longer be significant. Therefore the number of times it runs is bounded by $C^{\prime}n^{2}$.

The for loop going from line 25 to 50 simply goes through all the pieces of cake and therefore runs $C^{\prime}n$ times. The for loop from line 26 to 30 goes through all the agents and therefore runs $n$ times. The for loop from line 32 to 49 goes through all the agents and therefore runs $n$ times. The statement of line 40 is bounded by the complexity of the Discrepancy Protocol which according to Lemma 4.3 is bounded by $Bn\times n^{3}{(n^{2})}^{n}$.

The Main Protocol calls in line 42 and in line 43 each are on a strict subset of the agents and by assumption are bounded by $B^{\prime}_{n-1}$.

We therefore have a while loop running $C^{\prime}n^{2}$ with each run of the loop taking $C^{\prime}n\times(n+n\times(Bn\times n^{3}{(n^{2})}^{n}+B^{\prime}_{n-1}))$ steps, upper bounding the complexity of that while loop by $C^{\prime}n^{2}\times(C^{\prime}n\times(n+n\times(Bn\times n^{3}{(n^{2})}^{n}+B^{\prime}_{n-1})))$

The call to GoLeft in line 55 is bounded by the complexity of the GoLeft Protocol which by Lemma 4.5 is bounded by $B^{\prime}_{n-1}+2Cn^{3}+2n^{2}$. The call to the Main Protocol in line 62 is on a strict subset of the agents and therefore is bounded by $B^{\prime}_{n-1}$. This gives us an overall complexity of $C^{\prime}\times n^{3}{(n^{2})}^{n}+BnC^{\prime}n\times n^{3}{(n^{2})}^{n}+C^{\prime}n^{2}\times(C^{\prime}n\times(n+n\times(Bn\times n^{3}{(n^{2})}^{n}+B^{\prime}_{n-1})))+B^{\prime}_{n-1}+2Cn^{3}+2n^{2}+B^{\prime}_{n-1}$ which for $n>4$ can be verified to be less than $B^{\prime}$.∎

2 Argument for Envy-freeness

The Core Protocol results in an envy-free partial allocation in which the cutter cuts the cake into $n$ pieces, each agent gets a part of one of the pieces, and the cutter as well as at least one non-cutter agent gets a complete piece.

It is sufficient to prove that the SubCore for $n-1$ agents results in a neat allocation in which one agent gets a full piece. The cutter can take the last unallocated piece. No non-cutter agent $i$ is envious of a cutter agent because $i$’s piece is at least as preferred as any unallocated piece. The cutter is indifferent among all pieces so is not envious of any non-cutter agent.

In order to prove the statement, it is sufficient to prove by induction the following statement. Suppose there are $m$ agents and at least $m+1$ pieces and there exists an envy-free allocation of the $m$ agents where each agent partially gets one of the pieces giving him at least the specified benchmark value, then the SubCore will find a neat allocation for $m$ agents where at least one of the $m$ agents gets a full piece. When we call the SubCore for the first time, the benchmark values are zero, so there does exist an envy-free allocation in which each agent $i$ gets a piece of value at least $b_{i}$.

Base Case. If there is exactly one agent, he can be given the most preferred piece among the pieces. If there are multiple most preferred pieces, he is given the most preferred piece with the lowest index. The value achieved by the agent is at least $b_{i}$.

Induction. Suppose we get a neat allocation for $m-1$ agents where one agent gets a full piece. If the $m$-th agent most prefers an unallocated piece, then we are already done. No agent is envious of another. Since the first $m-1$ agents already achieved their benchmark values, they still achieve their benchmark value. As for agent $m$, he gets a most preferred piece so he trivially achieves his benchmark value because the benchmark value of an agent is either zero or a value of the one of the pieces.

If agent $m$ is not interested in any of the contested pieces, the induction follows easily. This is because $m$’s most preferred piece is outside of the allocated pieces so far, and by giving $m$ his most preferred piece we preserve neatness and the condition that one agent gets a full piece.

Now suppose that agent $m$ is also interested in one of the $m-1$ contested pieces. In that case, each agent in $[m]$ is asked to trim the highly valued contested pieces to equal the value of the most preferred uncontested piece (this value is kept track of by $b_{j}^{\prime}$). Thus for each agent in $[m]$ the most preferred uncontested piece provides a benchmark value that they expect to get in any envy-free allocation of the agents in $[m]$.

We first claim that each of the $m-1$ contested pieces has at least one trim even if the trim is on the extreme left margin. Suppose a contested piece $a$ has no trim not even on the left margin. This means that each agent in $[m]$ considers some uncontested piece more preferred than piece $a$. But this contradicts our hypothesis that the allocation for agents $[m-1]$ agents is neat.

When each agent in $[m]$ is asked to trim the contested pieces to the value of his most preferred uncontested piece, we distinguish between two cases: (1) we do not get multiple winners in $W$ i.e., each contested piece has one designated winner and the the number of designated winners for the contested pieces is $n-1$ and (2) some agent in $W$ is a multiple winner, i.e., he is the designated winner with the rightmost trim on more than one contested piece. We can ensure thanks to claim 2 that each piece has exactly one designated winner.

We first deal with (1) which is the easier case. Suppose we do not get multiple winners so that $|W|=m-1$. Each agent in $W$ gets the benchmark value if he gets the piece where he had the rightmost trim. The allocation is also envy-free for agents in $W$. Nonetheless we call SubCore recursively on agents in $W$ and the contested pieces. By the induction hypothesis, we get an envy-free allocation in which each agent in $W$ gets a piece of at least benchmark value. The only remaining agent in $[m]\setminus W$ can be given a most preferred uncontested piece which is a full piece because it was never trimmed. All the agents get their benchmark value so the value achieved is at least $b_{i}$.

No agent $i$ who is a winner of a contested piece envies another winner $j$ of a contested piece because $i$’s trim on $j$’s piece is not on the right of $j$’s trim on $j$’s piece. No agent $i$ who is a winner of a contested piece envies any uncontested piece because $i$’s benchmark value was exactly the value of the most preferred uncontested piece. Finally agent $j$ who is given an uncontested piece is not envious of any winner $i$ of a contested piece because $j$’s trim on $i$’s piece is not on the right of $i$’s trim on $i$’s piece. Also $j$ is not envious of an unallocated uncontested piece because $j$ got a most preferred uncontested piece.