Equilibria of Generalized Cut and Choose Protocols
Simina Br\^anzei \thanks{Simina Br\^{a}nzei was supported by the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540), and by the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. }
Ioannis Caragiannis \thanks{Ioannis Caragiannis was partially supported by the European Social Fund and Greek national funds through the research funding program Thales on ``Algorithmic Game Theory'' and by the Cost Action IC1205 ``Computational Social Choice''. }
David Kurokawa
Ariel D. Procaccia \thanks{Ariel Procaccia was partially supported by the NSF grant CCF-1215883.}
Classic cake cutting protocols --- which fairly allocate a divisible good among agents with heterogeneous preferences --- are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To answer this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the game-theoretic properties of algorithms that operate in this model. Specifically, we show that each protocol in the class of generalized cut and choose (GCC) protocols --- which includes the most important discrete cake cutting protocols --- is guaranteed to have approximate subgame perfect Nash equilibria. Moreover, we observe that the (approximate) equilibria of proportional protocols --- which guarantee each of the $n$ agents a $1/n$-fraction of the cake --- must be (approximately) proportional, and design a GCC protocol where all Nash equilibrium outcomes satisfy the stronger fairness notion of envy-freeness. Finally, we show that under an obliviousness restriction, which still allows the computation of approximately envy-free allocations, GCC protocols are guaranteed to have exact subgame perfect Nash equilibria.
1307.2225.tex
%\documentclass[10pt]{article} % For LaTeX2e
\documentclass[letterpaper,11pt]{article}

\usepackage[ruled, boxed]{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath, amsthm, amssymb, fullpage}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}

