%\documentstyle[12pt]{amsart}
\documentstyle[12pt]{amsart}
\begin{document}
\title{Satisfaction, Secrecy, and Inequity in the Problem of Fair
Division}
\author
{Raymond N. Greenwell
\\Hofstra University
}
\maketitle
\begin{abstract}
Two traditional criteria in the problem of fair division are
proportionality,
freedom from envy, and efficiency. To these we add two more:
maximization of
total satisfaction (the sum of all the players' evaluation of their own
piece),
and minimizing inequity. We show that these two criteria are
inconsistent. We
also show that secrecy of one's preferences, usually assumed in fair
division,
can be both advantageous and disadvantageous, depending upon the
circumstances.
\end{abstract}
%\newpage
\section{Introduction}
A topic that has recently become popular in mathematics courses for the
liberal arts major, to which Bob Bumcrot has devoted a great deal of
energy, is
fair division. The problem is to divide some object or set of objects
among $n$ players in such a way that all players receive their fair
share
in their own eyes. In this paper, we will consider the object to be
divisible in a continuous
way, such as a
cake or a piece of land, and we will consider
each player's fair share to be $1/n$. For cases in which a set of
indivisible objects is to be divided up, or where each player's fair
share is
not necessarily $1/n$, see \cite{brams} or \cite{webb}. Different people
may
value different parts of the cake differently, which allow for the
possibility of getting more than one's fair share.
There is a simple and elegant method for dividing a cake between two
people:
one person cuts and the other chooses. This method has two important
qualities of fair division:
\noindent
1) Proportionality: Each player is guaranteed a piece worth at least
$1/n$.
\noindent
2) Envy-free: Neither player prefers another player's piece.
For more than two players, the situation is more complicated. Methods
were
first developed after World War II by the Polish mathematicians Hugo
Steinhaus, Bronislaw Knaster, and Stefan Banach. At the present time,
there are
envy-free, proportional procedures using a finite number of cuts for
four or
fewer players. For more players, the best method so far, due to Brams
and
Taylor, is an envy-free, proportional procedure that can require an
unbounded
numbers of cuts. In practice, the remaining pieces eventually become so
small
that no one cares, so the procedure stops. This procedure also lacks a
third
important quality:
\noindent
3) Efficiency: No other division is strictly better for at least one
player and
at least as good for the others.
\section{Collective Satisfaction and Secrecy}
Let the value in the eyes of player $i$ of the piece given to player $j$
be
$v_{ij}$, where $0\le v_{ij}\le 1$ and $\sum_{j=1}^n v_{ij}=1.$ It
would be
desirable to maximize the collective satisfaction, defined as
$\sum_{i=1}^n v_{ii}.$ If all pieces are worth $1/n$ in each player's
eyes,
then the total satisfaction is 1, but in general it can be greater.
For example, suppose a cake has three equal-sized parts: chocolate,
vanilla, and
strawberry. Suppose Alice likes chocolate and vanilla equally well, but
does not
care at all for strawberry. Suppose Bill likes all flavors equally.
Alice makes a
cut dividing the cake into one piece, containing the chocolate, and a
second
piece, containing the vanilla and strawberry. Alice sees both pieces as
worth
1/2, but Bill sees the second piece as worth 2/3 and so chooses it. The
collective satisfaction is then $1/2+2/3=7/6\approx 1.16667.$
Fair division methods typically assume that each player does not know
the other
players' preferences. This is because a player can end up with a
smaller
piece if his or her preferences are known. In the previous example,
suppose Alice
knew that Bill likes all three flavors equally well. Then she can cut
the cake
into one piece containing all the chocolate and 49\% of the vanilla, and
a second
part containing all the strawberry and 51\% of the vanilla.
Unless Bill acts of out spite for Alice taking advantage of him, he will
choose
the second piece, for a satisfaction of $1/3+0.51*1/3\approx 0.5033,$
while
Alice ends up with a piece worth $1/2+0.49*1/2= 0.745.$ Notice that the
total
satisfaction is now approximately 1.2483, so Alice and Bill together are
better
off, but Bill is less satisfied than before.
There are other cases where lack of secrecy yields a division that is
preferable
to everyone. Consider the case where Alice, Bill, and Carol divide a
cake with
four equal-sized parts: chocolate, vanilla, strawberry, and coconut.
(See
figures.) All three like chocolate, only Alice likes vanilla, only Bill
likes
part strawberry, and only Carol likes coconut. If they all knew each
other's
preferences, they would realize the following obvious solution: give the
vanilla
to Alice, the strawberry to Bill, and the coconut to Carol, and divide
the
chocolate evenly between the three of them. Each player would then
receive a
part worth 2/3, for a collective satisfaction of 2.
In contrast, let us consider one possible outcome using the method of
Brams and
Taylor. (Because some of the steps are arbitrary, and the order of the
players
can be rearranged, different outcomes are possible.) In the first step,
Alice
divides the cake into three pieces that appear equal to her. There are
many
possibilities. Suppose the first piece consists of 2/3 of the chocolate
(worth
1/3 to her) and all of the strawberry and coconut (worth nothing to
her), as
shown. The second piece consists of 1/3 of the chocolate and 1/3 of the
vanilla. The third piece consists of 2/3 of the vanilla. Bill sees the
first
piece as worth 5/6, the second worth 1/6, and the third worth 0. In the
second
step, he trims the largest (first) piece as shown so it and the second
largest
piece are equal, that is, worth 1/6. In the third step, Carol puts aside
the
trimmings and then chooses whichever of the three pieces looks largest
to her.
Either the trimmed first piece or the second piece are worth 1/6;
suppose she
takes the second piece. Bill must take the trimmed piece if it is
available,
which it is in this case. Alice takes the third piece.
We repeat this process with the trimming. Alice cuts the trimming into
three
pieces, each containing 1/3 of the chocolate, and the third piece
containing
all the strawberry and coconut. Bill trims away the strawberry and
coconut.
Carol, then Bill, then Alice each takes one of the three identical
slices.
The process can go on indefinitely as the trimmings get smaller and
smaller,
but in this case, Alice has no interest in the trimmings and leaves the
process. Suppose that Bill and Carol divide up the trimming by Bill
cutting
halfway through the coconut, as shown, and Carol choosing the
all-coconut piece.
Then Alice's portion is worth $1/3+(1/9)(1/2)=7/18.$ Bill's portion is
worth
$1/6+(1/9)(1/2)+(1/2)(1/2)=17/36.$ Carol's portion is worth
$1/6+(1/9)(1/2)+1/2=13/18.$ The collective satisfaction is $19/12\approx
1.5833.$
Notice that some satisfaction is lost because Bill ends up with some
vanilla,
which is valuable only to Alice, and Carol ends up with some coconut,
which is
valuable only to Bill.
It may be that the best procedure is a division with preferences kept
secret,
followed by a revelation of preferences and another division, with a
voting procedure for deciding between the two divisions.
Such a combination procedure has not been thoroughly investigated by
researchers in fair division.
\section{Inequity}
Another issue that has not yet been sufficiently investigated is that of
inequity between the players. If $v_{ii}=v_{jj}$ for for all $i$ and
$j$, that
is, all players' portions in their own eyes are equal, the inequity is
0.
Otherwise, the inequality could be defined in various ways, such as the
standard
deviation of the $v_{ii}$.
Minimizing the inequity seems like a desirable goal. Unfortunately, it
is
inconsistent with the goal of maximizing the total satisfaction.
Consider the
example with Alice and Bill described earlier. The maximum satisfaction
is
achieved by giving Alice all the chocolate and vanilla, for a
satisfaction of 1,
and giving Bill the strawberry, for a satisfaction of 1/3, for a
collective
satisfaction of $4/3$. This is highly inequitable, but giving Bill any
more of
the cake will decrease the collective satisfaction. Any time a piece is
valued
differently, collective satisfaction is maximized by giving that piece
to the player
who values it most highly.
\section{Conclusions}
Researchers in fair division recognize that the ideal procedure has not
yet
been found, namely, one that is proportional, envy-free, and efficient,
and
that requires only a finite number of cuts. We have further complicated
matters by adding new criteria: maximizing collective satisfaction, and
minimizing inequity, which conflict with each other. Most procedures
rely on
secrecy of preferences; we have shown that this is not necessarily a
good
thing. We do not have the ideal solution to recommend here, but perhaps
the
ideas contained here might provoke others to find a better fair division
procedure.
%\newpage
\begin{thebibliography}{99}
\bibitem{brams} Steven J. Brams and Alan D. Taylor, {\it Fair Division:
from
Cake-Cutting to Dispute Resolution,} Cambridge University Press, 1996.
\bibitem{webb} Jack Robertson and William Webb, {\it Cake-Cutting
Algorithms:
Be Fair If You Can,} A K Peters, 1998.
\end{thebibliography}
\end{document}