\documentclass{llncs}
\usepackage{epsfig}

\sloppy

\def\E{{\mathrm{I\!E}}}

%\pagestyle{plain}

\begin{document}

\title{On low-envy truthful allocations\thanks{This work is partially supported by the European Union under
IST FET Integrated Project FP6-015964 AEOLUS and Cost Action IC0602 ``Algorithmic Decision Theory'', and
by a ``Caratheodory'' basic research grant from the University of Patras.}}
\author{Ioannis Caragiannis \and Christos Kaklamanis \and Panagiotis Kanellopoulos \and Maria Kyropoulou}
\institute{
Research Academic Computer Technology Institute and\\
Department of Computer Engineering and Informatics\\
University of Patras, 26500 Rio, Greece}

\newcommand{\remove}[1]{}

\maketitle

\begin{abstract}
We study the problem of allocating a set of indivisible items to players having additive utility functions
over the items. We consider allocations in which no player envies the bundle of items allocated to the other
players too much. We present a simple proof that deterministic truthful allocations do not minimize envy by
characterizing the truthful mechanisms for two players and two items. Also, we present an analysis
for uniformly random allocations which are naturally truthful in expectation. These results simplify or
improve previous results of Lipton et al.
\end{abstract}

\section{Introduction}
Resource allocation \cite{CDEL06} has been an important problem in several areas such as Computer Science, Artificial Intelligence, and Economics since their early days.
In the era of the Internet with a vast amount of computational, communication, and storage resources available worldwide, the problem
is still of paramount importance. Besides efficiency, fairness is another important aspect that resource allocation must satisfy. Additional
constraints such as the selfish behavior of resource owners and users make the variations of the problem very challenging.

A simple but foundational resource allocation problem is the well-known {\em cake-cutting} problem \cite{BT96,RW98}. In cake-cutting, we are given
$n$ players with different utilities for different parts of a cake. The objective is to allocate pieces of the cake to the players in
such a way that they are satisfied. Traditionally, satisfaction of players has been measured by two different notions: {\em envy-freeness}
and {\em proportionality}. Envy-freeness means that each player prefers her allocated pieces to the pieces allocated to any other player.
Proportionality means that the utility of each player for the pieces allocated to her is at least $1/n$ times her utility for the whole
cake. Due to the continuity of the cake and the utilities of the players, both objectives are always feasible.

A similar problem concerns the fair allocation of {\em indivisible items}; indivisibility implies that an item cannot be broken into parts
and must be allocated to a single player. Here, we again have a set ${\cal N}$ of $n$ players and a set ${\cal M}$ of $m$ indivisible items.
Each player $p$ has a non-negative utility function $u_p:2^{\cal M}\rightarrow \mathrm{I\!R}^+_0$. The objective is to assign to each player $p$ a bundle of items ${\cal M}_p\subseteq {\cal M}$,
so that $\bigcup_p {\cal M}_p = {\cal M}$ and some criterion concerning fairness is maintained. An important special case
is that of {\em additive utilities}. In this case, each player $p$ has a utility $u_{p,i}$ for each item $i\in {\cal M}$ and her utility for
a bundle of items is simply the sum of her utilities on these items. In contrast to the cake-cutting problem, envy-freeness and proportionality
are not always feasible goals in this setting even in the case of additive utilities. Here,
{\em envy minimization} is among the most prominent measures of fairness. Given an allocation $A$ in which players $p$ and $q$ are assigned bundles ${\cal M}_p$ and ${\cal M}_q$,
the envy $e_{pq}(A)$ of player $p$ for player $q$ is $e_{pq}(A)=u_p({\cal M}_q)-u_p({\cal M}_p)$. Then, envy of $A$ is defined as $e(A)=\max_{p,q\in {\cal N}}e_{pq}$.
Clearly, $A$ is envy-free if $e(A)=0$.


