\section{Introduction}








	Cake cutting is one the most fundamental topics in fair division~\citep[see \eg][]{Proc12a,BrTa96a,RoWe98a}. It concerns the setting in which a cake is represented by an interval $[0,1]$ and each of the $n$ agents has a value function over the cake. The main aim is to divide the cake fairly. 
	The framework is general enough to encapsulate the important problem of allocating a heterogeneous divisible good among multiple agents with different preferences.
	The cake cutting problem applies to many settings including the division of rent among housemates, disputed land between land-owners, and work among co-workers. It is especially useful in scheduling the use of a valuable divisible resource such as server time. 



	Within the cake cutting literature, the most important criteria of a fair allocation are \emph{envy-freeness} and \emph{proportionality}.  In an envy-free allocation, each agent considers his allocation at least as good as any other agent's allocation. An envy-free allocation is guaranteed to exist~\citep[see \eg][]{Stro80a, Su99a}. In a proportional allocation, each agent gets at least $1/n$ of the value he assigns to the cake. A desirable aspect of envy-freeness is that it implies proportionality.\footnote{This statement holds with the additional assumption of \emph{full allocation}: that every portion of the cake that is desired by at least one agent is allocated to some agent.  Otherwise, the empty allocation satisfies envy-freeness, but not proportionality.}


	Computation of a fair allocation of cake is one of the fundamental problems in algorithmic economics. \citet{BrTa95a}  designed an envy-free cake cutting algorithm for an arbitrary number of players. Although their algorithm is guaranteed to eventually terminate, its running time is unbounded. Moreover, the algorithm can divide the cake into infinitely small segments. 
	Since the result of \citet{BrTa95a}, researchers have examined restricted value density functions and proposed envy-free algorithms for them. 

In order to ascertain the running time of a cake cutting algorithm, it is important to know the computational model and input to the problem. In most of the literature~\citep[see \eg][]{RoWe98a}, it is assumed that the value an agent ascribes to any segment of the cake can be queried or evaluated via an oracle. While the classical literature uses this query model, computer scientists recently looked at the problem from the point of view of full report, as is common in mechanism design.
Throughout the paper we focus on \emph{piecewise constant value density functions} and \emph{piecewise uniform value density functions}. 
Piecewise constant value density functions are one of the most fundamental class of value functions. Piecewise uniform valuations are a restricted class of piecewise constant valuations. 

	\citet{CLPP10a, CLPP12a} presented a discrete, strategyproof, polynomial-time, envy-free and Pareto optimal algorithm for piecewise uniform valuations. They stated that generalizing their results for piecewise constant valuations is an open problem. They also presented an envy-free and proportional algorithm that satisfies strategyproofness by resorting to randomization. 
	
	



In this paper, we consider three of the most enduring goals in mechanism design and fair division: fairness, Pareto optimality and strategyproofness. Since many fair division algorithms need to be deployed on a large scale, we will also aim for algorithms that are \emph{computationally} efficient. Our main research question in this paper is as follows: \emph{among the different levels of fairness, Pareto optimality, strategyproofness, and efficient computability, what are the maximal set of properties that can be satisfied simultaneously for piecewise constant and piecewise uniform valuations?} Our main contribution is a detailed study of this question including the formulation of a number of desirable cake cutting algorithms satisfying many of the properties.

In the case where Pareto optimality cannot be satisfied, we also consider a weaker notion of efficient called \emph{non-wastefulness}. Non-wastefulness dictates that every portion of the cake that is desired by at least one agent is allocated to some agent who desires it.

For fairness, we not only consider the standard notions envy-freeness and proportionality but we also propose the concept of \emph{robust fairness} --- in particular \emph{robust envy-freeness} and \emph{robust proportionality}. The main idea of an allocation being robust envy-free is that even if an agent readjusts his value density function, as long as the ordinal information of the function is unchanged, then the allocation remains envy-free. The main advantages of robust envy-freeness are less information requirements and envy-freeness under uncertainty. 
\footnote{Although full information is a standard assumption in cake cutting, it can be argued that it is unrealistic that agents have exact utility value for each segment of the cake. Even if they do report exact utility values, they may be uncertain about these reports. Robust fairness bypasses these issues.}

