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.
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: . 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).There is a set
C
C
C
There are
n
i
Vi:C\toR
C
Define the following measure:
V=
n | |
\sum | |
i=1 |
Vi
Note that each
Vi
V
vi:C\to[0,infty)
X\inC
Vi(X)=\intXvidV
The
vi
x\inC
n | |
\sum | |
i=1 |
vi(x)=1
\foralli:0\leqvi(x)\leq1
For every point
x\inC
x
v(x)=(v1(x),...,vn(x))
Note that
v(x)
(n-1)
Rn
\Deltan-1
\Delta
n
The RNS of a cake is the set of all its RNS points:
RNS(C)=\{v(x)\midx\inC\}
The cake is decomposed and then re-constructed inside
\Delta
\Delta
\Delta
n=2
\Delta
n=3
We imagine a table shaped like an equilateral triangle with each consumer seated at a vertex... the desirability to consumer
i
v\in\Delta
vi
i
vi
The unit simplex
\Delta
i
\Deltai
C
i
C
\Deltai
Here are two example partitions for the two-partner example, where
\Delta
\Delta
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=(w1,...,wn)\in\Delta
\Delta=\Delta1\cup … \cup\Deltan
w
For all
i,j
(v1,...,vn)\in\Deltai
vi | |
vj |
\geq
wi | |
wj |
C=X1\cup … \cupXn
w
\Delta
w
For all
i,j
x\inXi
vi(x) | |
vj(x) |
\geq
wi | |
wj |
It is possible to prove that:
A partition
C=X1\cup … \cupXn
w=(w1,...,wn)\in\Delta+
if-and-only-if it maximizes the sum:
V1(X1) | + … + | |
w1 |
V1(Xn) | |
wn |
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,[1] the following theorem is also true:
A positive partition
C=X1\cup … \cupXn
\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:
(0.4,0.6)
(0.3,0.7)
VAlice | |
0.4 |
+
VGeorge | |
0.6 |
(0.5,0.5)
(0.5,0.5)
(0.5,0.5)
VAlice | |
0.5 |
+
VGeorge | |
0.5 |
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.