An implicit assumption in the above definitions is that the players express their true utilities which are used by the algorithm (i.e., the allocation
function) in order to compute an allocation. In practice, players are usually {\em selfish} in the sense that they aim to increase their benefit, i.e., their
total utility on the bundle of items the algorithm allocates to them. In order to do so, they may report false {\em valuations} of items to the algorithm (i.e., different
than their true utilities). {\em Truthful allocation functions} guarantee that the allocation is based on the true utilities of the players. A deterministic allocation
function is {\em truthful} if the benefit obtained by a player when reporting false valuations on the items is not greater than the benefit she would have obtained
by telling the truth. Similarly, a randomized allocation function is {\em truthful in expectation} if the
expected benefit of a player is maximized when revealing her true utilities.

\paragraph{Related work.}
Research concerning fair allocations originated in the $1940$s with a focus on cake-cutting \cite{S48}. Since then, the problem of achieving a proportional allocation
with the minimum number of operations has received much attention and is now well-understood \cite{EP06,EP84,BT96,RW98,WS07}. The problem of achieving envy-freeness has been proven to
be much more challenging \cite{BKM05,BT95,S80}; in fact, under the most common computational model of cut and evaluation queries \cite{RW98}, no algorithm with bounded running time is known for more than $3$ players.
Very recently, envy-freeness was proved to be a harder property to achieve than proportionality \cite{P09,S08}. Better solutions exist for different computational models (e.g., moving knife algorithms \cite{BTZ97}).

Lipton et al. \cite{LMMS04} studied envy minimization with indivisible items. Among other results, they proved that allocations with envy bounded by the
{\em marginal utility} always exist and can be computed in polynomial time. In the case of additive utilities, marginal utility translates to the maximum per item utility over all players.
They also present algorithms that compute allocations that approximate the minimum {\em envy-ratio}; the envy ratio of a player $p$ for a player $q$
is the utility of player $p$ for the items allocated to player $q$ over $p$'s utility for the items allocated to her. Complexity considerations about envy-freeness for indivisible items and non-additive utilities are presented in \cite{BL08}. The papers \cite{CEEM07,CEM07} study the problem of achieving envy-free and efficient allocations in distributed settings and when the allocation of items is accompanied by monetary side payments (in this case, envy-freeness is always a feasible goal). Lipton et al. \cite{LMMS04} also consider truthful allocations;
they show that any deterministic allocation function that returns an allocation with minimum possible envy cannot be truthful; their proof uses an instance with two players
and many items. Finally, they present an analysis of the randomized allocation function that assigns each item to one of the players uniformly at random and independently
of the allocations of the other items. This allocation function is truthful in expectation. For the case where the sum of utilities of each player over the items is $1$, they prove that, with high probability, the envy of the
resulting allocation is $O(\sqrt{\alpha}n^{1/2+\epsilon})$, where $\alpha$ is the maximum utility per item over all players and $\epsilon$ is an arbitrarily small positive
number. We remark that the study of truthful allocation functions belongs to the recent line of research on {\em algorithmic mechanism design} \cite{NRTV07}. In particular,
Mu'alem and Schapira \cite{MS07} prove lower bounds on the envy of truthful allocation functions. However, unlike the model of \cite{LMMS04} which we also follow in
the current paper, \cite{MS07} and most of the studies in algorithmic mechanism design allow monetary transfers between the players.

For indivisible items, a fairness objective that has been extensively considered recently is {\em max-min fairness}. Here, the objective is to compute an allocation in which
the benefit of the least happy player is maximized. The problem was studied by Bez\'{a}kov\'{a} and Dani \cite{BD05} and Golovin \cite{G05} who obtained approximation algorithms
that provably return a solution that is always a factor of $O(n)$ within the optimal value. The problem was popularized by Bansal and Sviridenko \cite{BS06} as the
{\em Santa Claus problem}, where Santa Claus aims to distribute presents to the kids so as to maximize the happiness of the least happy kid. Subsequently, Asadpour and
Saberi \cite{AS07} presented an $O(\sqrt{n}\log^3 n)$-approximation algorithm for this problem.

