On The Structure of Pareto Optimal Cake Partitions
by
Julius Barbanel
Department of Mathematics, Union College

We consider the cake division problem. Our "cake" C is some set. We wish to partition the cake among n players, whom we shall refer to as Player 1, Player 2, …, Player n. We assume that m1, m2, …, mn are countably additive, non-atomic, probability measures defined on some common sigma-algebra of subsets of C. For each i, Player i uses measure mi to evaluate the size of pieces of cake (i.e., subsets of C).

Consider a partition P = <P1, P2, …, Pn> of the cake among the n players where, for each i, Player i gets piece Pi. Various notions of why P might or might not be a "good" partition have been considered. These notions are of two types. One is concerned with issues of fairness. Two such characterizations of this type are proportionality and envy-freeness. We shall be concerned not with fairness issues, but with efficiency issues. More specifically, we shall be studying Pareto optimality. A partition P = <P1, P2, …, Pn> is said to be Pareto optimal if for no partition Q = <Q1, Q2, …, Qn> is it true that mi(Qi)>or=mi(Pi) for each i, with strict inequality holding for at least one such i. We study two geometric objects associated with cake partitions. We call these the Individual Pieces Set and the Radon - Nikodym Set.

The Individual Pieces Set, or IPS, is the set <m1(P1), m2(P2), …, mn(Pn)> : <P1, P2, …, Pn> is a partition of C. Dvoretsky, Wald, and Wolfovitz's Theorem [1951] tells us that the IPS is a closed and convex subset of Rn. It is not hard to see that the IPS includes the n-simplex and that it equals precisely the n-simplex if and only if the measures are identical. How much the IPS contains beyond the n-simplex reflects the degree to which the measures disagree.

Weller [1985] used Radon-Nikodym derivatives to provide a useful structure with which to study Pareto optimal partitions. Define a new measure m = m1+m2+…+mn. For each i, let fi, a function from the cake C to the reals, be the Radon-Nikodym derivative of mi with respect to m.

Let S denote the n-simplex in Rn. For each a in C, we define f(a) = <f1(a), f2(a), …, fn(a)>. Then, for almost every such a, f(a) is in S, and so f is a function from C to S. Intuitively, f(a) describes the relative worth that each player attaches to a, as compared to the other players. We note that the function f need not be 1-1 or onto. We shall refer to the range of f as the Radon - Nikodym Set, or RNS.

Every partition of C is associated with a point of the IPS and the Pareto optimal partitions associate with points on the " outer boundary" of the IPS. Weller [1985] described a natural association between Pareto optimal partitions and certain natural geometric constructions on the RNS.

We examine the relationship between these two structures. This study will connect these structures with the characterization of Pareto optimality as a maximization of convex combinations of the measures.

References:

1. Dvoretsky, A., Wald, A. and Wolfovitz, J, 1951, Relations among certain ranges of vector measures, Pacific Journal of Mathematics 1, 59-74.

2. Weller, D., 1985, Fair division of a measurable space, Journal of Mathematical Economics 14, 5-17.

Date received: April 25, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # caez-48.