For strategic properties, we consider three notions of truthfulness namely strategyproofness, weak group-strategyproofness and group-strategyproofness. In most of the cake-cutting literature, an algorithm is considered `strategyproof' if truth-telling is a maximin strategy~\citep{Bram08a} and it need not be dominant strategy incentive compatible. When we refer to strategyproofness, we will mean the reporting the truthful valuations is a dominant strategy. This stronger notion of strategyproofness has largely been ignored in cake-cutting barring a few recent exceptions~\citep{CLPP10a, CLPP12a, MoTa10a,MaNi12a}. 	\footnote{\citet{Proc12a} writes that the ``design of strategyproof cake cutting algorithms is largely an open problem.''}























	

	















	
	We present \emph{CCEA (Controlled Cake Eating Algorithm)} for piecewise constant valuations and show that it is polynomial-time and robust envy-free and robust proportional. 
	CCEA depends on a reduction to the  generalizations~\citep{AtSe11a,KaSe06a} of the \emph{PS (probabilistic serial)} algorithm introduced by \citet{BoMo01a} in the context of random assignments.\footnote{The CC algorithm of \citet{AtSe11a} is a generalization of the EPS algorithm \citep{KaSe06a} which in turn is a generalization of PS algorithm of \citet{BoMo01a}.} The algorithm relies on solving the parametric network flows~\citep[see \eg][]{GGT89a}.
	We show that the algorithm can handle variable claims and private endowments for piecewise constant valuations and also satisfies group-strategyproofness under piecewise uniform valuations.
	
	
		If we insist on Pareto optimality, then we show that there exists an algorithm which we refer to as the \emph{MEA (Market Equilibrium Algorithm)}  that is discrete, polynomial-time Pareto optimal, envy-free, and proportional for piecewise constant valuations. The algorithm relies on the Walras equilibrium formulation of \citet{RePo98a} for finding an $\alpha$-envy-free for general cake cutting valuations and the result of \citet{DPSV08a} that market equilibrium for Fischer markets with linear utilities can be computed in polynomial time. Both CCEA and MEA not only coincide on piecewise uniform valuations but are also group-strategyproof.
	
	Although CCEA and MEA are desirable algorithms, they are not strategyproof for piecewise constant valuations.
		           We present another algorithm called \textit{CSD (Constrained Serial Dictatorship)} which is strategyproof in expectation, robust proportional, and satisfies unanimity. For the important case of two agents\footnote{Many fair division problems involve disputes between two parties.}, it is polynomial-time,  and robust envy-free. To the best of our knowledge, it is the first cake cutting algorithm for piecewise constant valuations that satisfies strategyproofness, proportionality, and unanimity at the same time. CSD requires some randomization to achieve strategyproof in expectation. However, CSD is discrete in the sense that it gives the same utility guarantee (with respect to the reported valuation functions) over all realizations of the random allocation. Although CSD uses some essential ideas of the well-known \emph{serial dictatorship} rule for discrete allocation, it is significantly more involved.
		
		
		
	
          

	

	




	Our main technical results are as follows.




	\begin{theorem}\label{th:maintheorem1}
		For cake cutting with piecewise constant valuations, 
		there exists an algorithm (CCEA) that is discrete, polynomial-time, robust envy-free, and non-wasteful. 
	
	
	
	
	
	
	
	
	
	
	
	
		\end{theorem}



		



		
			\begin{theorem}\label{th:maintheorem3}
		For cake cutting with with piecewise constant valuations, there exists an algorithm (MEA)  that is discrete, polynomial-time, Pareto optimal, and envy-free.
\end{theorem}

	\begin{theorem}\label{th:maintheorem2}
		For cake cutting with piecewise uniform valuations,
		there exists algorithms (CCEA and MEA) that are discrete, 
	group strategyproof, polynomial-time, robust envy-free and Pareto optimal.
		\end{theorem}
		
		\begin{theorem}\label{th:maintheorem1b}
									For cake cutting with piecewise constant valuations, there exists a randomized implemention of an algorithm (CSD) that is (ex post) robust proportional, (ex post) symmetric, and (ex post) unanimous and strategyproof in expectation. For two agents, it is polynomial-time, robust proportional and robust envy-free.
					
		
			
			
		
		
		
		
		
		
		
		
			\end{theorem}


\noindent Our positive results are complemented by the following impossibility results. These impossibility results suggest the properties satisfied by CCEA and MEA are maximal subsets of properties that can be satisfied by any algorithm for piecewise constant valuation profiles.
 
\begin{theorem} \label{PE fair impossibility}
For piecewise constant valuation profiles with at least two agents, there exists no algorithm that is both Pareto optimal and robust proportional.
\end{theorem}

\begin{theorem} \label{PE SP Prop impossibility}
For piecewise constant valuation profiles with at least two agents, there exists no algorithm that is strategyproof, Pareto optimal, and proportional. 
\end{theorem}


\begin{theorem} \label{SP Rob Prop Non W impossibility}
For piecewise constant valuation profiles with at least two agents, there exists no algorithm that is strategyproof, robust proportional, and non-wasteful. 
\end{theorem}


As a consequence of CCEA and MEA, we generalize the positive results regarding piecewise uniform valuations in \citep{CLPP10a,CLPP12a} and piecewise constant valuations in \citep{CLPP11a} in a number of ways such as handling richer cake cutting settings, handling more general valuations functions, achieving a stronger envy-free concept, or a stronger strategyproofness notion.  
Moreover, we prove that CCEA and MEA --- two different algorithms --- are equivalent in the domain of piecewise constant valuations. Furthermore, we show that both CCEA and MEA are generalizations of the main mechanism in \citep{CLPP12a, CLPP10a}.
We also show which combinations of properties are impossible to satisfy simultaneously.
Some of our main results are summarized in Table~\ref{table:summary:cake}


		\begin{table}[t!]

		\centering
			\scalebox{0.8}{
	\centering

	\begin{tabular}{l|lccccccccccc}
	\toprule
		

	&Restriction&DISC&R-EF&EF&R-PROP&PROP&GSP&W-GSP&SP&PO&UNAN&POLYT\\
	Algorithms&&&\\
	\midrule
	CCEA&-&+&+&+&+&+&-&-&-&-&+&+\\
	CCEA&pw uniform&+&+&+&+&+&+&+&+&+&+&+\\


	
		\midrule
	MEA&&+&-&+&-&+&-&-&-&+&+&+\\
	MEA&pw uniform&+&+&+&+&+&+&+&+&+&+&+\\
	
	\midrule

		CMSD&-&-&-&-&+&+&-&-&+&-&+&-\\
		CMSD&pw uniform&-&-&-&+&+&-&-&+&+&+&-\\

		CMSD&2 agents&-&+&+&+&+&-&-&+&-&+&+\\











	




	\bottomrule
	\end{tabular}
	}

		\caption{Properties satisfied by the cake cutting algorithms for pw (piecewise) constant valuations:  DISC (discrete), R-EF (robust envy-freeness), EF (envy-freeness), R-PROP (robust proportionality), PROP (proportionality), GSP (group strategyproof), W-GSP (weak group strategyproof), SP (strategyproof), UNAN (unanimity), PO (Pareto optimal) and POLYT (polynomial-time).
		}

	\label{table:summary:cake}
	\end{table}

After presenting our main results, we enrich the cake cutting domain in two ways. We allow agents to have initial endowments of the cake. Moreover we consider the more general setting in which agents may have different claims or entitlements to the cake. We show that many of our results carry over to these more general settings.





	
	
		
		
			
	









	
	

			
	
	

		
		
		
					
	
	





	




	
	
	
	
	
	
	
		
	
		
			
	
	
	
	
	


	
	
		
	
	
	
	
	



	
		




	






















	



	


























	\section{Preliminaries}



	\subsection{Cake cutting setting}
	We consider a cake which is represented by the interval $[0,1]$.
	A \emph{piece of cake} is a finite union of disjoint subintervals of $[0,1]$. The length of an interval $I=[x,y]$ is  $len(I)=y-x$.  As usual, the set of agents is $N=\{1,\ldots, n\}$. Each agent has a piecewise continuous \emph{value density function} $v_i:[0,1]\rightarrow [0,\infty]$. The value of a piece of cake $X$ to agent $i$ is $V_i(X)=\int_{X}v_i(x)dx=\sum_{I\in X}\int_Iv_i(x)dx$. As generally assumed, valuations are non-atomic ($V_i([x,x])=0$)
and additive: $V_i(X\cup Y)=V_i(X)+V_i(Y)$ where $X$ and $Y$ are disjoint. 
	The basic cake cutting setting can be represented by the set of agents and their valuations functions, which we will denote as \emph{a profile of valuations}. In this paper we will assume that each agent's valuation function is private information for the agent that is not known to the algorithm designer. Each agent reports his valuation function to the designer and the designer then decides how to make the allocations based on the reported valuations.
	
	
Later on we will also consider two important extensions of cake cutting: claims and private endowments.	We will assume that agents have the following \emph{claims} on the cake respectively: $c_1,\ldots, c_n$. In the original cake cutting problem agents have equal claims. 
	Each agent $i\in N$ has a \emph{private endowment} $\omega(i)$ which is a segment of the cake privately owned by $i$.  The cake is assembled by joining the pieces $\omega(1), \ldots, \omega(n)$.
	Therefore the cake cutting setting in its full generality can be represented as a quadruple $(N,v,\omega,c)$.


	An allocation is a partitioning of the cake into $n$ pieces of cake  $X_1,\ldots, X_n$ such that the pieces are disjoint (aside from the interval boundaries) and $X_i$ is allocated to agent $i\in N$. A cake cutting algorithm takes as input $(N,v,\omega,c)$ and returns an allocation.

	\subsection{Preference functions}

In this paper we will only consider \emph{piecewise uniform} and \emph{piecewise constant} valuations functions. A function is \emph{piecewise uniform} if the cake can be partitioned into a finite number of intervals such that for some constant $k_i$, either $v_i(x)=k_i$ or $v_i(x)=0$ over each interval. A function is \emph{piecewise constant} if the cake can be partitioned into a finite number of intervals such that $v_i$ is constant over each interval. In order to report his valuation function to the algorithm designer, each agent will specify a set of points $\{d_1, ... , d_m\}$ that represents the consecutive points of discontinuity of the agent's valuation function as well as the constant value of the valuation function between every pair of consecutive $d_j$'s. 





	For a function $v_i$, we will refer by $\hat{V_i}=\{v_i'\midd v_i(x)\geq v_i(y)>0 \iff  v_i'(x)\geq v_i'(y)>0 ~~\forall x,y\in [0,1]\}$ as the set of density functions \emph{ordinally equivalent} to $v_i$. 

	Note that if an algorithm takes as input $v_i$ and returns the same output for any $v_i'\in \hat{V_i}$, then it is oblivious to the exact cardinal information of $v_i$.



	\subsection{Properties of allocations}


           An \emph{allocation} is a partition of the interval $[0,1]$ into a set $\{X_1,\ldots, X_n, W\}$, where $n$ is the number of agents and $X_i$ is a piece of cake that is allocated to agent $i$. And $W$ is the piece of the cake that is not allocated. All of the fairness and efficiency notations that we will discuss next are with respect to the reported valuation functions.
	In an \emph{envy-free allocation}, we have $ V_i(X_i)\geq V_i(X_j)$ for each pair of agent $i,j\in N$,. An allocation is \emph{individually rational} if $V_i(X_i)\geq V_i(\omega(i))$. In a \emph{proportional} allocation, each agent gets at least $1/n$ of the value he has for the entire cake. An allocation satisfies \emph{symmetry or equal treatment of equals} if any two agents with identical valuations get same utility. Clearly, envy-free implies proportionality and also symmetry. An allocation $X$ is \emph{Pareto optimal} if no agent can get a higher value without some other agent getting less value. Formally, $X$ is Pareto optimal if there does not exists another allocation $Y$ such that $V_i(Y_i)\geq V_i(X_i)$ for all $i\in N$ and $V_i(Y_i)> V_i(X_i)$ for some $i\in N$. For any $S \subseteq [0,1]$, define $D(S) = \{i \in N | V_i(S) > 0\}$. An allocation $X$ is \emph{non-wasteful} if for all $S \subseteq [0,1]$, $S \subseteq \cup_{i \in D(S)} X_i$. In other words, an allocation is non-wasteful if every portion of the cake desired by at least one agent is allocated to some agent who desires it.


	
	


	We now define robust analogues of the fairness concepts defined above. 
		An allocation satisfies \emph{robust proportionality} if for all $i,j\in N$ and for all $v_i'\in \hat{V_i}$, $\int_{X_i}v_i'(x)dx\geq 1/n\int_{0}^{1}v_i'(x)dx$.
		An allocation satisfies \emph{robust envy-freeness} if for all $i,j\in N$ and for all $v_i'\in \hat{V_i}$, $\int_{X_i}v_i'(x)dx\geq \int_{X_j}v_i'(x)dx$.
			Notice that both robust envy-freeness and robust proportionality would require each agents to get a piece of cake of the same length if every agent desires the entire cake.
		








	We give an example of piecewise constant value density function and demonstrate how the standard concept of envy-freeness is not robust under uncertainty. 

	\begin{example}[A cake-cutting problem with piecewise constant valuations]\label{example:piecewise}
	Consider the cake cutting problem in Figure~\ref{figure:piecewise}
	An allocation in which both agents get regions in which their value density function is the highest is envy-free. Agent 1 gets utility one for his allocation and has the same utility for the allocation of agent 2.  However if its probability density function is slightly lower in region $[0,0.1]$, then agent 1 will be envious of agent 2.
	\end{example}
\vspace{-3em}
	 \begin{figure}
	 \centering
	 	\[	
	 			\begin{tikzpicture}[scale=0.2]
	 				\centering
	 				\draw[-] (0,-.5) -- (0,15);     
	 				\draw[-] (-.5,0) -- (20,0);



	 			
	 			
	 			
	 			
	 				\draw[-] (20,15) -- (20,0);

	 				
	 				
	 				
	 				
	 				



	 							\fill[pattern=vertical lines,] (0,0) rectangle (2,15);
	 							\fill[pattern=vertical lines] (10,0) rectangle (20,5);
	 							\fill[pattern=horizontal lines] (6,0) rectangle (20,7.5);



	 							\draw (2,-.6) node(c){\small $0.1$};
	 							\draw (6,-.6) node(c){\small $0.3$};
	 							\draw (20/2,-.6) node(c){\small $0.5$};
	 					
	 					
	 					
	 							\draw (20,-.6) node(c){\small$1$};

	 				\draw(-.7,15) node(z){\small $10$};
	 				\draw(-.7,7.5) node(z){\small $3$};
	 				\draw(-.7,5) node(z){\small $2$};





	 				\end{tikzpicture}
	 		\]
	 \caption{Example of a cake cutting problem with piecewise constant value density functions. The area with vertical lines is under the value density function of agent $1$ and the area with horizontal lines is under the value density function of agent $2$.}
	 
	\label{figure:piecewise}
	 \end{figure}



	 \begin{figure}
	 \centering
	 	\[	
	 			\begin{tikzpicture}[scale=0.20]
	 				\centering
	 				\draw[-] (0,-.5) -- (0,15);     
	 				\draw[-] (-.5,0) -- (20,0);



	 			
	 			
	 			
	 			
	 				\draw[-] (20,15) -- (20,0);

	 				
	 				
	 				
	 				
	 				



	 							\fill[pattern=vertical lines,] (0,0) rectangle (2,10);
	 							\fill[pattern=vertical lines] (10,0) rectangle (20,5);
	 							\fill[pattern=horizontal lines] (6,0) rectangle (20,10);



	 							\draw (2,-.6) node(c){\small $0.1$};
	 							\draw (6,-.6) node(c){\small $0.3$};
	 							\draw (20/2,-.6) node(c){\small $0.5$};
	 					
	 					
	 					
	 							\draw (20,-.6) node(c){\small$1$};

	 				\draw(-.7,15) node(z){\small $10$};
	 				\draw(-.7,7.5) node(z){\small $3$};
	 				\draw(-.7,5) node(z){\small $2$};





	 				\end{tikzpicture}
	 		\]
	 \caption{Example of a cake cutting problem with piecewise constant value density functions. The area with vertical lines is under the value density function of agent $1$ and the area with horizontal lines is under the value density function of agent $2$. The valuation functions of both agents are ordinally equivalent to the ones in Figure~\ref{figure:piecewise}.}
	 
	\label{figure:piecewise-b}
	 \end{figure}
	
	
	\newpage	
	\subsection{Properties of cake cutting algorithms}
	A \emph{deterministic cake cutting algorithm} is a mapping from the set of valuation profiles to the set of allocations. A \emph{randomized cake cutting algorithm} is a mapping from the set of valuation profiles to a space of distributions over the set of allocations. The output of the algorithm in this case for a specific valuation profile is a random sample of the distributional function over the set of allocation for that profile. 

	An algorithm (either deterministic or randomized) satisfies property $P$ if it always returns (with probability 1) an allocation that satisfy property $P$. A deterministic algorithm is \emph{strategyproof} if no agent ever has an incentive to misreport in order to get a better allocation. The notion of strategyproofness is the one well-established in social choice~\citep[see \eg][]{Gibb73a}  and much stronger than the notion of `strategyproofness' used in some of the cake-cutting literature~\citep[see \eg][]{Bram08a}.
	By strategyproof, we mean truthful as has been used in \citep{CLPP10a}. 
	Similarly, a deterministic algorithm is \emph{group-strategyproof} if there exists no coalition $S\subseteq N$ such that members of $S$ can misreport their preferences so that each agent in $S$ gets as preferred an allocation and at least one agent gets a strictly better payoff. A deterministic algorithm is \emph{weak group-strategyproof} if there exists no coalition $S\subseteq N$ such that members of $S$ can misreport their preferences so that each agent in $S$ gets a strictly more preferred allocation.
	A randomized algorithm is \emph{strategyproof in expectation} if the expected utility from the random allocation that every agent receives in expectation under a profile where he reported truthfully is at least as large as the expected that he receives under a profile where he misreports while fixing the other agents' reports.

	We say that a cake cutting algorithm satisfies \emph{unanimity}, if when each agent's most preferred $1/n$ length of the cake is disjoint from another agent, $1/n$ length of the cake, then each agent gets their most preferred piece of cake of length $1/n$.
	











	\subsection{Relation between the properties of cake cutting algorithms}
	

	
	In this subsection, we recap the main properties of cake cutting algorithms: \begin{inparaenum}[i)]