\paragraph{Our results.} In this paper, we consider allocation of indivisible items to players having additive utility functions over the items. We present an alternative proof that no deterministic truthful allocation function minimizes envy
by characterizing the deterministic truthful allocation functions for two players and two items. Our proof
actually shows that for any truthful allocation function, there are instances in which the envy is almost
maximized. Our proof simplifies the proof of Lipton et al. \cite{LMMS04} that uses a large number of items.
Our impossibility result trivially extends to the case of many players and many items and also to the more general case of non-additive utility functions.
We also present an improved analysis of uniformly random allocations of $m$ items
over $n$ players. We show that the envy is at most $O(\alpha\sqrt{m\ln n})$ with high probability, where $\alpha$ is the maximum utility per item
over all players and items. For the case where the sum of utilities of each player is $1$, we prove a bound of $O(\sqrt{\alpha\ln n})$.
This improves the previous bound of $O(\sqrt{\alpha} n^{1/2+\epsilon})$ for any $\epsilon>0$ \cite{LMMS04}. Our proof follows similar lines
to the proof of \cite{LMMS04} but we exploit the fact that the allocation of each item is independent and use the Hoeffding bound instead
of the Chebychev inequality in order to bound the envy.

\paragraph{Roadmap.} Our characterization of the deterministic truthful allocations for two players and two items is presented in Section \ref{sec:det}.
The analysis of random allocations is presented in Section \ref{sec:rand}.

\section{Truthful allocations for two players and two items}\label{sec:det}
In this section we present a characterization of deterministic truthful allocations with two players
and two items.

In general, the first player will have utilities $u_1 x$ for the first item and $u_1 (1-x)$ for the second one
while the utilities of the second player are $u_2 y$ and $u_2 (1-y)$, respectively. Here, $x,y \in [0,1]$
and $u_1$, $u_2$ are the sums of utilities of the two players for both items.
So, an allocation function gets as input $u_1$, $u_2$, $x$, and $y$ and computes an allocation of the items
to the players. We denote each of the four possible allocations as a $2\times 2$ matrix with entries $1$ and $0$.
The columns correspond to the players and the rows to the items. An $1$ in an entry of such a matrix indicates
that the item corresponding to the row is allocated to the player corresponding to the column.

We use the term non-boundary values to denote real numbers in $[0,1]$ different than $0$, $1/2$, and $1$. We consider only
non-boundary values for $x$ and $y$ since they suffice for proving our main result on the envy. Our characterization
can be easily extended to boundary values of $x$ and $y$ as well.

We begin with an observation that simplifies the allocation functions that have to be considered.

\begin{lemma}\label{lem:total-utility}
For non-boundary values of $x$ and $y$, no truthful allocation function $f$ depends on $u_1$ and $u_2$.
\end{lemma}

\begin{proof}
Assume that this is not the case and that $f$ computes different allocations on inputs $(u_1, u_2, x, y)$ and $(u'_1, u_2, x, y)$ where
$x,y$ have non-boundary values and $u_1\not=u'_1$.

When $x$ has a non-boundary value, the four different possible allocations $\left(\begin{array}{c c}1 & 0\\1& 0\end{array}\right)$,
$\left(\begin{array}{c c}1 & 0\\0&1\end{array}\right)$, $\left(\begin{array}{c c}0 &1\\1&0\end{array}\right)$, and $\left(\begin{array}{c c}0 & 1\\0&1\end{array}\right)$
yield different benefit to player $1$ when her utilities on the items are $u_1 x$ and $u_1(1-x)$, namely $u_1$, $u_1 x$, $u_1(1-x)$, and $0$.

Now assume that the function $f$ returns an allocation of higher benefit to player $1$ when she reports $u'_1$ instead of $u_1$. Then, player $1$ has an incentive
to lie. If this is not the case and $f$ returns an allocation of lower benefit when player $1$ reports $u'_1$, then consider the case when
player $1$ has true utilities $u'_1 x$ and $u'_1(1-x)$ on the two items. In this case, player $1$ would have an incentive to lie and
report $u_1 x$ and $u_1(1-x)$ as her valuation.
\qed\end{proof}

By Lemma \ref{lem:total-utility}, we may assume that $f$ depends only on $x$ and $y$ when they have non-boundary values. Without loss of generality,
we also assume that $u_1=u_2=1$ in the following.

\begin{lemma}\label{lem:properties}
A truthful allocation function $f$ has the following properties:
\begin{enumerate}
\item[(a)] If $f(x^*,y^*)$ assigns both items to the same player for some non-boundary values $x^*,y^*$, then
$f(x,y)$ assigns both items to that player for any non-boundary values $x,y$.
\item[(b)] If $f(x^*,y^*)$ assigns to player $1$ the item which she prefers the least for some non-boundary values $x^*, y^*$, then $f(x,y^*)$ assigns that item
to player $1$ for any non-boundary value $x$.
\item[(c)] If $f(x^*,y^*)$ assigns to player $2$ the item which she prefers the least for some non-boundary values $x^*, y^*$, then $f(x^*,y)$ assigns that item
to player $2$ for any non-boundary value $y$.
\end{enumerate}
\end{lemma}

\begin{proof}
(a) Assume that the allocation function assigns both items to player $1$ for some non-boundary values and at most one of the items for some other non-boundary values.
Then, one of the following must hold:
\begin{itemize}
\item There exist non-boundary values $x^*,y^*,x'$ such that $f(x^*,y^*)$ assigns both items to player $1$ and $f(x',y^*)$ assigns at most one of the items to player $1$.
In this case, if the true utility of player $1$ for item $1$ is $x'$, she has an incentive to lie and report $x^*$ in order to get both items.
\item There exist non-boundary values $x^*,y^*,y'$ such that $f(x^*,y^*)$ assigns both items to player $1$ and $f(x^*,y')$ assigns at most one of the items to player $1$.
In this case, if the true utility of player $2$ for item $1$ is $y^*$, she has an incentive to lie and report $y'$ in order to get at least one item.
\end{itemize}
The case in which the allocation function assigns both items to player $2$ is symmetric.

