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.
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):
In effect, the cake is decomposed and re-constructed on the segment (1,0)-(0,1).
Definitions There is a set C {\displaystyle C} ("the cake"), and a set C {\displaystyle \mathbb {C} } which is a sigma-algebra of subsets of C {\displaystyle C} . There are n {\displaystyle n} partners. Every partner i {\displaystyle i} has a personal value measure V i : C → R {\displaystyle V_{i}:\mathbb {C} \to \mathbb {R} } . This measure determines how much each subset of C {\displaystyle C} is worth to that partner. Define the following measure:
V = ∑ i = 1 n V i {\displaystyle V=\sum _{i=1}^{n}V_{i}}
Note that each V i {\displaystyle V_{i}} is an absolutely continuous measure with respect to V {\displaystyle V} . Therefore, by the Radon–Nikodym theorem, it has a Radon–Nikodym derivative, which is a function v i : C → [ 0 , ∞ ) {\displaystyle v_{i}:C\to [0,\infty )} such that for every measurable subset X ∈ C {\displaystyle X\in \mathbb {C} } :
V i ( X ) = ∫ X v i d V {\displaystyle V_{i}(X)=\int _{X}v_{i}\,dV}
The v i {\displaystyle v_{i}} are called value-density functions. They have the following properties, for almost all points of the cake x ∈ C {\displaystyle x\in C} :
∑ i = 1 n v i ( x ) = 1 {\displaystyle \sum _{i=1}^{n}v_{i}(x)=1}
∀ i : 0 ≤ v i ( x ) ≤ 1 {\displaystyle \forall i:0\leq v_{i}(x)\leq 1}
For every point x ∈ C {\displaystyle x\in C} , the RNS point of x {\displaystyle x} is defined by:
v ( x ) = ( v 1 ( x ) , … , v n ( x ) ) {\displaystyle v(x)=(v_{1}(x),\dots ,v_{n}(x))}
Note that v ( x ) {\displaystyle v(x)} is always a point in the ( n − 1 ) {\displaystyle (n-1)} -dimensional unit simplex in R n {\displaystyle \mathbb {R} ^{n}} , denoted by Δ n − 1 {\displaystyle \Delta ^{n-1}} (or just Δ {\displaystyle \Delta } when n {\displaystyle n} is clear from the context). The RNS of a cake is the set of all its RNS points:
R N S ( C ) = { v ( x ) ∣ x ∈ C } {\displaystyle RNS(C)=\{v(x)\mid x\in C\}}
… excerpt ends here. Continue reading the full article.
