View source for Radon–Nikodym set

{{Short description|Geometric object that represents a "cake"}}
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.

{| class="wikitable" style="text-align:center"
|-
!        !! Chocolate !! Lemon !! Vanilla !! Cherries
|-
| Alice's value  || <big>18</big>  || <big>9</big> ||  <big>1</big>  || <big>2</big>
|-
| George's value || <big>18</big> || <big>0</big> ||  <big>4</big>  || <big>8</big>
|-
| 
|- 
| RNS point      || <big>(0.5,0.5)</big> || <big>(1,0)</big> ||  <big>(0.2,0.8)</big>  || <big>(0.2,0.8)</big>
|}

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 partners agree on the values for the chocolate part, so the coordinates of its RNS point are also equal (they are normalized such that their sum is 1). 
* The lemon part is only valuable for Alice, so in its RNS point, only Alice's coordinate is 1 while George's coordinate is 0.
* In both the vanilla and the cherries part, the ratio between Alice's value to George's value is 1:4. Hence, this is also the ratio between the coordinates of their RNS points. Note that both the vanilla and the cherries are mapped to the same RNS point.

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):

{| class="wikitable"
|-
! (1.0,&nbsp;0.0) !! (0.9,&nbsp;0.1) !! (0.8,&nbsp;0.2) !! (0.7,&nbsp;0.3) !! (0.6,&nbsp;0.4) !! (0.5,&nbsp;0.5) !! (0.4,&nbsp;0.6) !! (0.3,&nbsp;0.7) !! (0.2,&nbsp;0.8) !! (0.1,&nbsp;0.9) !! (0.0,&nbsp;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 <math>C</math> ("the cake"), and a set <math>\mathbb{C}</math> which is a [[sigma-algebra]] of subsets of <math>C</math>.

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

Define the following measure:
:<math>V = \sum_{i=1}^n V_i</math>

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

The <math>v_i</math> are called ''value-density functions''. They have the following properties, for almost all points of the cake <math>x\in C</math>:<ref name=Barbanel/>{{rp|222}}
* <math>\sum_{i=1}^n v_i(x) = 1</math>
* <math>\forall i: 0\leq v_i(x)\leq 1</math>

For every point <math>x\in C</math>, the RNS point of <math>x</math> is defined by:
:<math>v(x) = (v_1(x),\dots,v_n(x))</math>

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

The '''RNS''' of a cake is the set of all its RNS points:
:<math>RNS(C) = \{v(x) \mid x\in C\}</math>

The cake is decomposed and then re-constructed inside <math>\Delta</math>. Each vertex of <math>\Delta</math> is associated with one of the ''n'' partners. Each fraction of the cake is mapped to a point in <math>\Delta</math> 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 <math>n=2</math> partners (where <math>\Delta</math> is just the segment between (1,0) and (0,1)). Akin<ref name=Akin95/> describes the meaning of the RNS for <math>n=3</math> partners:
::We imagine a table shaped like an equilateral triangle with each consumer seated at a vertex... <!--::v(A) is the mass of cake in the subset A of the simplex while --> the desirability to consumer <math>i</math> of a fragment of cake at a point <math>v \in \Delta</math> is given by the barycentric coordinate <math>v_i</math> measuring its closeness to vertex <math>i</math>. Thus, <math>v_i</math> is 1 at the vertex and declines linearly to value 0 at the opposite face.

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

Here are two example partitions for the [[#Example|two-partner example]], where <math>\Delta</math> is the segment between (1,0) and (0,1)
* Cut <math>\Delta</math> in the point (0.4,0.6). Give the segment (1,0)-(0.4,0.6) to Alice and the segment (0.4,0.6)-(0,1) to George. This corresponds to giving the Lemon and Chocolate to Alice (total value 27) and the rest to George (total value 12). 
* Cut in the same point (0.4,0.6), but give the segment (1,0)-(0.4,0.6) to George (total value 18) and the segment (0.4,0.6)-(0,1) to Alice (total value 3).
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 <math>w = (w_1,\dots,w_n) \in \Delta</math>:
* Say that a partition of <math>\Delta = \Delta_1 \cup \cdots \cup \Delta_n</math> ''belongs to <math>w</math>'', if:
::For all <math>i,j</math> and for all <math>(v_1,\dots,v_n)\in \Delta_i</math>: <math>\frac{v_i}{v_j} \geq \frac{w_i}{w_j}</math>
* Say that a partition of <math>C = X_1 \cup \cdots \cup X_n</math> belongs to <math>w</math>, if it is induced by a partition of <math>\Delta</math> that belongs to <math>w</math>. I.e:
::For all <math>i,j</math> and for all <math>x \in X_i</math>: <math>\frac{v_i(x)}{v_j(x)} \geq \frac{w_i}{w_j}</math>

It is possible to prove that:<ref name=Barbanel/>{{rp|241–244}}
::A partition <math>C = X_1 \cup \cdots \cup X_n</math> belongs to a positive point <math>w = (w_1,\dots,w_n) \in \Delta^+</math>,
::if-and-only-if it maximizes the sum: <math>\frac{V_1(X_1)}{w_1}+\cdots+\frac{V_1(X_n)}{w_n}</math>
::I.e, iff it is a [[utilitarian cake-cutting|weighted-utilitarian-maximal]] division with weight vector <math>w</math>.

Since every Pareto-efficient division is weighetd-utilitarian-maximal for some selection of weights,<ref>{{Cite journal|title=Two applications of a theorem of Dvoretsky, Wald, and Wolfovitz to cake division|doi=10.1023/a:1004966624893 |year=1997 |last1=Barbanel |first1=Julius B. |journal=Theory and Decision |volume=43 |issue=2 |pages=203 |last2=Zwicker |first2=William S. }}</ref> the following theorem is also true:<ref name=Barbanel/>{{rp|246}}
::A positive partition <math>C = X_1 \cup \cdots \cup X_n</math> belongs to some positive point in <math>\Delta^+</math>,
::if-and-only-if it is [[Pareto-efficient]].

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

Returning to the above example:
* The first partition (giving the Lemon and Chocolate to Alice and the rest to George) belongs to the point <math>(0.4,0.6)</math>, as well as to other points such as <math>(0.3,0.7)</math> (some partitions belong to more than one point). Indeed, it is a [[utilitarian cake-cutting]] that maximizes the sum <math>\frac{V_\text{Alice}}{0.4} + \frac{V_\text{George}}{0.6}</math>, and it is also Pareto-efficient.
* In contrast, the second partition does not belong to any point, and indeed it is not Pareto-efficient.
* There are some points to which many different partitions belong. For example, the point <math>(0.5,0.5)</math>. This is a point of the RNS and there is a positive mass of cake associated with it, so any partition of that mass leads to a partition that belongs to <math>(0.5,0.5)</math>. For example, giving the Lemon and Chocolate to Alice (value 27) and the rest to George (value 12) belongs to <math>(0.5,0.5)</math>; giving only the Lemon to Alice (value 9) and the rest to George (value 30) also belongs to it; giving the Lemon and half the chocolate to Alice (value 18) and the rest to George (value 21) also belongs to it; etc. All these partitions maximize the sum <math>\frac{V_\text{Alice}}{0.5} + \frac{V_\text{George}}{0.5}</math>; indeed, this sum is 78 in all these partitions. They are all Pareto-efficient.

== 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]].<ref name=Akin95>{{Cite journal|doi=10.1016/0304-4068(94)00674-y|title=Vilfredo Pareto cuts the cake|journal=Journal of Mathematical Economics|volume=24|pages=23|year=1995|last1=Akin|first1=Ethan}}</ref> The term "Radon–Nikodym set" was coined by [[Julius Barbanel]].<ref name=Barbanel>{{Cite Geometry of Efficient Fair Division}}</ref>

== See also ==
* [[Individual pieces set]]

== References ==
{{reflist}}

{{DEFAULTSORT:Radon-Nikodym set}}
[[Category:Cake-cutting]]
[[Category:Measure theory]]