\item proportionality,
\item robust proportionality,
\item envy-freeness,
\item robust envy-freeness,
\item symmetry,
\item non-wastefulness,
\item Pareto optimality,
\item unanimity
\item strategyproofness,
\item weak group strategyproofness,
\item group strategyproofness,
\item polynomial-time.
	\end{inparaenum}


\begin{remark}
For cake cutting, 
\begin{inparaenum}[\itshape a\upshape)]	
\item Envy-freeness and non-wastefulness $\implies$ proportionality;
\item Robust proportionality $\implies$ proportionality;
\item Robust envy-freeness $\implies$ envy-freeness;
\item Robust envy-freeness and non-wastefulness $\implies$ robust proportionality; 
\item Group strategyproofness $\implies$ weak group strategyproofness $\implies$ strategyproofness;
\item Pareto optimality $\implies$ non-wastefulness;
\item Pareto optimality $\implies$ unanimity;
\item two agents, proportionality $\implies$ envy-freeness;
\item two agents, robust proportionality $\implies$ robust envy-freeness.
	\end{inparaenum}

\end{remark}




\subsection{The free disposal assumption}
We may assume without lost of generality that every part of the cake is desired by at least one agent.  If that is not the case, then we can discard the parts that are desired by no one and rescale what is left so that we get a $[0,1]$ interval representation of the cake. Notice that this procedure preserves the aforementioned properties of fairness, efficiency and truthfulness. The free disposal assumption that we are making is necessary to ensure strategyproofness for piecewise uniform valuation functions. See \citep{CLPP12a} for a discussion on the necessity of this assumption. \\




\noindent Before we present our algorithms, we will first take a detour to the literature on random assignments, as some of the algorithms in the random assignment literature are closely related to our algorithms.


	\section{A detour to random assignments}

	An assignment problem is a triple $(N, H, \pref)$ such that $N=\{1,\ldots, n\}$ is a set of agents, $H=\{h_1, \ldots, h_n\}$ is a set of houses and $\pref=(\pref_1,\ldots, \pref_n)$ is the preference profile in which $\pref_i$ denotes the preferences of agent $i$ over houses $H$. A \emph{deterministic assignment} is a one-to-one mapping from $N$ to $H$. 
	A \emph{random allocation} is a probability distribution over $H$. 
	A random assignment $p$ gives a random allocation to each agent. It can be represented by a bistochastic matrix $p$ in which the $i$th row is denoted by $p_i$ and all $i\in A$, and $h\in H$, $p_{ih}\geq 0$, $\sum_{j\in A}p_{jh}=\sum_{h'\in H}p_{ih'}=1$.\footnote{The bistochasticity of the matrix $p$ holds when there are the same number of agents as there are objects, which can be assumed without lost of generality by adding dummy agents or objects} The term $p_{ih}$ denotes the probability with which agent $i$ gets house $h$.
