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.
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 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).
has a personal value measure
This measure determines how much each subset of
Define the following measure: Note that each
is an absolutely continuous measure with respect to
Therefore, by the Radon–Nikodym theorem, it has a Radon–Nikodym derivative, which is a function
are called value-density functions.
They have the following properties, for almost all points of the cake
The RNS of a cake is the set of all its RNS points: The cake is decomposed and then re-constructed inside
Each fraction of the cake is mapped to a point in
according to the valuations: the more valuable a piece is to a partner, the closer it is to that partner's vertex.
Akin[2] describes the meaning of the RNS for
partners: The unit simplex
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.
: It is possible to prove that:[1]: 241–244 Since every Pareto-efficient division is weighetd-utilitarian-maximal for some selection of weights,[3] the following theorem is also true:[1]: 246 So there is a mapping between the set of Pareto-efficient partitions and the points in
Returning to the above example: 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.