Radon–Nikodym set
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.
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 <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 <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>: the following theorem is also true: The term "Radon–Nikodym set" was coined by Julius Barbanel. Ultimately named after Johann Radon and Otto M. Nikodym.