An assignment problem has commonalities with cake cutting with piecewise constant valuations. They also have some fundamental differences. For example, in cake cutting, the agents do not have continuous constant valuations over pre-determined segments of the cake.

	Given two random assignments $p$ and $q$, $p_i \succsim_i^{SD} q_i$ i.e.,  a player $i$ weakly SD prefers $p_i$ to $q_i$ if for all $h$,
	$	\sum_{h_j\in \set{h_k\midd h_k\succsim_i h}}p_{ih_j} \ge \sum_{h_j\in \set{h_k\midd h_k\succsim_i h}}q_{ih_j}.$ 
	Another way to see the SD relation is as follows. A player $i$ weakly SD prefers allocation $p_i$ to $q_i$ if for all vNM utilities consistent with his ordinal preferences, $i$ gets at least as much expected utility under $p_i$ as he does under $q_i$.
	Furthermore $p \succsim^{SD} q$, i.e., $p$ \emph{stochastically dominates} $q$ if $p_i \succsim_i^{SD} q_i$ for all $i\in N$ and $q\neq p$. 

	An algorithm satisfies \emph{SD-efficiency} if each returned assignment is Pareto optimal with respect to the SD-relation~\citep[see \eg][]{Yilm09a}. 
	An algorithm satisfies \emph{SD envy-freeness} if each agent (weakly) SD prefers his allocation to that of any other agent. SD envy-freeness is a very demanding notion of fairness. The reader may be able to notice that our notion of robust envy-freeness in cake cutting is based on a similar idea as SD envy-freeness. 
	We will consider random allocations as fractional allocations and random assignments as fractional assignments. Viewing the probability of getting a house simply as getting a fraction of the house is especially useful when some houses are not complete but only partial. In this vein, the definition of SD dominance should also be considered from the perspective of fractional allocations rather than probability distributions. 














	The most basic assignment problem concerns $n$ agents having strict preferences over $n$ objects. 
	For this basic setting a simple yet ingenious \emph{PS (probabilistic serial)} algorithm introduced by \citet{BoMo01a} and ~\citet{CrMo01a} which uses the \emph{simultaneous eating algorithm (SEA)}. Each house is considered to have a divisible probability weight of one, and agents simultaneously and with the same eating rate consume the probability weight of their most preferred house until no house is left. 

	The random allocation allocated to an agent by PS is then given by the amount of each object he has eaten until the algorithm terminates. The main result of \citet{BoMo01a} was that the fractional assignment returned by the PS algorithm is SD envy-free and SD-efficient.


	The PS algorithm has been extended in various ways. The EPS (extended PS algorithm) of \citet{KaSe06a} generalized PS to the case for indifferences using parametric network flows. EPS also generalized the \emph{egalitarian rule} of \citet{BoMo04a} for dichotomous preferences. \citet{Yilm09a} and \citet{AtSe11a} extended the work of \cite{KaSe06a} to propose PS generalization which also takes care of private endowments where $e_i$ indicates the endowment of agent $i$. For the case of endowments, \citet{Yilm09a} introduced the idea of justified envy-freeness. An assignment $p$ satisfies justified envy-freeness if for all $i,j\in N$,  $p_i \mathrel{\succsim_i^{SD}} p_{j}$ or $\neg(p_i \mathrel{\succsim_{j}^{SD}} e_{j}.)$


	The algorithms in \citep{Yilm09a,AtSe11a} satisfy justified envy-freeness in the presence of private endowments.
	In our algorithm CCEA, we rely on the full power of the controlled-consuming (CC) algorithm of \citet{AtSe11a}  which combines almost all the desirable features of other extensions of PS. In particular, we use the following fact. \emph{There exists an extension of the PS algorithm which can simultaneously handle indifferences in preferences, unacceptable objects in preferences, allocation of multiple objects to agents, agent owning fractions of houses, partial houses being available, and still returns an assignments which satisfies SD justified envy-freeness and SD-efficiency.} In addition, if there are no private endowments, then the extension can also handle variable eating rates.

	

			







	The Controlled-Consuming (CC) algorithm of \citet{AtSe11a}  can handle the case where each agent owns fractions of the complete houses. 

	We also require that for some houses, only an arbitrary fraction of the house is available to the market. This can be handled by a modification to CC~\citep[page 30, ][]{AtSe11a}. Finally we require the agents to want to be allocated as many houses as possible. This does not require any modification to CC.
	In the absence of endowments but presence of variable eating rates, CC is equivalent to the EPS algorithm that can also cater for variable eating rates~\citep[Section 6.4, ][]{KaSe06a}. 





























	\section{CCEA --- Controlled Cake Eating Algorithm}



	CCEA is based on CC (Controlled Consuming) algorithm of \citet{AtSe11a}. Since the original PS algorithm utilized the simultaneous eating algorithm, hence the name  \emph{Controlled Cake Eating Algorithm.}

	CCEA first divides the cake up into disjoint intervals each of whose endpoints are consecutive points of discontinuity of the agents' valuation functions. We will refer to these intervals as \emph{intervals induced by the discontinuity points}. The idea is to form a one-to-one correspondence of the set of cake intervals with a set of houses of an assignment problem. Since intervals may have different lengths, we consider the house corresponding to the interval with the maximum length as a complete house where as intervals corresponding to other houses are partial houses. The preferences of agents over the houses are naturally induced by the relative height of the piecewise constant function lines in the respective intervals. If an agent $i$ owns a sub-interval $J_j$, then in the housing setting, $e_{ih_j}$ is set to $size(h_j)$ and not to one. The reason is that an agent can only own as much of the house as exists. The technical heart of the algorithm is in CC (Controlled Consuming) algorithm of \citet{AtSe11a}. We recommend the reader to Section 3.2 of \citep{AtSe11a} in which an illustrative example on CC is presented. Once CC has been used to compute a fractional assignment $p$, it is straightforward to compute a corresponding cake allocation. If an agent $i$ gets a fraction of house $h_j$, then in the cake allocation agent $i$ gets the same fraction of subinterval $J_j$. 


	\begin{algorithm}[h]
	  \caption{ Controlled Cake Eating Algorithm (CCEA) to compute a robust envy-free allocation for piecewise constant value functions.
	}
	  \label{RAR-algo}
	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}} 
	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
	\begin{algorithmic}
	

		\REQUIRE  Piecewise constant value functions
		\ENSURE  A robust envy-free allocation.
	\end{algorithmic}
	\algsetup{linenodelimiter=\,}
	  \begin{algorithmic}[1] 
			\normalsize
	
	\STATE Divide the regions according to agent value functions. Let $\mathcal{J}=\{J_1, \ldots, J_m\}$ be the set of subintervals of $[0,1]$ formed by consecutive marks.
	\STATE Consider $(N',H,\succsim , size(\cdot))$ where

	\begin{itemize}	
	\item $H=\{h_1,\ldots, h_m\}$ where $h_i=J_i$ for all $i\in \{1,\ldots, m\}$ 
	\item  $\pref$ is defined as follows: $h\succsim_i h'$ if and only if $v_i(x)\geq v_i(y)$ for $x\in h$ and $y\in h'$; \\
	$\pref_{n+1}$ is defined in the way that each house in the market is unacceptable to agent $n+1$.
	\item $size(h_j)=1$ for $h_j\in \arg \max_{j\in \{1,\ldots, m\}}(len(J_j))$;\\

	 $size(h_j)=\frac{len(J_j)}{(\max_{j\in \{1,\ldots, m\}}(len(J_j)))}$ \\for all $h_j\notin \arg \max_{j\in \{1,\ldots, m\}}(len(J_j))$;


	\end{itemize}


	\STATE $p\longleftarrow CC(N',H,\succsim, size(\cdot))$


	\STATE For interval $J_j$, agent $i$ is an allocated subinterval of $J_j$, denoted by $J^{i}_j$, which is of length $p_{ih_j}/size(h_j)\times len(J_j)$. For example, if $J_j = [a_i, b_i]$, then one possibility of $J^{i}_{j}$ can be $[a_i + \sum_{n=1}^{i-1} p_{ih_j}/size(h_j)\times len(J_j), \ a_i + \sum_{n=1}^{i} p_{ih_j}/size(h_j)\times len(J_j) ]$.  \\
	$X_i\longleftarrow \bigcup_{j=1}^m J^{i}_j$ for all $i\in N$
	  \RETURN $X=(X_1,\ldots, X_n)$ 
	 \end{algorithmic}
	\label{algo:f}
	\end{algorithm}

	In Example~\ref{example:transform}, we show how CCEA transforms a cake cutting problem with piecewise constant valuations into a random assignment problem.

	\begin{example}[Illustration of CCEA]\label{example:transform}
	We examine how CCEA runs on the cake cutting problem in Figure~\ref{figure:piecewise}.
	Firstly,  let $\mathcal{J}=\{J_1, \ldots, J_4\}$ be the set of subintervals of $[0,1]$ formed by consecutive points of discontinuity are identified: $J_1=[0,0.1], J_2=[0.1,0.3], J_3=[0.3,0.5]$, and $J_4=[0.5,1]$. $J_2$ is discarded because it is desired by no agent. In set $\{h_1, h_3,h_4\}$, each house $h_j$ corresponds to subinterval $J_j$. The preferences of the agents over $H$ are inferred from their valuation function height in the subintervals so that $h_1 \succ_1 h_4 \succ_1 h_3$ and $h_3 \sim_2 h_4 \succ_2 h_1.$ We also set the number of units of each house that is available. Since $J_4$ is the biggest interval, we consider $h_4$ as complete house. So, $size(h_4)=1$, $size(h_1)=0.2$, and $size(h_3)=0.4$.
	If we run CC over the housing market instance with the specified set of agents, houses, fraction of houses available to the market, and agent preferences, then the assignment returned by CC is as follows:
	$p_{1h_1}=0.2$, $p_{1h_3}=0$, $p_{1h_4}=0.6$, $p_{2h_1}=0$, $p_{2h_3}=0.4$, and $p_{2h_4}=0.4$. The house assignment $p$ can be used to divide the subintervals among the agents: $X_1=\{[0,0.1], [0.7,1]\}$ and $X_2=\{[0.3,0.5], [0.5,0.7]\}$.

	\end{example}


































































































CCEA satisfies the strong fairness property of robust envy-freeness.

	\begin{proposition}\label{prop:CCEA is robust envy-free}
	For piecewise constant valuations, CCEA satisfies robust envy-freeness and non-wastefulness.
	\end{proposition}






	Let $m$ be the number of relevant subintervals in a cake cutting problem with piecewise constant valuations.

	\begin{proposition}\label{prop:CCEA time}
	CCEA runs in time $O(n^5m^2\log(n^2/m))$, where $n$ is the number of agents and $m$ is the number of subintervals defined by the union of discontinuity points of the agents' valuation functions.
	\end{proposition}

	
	
	






















	Although CCEA satisfies the demanding property of robust envy-freeness, it is not immune to manipulation. We show that CCEA is not strategyproof even for two agents. In the next section, we will present a different algorithm that is both robust envy-free and strategyproof for two agents. 

	\begin{proposition}\label{prop:CCEA is not SP}
	For piecewise constant valuations, CCEA is not strategyproof even for two agents.
	\end{proposition}





































If we restricted the preferences to piecewise uniform with no private endowment or variable claims, then CCEA is not only strategyproof but group-strategyproof. We first show that in this restricted setting, CCEA is in fact equivalent to the algorithm of \citep{CLPP10a}.


	\begin{lemma} \label{prop: equivalence}
	 For piecewise uniform value functions with no private endowments and variable claims, CCEA is equivalent to Mechanism 1 of \citet{CLPP10a}. 
	\end{lemma}

	

	
	
	
	
	


Since the set of valuations that can be reported is bigger in cake cutting than in the assignment problem, establishing group strategyproofness does not follow automatically from group-strategyproofness of CC for dichotomous preferences~\citep[Theorem 2, ][]{BoMo04a}. Using similar arguments, we give a detailed proof that CCEA and hence Mechanism 1 of \citet{CLPP10a} is group strategyproof for piecewise uniform valuations.\footnote{\citet{CLPP10a} had shown that their mechanism for piecewise uniform valuations is strategyproof.} In Section~\ref{sec:extensions}, we extend the result to the case where agents may have variable claims. 

\begin{proposition}\label{prop:gsp1}
For cake cutting with piecewise uniform value functions, CCEA is group strategyproof.
	\end{proposition}



	

	







	




	



	
	For piecewise uniform valuations, CCEA is also Pareto optimal. The result follows directly from lemma \ref{prop: equivalence} along with the fact that Mechanism 1 of \citet{CLPP10a} is Pareto optimal.
	
 
	\begin{proposition}\label{prop: pareto optimality}
	For cake cutting with piecewise uniform value functions, CCEA is Pareto optimal. 
	\end{proposition}













\section{MEA --- Market Equilibrium Algorithm}



In the previous section we presented CCEA which is not Pareto optimal for piecewise constant valuations.
It turns out that if we relax the robust notion of fairness to envy-freeness, then we can use fundamental results in general equilibrium theory and recent algorithmic advances ~\citep{DPSV08a} to formulate a convex program that always returns an envy-free and Pareto optimal allocation as its optimal solution.  For each valuation profile, let $J = \{J_1, \ldots, J_k\}$ be the intervals whose endpoints are consecutive points in the union of break points of the agents' valuation functions. Let $x_{ij}$ be the length of any subinterval of $J_i$ that is allocated to agent $j$. Then we run a convex program to compute a Pareto optimal and envy-free allocation.
We will call the convex program outlined in Algorithm~\ref{algo:MARKET} as the \emph{Market Equilibrium Algorithm (MEA)}. MEA is based on computing the market equilibrium via a primal-dual algorithm for a convex program that was shown to be polynomial-time solvable by \citet{DPSV08a}. Notice that if we ignore strategyproofness, or in other words, if we assume that agents report truthfully, then agents are truly indifferent between which subinterval they receive since their valuation function is a constant over any $J_i$. Hence, one we determine the length of $J_j$ to be allocated to an agent, we can allocate any subinterval of that length to the agent.

	\begin{algorithm}[h!]

	  \caption{ The Market 	Equilibrium Algorithm to compute a Pareto optimal, envy-free, and proportional allocation.}
	  \label{RAR-algo}
	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}} 
	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
