Radon–Nikodym set

In the theory of fair cake-cutting, the Radon–Nikodym set (RNS) is a geometric object that represents a cake, based on how different people evaluate the different parts of the cake.

Example

Suppose we have a cake made of four parts. There are two people, Alice and George, with different tastes: each person values the different parts of the cake differently. The table below describes the parts and their values; the last row, "RNS Point", is explained afterwards.

Chocolate Lemon Vanilla Cherries
Alice's value 18 9 1 2
George's value 18 0 4 8
RNS point (0.5,0.5) (1,0) (0.2,0.8) (0.2,0.8)

The "RNS point" of a piece of cake describes the relative values of the partners to that piece. It has two coordinates - one for Alice and one for George. For example:

The RNS of a cake is just the set of all its RNS points; in the above cake this set contains three points: {(0.5,0.5), (1,0), (0.2,0.8)}. It can be represented by the segment (1,0)-(0,1):

(1.0,.0) (.9,.1) (.8,.2) (.7,.3) (.6,.4) (.5,.5) (.4,.6) (.3,.7) (.2,.8) (.1,.9) (.0,1.0)
Lemon - - - - Chocolate - - Vanilla, Cherries - -

In effect, the cake is decomposed and re-constructed on the segment (1,0)-(0,1).

Definitions

There is a set C ("the cake"), and a set \mathbb{C} which is a sigma-algebra of subsets of C.

There are n partners. Every partner i has a personal value measure V_i: \mathbb{C} \to \mathbb{R}. This measure determines how much each subset of C is worth to that partner.

Define the following measure:

V = \sum_{i=1}^n V_i

Note that each V_i is an absolutely continuous measure with respect to V. Therefore, by the Radon–Nikodym theorem, it has a Radon–Nikodym derivative, which is a function v_i: C\to [0,\infty) such that for every measurable subset X\in \mathbb{C}:

V_i(X) = \int_X v_i \, dV

The v_i are called value-density functions. They have the following properties, for almost all points of the cake x\in C:[1]:222

For every point x\in C, the RNS point of x is defined by:

v(x) = (v_1(x),\dots,v_n(x))

Note that v(x) is always a point in the (n-1)-dimensional unit simplex in \mathbb{R}^n, denoted by \Delta^{n-1} (or just \Delta when n is clear from the context).

The RNS of a cake is the set of all its RNS points:

RNS(C) = \{v(x) | x\in C\}

The cake is decomposed and then re-constructed inside \Delta. Each vertex of \Delta is associated with one of the n partners. Each fraction of the cake is mapped to a point in \Delta according to the valuations: the more valuable a piece is to a partner, the closer it is to that partner's vertex. This is shown in the above example for n=2 partners (where \Delta is just the segment between (1,0) and (0,1)). Akin[2] describes the meaning of the RNS for n=3 partners:

We imagine a table shaped like an equilateral triangle with each consumer seated at a vertex... the desirability to consumer i of a fragment of cake at a point v \in \Delta is given by the barycentric coordinate v_i measuring its closeness to vertex i. Thus, v_i is 1 at the vertex and declines linearly to value 0 at the opposite face.

Efficient RNS partitions

The unit simplex \Delta can be partitioned among the partners, giving each partner i a subset \Delta_i. Each such partition induces a partition of the cake C, in which partner i receives the bits of C whose RNS-points fall within \Delta_i.

Here are two example partitions for the two-partner example, where \Delta is the segment between (1,0) and (0,1)

The first partition looks much more efficient than the second one: in the first partition, each partner is given the pieces that are more valuable to him/her (closer to his/her vertex of the simplex), while in the second partition the opposite is true. In fact, the first partition is Pareto efficient while the second partition is not. For example, in the second partition, Alice can give the cherries to George in exchange for 2/9 of the chocolate; this will improve Alice's utility by 2 and George's utility by 4. This example illustrates a general fact that we define below.

For every point w = (w_1,\dots,w_n) \in \Delta:

For all i,j and for all (v_1,\dots,v_n)\in \Delta_i: \frac{v_i}{v_j} \geq \frac{w_i}{w_j}
For all i,j and for all x \in X_i: \frac{v_i(x)}{v_j(x)} \geq \frac{w_i}{w_j}

It is possible to prove that:[1]:241–244

A partition C = X_1 \cup \dots \cup X_n belongs to a positive point w = (w_1,\dots,w_n) \in \Delta^+,
if-and-only-if it maximizes the sum: \frac{V_1(X_1)}{w_1}+\cdots+\frac{V_1(X_n)}{w_n}
I.e, iff it is a weighted-utilitarian-maximal division with weight vector w.

Since every Pareto-efficient division is weighetd-utilitarian-maximal for some selection of weights,[3] the following theorem is also true:[1]:246

A positive partition C = X_1 \cup \dots \cup X_n belongs to some positive point in \Delta^+,
if-and-only-if it is Pareto-efficient.

So there is a mapping between the set of Pareto-efficient partitions and the points in \Delta.

Returning to the above example:

History

The RNS was introduced as part of the Dubins–Spanier theorems and used in the proof of Weller's theorem and later results by Ethan Akin.[2] The term "Radon–Nikodym set" was coined by Julius Barbanel.[1]

References

  1. 1 2 3 4 Barbanel, Julius B.; with an introduction by Alan D. Taylor (2005). The geometry of efficient fair division. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511546679. ISBN 0-521-84248-4. MR 2132232. Short summary is available at: Barbanel, J. (2010). "A Geometric Approach to Fair Division". The College Mathematics Journal 41 (4): 268. doi:10.4169/074683410x510263.
  2. 1 2 Akin, Ethan (1995). "Vilfredo Pareto cuts the cake". Journal of Mathematical Economics 24: 23. doi:10.1016/0304-4068(94)00674-y.
  3. Barbanel, Julius B.; Zwicker, William S. (1997). "Two applications of a theorem of Dvoretsky, Wald, and Wolfovitz to cake division". Theory and Decision 43 (2): 203. doi:10.1023/a:1004966624893.
This article is issued from Wikipedia - version of the Sunday, March 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.