\newcommand{\todo}[1]{\noindent\textbf{BEGIN TODO }\marginpar{****}\textit{{#1}}\textbf{ END TODO}}%

\title{Equilibria of Generalized Cut and Choose Protocols}
\author{
Simina Br\^anzei
\thanks{Simina Br\^{a}nzei was supported by the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540), and by the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. }\\
\small{Aarhus University}\\
\small{simina@cs.au.dk}
\and
Ioannis Caragiannis
\thanks{Ioannis Caragiannis was partially supported by the European Social Fund and Greek national funds through the research funding program Thales on ``Algorithmic Game Theory'' and by the Cost Action IC1205 ``Computational Social Choice''.
}\\
\small{University of Patras}\\
\small{caragian@ceid.upatras.gr}
\and
David Kurokawa\\
\small{Carnegie Mellon University}\\
\small{dkurokaw@cs.cmu.edu}
\and
Ariel D. Procaccia
\thanks{Ariel Procaccia was partially supported by the NSF grant CCF-1215883.}\\
\small{Carnegie Mellon University}\\
\small{arielpro@cs.cmu.edu}
}
\date{}


\begin{document}
\maketitle

\begin{abstract}
Classic cake cutting protocols --- which fairly allocate a divisible good among agents with heterogeneous preferences --- are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To answer this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the game-theoretic properties of algorithms that operate in this model. Specifically, we show that each protocol in the class of \emph{generalized cut and choose (GCC) protocols} --- which includes the most important discrete cake cutting protocols --- is guaranteed to have approximate subgame perfect Nash equilibria. Moreover, we observe that the (approximate) equilibria of proportional protocols --- which guarantee each of the $n$ agents a $1/n$-fraction of the cake --- must be (approximately) proportional, and design a GCC protocol where all Nash equilibrium outcomes satisfy the stronger fairness notion of envy-freeness. Finally, we show that under an \emph{obliviousness} restriction, which still allows the computation of approximately envy-free allocations, GCC protocols are guaranteed to have exact subgame perfect Nash equilibria. 
\end{abstract}

\setcounter{page}{0} \thispagestyle{empty} 
\newpage


\section{Introduction}

A large body of literature deals with the so-called \emph{cake cutting} problem --- a misleadingly childish metaphor for the challenging and important task of fairly dividing a heterogeneous divisible good between multiple agents (see, e.g., the recent survey by Procaccia~\cite{Pro13}, and the books by Brams and Taylor~\cite{BT96} and Robertson and Webb~\cite{RW98}). Two formal notions of fairness have emerged as the most appealing and well-studied: {proportionality}, in which each of the $n$ agents receives at least a $1/n$-fraction of the entire cake according to its valuation; and \emph{envy-freeness}, which stipulates that no agent would want to swap its own piece with that of another agent. At the heart of the cake cutting endeavor is the design of cake cutting \emph{protocols}, which specify an interaction between agents --- typically via iterative steps of manipulating the cake --- such that the final allocation is guaranteed to be proportional or envy-free.

The simplest cake cutting protocol is known as \emph{cut and choose}, and is designed for the case of two agents. The first agent cuts the cake into two pieces that it values equally; the second agent then chooses the piece that it prefers, leaving the first agent with the remaining piece. It is easy to see that this protocol yields a proportional and envy-free allocation (in fact these two notions coincide when there are only two agents). However, taking the game-theoretic point of view, it is immediately apparent that the agents can often do better by disobeying the protocol when they know each other's valuations. For example, in the cut and choose protocol, assume that the first agent only desires a specific small piece of cake, whereas the second agent uniformly values the cake. The first agent can obtain its entire desired piece, instead of just half of it, by carving that piece out.

So how would strategic agents behave when faced with the cut and choose protocol? A standard way of answering this question employs the notion of \emph{Nash equilibrium}: each agent would use a strategy that is a best response to the other agent's strategy. It turns out that the cut and choose protocol has a unique\footnote{Assuming there are pieces of cake that the two agents value differently, and every piece has positive value.} Nash equilibrium: the first agent cuts two pieces that the second agent values equally; the second agent selects its more preferred piece, and the one less preferred by the first agent in case of a tie. Clearly, the second agent cannot gain from deviating, as it is selecting a piece that is at least as preferred as the other. As for the first agent, if it makes its preferred piece even bigger, the second agent would choose that piece, making the first agent worse off. 
Interestingly enough, in equilibrium the roles of the agents are reversed; now it is the second agent who is getting exactly half of its value for the whole cake, while the first agent generally gets more. Crucially, the equilibrium outcome is also proportional and envy-free. In other words, even though the agents are strategizing rather than following the protocol, the outcome in equilibrium has the same fairness properties as the ``honest'' outcome!

With this motivating example in mind, we would like to make general statements regarding the equilibria of cake cutting protocols. We wish to identify a general family of cake cutting protocols --- which captures the classic cake cutting protocols --- so that each protocol in the family is guaranteed to possess (approximate) equilibria. Moreover, we wish to argue that these equilibrium outcomes are fair. Ultimately, our goal is to be able to reason about cake divisions that are obtained as outcomes when agents are presented with a standard cake cutting protocol and behave strategically; ideally we would like to be able to argue that these cake divisions must nevertheless be fair.


\subsection{Model, Results, and a New Algorithmic Paradigm}

To set the stage for a result that encompasses classic cake cutting protocols, we introduce (in Section~\ref{sec:model}) the class of \emph{generalized cut and choose (GCC)} protocols. A GCC protocol is represented by a tree, where each node is associated with the action of an agent. There are two types of nodes: a \emph{cut node}, which instructs the agent to make a cut between two existing cuts; and a \emph{choose} node, which offers the agent a choice between a collection of pieces that are induced by existing cuts. Moreover, we assume that the progression from a node to one of its children depends only on the relative positions of the cuts (in a sense to be explained formally below). We argue that classic protocols --- such as Dubins-Spanier~\cite{DS61}, Selfridge-Conway (see \cite{RW98}), Even-Paz~\cite{EP84}, as well as the original cut and choose protocol --- are all GCC protocols. We view the definition of the class of GCC protocols as one of our main contributions.

In Section~\ref{sec:eq}, we observe that GCC protocols may not have exact Nash equilibria (NE). However, we prove that every GCC protocol has at least one $\varepsilon$-NE for every $\varepsilon>0$, in which agents cannot gain more than $\varepsilon$ by deviating, and $\varepsilon$ can be chosen to be arbitrarily small. In fact, we establish this result for a stronger equilibrium notion, (approximate) \emph{subgame perfect Nash equilibrium (SPNE)}, which is, intuitively, a strategy profile where the strategies are in NE even if the game starts from an arbitrary point. We also observe that for any proportional protocol, the outcome in any $\varepsilon$-equilibrium must be an $\varepsilon$-proportional division. We conclude that under the classic cake cutting protocols listed above --- which are all proportional --- strategic behavior (almost) preserves the proportionality of the outcome.

The natural question at this point is whether there are GCC protocols with \emph{envy-free} equilibria. We give an affirmative answer in Section \ref{sec:ef}. Specifically, we design a curious GCC protocol in which every NE outcome is a contiguous envy-free allocation and vice versa, that is, the set of NE outcomes coincides with the set of contiguous envy-free allocations. It remains open whether a similar result can be obtained for SPNE instead of NE. 

In Section~\ref{sec:obliv} we establish an existence result for exact SPNE by focusing on \emph{oblivious} GCC protocols, where the available actions at each step are independent of the history. While the obliviousness property is restrictive, we demonstrate that oblivious GCC protocols are powerful enough to compute $\varepsilon$-envy-free allocations. 

Taking a broader perspective, our approach involves introducing a concrete computational model that captures well-known algorithms, and reasoning about the game-theoretic guarantees of \emph{all} algorithms operating in this model. This approach appears distinct from related ones, where concrete query models are defined in order to evaluate the computational complexity of economic methods~\cite{BN09,HN13}, or restrictions \emph{on the output of the algorithm} --- such as the well-known \emph{maximal-in-range} restriction~\cite{Dob07} --- give rise to desirable game-theoretic properties. 
Perhaps the most closely related approach was taken by Tennenholtz in his work on program equilibrium~\cite{Ten04b} (later extended by Fortnow~\cite{Fort09}), but there the strategies are the programs themselves, whereas in our work a common algorithm induces the agents' strategies. 
%in which the strategies of the agents are loop-free programs, and a program equilibrium is a choice of programs for each agent such that neither agent has an incentive to choose a different program. This work has been generalized to allow arbitrary Turing machines by Fortnow \cite{Fort09}, where utility is discounted by the computation time.
%However, none of these papers considered the scenario in which agents are executing instructions belonging to the same program.
We therefore believe that our conceptual contributions may be of independent interest to researchers working in auction design and other areas of algorithmic game theory.

\subsection{Related Work on Incentives in Cake Cutting}

Nicol\`o and Yu~\cite{Ny08} were the first to suggest equilibrium analysis for cake cutting protocols. Focusing exclusively on the case of two agents, they design a specific cake cutting protocol whose unique SPNE outcome is envy-free. And while the original cut and choose protocol also provides this guarantee, it is not ``procedural envy free'' because the cutter would like to exchange roles with the chooser; the two-agent protocol of Nicol\'o and Yu aims to solve this difficulty. Br\^anzei and Miltersen~\cite{BM13} also investigate equilibria in cake cutting, but in contrast to our work they focus on one cake cutting protocol --- the Dubins-Spanier protocol --- and restrict the space of possible strategies to \emph{threshold strategies}. Under this assumption, they characterize NE outcomes, and in particular they show that in NE the allocation is envy-free. Br\^anzei and Miltersen also prove the existence of $\varepsilon$-equilibria that are $\varepsilon$-envy-free; again, this result relies on their strong restriction of the strategy space.

Several recent papers by computer scientists~\cite{CLPP13,MT10,MN12} take a mechanism design approach to cake cutting; their goal is to design fair cake cutting protocols that are \emph{strategyproof}, in the sense that agents can never benefit from manipulating the protocol. This turns out to be an almost impossible task~\cite{Zhou91}, and positive results are obtained by either making extremely strong assumptions (agents' valuations are highly structured and fully reported to a central authority), or by employing randomization and significantly weakening the desired properties. In contrast, our result of Section~\ref{sec:eq} deals with strategic outcomes under a large class of cake cutting protocols, and aims to capture well-known protocols; our result of Section~\ref{sec:ef} is a positive result that achieves fairness ``only'' in equilibrium, but without imposing any restrictions on the agents' valuations.

%\todo{The IJCAI submission had more references to previous work, include some of those here.}


\subsection{Main Open Problem}

We show that oblivious GCC protocols are guaranteed to have exact Nash equilibria. However, this is not true for GCC protocols in general, and the enigmatic question of whether classic cake cutting protocols possess exact Nash equilibria and, if so, whether the corresponding cake divisions are envy-free, remains open (because these protocols do not satisfy the obliviousness restriction). Note that the work of Br\^anzei and Miltersen~\cite{BM13} does not answer this question even for the Dubins-Spanier protocol, as they strongly restrict the strategy space to the subset of threshold strategies, and therefore their equilibrium results do not capture deviations to non-threshold strategies. Our model provides the formal framework that is required to tackle this question in its most general --- and presumably extremely challenging --- form.


\section{The Model}
\label{sec:model}

%\begin{todo}
%Discuss the Robertson-Webb communication model; this doesn't say very much about what the protocol is allowed to do. The protocol
%could check that the cuts are made at irrational points, for example.
%\end{todo}

The cake cutting literature typically represents the cake as the interval $[0,1]$. There is a set of agents $N=\{1,\ldots,n\}$, and each agent $i\in N$ is endowed with a valuation function $V_i$ that assigns a value to every subinterval of $[0,1]$. These values are induced by a non-negative continuous value density function $v_i$, so that for an interval $I$, $V_i(I)=\int_{x\in I} v_i(x)\ dx$. By definition, $V_i$ satisfies the first two properties below; the third is an assumption that is made without loss of generality. 
\begin{enumerate}
\item Additivity: For every two disjoint intervals $I_1$ and $I_2$, $V_i(I_1\cup  I_2) = V_i(I_1) + V_i(I_2)$.
\item Divisibility: For every interval $I\subseteq [0,1]$ and $0\leq \lambda\leq 1$ there is a subinterval $I'\subseteq I$ such that $V_i(I') = \lambda V_i(I)$.
\item Normalization: $V_i([0,1])=1$.
\end{enumerate}

Note that the valuation functions are non-atomic, i.e., they assign zero value to points. This allows us to disregard the boundaries of intervals, and in particular we treat intervals that overlap at their boundary as disjoint. We sometimes explicitly assume that the valuations are \emph{strictly positive}, that is, $v_i(x)>0$ for all $x\in[0,1]$ and for all $i \in N$. 

A \emph{piece of cake} is a finite union of disjoint intervals. We are interested in allocations of disjoint pieces of cake $X_1,\ldots,X_n$, where $X_i$ is the piece that is allocated to agent $i\in N$. A piece is \emph{contiguous} if it consists of a single interval.

We study two fairness notions. An allocation $X$ is \emph{proportional} if for all $i\in N$, $V_i(X_i)\geq 1/n$; and \emph{envy-free} if for all $i,j\in N$, $V_i(X_i)\geq V_i(X_j)$. Note that envy-freeness implies proportionality. 


\subsection{Generalized Cut and Choose Protocols}

The standard communication model in cake cutting was proposed by Robertson and Webb \cite{RW98}, and was employed in a body of work studying the complexity of cake cutting~\cite{EP06,EP06b,WS07,Pro09,KLP13}. 
The model restricts the interaction between the protocol and the agents to two types of queries:
\begin{itemize}
\item \emph{Cut} query: $Cut_{i}(x, \alpha)$ asks agent $i$ to return a point $y$ such that $V_{i}([x,y]) = \alpha$.
\item \emph{Evaluate} query: $Evaluate_{i}(x, y)$ asks agent $i$ to return a value $\alpha$ such that $V_{i}([x,y]) = \alpha$.
\end{itemize}
However, the communication model does not give much information about the actual implementation of the protocol and
what allocation it produces. For example,
the protocol could allocate pieces depending on whether a particular cut was made at an irrational point (see Algorithm \ref{alg:nonGCC}).

For this reason, we define a generic class of protocols that are implementable with natural operations, which capture all the bounded\footnote{In the sense that the number of operations is upper-bounded by a function that takes the number of agents $n$ as input.} cake cutting algorithms,
such as cut and choose, Dubins-Spanier, Even-Paz, Successive-Pairs, and Selfridge-Conway (see, e.g., \cite{Pro13}). At a high level, the standard protocols
are implemented using a sequence of natural instructions, each of which is either a
\emph{Cut} operation, in which some agent is asked to make a cut
in a specified region of the cake; or a \emph{Choose} operation, in which some agent is asked to take a piece from a set of already demarcated
pieces indicated by the protocol.
In addition, every node in the decision tree of the protocol is based exclusively on the execution history and absolute ordering of the cut points,
which can be verified with any of the following operators: $<, \leq, = , \geq, >$.

More formally, a \emph{generalized cut and choose (GCC)} protocol is implemented exclusively with the following types of instructions:
\begin{itemize}
\item \emph{Cut}: The syntax is ``$i$ \emph{Cuts} in $S$'',
where $S = \{[x_1, y_1], \ldots, [x_m, y_m]\}$ is a set of contiguous pieces (intervals), such that the endpoints of every piece $[x_j, y_j]$ are $0, 1$, or cuts made in the previous steps of the protocol. Agent $i$ can make a cut at any point $z \in [x_j, y_j]$, for some $j \in \{1, \ldots, m\}$.

\item \emph{Choose}: The syntax is ``$i$ \emph{Chooses} from $S$'',
where $S = \{[x_1, y_1], \ldots, [x_m, y_m]\}$ is a set of contiguous pieces, such that the endpoints of every piece $[x_j, y_j] \in S$ are
$0$, $1$, or cuts made in the previous steps of the protocol. Agent $i$ can choose any \emph{single} piece $[x_j, y_j]$ from $S$.

\item \emph{If-Else Statements}: The conditions depend on the absolute order of all the cut points made in the previous steps and the execution history of the protocol.
\end{itemize}

%We note that every bounded cake cutting protocol can be written in this form when the number of iterations is known in advance.
A GCC protocol uniquely identifies every contiguous piece by the symbolic names of all the cut points contained in it.
For example, Algorithm 1 is a GCC protocol. Algorithm \ref{alg:nonGCC} is not a GCC protocol, because
it verifies that the point where agent $1$ made a cut is exactly $1/3$, whereas a GCC protocol can only
verify the ordering of the cut points relative to each other and the endpoints of the cake. Note that, unlike in the 
communication model of Robertson and Web \cite{RW98}, GCC protocols cannot obtain and use information about the valuations of the agents --- the allocation is only decided by the agents' \emph{Choose} operations.

\begin{algorithm}[t]
\begin{algorithmic}
\STATE agent $1$ \emph{Cuts} in $\{[0,1]\}$ // $@x$
\STATE agent $1$ \emph{Cuts} in $\{[0,1]\}$ // $@y$
\STATE agent $1$ \emph{Cuts} in $\{[0,1]\}$ // $@z$
\IF {$\left(x < y < z \right)$}
\STATE agent $1$ \emph{Chooses} from $\{ [x,y], [y, z]\}$
\ENDIF
\end{algorithmic}
\caption{A GCC protocol. The notation ``// $@x$'' assigns the symbolic name $x$ to the cut point made by agent 1.}
\label{alg:GCC_protocol}
\end{algorithm}


\begin{algorithm}[t]
\begin{algorithmic}
\STATE agent $1$ \emph{Cuts} in $\{[0,1]\}$ // $@x$
\IF{$\left(x = \frac{1}{3}\right)$}
\STATE agent $1$ \emph{Chooses} from $\{[0, x], [x,1]\}$
\ENDIF
\end{algorithmic}
\caption{A non-GCC protocol.}
\label{alg:nonGCC}
\end{algorithm}

%can add: first describe D-S in more detail and why it is proportional, then simulate it as GCC protocol

To gain some intuition we illustrate why the discrete version of Dubins-Spanier belongs to the class of GCC protocols.
The first round of the algorithm asks each agent $i$ to make a cut at any point in $[0,1]$
--- denoted by $x_{i}^{1}$ --- and allocates the first piece, $[0, x_{i}^{1}]$ to the agent $i$ that
made the leftmost cut. This admits a GCC implementation
as follows. First, each agent $i$ is required to make a cut in $\{[0,1]\}$, at some point denoted by $x_{i}^{1}$.
The agent $i^*$ with the leftmost cut $x_{i^*}^{1}$ can be determined using \emph{if-else} statements whose conditions only
depend on the ordering of the cut points $x_{1}^{1}, \ldots, x_{n}^{1}$.
Then, agent $i^*$ is asked to choose ``any'' piece in the singleton set $\{[0,x_{i^*}^{1}]\}$.
The subsequent rounds are similar: at the end of every round the agent that was allocated a piece is removed, and the protocol iterates on the remaining players and remaining cake.  
Note that, while the Dubins-Spanier protocol allocates one contiguous piece to each agent, other protocols such as Selfridge-Conway can assign non-contiguous pieces. In general, the GCC implementations of these protocols construct their decision trees by looking at both the ordering of the cut points and the allocation history.
%
%
%  TODO: DO WE NEED TO EXPLAIN WHAT THE ALLOCATION HISTORY IS???
%
%
%where an allocation is recorded in history by the name of the agent that took the piece and
%the symbolic names of all the cut points contained by that piece.


\subsection{The Game}

We study GCC protocols when the agents behave strategically. Specifically, we consider a GCC protocol, coupled with the valuation functions of the agents, 
as an \emph{extensive-form game of perfect information} (see, e.g., \cite{SL08}). In such a game, agents execute the \emph{Cut} and \emph{Choose} instructions strategically. 
Each agent is fully aware of the valuation functions of the other agents and aims to optimize its overall utility for the chosen pieces, given the strategies of other agents. 
The game can be represented by a tree (called a \emph{game tree}) with Cut and Choose nodes:
\begin{itemize}
\item In a \emph{Cut} node defined by ``\emph{$i$ cuts in $S$}'', where $S = \{[x_1, y_1], \ldots, [x_m, y_m]\}$, the strategy space of agent $i$ is the set $S$ of points where agent $i$ can make a cut at this step.
\item  In a \emph{Choose} node defined by ``\emph{$i$ chooses from $S$}'', where $S = \{[x_1, y_1], \ldots, [x_m, y_m]\}$, the strategy space is the set $\{1, \ldots, m\}$, i.e., the indices of the pieces that can be chosen by the agent from the set $S$.
\end{itemize}

The strategy of an agent defines an action for \emph{each} node of the game tree where it executes a Cut or a Choose operation. If an agent deviates, the game can follow a completely different branch of the tree, but the outcome will still be well-defined. 

The strategies of the agents are in \emph{Nash equilibrium (NE)} if no agent can improve its utility by unilaterally deviating from its current strategy, i.e., by cutting at a different set of points and/or by choosing different
pieces. A \emph{subgame perfect Nash equilibrium (SPNE)} is a stronger equilibrium notion, which means that the strategies are in NE in every subtree of the game tree. In other words, even if the game started from an arbitrary node of the game tree, the strategies would still be in NE. An \emph{$\varepsilon$-NE} (resp., $\varepsilon$-SPNE) is a relaxed solution concept where an agent cannot gain more than $\varepsilon$ by deviating (resp., by deviating in any subtree).

%canadd: look at cut and choose game as example


\section{Existence of Approximate Equilibria} \label{sec:eq}

It is well-known that finite extensive-form games of perfect information can be solved using \emph{backward induction}: starting from the leaves and progressing towards the root, at each node the relevant agent chooses an action that maximizes its utility, 
given the actions that were computed for the node's children. The induced strategies form an SPNE. Unfortunately, although we consider finite GCC protocols, we also need to deal with \emph{Cut} nodes where the action space is infinite, hence na\"ive backward induction does not apply. 

In fact, it turns out that not every GCC protocol admits an exact NE. For example, consider Algorithm 1, and assume that the valuation function of agent 1 is strictly positive.
Assume there exists a NE where agent $1$ cuts at  $x^{*}, y^{*}, z^{*}$, respectively,
and chooses the piece $[x^{*}, y^{*}]$.
If $x^{*} > 0$, then the agent can improve its utility by making the first cut at $x' = 0$ and choosing the piece $[x', y^{*}]$,
since $V_1([x', y^{*}]) > V_{1}([x^{*}, y^{*}])$. Thus, $x^{*} = 0$.
Moreover, it cannot be the case that $y^{*} = 1$, since the agent only receives an allocation
if $y^{*} < z^{*} \leq 1$. Thus, $y^{*} < 1$. Then, by making the second cut at any $y' \in (y^{*}, z^{*})$, agent $1$ can obtain
the value
$V_{1}([0, y']) > V_{1}([0, y^{*}])$.
It follows that there is no exact NE where the agent chooses the first piece. Similarly, it can be shown that there is no exact NE where the
agent chooses the second piece, $[y^{*}, z^{*}]$. This illustrates why backward induction does not apply: the maximum value at some \emph{Cut} nodes may not be well defined.
Nevertheless, we are able to prove a strong positive result.

\begin{theorem} \label{thm:existence}
Every GCC protocol with a bounded number of steps has an $\varepsilon$-SPNE,
for every $\varepsilon>0$.
\end{theorem}

The high-level idea of our proof, which appears in Appendix~\ref{app:existence}, relies on discretizing the cake --- such that every cell in the resulting grid has
a very small value for each agent --- and computing the optimal outcome on the discretized cake using backward induction. At every cut step of the protocol,
the grid is refined by adding a point
between every two consecutive points of the grid from the previous cut step. This ensures that any ordering of the cut points that can be enforced by
playing on the continuous cake can also be enforced on the discretized instance. So, for the purpose of computing an approximate SPNE, it is sufficient to work with the discretization.
Then, we show that the backward induction outcome from the discrete game gives an $\varepsilon$-SPNE
on the continuous cake.



\section{Fair Equilibria}
\label{sec:ef}

The existence of approximate equilibria gives us a tool for predicting the strategic outcomes of cake cutting protocols. In particular, classic protocols provide fairness guarantees when agents act honestly; but do they provide any fairness guarantees in equilibrium?

We first make a simple yet important observation. In a proportional protocol, every agent is guaranteed a value of at least $1/n$ regardless of what the others are doing. Therefore, in every NE (if any) of the protocol, the agent still receives a piece worth at least $1/n$; otherwise it can deviate to the strategy that guarantees it a utility of $1/n$ and do better. Similarly, an $\varepsilon$-NE must be $\varepsilon$-proportional, i.e., each agent must receive a piece worth at least $1/n-\varepsilon$. Hence, classic protocols such as Dubins-Spanier, Even-Paz, and Selfridge-Conway guarantee (approximately) proportional outcomes in any (approximate) NE (and of course this observation carries over to the stronger notion of SPNE).

We do not know whether an analogous general statement holds for envy-freeness (except for the case of two agents, where the two fairness notions coincide). However, our second result is the design of a specific GCC protocol that forces strategic agents to compute envy-free allocations in every NE. As we shall see, guaranteeing envy-free equilibria for any number of agents is quite nontrivial; in fact it remains open whether an analogous result holds when one asks for SPNE rather than just NE. 

\begin{theorem}
\label{thm:ef}
There exists a GCC protocol $\mathcal{P}$ such that on every cake cutting instance with strictly positive valuation functions, an allocation $X$ is the outcome of a NE of $\mathcal{P}$ if and only if $X$ is an envy-free contiguous allocation that contains the entire cake.
\end{theorem}

Crucially, an envy-free contiguous allocation is guaranteed to exist~\cite{Strom80}, hence the set of NE of protocol $\mathcal{P}$ is nonempty. The proof of the theorem uses the Thieves Protocol given by Algorithm 3. In this protocol, agent $1$ first demarcates a contiguous allocation $X=\{X_1, ..., X_n\}$ of the entire cake, where $X_i$ is a contiguous piece that corresponds to agent $i$. This can be implemented as follows. First, agent $1$ makes $n$ cuts such that the $i$-th cut is interpreted as the left endpoint of $X_i$. The left endpoint of the leftmost piece is reset to $0$ by the protocol. Then, the rightmost endpoint of $X_i$ is naturally the leftmost cut point to its right or $1$ if no such point exists. Ties among overlapping cut points are resolved in favor of the agent with the smallest index; the corresponding cut point is assumed to be the leftmost one. Notice that every allocation that assigns nonempty contiguous pieces to all agents can be demarcated in this way.

\begin{algorithm}[t]\label{alg1}
\begin{algorithmic}
\caption{Thieves Protocol: Every NE induces a contiguous envy-free allocation that contains the entire cake and vice versa.}
\STATE Agent $1$ demarcates a contiguous allocation $X$ of the cake
\FOR {$i = 2, \ldots, n, 1$}
%\STATE \hrulefill
\STATE \textit{{// Verification of envy-freeness for agent $i$}}
\STATE Agent $i$ \emph{Cuts} in $\{[0,1]\}$ // @$w_i$ % ($w_i, z_i$) // \textit{Every agent can indicate envy}
\STATE Agent $i$ \emph{Cuts} in $\{[w_i,1]\}$ // @ $z_i$
\FOR{$j = 1$ to $n$}
\IF{$\emptyset \not= ([w_i, z_i] \cap X_j) \subsetneq X_j$}
% {$\left(x_j <  w_i < z_i < y_j\right)$}
\STATE \textit{{// Agent $i$ steals a non-empty strict subset of $X_j$}}
\STATE Agent $i$ \emph{Chooses} from $\{[w_i, z_i] \cap X_j\}$
\STATE \textbf{exit} \textit{// Verification failed: protocol terminates}
\ENDIF
\ENDFOR
\STATE \textit{{// Verification successful for agent $i$}}
\ENDFOR
%\STATE \hrulefill
\FOR{$i = 1$ to $n$}
\STATE Agent $i$ \emph{Chooses} from $\{X_i\}$
\ENDFOR
\end{algorithmic}
\end{algorithm}

After the execution of the demarcation step, $X$ is only a tentative allocation. 
Then, the protocol enters a verification round, where each agent $i$ is allowed 
to {\em steal} some non-empty strict subset of a piece (say, $X_j$) demarcated 
for another agent. If this happens (i.e., the if-condition is true) then agent $i$ 
takes the stolen piece and the remaining agents get nothing. This indicates the 
failure of the verification and the protocol terminates. Otherwise, the pieces 
of $X$ are eventually allocated to the agents, i.e., agent $i$ takes $X_i$.

The proof of Theorem \ref{thm:ef} uses two important characteristics of the protocol. First, it guarantees that no state in which some agent steals can be a NE; this agent can always steal an even more valuable piece. Second, stealing is beneficial for an envious agent.

\begin{proof}[Proof of Theorem \ref{thm:ef}]
Let $\mathcal{P}$ be the Thieves protocol given by Algorithm 3 and $\mathcal{E}$ be any NE of $\mathcal{P}$.
Denote by $X$ the contiguous allocation of the entire cake obtained during the demarcation step, where $X_i = [x_i, y_i]$ for all $i \in N$, and let $w_i$ and $z_i$ be the cut points of agent $i$ during its verification round.
Assume for the sake of contradiction that $X$ is not envy-free.
Let $k^*$ be an envious agent, where $V_{k^*}(X_{j^*}) > V_{k^*}(X_{k^*})$, for some $j^* \in N$.
There are two cases to consider:

\emph{Case 1}: Each agent $i$ receives the piece $X_i$ in $\mathcal{E}$. This means that, during its verification round, each agent $i$ selects its cut points from the set $\bigcup_{j=1}^n\{x_j,y_j\}$. 
By the non-envy-freeness condition for $X$ above (and by the fact that the valuation function $V_{k^*}$ is strictly positive), there exist $w'_{k^*}, z'_{k^*}$ such that $x_{j^*} < w'_{k^*} < z'_{k^*} < y_{j^*}$ and $V_{k^*}([w'_{k^*}, z'_{k^*}]) > V_{k^*}([x_{k^*}, y_{k^*}])$. Thus, agent $k^*$ could have been better off by cutting at points $w'_{k^*}$ and $z'_{k^*}$ in its verification round, contradicting the assumption that $\mathcal{E}$ is a NE.

\emph{Case 2}: There exists an agent $i$ that did not receive the piece $X_i$. Then, it must be
the case that some agent $k$ stole a non-empty strict subset $[w''_k,z''_k] = [w_k, z_k]\cap Z_j$ of another piece $X_j$. However,
agent $k$ could have been better off at the node in the game tree reached in its verification round by making the following marks:
$w_k' = \frac{x_j + w''_k}{2}$ and $z_k' = \frac{z''_k + y_j}{2}$. Since either $x_j \leq w_{k}'' < z_k'' < y_j$ or $x_j < w_k'' < z_k'' \leq y_j$ (recall that $[w''_k,z_k'']$ is a non-empty strict subset of $X_j$ and the valuation function $V_k$ is strictly positive), it is also true that $V_k([w_k', z_k']) > V_k([w_k'', z_k''])$, again contradicting the assumption that $\mathcal{E}$ is a NE.

So, the allocation computed by agent $1$ under every NE $\mathcal{E}$ is indeed envy-free; this completes the proof of the first part of the theorem.

We next show that every contiguous envy-free allocation of the entire cake is the outcome of a NE. Let $Z$ be such an allocation, with $Z_i=[x_i,y_i]$ for all $i\in N$. We define the following set of strategies $\mathcal{E}$ for the agents:
\begin{itemize}
\item At every node of the game tree (i.e., for every possible allocation that could be demarcated by agent 1), agent $i\geq 2$ cuts at points $w_i=x_i$ and $z_i=y_i$ during its verification round.
\item Agent 1 specifically demarcates the allocation $Z$ and cuts at points $w_1=x_1$ and $z_1=y_1$ during its verification round.
\end{itemize}
Observe that $[w_i,z_i]\cap Z_j$ is either empty or equal to $Z_j$ for every pair of $i,j\in N$. Hence, the verification phase 
is successful for every agent and agent $i$ receives the piece $Z_i$.

We claim that this is a NE. Indeed, consider a deviation of agent 1 to a strategy that consists of the demarcated allocation $Z'$ (and the cut points $w'_1$ and $z'_1$). First, assume that the set of pieces in $Z'$ is different from the set of pieces in $Z$. Then, there is some agent $k \not= 1$ and some piece $Z'_j$ such that the if-condition $\emptyset \subset [x_k,y_k] \cap Z'_j \subset Z'_j$ is true. Hence, the verification round would fail for some agent $i\in \{2, ..., k\}$ and agent 1 would receive nothing. So, both $Z'$ and $Z$ contain the same pieces, and may differ only in the way these pieces are tentatively allocated to the agents. 
But in this case the maximum utility agent 1 can get is $\max_{j}{V_1(Z'_j)}$, either by keeping the piece $Z'_1$ or by stealing a strict subset of some other piece $Z'_j$. Due to the envy-freeness of $Z$, we have: $\max_{j}{V_1(Z'_j)} = \max_j{V_1(Z_j)} = V_1(Z_1)$,
%$$\max_{j}{V_1(Z'_j)} = \max_j{V_1(Z_j)} = V_1(Z_1);
%$$ 
hence, the deviation is not profitable in this case either.

Now, consider a deviation of agent $i\geq 2$ to a strategy that consists of the cut points $w'_i$ and $z'_i$. If both $w'_i$ and $z'_i$ belong to $\bigcup_{j=1}^n\{x_i,y_i\}$, then $[w'_i,z'_i] \cap Z_j$ is either empty or equal to $Z_j$ for some $j\in N$. Hence, the deviation will leave the allocation unaffected and the utility of agent $i$ will not increase. 
If instead one of the cut points $w'_i$ and $z'_i$ does not belong to $\bigcup_{j=1}^n\{x_i,y_i\}$, this implies that the condition 
$\emptyset \subset [w'_i,z'_i]\cap Z_j \subsetneq Z_j$ is true for some $j\in N$, i.e., agent $i$ will steal the piece $[w'_i,z'_i]\cap Z_j$. 
However, the utility $V_i([w'_i,z'_i] \cap Z_j)$ of agent $i$ cannot be greater than $V_i(Z_j)$, which is at most $V_i(Z_i)$ due to the envy-freeness of $Z$. Hence, again, this deviation is not profitable for agent $i$.

We conclude that $\cal E$ is a NE; this completes the proof of the theorem.
\end{proof}

The Thieves Protocol is only practical insofar as it delegates the computation of the envy-free allocation from the center to the agents (specifically, to agent 1). Its shortcoming is that agent 1 must compute the entire envy-free allocation up-front. Nevertheless, we view this as a strong positive result \emph{\`a la} implementation theory (see, e.g., \cite{Mask99}), which aims to construct (typically impractical) games where the NE outcomes coincide with a given specification of acceptable outcomes for each constellation of agents' preferences (known as a \emph{social choice correspondence}). Our construction guarantees that the NE outcomes coincide with (contiguous) envy-free allocations, that is, in this case the envy-freeness criterion specifies which outcomes are acceptable. We find it highly encouraging that there exist GCC protocols with this property.


\section{Obliviousness and Exact Equilibria}
\label{sec:obliv}

In Section~\ref{sec:eq} we noted that GCC protocols may not have exact Nash equilibria. We therefore ask whether there is a reasonable set of algorithmic restrictions that give rise to a family of cake-cutting protocols that have exact equilibria. For the set of restrictions to be ``reasonable'', we would need to show that there are interesting protocols satisfying the required properties.

Going back to the equilibrium-less GCC protocol --- Algorithm~\ref{alg:GCC_protocol} --- we observe that by removing the \emph{if} statement we would circumvent the lack of equilibrium. Leveraging this observation, we say that a GCC protocol is \emph{oblivious} if all of the nodes at depth $d$ are of the form ``$i_d$ cuts in $[0,1]$'', or all of the nodes at depth $d$ are of the form ``$i_d$ chooses any available interval between adjacent cuts'', for a fixed agent $i_d\in N$. 
%Less formally, the next agent to play and its action space are independent of the history\footnote{We formalize this statement in Lemma~\ref{lem:props}.} --- there are no ``if'' statements, and moreover cuts can be made anywhere and choose steps are restricted to a specific choice of intervals.
Less formally, the next agent to play and its action space are independent of the history\footnote{We formalize this statement in Lemma~\ref{lem:props}.}: in a cut step, the agent can make a cut anywhere on the cake, and in a choose step, the agent can choose any unclaimed piece which is demarcated by two adjacent cuts.
One may be tempted to think that the game tree of an oblivious GCC protocol is simply a path, but in fact it is not, because there are multiple outcomes (i.e., multiple leaves) --- different cuts and choices lead to different allocations and values. 

Although obliviousness is a significant restriction, we show that oblivious GCC protocols are powerful enough to compute approximately envy-free allocations. Indeed, Algorithm~\ref{alg_loop} is an oblivious GCC protocol that is $\varepsilon$-envy free, and requires $O(n^2/\varepsilon)$ steps. In words, the agents cut the cake into $O(n^2/\varepsilon)$ pieces (intervals between adjacent cuts), and the pieces are allocated in a round robin fashion. The algorithm's while loop seems like it violates the obliviousness restriction, but observe that we know in advance how many iterations are required; thus the protocol can be implemented using only \emph{Cut} and \emph{Choose} instructions.
And why can each agent guarantee envy of at most $\varepsilon$? Taking the point of view of agent $i$, this agent can make the initial cuts so that it values each interval between its own adjacent cuts at most at $\varepsilon$; it follows that it values any of the $O(n^2/\varepsilon)$ pieces induced by everyone's cuts at most at $\varepsilon$. Partition the choices into phases, where in each phase, $i$ chooses first, followed by agents $i+1,\ldots,n,1,\ldots,i-1$. In each phase, $i$ prefers its own piece to the piece selected by any other agent. Agent $i$ may envy the choices made by agents $1,\ldots,i-1$ before the beginning of the first phase, but its value for each of these pieces is at most $\varepsilon$. 


\begin{algorithm}[t]
\begin{algorithmic}
  \FOR{$\forall i \in N$}
		\STATE Agent $i$ makes $\lceil n/\varepsilon\rceil$ cuts in $[0,1]$
   %\STATE Agent $i$ makes cuts $\left(x_{i,0}, \ldots, x_{i, \left\lceil\frac{n}{\varepsilon}\right\rceil}\right)$, where $x_{i,0}=0,x_{i,\left\lceil\frac{n}{\varepsilon}\right\rceil}=1$, and $V_{i}([x_{i,j}, x_{i,j+1}]) \leq \varepsilon, \forall j$
   \ENDFOR
	\STATE $i = 1$
  \WHILE{$\exists$ available pieces between two adjacent cuts} 
     \STATE  Agent $i$ takes his (remaining) favorite piece
		 \STATE $i=(i\ \text{mod}\ n)+1$
   \ENDWHILE
\end{algorithmic}
\caption{$\varepsilon$-envy-free oblivious GCC protocol.}
\label{alg_loop}
\end{algorithm}

%\begin{theorem}
%For every $\varepsilon > 0$, an $\varepsilon$-envy-free allocation that contains the entire cake can be computed in $O\left(\frac{n^2}{\varepsilon}\right)$.
%\end{theorem}
%\begin{proof}
%The allocation produced by Algorithm \ref{alg_loop} is $\varepsilon$-envy-free and contains the entire cake.
%\end{proof}

%%%Of course, the purpose of the obliviousness restriction is to facilitate the existence of exact Nash equilibria: 
%%% SIMINA: I rephrased the above sentence because it could be used as a point of attack, i.e. that it's artificial but serves our purpose
As we show next, the obliviousness restriction facilitates the existence of exact Nash equilibria:

\begin{theorem} 
\label{thm:obliv}
Every oblivious GCC protocol with a bounded number of steps has an (exact) SPNE.
\end{theorem}

The proof of Theorem~\ref{thm:obliv} is relegated to Appendix~\ref{app:obliv}; it is completely different from the proof of Theorem~\ref{thm:existence}, and in particular relies on real analysis instead of backward induction on a discretized space. In the context of the proof it is worth noting that some papers prove the existence of SPNE in games with infinite action spaces (see, e.g., \cite{Harr85,HL87}), but our game does not satisfy the assumptions required therein. 

Interestingly, Theorem~\ref{thm:obliv} implies that any approximately proportional oblivious GCC protocol (such as Algorithm~\ref{alg_loop}) has exact Nash equilibria, which must be approximately proportional (because an agent has a strategy that guarantees a value of $1/n-\varepsilon$). In contrast, if we do not assume obliviousness then we can achieve exact proportionality --- but a proportional GCC protocol is only guaranteed to give rise to \emph{approximate} equilibria, which are therefore only guaranteed to be \emph{approximately} proportional (even though the protocol itself is exactly proportional). 


\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{BN09}
L.~Blumrosen and N.~Nisan.
\newblock On the computational power of demand queries.
\newblock {\em SIAM Journal on Computing}, 39(4):1372â€“--1391, 2009.

\bibitem{BT96}
S.~J. Brams and A.~D. Taylor.
\newblock {\em Fair Division: From Cake-Cutting to Dispute Resolution}.
\newblock Cambridge University Press, 1996.

\bibitem{BM13}
S.~Br\^anzei and P.~B. Miltersen.
\newblock Equilibrium analysis in cake cutting.
\newblock In {\em Proceedings of the 12th International Joint Conference on
  Autonomous Agents and Multi-Agent Systems (AAMAS)}, pages 327--334, 2013.

\bibitem{CLPP13}
Y.~Chen, J.~K. Lai, D.~C. Parkes, and A.~D. Procaccia.
\newblock Truth, justice, and cake cutting.
\newblock {\em Games and Economic Behavior}, 77:284--297, 2013.

\bibitem{Dob07}
S.~Dobzinski.
\newblock Better mechanisms for combinatorial auctions via maximal-in-range
  algorithms?
\newblock {\em SIGecom Exchanges}, 7(1):30--33, 2007.

\bibitem{DS61}
L.~E. Dubins and E.~H. Spanier.
\newblock How to cut a cake fairly.
\newblock {\em American Mathematical Monthly}, 68(1):1--17, 1961.

\bibitem{EP06b}
J.~Edmonds and K.~Pruhs.
\newblock Balanced allocations of cake.
\newblock In {\em Proceedings of the 47th Symposium on Foundations of Computer
  Science (FOCS)}, pages 623--634, 2006.

\bibitem{EP06}
J.~Edmonds and K.~Pruhs.
\newblock Cake cutting really is not a piece of cake.
\newblock In {\em Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 271--278, 2006.

\bibitem{EP84}
S.~Even and A.~Paz.
\newblock A note on cake-cutting.
\newblock {\em Discrete Applied Mathematics}, 7:285--296, 1984.

\bibitem{Fort09}
L.~Fortnow.
\newblock Program equilibria and discounted computation time.
\newblock In {\em Proceedings of the 12th Conference on Theoretical Aspects of
  Rationality and Knowledge (TARK)}, pages 128--133, 2009.

\bibitem{Harr85}
C.~Harris.
\newblock Existence and characterization of perfect equilibrium in games of
  perfect information.
\newblock {\em Econometrica}, 53(3):613--628, 1985.

\bibitem{HN13}
S.~Hart and N.~Nisan.
\newblock The query complexity of correlated equilibria.
\newblock CoRR abs/1305.4874, 2013.

\bibitem{HL87}
H.~Hellwig and W.~Leininger.
\newblock On the existence of subgame-perfect equilibrium in infinite-action
  games of perfect information.
\newblock {\em Journal of Economic Theory}, 45:55--75, 1987.

\bibitem{KLP13}
D.~Kurokawa, J.~K. Lai, and A.~D. Procaccia.
\newblock How to cut a cake before the party ends.
\newblock In {\em Proceedings of the 27th AAAI Conference on Artificial
  Intelligence (AAAI)}, 2013.
\newblock Forthcoming.

\bibitem{Mask99}
E.~Maskin.
\newblock Nash equilibrium and welfare optimality.
\newblock {\em Review of Economic Studies}, 66:23--38, 1999.
\newblock First circulated in 1977.

\bibitem{MN12}
A.~Maya and N.~Nisan.
\newblock Incentive compatible two player cake cutting.
\newblock In {\em Proceedings of the 8th International Workshop on Internet and
  Network Economics (WINE)}, pages 170--183, 2012.

\bibitem{MT10}
E.~Mossel and O.~Tamuz.
\newblock Truthful fair division.
\newblock In {\em Proceedings of the 3rd International Symposium on Algorithmic
  Game Theory (SAGT)}, pages 288--299, 2010.

\bibitem{Ny08}
A.~Nicol\`o and Y.~Yu.
\newblock Strategic divide and choose.
\newblock {\em Games and Economic Behavior}, 64(1):268--289, 2008.

\bibitem{Pro09}
A.~D. Procaccia.
\newblock Thou shalt covet thy neighbor's cake.
\newblock In {\em Proceedings of the 21st International Joint Conference on
  Artificial Intelligence (IJCAI)}, pages 239--244, 2009.

\bibitem{Pro13}
A.~D. Procaccia.
\newblock Cake cutting: Not just child's play.
\newblock {\em Communications of the ACM}, 56(7):78--87, 2013.

\bibitem{RW98}
J.~M. Robertson and W.~A. Webb.
\newblock {\em Cake Cutting Algorithms: Be Fair If You Can}.
\newblock A. K. Peters, 1998.

\bibitem{SL08}
Y.~Shoham and K.~Leyton-Brown.
\newblock {\em Multiagent Systems: Algorithmic, Game-Theoretic, and Logical
  Foundations}.
\newblock Cambridge University Press, 2008.

\bibitem{Strom80}
W.~Stromquist.
\newblock How to cut a cake fairly.
\newblock {\em American Mathematical Monthly}, 87(8):640--644, 1980.

\bibitem{Ten04b}
M.~Tennenholtz.
\newblock Program equilibrium.
\newblock {\em Games and Economic Behavior}, 49(2):363--373, 2004.

\bibitem{WS07}
G.~J. Woeginger and J.~Sgall.
\newblock On the complexity of cake cutting.
\newblock {\em Discrete Optimization}, 4:213--220, 2007.

\bibitem{Zhou91}
L.~Zhou.
\newblock Inefficiency of strategy-proof allocation mechanisms in pure exchange
  economies.
\newblock {\em Social Choice and Welfare}, 8:247--254, 1991.

\end{thebibliography}

\appendix

\section{Proof of Theorem~\ref{thm:existence}}
\label{app:existence}

%\begin{proof}[Proof of Theorem~\ref{thm:existence}]
Let $\varepsilon > 0$, and let $f(n)$ be an upper bound on the number of operations (i.e., on the height of the game tree) of the protocol. 
Define a grid, $\mathcal{G}_1$, such that every cell on the grid is worth at most
$\frac{\varepsilon}{2f(n)}$ to each agent.
For every $n$, let
$K$ denote the maximum number of cut operations, where $0 \leq K \leq f(n)$. For each $i \in \{1, \ldots, K\}$, we define the grid $\mathcal{G}_i$ so that the following properties are satisfied:
\begin{itemize}
\item The grids are nested, i.e.,
$\{0, 1\} \subset \mathcal{G}_1 \subset \mathcal{G}_2 \subset \ldots \subset \mathcal{G}_K$.
\item There exists a unique point $z \in \mathcal{G}_{i+1}$
between any two consecutive points $x, y \in \mathcal{G}_i$, such
that $x < z < y$ and $z \not \in \mathcal{G}_i$, for every $i\in\{1, \ldots, K-1\}$.
\item
Each cell on $\mathcal{G}_i$ is worth at most $\frac{\varepsilon}{2f(n)}$ to any agent, for all $i \in \{1, \ldots, K\}$.
\end{itemize}

Having defined the grids, we compute the backward induction outcome on the discretized cake, where the $i$-th \emph{Cut} operation can only be
made on the grid $\mathcal{G}_i$. We will show that this outcome is an $\varepsilon$-SPNE, even though agents could deviate by cutting anywhere on the cake. 
%Actually, our proof 
%establishes the stronger fact that this outcome is a subgame perfect $\varepsilon$-equilibrium \cite{SL08}.
%
%SIMINA, CHECK THE NEXT SENTENCES -- REMOVE AND/OR EXPLAIN BETTER
%
%
On the continuous cake, the agents play a perturbed version of the
idealized game from the grid $\mathcal{G}$, but
maintain a bijective mapping between the perturbed game
and the idealized version throughout
the execution of the protocol. Thus when determining the next action, the agents use the idealized grid as a reference.
The order of the cuts is the same in the ideal and perturbed game, however the sizes of the pieces may differ
by at most $\varepsilon/f(n)$.

Consider the following strategies. Let $x_1, \ldots, x_{k}$ be the history of cuts made at some point during the execution
of the protocol.
For each $i \in \{1, \ldots, k\}$, map the point $x_i$ to the \emph{closest} point $\mathcal{M}(x_i) \in \mathcal{G}_i$ such that:
\begin{itemize}
\item The order of the points $x_1, \ldots, x_{i}$ is the same as the order of
$\mathcal{M}(x_1), \ldots, \mathcal{M}(x_{i})$. Note this is always possible since the grid $\mathcal{G}_i$ is a strict superset
of $\mathcal{G}_{i-1}$ and has one point between every two points from $\mathcal{G}_{i-1}$.
\item $\mathcal{M}(x_i) = \mathcal{M}(x_j) \iff x_i = x_j$, $\forall j \in \{1, \ldots, i-1\}$.
\item $\mathcal{M}(x_i) = 0 \iff x_i = 0$.
\item $\mathcal{M}(x_i) = 1 \iff x_i = 1$.
\end{itemize}
Note that the map $\mathcal{M}$ is bijective. Moreover, the value of each agent for every piece with endpoints
$x_i$ and $\mathcal{M}(x_i)$ is at most $\frac{\varepsilon}{2f(n)}$. That is,
$V_{k}\left([x_i, \mathcal{M}(x_i)]\right) \leq \frac{\varepsilon}{2f(n)}$
if $x_i \leq \mathcal{M}(x_i)$, and $V_{k}\left([\mathcal{M}(x_i), x_i]\right) \leq \frac{\varepsilon}{2f(n)}$ otherwise, for all $k \in N$.

Consider any history of cuts $(x_1, \ldots, x_k)$. Let $i$ be the agent that moves next.
Agent $i$ computes the mapping
$(\mathcal{M}(x_1), \ldots, \mathcal{M}(x_k))$.
If the next operation is:
%For each agent $i$, when it is $i$'s turn to move:

\begin{itemize}

\item \emph{Choose}:
%The agent computes the mapping of the points $(x_1, \ldots, x_k)$ to $(\tilde{x}_1, \ldots, \tilde{x}_k)$.
%The agent maps each cut $x_j$ to the closest point $\tilde{x}_j$ on the grid $\mathcal{G}_{j}$, with the exception of the
%endpoints $0$ and $1$. That is, the mapping is such that order of the points in the continuous game is the same as their
%mappings on the grid. A point is never rounded to $0$ or $1$,
%such a mapping incorrectly
%predicts that certain orderings of the cuts for the other agents cannot occur, and may result in an equilibrium
%which is not subgame perfect. Moreover, the mapping is bijective, i.e. the mappings of two cut points overlap on the grid
%if and only if the original points overlap in the continuous game as well.
agent $i$ chooses the available piece (identified by the symbolic names of the cut points
it contains and their order) which is optimal in the idealized game, given the current state and
the existing set of ordered ideal cuts, $\mathcal{M}(x_1), \ldots, \mathcal{M}(x_k)$.
Ties are broken according to a fixed deterministic scheme which is known to all the agents.

\item \emph{Cut}:
%Again, the agent computes the mapping $(x_1, \ldots, x_k)$ to
%$(\tilde{x}_1, \ldots, \tilde{x}_k)$.
%maps each cut point $x_j$ to its equivalent $\tilde{x}_j$ on the
%grid $\mathcal{G}_j$, $\forall j \in \{1, \ldots, k\}$.
agent $i$ computes the optimal cut on $\mathcal{G}_{k+1}$, say at $x^{*}_{k+1}$. Then $i$ maps $x^{*}_{k+1}$ back to a point $x_{k+1}$
on the continuous game, such that $\mathcal{M}(x_{k+1}) = x^{*}_{k+1}$. That is, the cut $x_{k+1}$ (made in step $k+1$)
is always mapped by the other agents to $x^{*}_{k+1} \in \mathcal{G}_{k+1}$.
%That is, whenever the other agents
%interpret the cut $x_{k+1}$ made in step $k+1$, they would map it to $x^{*}_{k+1} \in \mathcal{G}_{k+1}$.
Agent $i$ cuts at $x_{k+1}$.
\end{itemize}

We claim that these strategies give an $\varepsilon$-SPNE.
The proof follows from the following claim, which we show by induction on $t$ (the
maximum number of remaining steps of the protocol):

\emph{Whenever there are at most $t$ operations left in the execution,
it is $\frac{t\varepsilon}{f(n)}$-optimal to play on the grid.}

Consider any history of play, where the cuts were made at $x_1, \ldots, x_k$. Without loss of generality, assume it is
agent $i$'s turn to move.

\emph{Base case:} $t=1$. The protocol has at most one remaining step. If it is a cut operation, then no agent receives
any utility in the remainder of the game regardless of where the cut is made. Thus cutting on the grid ($\mathcal{G}_k$) is optimal.
If it is a choose operation, then let $Z = \{Z_1, \ldots, Z_s\}$ be the set of pieces that $i$ can choose
from. Agent $i$'s strategy is to map each piece $Z_j$ to its equivalent $\mathcal{M}(Z_j)$ on the grid $\mathcal{G}_k$, and choose
the piece that is optimal on $\mathcal{G}_k$. Recall that $V_k([x_j, \mathcal{M}(x_j)]) \leq \frac{\varepsilon}{2f(n)}$ for all $k \in N$.
%since each point $x_j$ is mapped to the closest
%available on the grid
%$\tilde{x}_j$, the value of any agent for the segment $[x_j, \tilde{x}_j]$ is at most $\frac{\varepsilon}{2f(n)}$.
Thus a piece which is optimal on the grid, is $\frac{\varepsilon}{f(n)}$-optimal in the continuous game (adding up the difference on both sides). It follows that $i$ cannot gain
more than $\frac{\varepsilon}{f(n)}$ in the last step by deviating from the optimal piece on $\mathcal{G}_k$.
%and the value of an agent for each cell on $\mathcal{G}_k$ is less than $\frac{\varepsilon}{f(n)}$, a piece which
%is optimal on the grid, is $\varepsilon$-optimal in the continuous game, and so the agent does not lose more than
%$\frac{\varepsilon}{f(n)}$ by choosing a piece that is optimal on $\mathcal{G}_k$.

\emph{Induction hypothesis:} Assume that playing on the grid is $\frac{(t-1)\varepsilon}{f(n)}$-optimal whenever there
are at most $t-1$ operations left on every possible execution path of the protocol,
and there exists one path that has exactly $t-1$ steps.

\emph{Induction step:}
If the current operation is \emph{Choose}, then by the induction hypothesis, playing on the grid in the remainder of the protocol
is
$\frac{(t-1)\varepsilon}{f(n)}$-optimal for all
the agents, regardless of $i$'s move in the current step. Moreover,
agent $i$ cannot gain by more than $\frac{\varepsilon}{f(n)}$ by choosing a different piece in the current step,
compared to
piece which is optimal on $\mathcal{G}_k$, since $V_{i}([x_{l}, \mathcal{M}(x_{l})]) \leq \frac{\varepsilon}{2f(n)}$ for all $l \in \{1, \ldots, k\}$.

If the current operation is \emph{Cut}, then the following hold:
\begin{enumerate}
\item By construction of the grid $\mathcal{G}_{k+1}$, agent $i$
can induce any given branch of the protocol using a cut in the continuous game if and only if the same branch
can be induced using a cut on the grid $\mathcal{G}_{k+1}$.
\item Given that the other agents will play on the grid for the remainder of the protocol, agent $i$ can change the size of at most one piece that it receives down the road
by at most
$\frac{\varepsilon}{f(n)}$ by deviating (compared to the grid outcome), since
$V_{j}([x_{l}, \mathcal{M}(x_{l})]) \leq \frac{\varepsilon}{2f(n)}$ for all $l \in \{1, \ldots, k+1\}$ and for all $j \in N$.
%That is, the cut made in the current step, $x_{k+1}$ is mapped in the remainder of the protocol to $\mathcal{M}(x_{k+1})$
%such that $V_{j}([x_{k+1}, \mathcal{M}(x_{k+1})]) \leq \frac{\varepsilon}{2f(n)}$, $\forall j \in N$.
\end{enumerate}
Thus by deviating in the current step, agent $i$ cannot gain more than $\frac{t\varepsilon}{f(n)}$. Since $t\leq f(n)$, 
the overall loss of any agent is bounded by $\varepsilon$. 
We conclude that playing on the grid is $\varepsilon$-optimal for all the agents. \qed
%Thus if agent $i$ had a deviation that improved his utility by more than $\varepsilon$ in the continuous game, he also had a big improving
%deviation on the idealized grid, which is a contradiction.


\section{Proof of Theorem~\ref{thm:obliv}}
\label{app:obliv}

We start with a lemma that crystallizes the properties of games induced by oblivious GCC protocols. 

\begin{lemma}
\label{lem:props}
An extensive-form game of perfect information that is induced by an oblivious GCC protocol enjoys the following properties:
\begin{enumerate}
\item The action space at every node of the game tree is compact.
\item Valuations are bounded. 
\item Every action space is independent of the history. 
\item The valuations $V_1,\ldots,V_n$ are continuous in the actions. 
\end{enumerate}
\end{lemma}

\begin{proof}[Proof sketch]
Properties 1 and 2 are trivially true, and also hold for GCC protocols in general. 

Properties 3 and 4 are somewhat more delicate. For property 3, we think of a \emph{Choose} step when there are $k$ available pieces between adjacent cuts as choosing a number $t\in \{1,\ldots,k\}$, and receiving the available piece that is $t$'th from the left (this can be defined precisely); note that $k$ can be calculated based on the number of cuts and choices before the choose node, i.e., it is independent of the history. 

Property 4 is only relevant when considering \emph{Cut} nodes. To establish it, first consider the action in a single \emph{Cut} node, and fix all the other actions. We claim that for every $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ \emph{that is independent of the choice of actions in other nodes} such that moving the cut by at most $\delta$ changes the values by at most $\epsilon$. 
%Using the definition of valuation functions via value density functions (Section~\ref{sec:model}), it is easy to see that the agent's value changes continuously 
Indeed, let us examine how pieces change as the cut point moves. As long as the cut point moves without passing any other cut point, one piece shrinks as another grows. As the cut point approaches another cut point, the induced piece --- say $k$'th from the left --- shrinks. When the cut point passes another cut point $x$, the $k$'th piece from the left grows larger, or it remains a singleton and another piece grows if there are multiple cut points at $x$. In any case, it is easy to verify that the sizes of various pieces received in \emph{Choose} nodes change by at most $\delta$ if the cut point is moved by $\delta$. Furthermore, note that the number of steps is bounded by $r$ and --- since the value density functions are continuous --- there is an upper bound $M$ on the value density functions such that if $y-x\leq \delta'$ then $V_i([x,y])\leq M\delta'$ for all $i\in N$. Therefore, choosing $\delta\leq \epsilon/(Mr)$ is sufficient. Finally, $V_1,\ldots,V_n$ are continuous even in the actions taken in multiple \emph{Cut} nodes, because we could move the cut points sequentially. 
\end{proof}

Note that for property 4 to be well defined, property 3 is actually required: We can fix the actions in other nodes only because the action spaces in these nodes are independent of the action at node $u$. %We also remark that property 4 implies that $V_1,\ldots,V_n$ are continuous even in the actions taken in multiple \emph{Cut} nodes, because we could move the cut points sequentially. 


%
%To begin, we require the use of a few definitions.
%
%\begin{definition}
%In an oblivious GCC protocol, let an \emph{action tuple} describe a complete sequence of actions taken by the players. In other words, an action tuple $(a_1, a_2, ..., a_r)$ states that the first action played was $a_1$, followed by $a_2$ and so on (until the end of the game was reached by the play of $a_r$).
%\end{definition}
%
%Note that by the properties of oblivious GCC protocols, that regardless of the actions played before and after the $k$th action, the player of the $k$th action and its action space is unaffected. %Importantly, the utility of said player can most definitely be affected by its surrounding decisions.
%
%\begin{definition}
%Suppose we have an action tuple $(a_1, a_2, ..., a_r)$. We say that this is a \emph{$k$-tail SPNE action tuple} if the last $k$ actions are SPNE actions, in the following sense: It is possible to complete the assignment of actions and obtain an SPNE strategy for the subtree rooted at the node where $s_{r-k+1}$ is played.
%\end{definition}

As noted above, in finite games SPNE can be found using backward induction. However, (oblivious) GCC protocols do not exhibit this finiteness and thus do not succumb to such tactics. Due to the branching of the game tree, such a notion is unwieldy in the setting of general GCC protocols, but oblivious GCC protocols allow for a far simpler analysis. In what follows, we prove that any such protocol must always have an SPNE.

To begin we require the use of some notation. Let us define $r$ to be the number of actions in the oblivious GCC protocol, and $X_i$ to be the action space of the $i$th action \emph{from the end}. For example, $X_r$ represents the possible actions that the first action can be. Note that the properties of oblivious GCC protocols allow these definitions to be well-defined.

We can now define a strategy in this context. For each $i$, let $s_i : X_{i + 1} \times X_{i + 2} \times ... \times X_r \rightarrow X_i$ describe the action a player will play given the history of actions played before. We denote by $Y_i$ the set of all possible strategies for the $i$'th action from the end.

\begin{definition}
An action tuple is a tuple of $r$ actions that describe an outcome of the protocol.
\end{definition}

Often we will find it convenient to think of strategies as actions. For example, if $s_1, s_2, ..., s_k$ are strategies, and $a_{k + 1}, a_{k + 2}, ..., a_r$ are actions, we may refer to $(s_1, s_2, ..., s_k, a_{k + 1}, a_{k + 2}, ..., a_r)$ as an action tuple. This can be thought of as equivalent to the action tuple $(a_1, a_2, ..., a_r)$ where for $i \leq k$ we have $a_i = s_i(a_{i + 1}, a_{i + 2}, ..., a_r)$.

We now take a moment to introduce the valuation functions. Let $V_i$ represent the valuation for the agent committing the $i$'th action from the end. Note that $V_i$ is not the valuation of some agent denoted by $i$, in contrast to the rest of the paper. As input, it will take an action tuple and output a value in some bounded range. 

With this idea of valuations in hand, we are now ready to define the main notion of interest.

\begin{definition}
A $k$-SPNE strategy profile is a $k$-tuple of strategies $(s_1, s_2, ..., s_k)$ where for all $i$, $s_i \in Y_i$ and the $s_i$ are SPNE. To be more explicit, we define the term recursively: The empty profile is vacuously $0$-tail SPNE, and for $k \geq 1$, the tuple is $k$-tail SPNE if the first $k - 1$ strategies in the tuple are $(k - 1)$-SPNE and for every $a_k \in X_k, a_{k + 1} \in X_{k + 1}, ..., a_r \in X_r$ we have:
\begin{align*}
V_k(s_1, s_2, ..., s_k, a_{k + 1}, a_{k + 2}, ..., a_r) \geq V_k(s_1, s_2, ..., s_{k - 1}, a_k, a_{k + 1}, ..., a_r).
\end{align*}
A $k$-SPNE action tuple is an action tuple such that the last $k$ actions can be induced by a $k$-SPNE strategy profile. That is $(a_1, a_2, ..., a_r)$ is $k$-SPNE if there exists a $k$-SPNE strategy profile $(s_1, s_2, ..., s_k)$ such that:
\begin{align*}
(a_1, a_2, ..., a_{k - 1}, a_k, a_{k + 1}, ..., a_r) = (s_1, s_2, ..., s_{k - 1}, s_k, a_{k + 1}, ..., a_r)
\end{align*}
\end{definition}

Note that the classical definition of SPNE is equivalent in our setting to the existence of an $r$-SPNE strategy profile. With the notation and definitions out of the way, we begin our proof of the theorem. We start with the following lemma.

\begin{lemma}
\label{lem:jeef}
Any convergent sequence of $k$-SPNE action tuples converges to a $k$-SPNE action tuple.
\end{lemma}
\begin{proof}
We proceed by induction.
\begin{enumerate}
\item Base Case ($k = 0$): This is vacuously true by the definition of $0$-SPNE action tuples.
\item Inductive Assumption ($k = m - 1$): Assume we have shown that the result is true for $k = m - 1$.
\item Inductive Step ($k = m$):\\
We are given that for every $i$ we have an $m$-SPNE action tuple:
\begin{align*}
A^i = (s^i_1, s^i_2, ..., s^i_m, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r)
\end{align*}
where the $s_j$ are strategies such that $(s^i_1, s^i_2, ..., s^i_m)$ is $m$-SPNE and the $a^i_j$ are actions. Furthermore, we are given that the sequence $\{A^i\}_i$ converges to some action tuple $A = (a_1, a_2, ..., a_r)$. We wish to show $A$ is an $m$-SPNE action tuple itself.

Since any $m$-SPNE action tuple is an $(m - 1)$-SPNE action tuple, we know that the $A^i$ are $(m - 1)$-SPNE action tuples and thus, by the inductive assumption, so too is $A$. Suppose the $(m - 1)$-SPNE strategy profile $S = (s_1, s_2, ..., s_{m - 1})$ induces $A$. That is, $A = (s_1, s_2, ..., s_{m - 1}, a_k, a_{k + 1}, ..., a_r)$.

Now for every $\alpha \in X_m$, let us replace $s^i_{m}$ with the constant function $\tilde{s}^i_{m} = \alpha$ in the sequence $\{A^i\}_i$. Let $\{B^i\}_i$ be the resulting sequence of action tuples and call this the \emph{completion} for $\alpha$. Due to the compactness of the action spaces, there exists some convergent subsequence of $\{B^i\}_i$. Denote by $I^\alpha$ the indices of such a convergent subsequence of $\{B^i\}_i$. That is, the definition $B = \lim_{i \in I^\alpha, i \rightarrow \infty} B^i$ is well defined. As this subsequence is a convergent sequence of $(m - 1)$-SPNE action tuples, we have by the inductive assumption that there exists some $(m - 1)$-SPNE strategy profile $(t^\alpha_1, t^\alpha_2, ..., t^\alpha_{m - 1})$ that induces $B$.

We are now ready to construct the desired strategy profiles $t_i : X_{i + 1} \times X_{i + 2} \times ... \times X_r \rightarrow X_i$.

For $i < m$, define $t_i$ as:
\begin{equation*}
t_i(x_{i + 1}, x_{i + 2}, ..., x_r)
= \begin{cases}
t^{x_m}_i(x_{i + 1}, x_{i + 2}, ..., x_r) & \text{if $x_m \neq a_m$ and for all $j > m: x_j = a_j$}\\
s_i(x_{i + 1}, x_{i + 2}, ..., x_r) & \text{if for all $j \geq m: x_j = a_j$}\\
s^1_i(x_{i + 1}, x_{i + 2}, ..., x_r) & \text{otherwise.}
\end{cases}
\end{equation*}
Define $t_m$ as:
\begin{equation*}
t_m(x_{m + 1}, x_{m + 2}, ..., x_r)
= \begin{cases}
a_m & \text{if for all $j > m: x_j = a_j$} \\
s^1_m(x_{m + 1}, x_{m + 2}, ..., x_r) & \text{otherwise.}
\end{cases}
\end{equation*}

We claim that the strategy profile $T = (t_1, t_2, ..., t_m)$ is $m$-SPNE. If the actions $x_j \in X_j$ for $j \geq m$ are fixed, then by the definition of $t_i$ for $i < m$, we have that $(t_1, t_2, ..., t_{m - 1})$ is one of $(t^{x_m}_1, t^{x_m}_2, ..., t^{x_m}_{m - 1})$, $(s_1, s_2, ..., s_{m - 1})$, or $(s^1_1, s^1_2, ..., s^1_{m - 1})$. Regardless, it is equivalent to some $(m - 1)$-SPNE strategy profile, and so $T$ therefore is $(m - 1)$-SPNE as well. To show that $T$ is $m$-SPNE it only remains to show that $t_m$ is weakly optimal. Before we show this, we make an observation. For all $\alpha \in X_m$, its completion $\{(b^i_1, b^i_2, ..., b^i_r)\}_i$, and subsequent $i \in I^\alpha$ we have:
\begin{align*}
V_m(s^i_1, s^i_2, ..., s^i_{m - 1}, s^i_m, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r)
%ap replaced x_m with \alpha
&\geq V_m(s^i_1, s^i_2, ..., s^i_{m - 1}, \alpha, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r)\\
&= V_m(b^i_1, b^i_2, ..., b^i_{m - 1}, b_m, b^i_{m + 1}, b^i_{m + 2}, ..., b^i_r)
\end{align*}
In particular, this (along with continuity of $V_m$) implies that:
\begin{align*}
&\lim_{i \rightarrow \infty} V_m(s^i_1, s^i_2, ..., s^i_{m - 1}, s^i_m, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r)\\
&\geq \lim_{i \in I, i \rightarrow \infty} V_m(b^i_1, b^i_2, ..., b^i_{m - 1}, b_m, b^i_{m + 1}, b^i_{m + 2}, ..., b^i_r)
\end{align*}
Now suppose $x_m \in X_m, x_{m + 1} \in X_{m + 1}, ..., x_r \in X_r$ are fixed and that the $\{(b^i_1, b^i_2, ..., b^i_r)\}_i$ are the completion for $x_m$. If for all $j > m$ we have that $x_j = a_j$, then we see that:
\begin{align*}
&V_m(t_1, t_2, ..., t_{m - 1}, t_m, x_{m + 1}, x_{m + 2}, ..., x_r)\\
&= V_m(t_1, t_2, ..., t_{m - 1}, t_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= V_m(t_1, t_2, ..., t_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= V_m(s_1, s_2, ..., s_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= V_m(a_1, a_2, ..., a_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= \lim_{i \rightarrow \infty} V_m(s^i_1, s^i_2, ..., s^i_{m - 1}, a^i_m, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r) \text{ (by the continuity of $V_m$)}\\
&= \lim_{i \rightarrow \infty} V_m(s^i_1, s^i_2, ..., s^i_{m - 1}, a^i_m, a^i_{m + 1}, a^i_{m + 2}, ..., a^i_r)\\
&\geq \lim_{i \in I, i \rightarrow \infty} V_m(b^i_1, b^i_2, ..., b^i_{m - 1}, b_m, b^i_{m + 1}, b^i_{m + 2}, ..., b^i_r) \text{ (by the observation)}\\
&= V_m(b_1, b_2, ..., b_{m - 1}, b_m, b_{m + 1}, b_{m + 2}, ..., b_r) \text{ (by the continuity of $V_m$)}\\
&= V_m(b_1, b_2, ..., b_{m - 1}, x_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= V_m(t^{x_m}_1, t^{x_m}_2, ..., t^{x_m}_{m - 1}, x_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= V_m(t^{x_m}_1, t^{x_m}_2, ..., t^{x_m}_{m - 1}, x_m, x_{m + 1}, x_{m + 2}, ..., x_r)\\
&= V_m(t_1, t_2, ..., t_{m - 1}, x_m, x_{m + 1}, x_{m + 2}, ..., x_r)
\end{align*}
If on the other hand we have that there exists some $j > m$ for which $x_j \neq a_j$, then we see that $(t_1, t_2, ... t_m)$ is equivalent to $(s^1_i, s^1_2, ..., s^1_m)$ --- which is $m$-SPNE. Therefore, $T$ is $m$-SPNE.

All that remains to prove is that $A$ is indeed induced by the strategy profile $T$. The following shows exactly this.
\begin{align*}
(t_1, t_2, ..., t_{m - 1}, t_m, a_{m + 1}, a_{m + 2}, ..., a_r)
&= (t_1, t_2, ..., t_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= (s_1, s_2, ..., s_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)\\
&= (a_1, a_2, ..., a_{m - 1}, a_m, a_{m + 1}, a_{m + 2}, ..., a_r)
\end{align*}
This completes the proof.
\end{enumerate}
\end{proof}

We are now ready for our main result.

\begin{lemma}
Every oblivious GCC protocol has a $k$-SPNE strategy profile for every $k\leq r$.
\begin{proof}

Again, we proceed by induction.
\begin{enumerate}
\item Base Case ($k = 0$): This is vacuously true by the definition of $0$-SPNE strategy profile.
\item Inductive Assumption ($k = m - 1$): Assume we have shown that the result is true for $k = m - 1$.
\item Inductive Step ($k = m$):\\
We wish to construct an $m$-SPNE strategy profile $(t_1, t_2, ..., t_m)$. By the inductive assumption, we know there exists some $(m - 1)$-SPNE strategy profile $(s_1, s_2, ..., s_{m - 1})$. In addition, let $x_{m + 1} \in X_{m + 1}, x_{m + 2} \in X_{m + 2}, ..., x_r \in X_r$ be fixed. As $V_m$ is bounded, % by the least-upper-bound property of $\mathbb{R}$ we know the definition
we know that
\begin{align*}
SUP = \sup\{V_m(s_1, s_2, ..., s_{m - 1}, x_m, x_{m + 1}, ..., x_r) \mid x_m \in X_m\}
\end{align*}
is well-defined. Via the continuity of $V_m$, we can then construct a sequence $\{x^i_m\}_i$ such that:
\begin{align*}
\lim_{i \rightarrow \infty} V_m(s_1, s_2, ..., s_{m - 1}, x^i_m, x_{m + 1}, x_{m + 2}, ..., x_r) = SUP.
\end{align*}
Now note that the sequence of action tuples $\{(s_1, s_2, ..., s_{m - 1}, x^i_m, x_{m + 1}, x_{m + 2}, ..., x_r)\}_i$ is a sequence in a compact space and thus, has a convergent subsequence. Via use of a possible redefinition, assume the sequence itself converges. Then by Lemma \ref{lem:jeef}, we know that this convergent sequence of $(m - 1)$-SPNE action tuples converges to an $(m - 1)$-SPNE action tuple induced by some $(m - 1)$-SPNE strategy profile $(\tilde{s}_1, \tilde{s}_2, ..., \tilde{s}_{m - 1})$.

Suppose that the desired strategy profiles $t_i$ satisfy the following. For $i < m$, $t_i$ satisfies:
\begin{align*}
t_i(x_{i + 1}, x_{i + 2}, ..., x_r)
= \begin{cases}
\tilde{s}_i(x_{i + 1}, x_{i + 2}, ..., x_r) & \text{if $x_m = \lim_{i \rightarrow \infty} x^i_m$}\\
s_i(x_{i + 1}, x_{i + 2}, ..., x_r) & \text{otherwise,}
\end{cases}
\end{align*}
and $t_m$ satisfies:
\begin{align*}
t_m(x_{m + 1}, x_{m + 2}, ..., x_r) = \lim_{i \rightarrow \infty} x^i_m.
\end{align*}

Clearly, $(t_1, t_2, ..., t_{m - 1})$ is $(m - 1)$-SPNE since for the fixed $x_j \in X_j$, for $j \geq m$, it is equivalent to some other $(m - 1)$-SPNE strategy profile. It therefore suffices to show that  $t_m$ is weakly optimal. This is true as we have for every $a_m \in X_m$ where $a_m \neq \lim_{i \rightarrow \infty} x^i_m$:
\begin{align*}
&V_m(t_1, t_2, ..., t_{m - 1}, t_m, x_{m + 1}, x_{m + 2}, ..., x_r)\\
&= V_m(\tilde{s}_1, \tilde{s}_2, ..., \tilde{s}_{m - 1}, t_m, x_{m + 1}, x_{m + 2}, ..., x_r)\\
&= \lim_{i \rightarrow \infty} V_m(s_1, s_2, ..., s_{m - 1}, x^i_m, x_{m + 1}, x_{m + 2}, ..., x_r) \text{ (by the continuity of $V_m$)}\\
&= \sup\{V_m(s_1, s_2, ..., s_{m - 1}, x_m, x_{m + 1}, x_{m + 2} ..., x_r) \mid x_m \in X_m\}\\
&\geq V_m(s_1, s_2, ..., s_{m - 1}, a_m, x_{m + 1}, x_{m + 2} ..., x_r)\\
&= V_m(t_1, t_2, ..., t_{m - 1}, a_m, x_{m + 1}, x_{m + 2} ..., x_r)
\end{align*}
\end{enumerate}
\end{proof}
\end{lemma}

From the above lemma, we see immediately that every bounded oblivious GCC protocol has an $r$-SPNE (where $r$ is the number of actions), and thus has an SPNE. This completes the theorem's proof.\qed


\end{document}












1307.2225.extracted_bib
\begin{thebibliography}{10}

\bibitem{BN09}
L.~Blumrosen and N.~Nisan.
\newblock On the computational power of demand queries.
\newblock {\em SIAM Journal on Computing}, 39(4):1372â€“--1391, 2009.

\bibitem{BT96}
S.~J. Brams and A.~D. Taylor.
\newblock {\em Fair Division: From Cake-Cutting to Dispute Resolution}.
\newblock Cambridge University Press, 1996.

\bibitem{BM13}
S.~Br\^anzei and P.~B. Miltersen.
\newblock Equilibrium analysis in cake cutting.
\newblock In {\em Proceedings of the 12th International Joint Conference on
  Autonomous Agents and Multi-Agent Systems (AAMAS)}, pages 327--334, 2013.

\bibitem{CLPP13}
Y.~Chen, J.~K. Lai, D.~C. Parkes, and A.~D. Procaccia.
\newblock Truth, justice, and cake cutting.
\newblock {\em Games and Economic Behavior}, 77:284--297, 2013.

\bibitem{Dob07}
S.~Dobzinski.
\newblock Better mechanisms for combinatorial auctions via maximal-in-range
  algorithms?
\newblock {\em SIGecom Exchanges}, 7(1):30--33, 2007.

\bibitem{DS61}
L.~E. Dubins and E.~H. Spanier.
\newblock How to cut a cake fairly.
\newblock {\em American Mathematical Monthly}, 68(1):1--17, 1961.

\bibitem{EP06b}
J.~Edmonds and K.~Pruhs.
\newblock Balanced allocations of cake.
\newblock In {\em Proceedings of the 47th Symposium on Foundations of Computer
  Science (FOCS)}, pages 623--634, 2006.

\bibitem{EP06}
J.~Edmonds and K.~Pruhs.
\newblock Cake cutting really is not a piece of cake.
\newblock In {\em Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 271--278, 2006.

\bibitem{EP84}
S.~Even and A.~Paz.
\newblock A note on cake-cutting.
\newblock {\em Discrete Applied Mathematics}, 7:285--296, 1984.

\bibitem{Fort09}
L.~Fortnow.
\newblock Program equilibria and discounted computation time.
\newblock In {\em Proceedings of the 12th Conference on Theoretical Aspects of
  Rationality and Knowledge (TARK)}, pages 128--133, 2009.

\bibitem{Harr85}
C.~Harris.
\newblock Existence and characterization of perfect equilibrium in games of
  perfect information.
\newblock {\em Econometrica}, 53(3):613--628, 1985.

\bibitem{HN13}
S.~Hart and N.~Nisan.
\newblock The query complexity of correlated equilibria.
\newblock CoRR abs/1305.4874, 2013.

\bibitem{HL87}
H.~Hellwig and W.~Leininger.
\newblock On the existence of subgame-perfect equilibrium in infinite-action
  games of perfect information.
\newblock {\em Journal of Economic Theory}, 45:55--75, 1987.

\bibitem{KLP13}
D.~Kurokawa, J.~K. Lai, and A.~D. Procaccia.
\newblock How to cut a cake before the party ends.
\newblock In {\em Proceedings of the 27th AAAI Conference on Artificial
  Intelligence (AAAI)}, 2013.
\newblock Forthcoming.

\bibitem{Mask99}
E.~Maskin.
\newblock Nash equilibrium and welfare optimality.
\newblock {\em Review of Economic Studies}, 66:23--38, 1999.
\newblock First circulated in 1977.

\bibitem{MN12}
A.~Maya and N.~Nisan.
\newblock Incentive compatible two player cake cutting.
\newblock In {\em Proceedings of the 8th International Workshop on Internet and
  Network Economics (WINE)}, pages 170--183, 2012.

\bibitem{MT10}
E.~Mossel and O.~Tamuz.
\newblock Truthful fair division.
\newblock In {\em Proceedings of the 3rd International Symposium on Algorithmic
  Game Theory (SAGT)}, pages 288--299, 2010.

\bibitem{Ny08}
A.~Nicol\`o and Y.~Yu.
\newblock Strategic divide and choose.
\newblock {\em Games and Economic Behavior}, 64(1):268--289, 2008.

\bibitem{Pro09}
A.~D. Procaccia.
\newblock Thou shalt covet thy neighbor's cake.
\newblock In {\em Proceedings of the 21st International Joint Conference on
  Artificial Intelligence (IJCAI)}, pages 239--244, 2009.

\bibitem{Pro13}
A.~D. Procaccia.
\newblock Cake cutting: Not just child's play.
\newblock {\em Communications of the ACM}, 56(7):78--87, 2013.

\bibitem{RW98}
J.~M. Robertson and W.~A. Webb.
\newblock {\em Cake Cutting Algorithms: Be Fair If You Can}.
\newblock A. K. Peters, 1998.

\bibitem{SL08}
Y.~Shoham and K.~Leyton-Brown.
\newblock {\em Multiagent Systems: Algorithmic, Game-Theoretic, and Logical
  Foundations}.
\newblock Cambridge University Press, 2008.

\bibitem{Strom80}
W.~Stromquist.
\newblock How to cut a cake fairly.
\newblock {\em American Mathematical Monthly}, 87(8):640--644, 1980.

\bibitem{Ten04b}
M.~Tennenholtz.
\newblock Program equilibrium.
\newblock {\em Games and Economic Behavior}, 49(2):363--373, 2004.

\bibitem{WS07}
G.~J. Woeginger and J.~Sgall.
\newblock On the complexity of cake cutting.
\newblock {\em Discrete Optimization}, 4:213--220, 2007.

\bibitem{Zhou91}
L.~Zhou.
\newblock Inefficiency of strategy-proof allocation mechanisms in pure exchange
  economies.
\newblock {\em Social Choice and Welfare}, 8:247--254, 1991.

\end{thebibliography}