\begin{algorithmic}


		\REQUIRE  Cake-cutting problem with piecewise constant valuations.
		\ENSURE  A proportional, envy-free, and Pareto optimal allocation.
	\end{algorithmic}
	\algsetup{linenodelimiter=\,}
	  \begin{algorithmic}[1] 
	

\STATE Let $J = \{J_1, \ldots, J_k\}$ be the intervals whose endpoints are consecutive points in the union of break points of the agents' valuation functions. 
\STATE Let $x_{ij}$ be the length of any subinterval of $J_i$ that is allocated to agent $j$.
\STATE $l_i\longleftarrow len(J_i)$
\STATE Solve the following convex program. 
\begin{align}
\text{min} \quad
-\sum_{j =1}^{n} log(u_j) \notag \\
\text{s.t.} \quad
u_j = \sum_{i=1}^{k} v_{ij}x_{ij} &\quad \forall j = 1, \ldots, n \notag \\
\sum_{j=1}^{n} x_{ij} \leq l_i &\quad \forall i = 1, \ldots, k \notag \\
x_{ij} \geq 0 &\quad \forall i, j. \notag \notag
\end{align}
\STATE Let $u^{\star}_j$, $x^{\star}_{ij}$ be an optimal solution to the convex program. Partition every interval $J_i$ into $n$ subintervals where the $j$-th subinterval $J^{j}_i$ has length $x^{\star}_{ij}$.
\STATE $Y_j \longleftarrow \cup_{i=1}^{k} J^{j}_i$ be the allocation of each $j = 1, \ldots, n$.
	  \RETURN $Y=(Y_1,\ldots, Y_n)$.
	 \end{algorithmic}
	\label{algo:MARKET}
	\end{algorithm}



 





\begin{proposition} \label{PE, EF, Prop}
MEA is polynomial-time, Pareto efficient and envy free.
\end{proposition}


We mention here that the connection between a fair and efficient algorithm for cake cutting and computing market equilibria was already pointed by \citet{RePo98a}. \citet{RePo98a} presented an algorithm to compute an approximately envy-free and Pareto optimal allocation for cake cutting with general valuations. However their algorithm is not polynomial-time even for piecewise constant valuations~\citep{ZDO+10a}. 

MEA requires the machinery of convex programming. It remains open whether MEA can be implemented via linear programming.
\citet{CLPP11a} presented an algorithm that uses a linear program to compute an optimal envy-free allocation. The allocation is Pareto optimal among all envy-free allocations. However it need not be Pareto optimal in general. 


Although MEA is not robust envy-free like CCEA, it is Pareto optimal because it maximizes the Nash product.
What is interesting is that under uniform valuations, both MEA and CCEA are equivalent.
In the next result we demonstrate this equivalence~(Proposition~\ref{CCEA equivalence}). The proof requires a careful comparison of both CCEA and MEA under uniform valuations.

\begin{proposition} \label{CCEA equivalence}
For piecewise uniform valuations,  the allocation given by CCEA is identical to that given by MEA.
\end{proposition}
\begin{corollary}
For piecewise uniform valuations, MEA is group-strategyproof.
\end{corollary}