(b) Consider the case with $x^*<1/2$ (the case $x^*>1/2$ is symmetric) so that $f(x^*,y^*)$ assigns item $1$ to player $1$. Assume otherwise that there exists a non-boundary
value $x'$ such that $f(x',y^*)$ assigns item $2$ to player $1$. Then, if the true utility of player $1$ for item $1$ is $x^*$, player $1$ has an incentive to lie and report
$x'$ in order to get item $2$ which she prefers the most.

(c) The proof of this case is very similar to (b).
\qed\end{proof}

The properties of Lemma \ref{lem:properties} yield the following.

\begin{lemma}
The only truthful allocations with respect to non-boundary item valuations are those depicted in Figure \ref{fig:alloc}.
\end{lemma}

\begin{figure}[htbp]
\centerline{\psfig{file=allocations.eps,height=2.2in}}  %,width=3in
\caption{The eight truthful allocation functions for two players.}
\label{fig:alloc}
\end{figure}

\begin{proof}
Figure \ref{fig:alloc} contains the eight possible allocation functions that satisfy the properties of Lemma \ref{lem:properties}.
Truthfulness follows since for each player, given the valuation of the other player, these allocation functions either assign her
the most preferred item or the allocation does not depend on her valuations.
\qed\end{proof}

We are now ready to prove the main statement of this section.

\begin{theorem}\label{thm:envy}
No truthful allocation minimizes envy.
\end{theorem}

\begin{proof}
Clearly, for the two first fixed truthful allocation functions of Figure \ref{fig:alloc}, both items are assigned to one player and hence
the other player always has envy $1$. Let $\epsilon\in (0,1/4)$. Consider the two valuation pairs $(1-\epsilon,1/2+\epsilon)$ and
$(1/2+\epsilon,1-\epsilon)$. The allocations $\left(\begin{array}{c c}1&0\\0&1\end{array}\right)$ and $\left(\begin{array}{c c}0&1\\1&0\end{array}\right)$
yield envy $2\epsilon$, respectively. For any of the six last truthful allocation functions of Figure \ref{fig:alloc}, in one of these
valuations pairs, the allocation yields benefit $\epsilon$ for one player and $1/2+\epsilon$ to the other. Hence, one player
has envy $1-2\epsilon$. By setting $\epsilon$ very close to $0$, we have that the envy is actually maximized.
\qed\end{proof}

\begin{figure}[htbp]
\centerline{\psfig{file=envy.eps,height=2.1in}}  %,width=3in
\caption{The minimum envy allocation function when the sum of utilities of each player on the two items is $1$.}
\label{fig:envy}
\end{figure}