Thus if we want to generalize Mechanism 1 of \citet{CLPP10a} to piecewise constant valuations and maintain robust envy-freeness then we should opt for CCEA. On the other hand, if want to still achieve Pareto optimality, then MEA is the appropriate generalization. In both generalization, we lose strategyproofness.








\section{Impossibility Results}


	



Thus far, we presented two polynomial time algorithms, each of which satisfies a different set of properties. CCEA is robust envy-free and non-wasteful, whereas MEA is Pareto optimal and envy-free. This naturally leads to the following question: does there exist an algorithm satisfies all of the properties that CCEA and MEA satisfy? It turns out that the answer is no, as Theorem~\ref{PE fair impossibility} shows that there is no algorithm that is both Pareto efficient and robust proportional. 
Similarly, Theorem~\ref{PE SP Prop impossibility} argues that there is no algorithm that satisfies the properties CCEA satisfies along with strategyproofness. Lastly, Theorem~\ref{SP Rob Prop Non W impossibility} argues that there is no algorithm that satisfies the properties CCEA satisfies plus strategyproofness. The impossibility results are summarized in Table~\ref{table:summary:impossible}.

	\begin{table}[h!]
	\centering
		\scalebox{0.9}{
\centering
\begin{tabular}{ll}
\toprule
Impossibility& Reference\\
\midrule
Pareto efficient and robust proportional&Theorem.~\ref{PE fair impossibility}\\
Strategyproof, Pareto optimal, and proportional&Theorem~\ref{PE SP Prop impossibility}\\
Strategyproof, robust proportional, and non-wasteful 	& Theorem~\ref{SP Rob Prop Non W impossibility}\\
\bottomrule
\end{tabular}
}

	\caption{Impossibility results for cake-cutting algorithms for piecewise constant valuations.
	}
\label{table:summary:impossible}
\end{table}


Consequently, we may conclude that the properties satisfied by CCEA and MEA are respectively maximal subsets of properties that an algorithm can satisfy for piecewise constant valuations.


\section{CSD --- Constrained Serial Dictatorship Algorithm}

 



	





          











	






		



	
	
	



	
	
	







	
	


	







In the previous sections, we saw that CCEA and MEA are only strategyproof for piecewise uniform valuations. In light of the impossibility results established in the preivous section, it is reasonable to ask what other property along with strategyproofness can be satisfied by some algorithm. It follows from \citep[Theorem 3, ]{Schu97a} that the only type of strategyproof and Pareto optimal mechanisms are dictatorships. \citet{CLPP12a} raised the question whether there exists a strategyproof and proportional algorithm for piecewise constant valuations. The algorithm CSD answers this question partially.

Before diving into the CSD algorithm, it is worth noting that there is some fundamental difference between random assignment setting and the cake cutting setting. In the random assignment setting, the objects that we are allocating are well defined and known to the public. On the other hand, in the cake cutting setting, the discontinuity points of each agent's valuation function is private information for the agent. Hence, any algorithm that uses the reported discontinuity points to artificially create the objects runs into the risk of having the objects created by the algorithm be manipulated by the reports of the agents. In order to illustrate this difficulty, consider the uniform allocation rule.  The uniform allocation rule (that assigns $1/n$ of each house)~\citep{Cham04a} is both strategyproof and proportional in the random assignment setting. However it cannot be adapted for cake cutting with piecewise constant valuations since strategyproofness is no longer satisfied if allocating $1/n$ of each interval (induced by the agent valuations) is done deterministically. 


\begin{proposition} \label{prop: uniform allocation is not SP}
The uniform allocation rule (done deterministically) is not strategyproof.
\end{proposition}


Now we are ready to present CSD. In order to motivate CSD, we will give a randomized algorithm that is strategyproof and robust proportional in expectation. The algorithm is a variant of random dictatorship: each agent has uniform probability of being chosen as a dictator. However, if the whole cake is acceptable to each agent, then each time a dictator is chosen, he will take the whole cake. This approach is not helpful since we return to square one of having to divide the whole cake. We add an additional requirement which is helpful. We require that each time a dictator is chosen, the piece he takes has to be of maximum value $1/n$ length of the total size of the cake. We will call this algorithm Constrained Random Serial Dictatorship (CRSD). Formally speaking, CRSD draws a random permutation of the agents. The algorithm then makes the allocation to agents in the order that the lottery is drawn. Everytime when it is agent $i$'s turn to receive his allocation, CRSD looks at the remaining portion of the cake and allocates a maximum value $1/n$ length piece of the cake to agent $i$ (break ties arbitrarily). Notice that CRSD is strategyproof,  as in every draw of lottery, it is in the best interest of the agents to report their valuation function truthfully in order to obtain a piece that maximizes his valuation function out of the remaining pieces of cake. Later on we will see, through the proof of Proposition~\ref{prop: CSD is robust prop}, that CRSD is robust proportional in expectation.  \\

CSD is an algorithm that derandomizes CRSD by looking at its allocation for all $n!$ different permutations and aggregate them in a suitable manner. The algorithm is formally presented as Algorithm~\ref{CSD-algo}.\\




\begin{algorithm}[t]

	  \caption{CSD (Constrained Serial Dictatorship)---  proportional and unanimous algorithm for piecewise constant valuations}
	  \label{CSD-algo}
	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}} 
	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
	\begin{algorithmic}

		
		\REQUIRE  Cake-cutting problem with piecewise constant valuations.
		\ENSURE  A robust proportional allocation.
	\end{algorithmic}
	\algsetup{linenodelimiter=\,}
	  \begin{algorithmic}[1] 
	
		

	\FOR{each $\pi\in \Pi^N$}
	\STATE $C \longleftarrow[0,1]$ (intervals left)
	\FOR{$i=1$ to $n$}
	\STATE $X_{\pi(i)}^{\pi}\longleftarrow$ maximum preference cake piece of size $1/n$ from $C$
	\STATE $C\longleftarrow C - X_{\pi(i)}^{\pi}$.
	\STATE $i\longleftarrow i+1$.
	\ENDFOR
	\ENDFOR
	
	\STATE Construct a disjoint and exhaustive interval set $\mathcal{J'}$ induced by the discontinuities in agent valuations and the cake cuts in the $n!$ cake allocations. 
	\STATE $Y_i \longleftarrow$ empty allocation for each $i\in N$.
	\FOR{each $J_j = [a_j, \ b_j] \in \mathcal{J'}$}
	\FOR{each $i\in N$}
\STATE Let $p_{ij} = \frac{count(i,J_j)}{n!}$ where $count(i,J_j)$ is the number of permutations in which $i$ gets $J_j$.
\STATE Generate $A_{ij} \subseteq J_j$, which is of length $p_{ij}|J_j|$ according to some subroutine.
\STATE $Y_i\longleftarrow Y_i \cup A_{ij}$ 
	\ENDFOR
\ENDFOR
	
	
	
	

	  \RETURN $Y=(Y_1,\ldots, Y_n)$
	 \end{algorithmic}
	\label{algo:CSD}
	\end{algorithm}
	

	

	Although CSD does not necessarily require $n!$ cuts of the cake, it may take exponential time if the number of agents is not a constant. In Example~\ref{example:CSD}, we illustrate how CSD works. 
	
	
	\begin{example}[Illustration of CSD]\label{example:CSD}
		We implement CSD on the cake cutting problem in Figure~\ref{figure:piecewise}
	
	
	
	
	
		
For permutation $12$, agent $1$ first chooses the cake piece $\{[0,0.1],[0.6,1]\}$ and agent $2$ then takes the remaining piece $\{[0.1,0.6]\}$. For permutation $21$, agent $2$ first chooses the cake piece $\{[0.3,0.8]\}$ and agent $1$ then takes the remaining piece $\{[0,0.3],[0.8,1]\}$.
		
		The set of all relevant subintervals induced by the two permutations are $\{[0,0.1], [0.1,0.3],[0.3,0.6],[0.6,0.8],[0.8,1]\}$. When we we additionally consider the discontinuities in the players' valuations, the set of relevant subintervals is 
		$\mathcal{J'}=\{[0,0.1], [0.1,0.3],[0.3,0.5],[0.5,0.6], [0.6,0.8],[0.8,1].$
	
		\noindent Then \[Y_1=\{[0,0.1],\frac{1}{2}[0.1,0.3],\frac{1}{2}[0.6,0.8], [0.8,1]\}\] 
	and
	\[Y_2=\{\frac{1}{2}[0.1,0.3],[0.3,0.5],[0.5,0.6], \frac{1}{2}[0.6,0.8]\}. \]
			\end{example}

\begin{proposition}\label{prop:CSD-well-defined}
	For piecewise constant valuations, CSD is well-defined and returns a feasible cake allocation in which each agents gets a piece of size $1/n$. 
	\end{proposition}
	
	\begin{proposition}\label{prop: CSD is robust prop}
		For piecewise constant valuations, CSD  satisfies robust proportionality and symmetry.
		\end{proposition}

	





 Notice that unlike CRSD, CSD interprets the probability of allocating each interval to an agent as allocation a fractional portion of the interval to that agent.  Unless the actual way of allocating the fractions is specified, one cannot discuss the notion of strategyproofness for CSD because a deviating agent is unable to properly evaluate his allocation against his true valuation function in the reported profile. Contrary to intuition, CSD may or may not be strategproof depending on how the fractional parts of each interval are allocated. In fact, the following remark illustrates this issue.


\begin{remark}\label{remark:csd-not-sp}
CSD is not strategyproof if the fraction of each interval of $\mathcal{J'}$ is allocated deterministically (please see the appendix for the proof). 
\end{remark}


In light of difficulty, we will implement a method (see Algorithm~\ref{CSD: subroutine}) that randomly allocating the fractions of intervals to agents. With this implementation, CSD is strategyproof in expectation.

\begin{algorithm}[t]

	  \caption{A subroutine that converts fractional allocation into subintervals via randomization}
	  \begin{algorithmic}[1] 
\STATE Generate $U_j \sim unif[a_j, \ b_j]$.
\STATE For $a_j \leq x \leq 2b_j - a_j$, let $\mod(x) = x$ if $a_j \leq x \leq b_j$ and $x - (b_j-a_j)$ if $x > b_j$.  Let  
\[A_{ij} = [\mod(U_j + \sum_{k = 1}^{i-1}p_{kj}(b_j-a_j)), \mod(U_j + \sum_{k = 1}^{i}p_{kj}(b_j-a_j))]\]
if $\mod(U_j + \sum_{k = 1}^{i-1}p_{kj}(b_j-a_j)) \leq \mod(U + \sum_{k = 1}^{i}p_{kj}(b_j-a_j))$ and
\[A_{ij} = [a_j, \mod(U_j + \sum_{k = 1}^{i}p_{kj}(b_j-a_j))] \cup [\mod(U_j + \sum_{k = 1}^{i-1}p_{nj}(b_j-a_j)), b_j]\]
otherwise.
\end{algorithmic}
\label{CSD: subroutine}
\end{algorithm}
We will refer this randomized implemention of CSD as \emph{Constrained Mixed Serial Dictatorship}, or \emph{CMSD} for short.



\begin{proposition}\label{CSD: SP}

CSD implemented with the aforementioned random allocation rule is strategyproof in expectation.
\end{proposition}



Although CSD is strategyproof in expectation, it fails to satisfy truthfulness based on group-based deviations no matter how the fractional parts of each interval are allocated.




\begin{proposition} \label{CSD: not GSP for PWC}
	For cake cutting with piecewise constant valuations, CSD is not weakly group-strategyproof even for two agents.
	\end{proposition}


Moreover, for cake cutting with piecewise uniform valuations, CSD is not weakly group-strategyproof for at least seven agents. The statement above follows from the fact that RSD is not weakly group-strategyproof for dichotomous preferences when there are at least seven agents~\citep{BoMo01b,BoMo04a}.










		


		








	
	
	
	
	
	
	
	
	
	
	
	
		
		
		
		
		
		
		
		
		
	




















 

	 
	 

	


	
	


	 


	











	 
	



	Even though CSD satisfies both proportionality and symmetry, it does not satisfy the stronger notion of envy-freeness.

	\begin{proposition}\label{prop: CSD is not envy-free}
		CSD is not necessarily envy-free for three agents even for piecewise uniform valuations.
	\end{proposition}










Another drawback of CSD is that it is not Pareto optimal for piecewise constant valuations. The statement follows from the fact that RSD is not SD-efficient~\citep{BoMo01a}. However for the case of two agents, it is robust envy-free and polynomial-time.

\begin{proposition}

		For two agents and piecewise constant valuations, CSD is robust envy-free, and polynomial-time but not Pareto optimal. 
	\end{proposition}


\begin{remark}
	For piecewise uniform valuations, CSD can be modified to be made Pareto optimal. The main change is that for each permutation CSD, the resultant outcome needs to be made Pareto optimal. This can be done by using the idea in \citep{ABH11b}.
\end{remark}





	
	
	
	


	
	
	





  


	
	
	
	
	
	
	\section{Extensions}\label{sec:extensions}
	
	
	In this section, we show how some of our positive results concerning CCEA extend to more general settings where agents may have variable claims or they may have initial endowments (please see Algorithm~\ref{algo:ccea-extensions}).
	
	\begin{algorithm}[h]

	  \caption{ Controlled Cake Eating Algorithm (CCEA) to compute a robust envy-free allocation for piecewise constant value functions. CCEA works for either private endowments or variable claims but is not defined for both.}
	  \label{RAR-algo}
	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}} 
	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
	\begin{algorithmic}
		
		\REQUIRE  Piecewise constant value functions with priority claims $(c_1,\ldots, c_n)$ or private endowments $(\omega_1,\ldots, \omega_n)$ 
		\ENSURE  A robust envy-free and individually rational allocation.
	\end{algorithmic}
	\algsetup{linenodelimiter=\,}
	  \begin{algorithmic}[1] 
		
			
	\STATE  Let $N'=N\cup\{n+1\}$ where $n+1$ is the agent owning all public cake but with no interest in any of the cake.  Join the segments $\omega(1), \ldots, \omega(n), \omega(n+1)$ to assemble a cake. 
	\STATE Divide the regions according to agent value functions. Let $\mathcal{J}=\{J_1, \ldots, J_m\}$ be the set of subintervals of $[0,1]$ formed by consecutive marks.
	\STATE Consider $(N',H,\succsim ,e, rate(\cdot), size(\cdot))$ where

	\begin{itemize}	
	\item $H=\{h_1,\ldots, h_m\}$ where $h_i=J_i$ for all $i\in \{1,\ldots, m\}$ 
	\item  $\pref$ is defined as follows: $h\succsim_i h'$ if and only if $v_i(x)\geq v_i(y)$ for $x\in h$ and $y\in h'$; \\
	$\pref_{n+1}$ is defined in the way that each house in the market is unacceptable to agent $n+1$.
	\item $size(h_j)=1$ for $h_j\in \arg \max_{j\in \{1,\ldots, m\}}(len(J_j))$;\\

	 $size(h_j)=\frac{len(J_j)}{(\max_{j\in \{1,\ldots, m\}}(len(J_j)))}$ \\for all $h_j\notin \arg \max_{j\in \{1,\ldots, m\}}(len(J_j))$;
	\item $rate(i)=claim(i)$; 
	\item $e_{ih_j}=size(h_j)$ if $J_j\in \omega(i)$ and zero otherwise.
	\end{itemize}


	\STATE $p\longleftarrow CC(N',H,\succsim ,e, rate(\cdot), size(\cdot))$ 


	\STATE For interval $J_j$, agent $i$ is allocated a subinterval of $J_j$, denoted by $J^{i}_j$, which is of length $p_{ih_j}/size(h_j)\times len(J_j)$. \\
	$X_i\longleftarrow \bigcup_{j=1}^m p_{ih_j}/size(h_j)J_j$ for all $i\in N$\\
	
	  \RETURN $X=(X_1,\ldots, X_n)$
	 \end{algorithmic}
	\label{algo:ccea-extensions}
	\end{algorithm}
	
	
	
	\subsection{Variable claims}
	
We consider the concept of \emph{variable claims} in cake cutting.
	It is generally assumed in the literature that each agent has equal claim to the cake. In this case we modify the definition of proportionality and envy-freeness accordingly. Reasoning about claims has a long tradition in the fair division literature. However this strand of research assumes that agents have uniform and identical preferences over the whole of the divisible object and their only concern is the proportion of the object they get~\citep[see \eg][]{Thom03a,Youn94a}. 
\citet{BrTa96a} refer to variable claims as entitlements and touch upon entitlements in cake cutting at a few places in their book. They present a general idea of handling entitlements by cloning agents~\citep[Page 152, ][]{BrTa96a} but doing so can lead to an exponential blowup of time and space.   \citet{BJK08a} also considered entitlements in pie-cutting but presented an impossibility result and also a positive result for two agents. On the other hand, one of our algorithms handles variable claims for arbitrary number of agents and does not require cloning.
	
          An allocation satisfies  \emph{proportionality for variable claims} if $V_i(X_i) \geq c_i/\sum_{j \in N} c_j V_i([0,1])$ for all $i \in N$.
	An allocation satisfies \emph{robust proportionality for variable claims} if for all $i \in N$ and for all $v_i'\in \hat{V_i}$, $\int_{X_i}v_i'(x)dx\geq (c_i/ \sum_{j \in N} c_j)\int_{[0,1]}v_i'(x)dx$.

	An allocation satisfies \emph{envy-freeness for variable claims}, if  $V_i(X_i)\geq (c_i/c_j)V_i(X_j)$ for all $i,j\in N$. 
	
	An allocation satisfies \emph{robust envy-freeness for variable claims} if for all $i, j \in N$ and for all $v_i'\in \hat{V_i}$,
	$\int_{X_i}v_i'(x)dx\geq (c_i/c_j)\int_{X_j}v_i'(x)dx$.
	
	
		\begin{proposition}\label{prop: CCEA envy for claims}
	For cake cutting with variable claims and piecewise constant valuations, CCEA satisfies robust envy-freeness for variable claims.
	\end{proposition}

For uniform valuations, group-strategyproofness of CCEA even holds when agents have variable claims.

	\begin{proposition}\label{prop:sp-with-speed}
	For cake cutting with piecewise uniform value functions and variable claims, CCEA is group-strategyproof. 
	\end{proposition}
	


	On the other hand, it can be shown that the following natural modification of CSD does not satisfy proportionality in the presence of variable claims: each agent $i$ gets $c_i/(\sum_{j\in n}c_j)$ length of the most preferred interval for each permutation.
	
	
	We note that MEA can be easily adapted to cater for variable claims. Each agent's budget is proportional to his claim.
	
				\begin{proposition}\label{th:maintheorem3b}
			For cake cutting with with piecewise constant valuations and variable claims, there exists an algorithm (MEA)  that is polynomial-time, Pareto optimal, envy-free, and proportional.
	\end{proposition}
	





	
	
	\subsection{Private endowments}
	
In the cake cutting literature, the cake is generally considered to be a public good which is divided among the agents. It could also be that each agent brings part of the cake and then the assembled cake needs to be reassigned among the agents fairly. We call the setting cake cutting with \emph{private endowments}. In this context, individual rationality is a minimal requirement and envy-freeness need to be redefined. Classic cake cutting can be modelled by cake cutting with private endowments in the following manner: none of the agents have any endowments and one additional agents owns the whole cake but has no interest in the cake.
	
	An allocation is \emph{individually rational} if $V_i(X_i)\geq V_i(\omega(i))$. An allocation satisfies \emph{justified envy-freeness for private endowments} if $V_i(X_i)\geq V_i(X_j)$ or $V_j(X_i)< V_j(\omega(j))$ for each pair of agent $i,j\in N$. Either $i$ should not be envious of $j$ or if he is envious, then giving $i$'s allocation to $j$ violates individual rationality.\footnote{The definition of justified envy-freeness for private endowments is based on a similar concept due to \citet{Yilm09a} for the domain of housing assignment problems.} It is not entirely clear how to obtain the canonical concept of justified envy-freeness which takes into account both private endowments and variable claims.
	
		An allocation satisfies \emph{robust justified envy-freeness for private endowments} if for all $i,j\in N$ either
	$\forall v_i'\in \hat{V_i} \midd \int_{X_i}v_i'(x)dx\geq \int_{X_j}v_i'(x)dx$ or $ \exists v_j'\in \hat{v_j}\midd \int_{X_i}v_j'(x)dx<\int_{\omega(j)}v_j'(x)dx$. If $i$ does not get an unambiguously as preferred a piece as $j$'s, $j$ has a counter claim that $j$'s endowment is better than $i$'s piece for some ordinally equivalent valuation function of $j$. 
	
		\begin{proposition}\label{prop:CCEA endowments}
	For cake cutting with private endowments and piecewise constant valuations, CCEA satisfies robust justified envy-freeness for private endowments.
	\end{proposition}



	
	
	
	Generalizing CSD to handle endowments without losing its properties seems to be a challenging task. We have not addressed it in this paper.
		\section{Related work and discussion}


	A mathematical analysis of cake cutting started with the work of Polish mathematicians Steinhaus, Knaster, and Banach~\citep{Stei48a}. As applications of fair division have been identified in various multiagent settings, a topic which was once considered a mathematical curiosity has developed into a full-fledged sub-field of mathematical social sciences~\citep[see \eg][]{Moul03a}. 
	In particular, in the last few decades, the literature of cake cutting has grown considerably~\citep[see \eg][]{Moul03a,BrTa96a,RoWe98a,Proc12a}. 






	
	

	The relation between the random assignment problem and cake cutting has been noticed before~\citep{CLPP12a}. However, in their discussion of related work, \citeauthor{CLPP12a} argue that techniques from the random assignment literature cannot be directly applied even to piecewise uniform functions---a subclasses of piecewise constant functions. 

	Stumbling blocks identified  include the fact that in the random assignment problem, each agents gets one object. 
	We observed that PS satisfies envy-freeness even when agents get multiple objects.\footnote{Even in the first paper on the PS algorithm for strict preferences, it was observed that PS can be extended to the case where there are many more objects than agents~\citep[Page 310, ][]{BoMo01a}.}
	Another issue raised is that `if two agents desire two subintervals, both agents would value the longer subinterval more than the shorter.' 
This problem can be circumvented by using the algorithm to compute the greatest common denominator of the lengths of the intervals and then dividing the intervals in equally sizes subintervals. However the number of subintervals can be exponential in the input size. 
We use the idea of \citet{AtSe11a} that some houses may only be partially available.




	\citet{CLPP12a} stated that generalizing their strategyproof algorithm for piecewise uniform valuations to the case for piecewise constant valuations as an open problem.




We presented two algorithms --- CCEA and MEA --- that generalize Mechanism 1 of \citet{CLPP10a, CLPP12a}. Although they both satisfy certain desirable properties, both natural generalizations are not strategyproof. 
	



	















	
         A number of works in the cake-cutting literature reason about strategyproofness. However they refer to a very weak notion of strategyproofness which is equivalent to a maximin strategy. Apart from the papers of \citet{CLPP10a,CLPP12a}, we are aware of no positive results regarding discrete, strategyproof, and fair algorithms even for the restricted domain of piecewise constant valuations. In this paper we present a proportional algorithm (CSD) for piecewise constant valuations that although not formally strategyproof seems less like likely to manipulate in comparison to CCEA. If we are allowed to use randomization, then we show that CSD can be adapted to be strategyproof in expectation. Notice that if we instead require our algorithm to be strategyproof always, and proportional in expectation, then CRSD would satify these properties. Moreover, we note that \citet{CLPP10a} also presented an algorithm that is randomized, envy-free and proportional, and strategyproof in expectation. However, it does not satisfy unanimity and requires much more randomization in contrast to CSD.  It remains an open question whether there exists an algorithm that always returns a proportional allocation and is always immune to agent manipulation. 
	
	A difficulty that arises in coming up with strategyproof and proportional algorithm lies in that there is no restriction on the distribution of the discontinuity points of the agents' valuation functions. To illustrate this point, suppose the algorithm designer knows that the discontinuity points of the agents' valuation functions come from a set $S = \{x_1, \ldots, x_k\}$, where $0 \leq x_1 \leq \ldots \leq x_k \leq 1$. Consequently, a mechanism that partitions $[0,1]$ into intervals of the form $[x_i, x_{i+1}]$ and allocates $1/n$ of each interval to each agent would be proportional, envy-free and strategyproof. Even if the designer does not know such a $S$, but instead we require the minimum distance between any two consecutive discontinuity points of the agent's valuation function to be at least some $\epsilon > 0$, then there exists a strategyproof and $\delta$-proportional algorithm for this setting.
	
	
		As for private endowments, we are only aware of \citep{Thom07a} where private endowment are considered in pie-cutting. However, in comparison to our positive results concerning envy-freeness, \citet{Thom07a} presents a negative result concerning the core.
	







	
	\section{Conclusion}
	






































In this paper, we made a number of conceptual and technical contributions. It will be interesting to consider new results with respect to robust versions of fairness, endowments, and variable claims. Cake cutting is an exciting sub-field of microeconomics with numerous applications to computer science. In order for theory to be more relevant to practice, we envision exciting work in much richer models of cake cutting. 



\section*{Acknowledgements}
The authors acknowledge the helpful comments  of Jay Sethuraman and Simina Br{\^a}nzei.

This material is based upon work supported by
	the Australian Government's
	Department of Broadband, Communications and the Digital
	Economy, the Australian Research Council, the Asian
	Office of Aerospace Research and Development through
	grant AOARD-12405.