We remark that the four non-fixed allocation functions in Figure \ref{fig:alloc} produce an envy-free allocation if one exists.
Figure \ref{fig:envy} presents the allocations that minimize envy when the sum of the utilities of each player
on the items is $1$. The grey areas indicate the cases of envy-free allocations.
The two pairs of valuations considered in the proof of Theorem \ref{thm:envy} have been selected to be outside but very close
to these areas.

\section{Improved analysis of random allocations}\label{sec:rand}
In this section we consider the randomized allocation function that allocates each item to a player selected
uniformly at random among the $n$ players and in such a way that the allocation of an item is independent
of the other allocations. Note that the allocation function does not depend on the valuations of the players.
Hence, it is truthful in expectation since no player has an incentive to report a false valuation in order to
increase her expected benefit. We present an upper bound on the envy of the resulting allocations using
Hoeffding inequality \cite{H63}.

\begin{theorem}[Hoeffding \cite{H63}]
Let $X_1, \dots, X_k $ be independent random variables with $\Pr(X_i \in [a_i, b_i]) = 1$ for $1\leq i\leq k$.
Then, for the sum of these variables $S = \sum_{i=1}^k{X_i}$, we have
\[\Pr(S - \E[S] \geq t) \leq \exp \left( - \frac{2\,t^2}{\sum_{i=1}^k (b_i - a_i)^2} \right).\]
\end{theorem}

So, the particular version of Hoeffding inequality upperbounds the probability that a random variable
which can be expressed as the sum of independent random variables exceeds its expectation by a certain amount.
Our statement is the following; besides the number of players and items, it is also expressed in terms of
the maximum utility per item over all players. We assume that the number $n$ of players is large and the
term high probability denotes a probability of $1-1/n$. We also denote by $v_{p,i}$ the utility of player $p$ for
item $i$.

\begin{theorem}
Consider an instance with $n$ players and $m$ items and let $\alpha=\max_{p,i}{v_{p,i}}$.
\begin{itemize}
\item[(a)] With high probability, the random allocation yields an envy of at most $O(\alpha\sqrt{m\ln n})$.
\item[(b)] If the sum of utilities of each player is $1$, then with high probability, the random allocation yields an envy of at most $O(\sqrt{\alpha \ln n})$.
\end{itemize}
\end{theorem}

\begin{proof}
Consider two players $p$ and $q$. We define the random variable $Y_i^{pq}$ indicating the contribution of item $i$ to the envy of player $p$ for player $q$.
Then, the envy $S^{pq}$ of player $p$ for player $q$ is $S^{pq}=\sum_{i=1}^m{Y_i^{pq}}$.
Observe that
\begin{itemize}
\item $Y_i^{pq}=v_{p,i}$ if item $i$ is allocated to $q$ (and this happens with probability $1/n$),
\item $Y_i^{pq}=-v_{p,i}$ if item $i$ is allocated to $p$ (and this happens with probability $1/n$), and
\item $Y_i^{pq}=0$ if item $i$ is not allocated to $p$ or $q$ (this happens with probability $1-2/n$).
\end{itemize}
Clearly, the random variables $Y_i^{pq}$ are independent, $\Pr(Y_i^{pq}\in [-v_{p,i},v_{p,i}])=1$ and $\E[S^{pq}]=0$.
By applying the Hoeffding bound for any $t\geq 0$, we have
\begin{eqnarray}\label{ineq:hoeffding}
\Pr(S^{pq}\geq t) &\leq &\exp\left(-\frac{t^2}{2\sum_{i=1}^m{v_{p,i}^2}}\right).
\end{eqnarray}
In order to prove (a), we use inequality (\ref{ineq:hoeffding}) by setting $t=\alpha\sqrt{6m\ln n}$ and the fact that $\sum_{i=1}^m{v_{p,i}^2}\leq m\alpha^2$ to obtain
\begin{eqnarray*}
\Pr(S^{pq}\geq \alpha\sqrt{6m\ln n}) &\leq & 1/n^3.
\end{eqnarray*}
Since there are at most $n^2$ pairs of players $p,q$, by applying the union bound we have that the probability that the maximum envy between any two players exceeds $\alpha\sqrt{6m\ln n}$ is at most $1/n$.

In order to prove (b), we set $t=\sqrt{6\alpha\ln n}$ and use the fact that $\sum_{i=1}^m{v_{p,i}^2}\leq \alpha$ when $\sum_{i=1}^m{v_{p,i}}=1$ and $v_{p,i}\geq 0$. By (\ref{ineq:hoeffding}), we obtain that
\begin{eqnarray*}
\Pr(S^{pq}\geq \sqrt{6\alpha\ln n}) &\leq & 1/n^3.
\end{eqnarray*}
Again, by applying the union bound we have that the probability that the maximum envy between any two players exceeds $\sqrt{6\alpha\ln n}$ is at most $1/n$.
\qed\end{proof}

The first upper bound should be compared to the lower bound of $\alpha$ \cite{LMMS04} on the envy of allocations in which the maximum utility per item among all
players is $\alpha$. This bound is shown to be tight in \cite{LMMS04} but the upper bound is not obtained by a truthful allocation function. Our second upper bound significantly
improves the upper bound of $O(\sqrt{\alpha}n^{1/2+\epsilon})$ for the case where the sum of utilities of each player is $1$. Whether there exist better allocation functions
(i.e., that yield allocations with smaller envy) that are truthful in expectation is an interesting open problem.

\paragraph{Acknowledgments.} We thank Ariel Procaccia for helpful discussions.

\begin{thebibliography}{99}
%\bibitem{ADG91}
%A. Alkan, G. Demange, and D. Gale. Fair allocation of
%indivisible goods and criteria of justice. {\em Econometrica}, Vol.
%59, pp. 1023--1039, 1991.

\bibitem{AS07}
A. Asadpour and A. Saberi.
Max-min fair allocation of indivisible
goods. In {\em Proceedings of the 39th ACM Symposium on Theory of Computing
(STOC '07)}, pp. 114--121, 2007.

\bibitem{BS06}
N. Bansal and M. Sviridenko. The Santa Claus problem. In {\em Proceedings of the 38th ACM Symposium on Theory of Computing (STOC '06)}, pp. 31--40, 2006.

\bibitem{BD05}
I. Bez\'{a}kov\'{a} and V. Dani. Allocating indivisible goods. {\em SIGecom Exchanges}, Vol. 5 (3), pp. 11--18, 2005.

\bibitem{BL08}
S. Bouveret and J. Lang. Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity, {\em Journal of Artificial Intelligence Research}, Vol. 32, pp. 525--564, 2008.

\bibitem{BT95}
S. J. Brams and A. D. Taylor. An
envy-free cake division protocol. {\em The American Mathematical
Monthly}, Vol. 102 (1), pp. 9--18, 1995.

\bibitem{BT96}
S. J. Brams and A. D. Taylor. Fair division: From
cake-cutting to dispute resolution. {\em Cambridge
University Press}, 1996.

\bibitem{BTZ97}
S. J. Brams, A. D. Taylor, and W. S. Zwicker. A moving-knife solution to the four-person envy free cake division problem. {\em Proceedings of the American Mathematical Society}, Vol. 125(2), pp. 547-554, 1997

\bibitem{BKM05}
C. Busch, M. S. Krishnamoorthy, and
M. Magdon-Ismail. Hardness results for cake-cutting. {\em Bulletin
of the EATCS}, Vol. 86, pp. 85--106, 2005.

\bibitem{CDEL06}
Y. Chevaleyre, P. E. Dunne, U. Endriss,
J. Lang, M. Lema\^itre, N. Maudet, J. Padget,
S. Phelps, J. A. Rodr\'iguez-Aguilar, and P. Sousa. Issues
in multiagent resource allocation. {\em Informatica}, Vol. 30, pp. 3--31,
2006.

\bibitem{CEEM07}
Y. Chevaleyre, U. Endriss, S. Estivie, and N. Maudet. Reaching envy-free states in distributed negotiation settings. In {\em Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI '07)}, pp. 1239­-1244, 2007.

\bibitem{CEM07}
Y. Chevaleyre, U. Endriss, and N. Maudet. Allocating goods on a graph to eliminate envy. In {\em Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI '07)}, pp. 700--705, 2007.

%\bibitem{CL01}
%T. H. Cormen, C. E. Leiserson, R. L.
%Rivest, and C. Stein. Introduction to algorithms, Second edition. {\em MIT
%Press}, 2001.

%\bibitem{DH03}
%M. Dall'Aglio and T. P. Hill. Maximin-share and
%minimax-envy in fair-division problems. {\em Journal of
%Mathematical Analysis and Applications}, Vol. 281 (1), pp. 346--361, 2003.

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

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

%\bibitem{F67}
%D. Foley. Resource allocation and the public sector.
%{\em Yale Economics Essays}, Vol. 7, pp. 45--98, 1967.

\bibitem{G05}
D. Golovin. Max-min fair allocation of indivisible
goods. {\em Technical Report, Carnegie Mellon University},
CMU-CS-05-144, 2005.

\bibitem{H63}
W. Hoeffding. Probability inequalities for sums of bounded random variables. {\em Journal of the American Statistical Association}, Vol. 58 (301), pp. 13--30, 1963.

%\bibitem{KRT99}
%J. Kleinberg, Y. Rabani and E. Tardos. Fairness in
%routing and load balancing. In {\em Proceedings of the 40th Annual Symposium on
%Foundations of Computer Science (FOCS '99)}, pp. 568--578, 1999.

%\bibitem{KK00}
%A. Kumar and J. Kleinberg. Fairness measures for
%resource allocation. In {\em Proceedings of the 41st Annual Symposium on Foundations of
%Computer Science (FOCS '00)}, pp. 75--85, 2000.

%\bibitem{LST90}
%J. K. Lenstra, D. B. Shmoys and E. Tardos.
%Approximation algorithms for scheduling unrelated
%parallel machines. {\em Mathematical Programming}, Vol. 46, pp. 259--271, 1990.

\bibitem{LMMS04}
R. Lipton, E. Markakis, E. Mossel and A. Saberi. On
approximately fair allocations of indivisible goods. In
{\em Proceedings of the 5th ACM Conference on Electronic Commerce (EC '04)}, pp. 125--131, 2004.

\bibitem{MS07}
A. Mu'alem and M. Schapira.
Setting lower bounds on truthfulness.
In {\em Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07)}, pp. 1143--1152, 2007.

\bibitem{NRTV07}
N. Nisan. Introduction to mechanism design (for computer scientists). Chapter in: N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, eds.
{\em Algorithmic game theory}. Cambridge University Press, 2007.

\bibitem{P09}
A. Proccacia.
Thou shalt covet thy neighbor's cake.
In {\em Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI '09)}, 2009, to appear.

\bibitem{RW98}
J. M. Robertson and W. A. Webb. Cake-cutting
algorithms: Be fair if you can, {\em AK Peters Ltd}, 1998.

%\bibitem{ST93}
%D. B. Shmoys and E. Tardos. An approximation
%algorithm for the generalized assignment problem.
%{\em Mathematical Programming, Series A}, Vol. 62, pp. 461--474,
%1993.

\bibitem{S48}
H. Steinhaus. The problem of fair division.
{\em Econometrica}, Vol. 16, pp. 101--104, 1948.

\bibitem{S80}
W. Stromquist. How to cut a cake fairly.
{\em American Mathematical Monthly}, Vol. 87 (8), pp. 640--644, 1980.

\bibitem{S08}
W. Stromquist. Envy-free cake divisions
cannot be found by finite protocols. {\em The Electronic Journal
of Combinatorics}, Vol. 15, R11, 2008.

%\bibitem{TT93}
%K. Tadenuma and W. Thomson. The fair allocation of
%an indivisible good when monetary compensations are
%possible. {\em Mathematical Social Sciences}, Vol. 25 (2), pp. 117--132,
%1993.

%\bibitem{V74}
%H. Varian. Equity, envy and efficiency. {\em Journal of
%Economic Theory}, Vol. 9, pp. 63--91, 1974.

\bibitem{WS07}
G. J. Woeginger and J. Sgall.
On the complexity of cake-cutting. {\em Discrete Optimization}, Vol. 4, pp. 213--220, 2007.
\end{thebibliography}
\end{document} 