ラドン・ニコディムセット

公平なケーキカットの理論において、ラドン・ニコディム集合（RNS）は、異なる人々がケーキの異なる部分をどのように評価するかに基づいて、ケーキを表す幾何学的オブジェクトである。

4つの部分からなるケーキがあるとします。アリスとジョージという2人の人物は好みが異なり、それぞれがケーキの各部分を異なる価値で評価します。下の表は、各部分とその価値を示しています。最後の行「RNSポイント」については後ほど説明します。

ケーキの「RNSポイント」は、そのケーキに対するパートナーの相対的な価値を表します。RNSポイントには2つの座標があり、1つはアリス用、もう1つはジョージ用です。例：

• パートナーはチョコレート部分の値について合意しているため、そのRNSポイントの座標も等しくなります（合計が1になるように正規化されます）。
• レモンの部分はアリスにとってのみ価値があるので、そのRNSポイントでは、アリスの座標のみが1であり、ジョージの座標は0である。
• バニラとチェリーの両方の部分において、アリスの値とジョージの値の比率は1:4です。したがって、これは彼らのRNSポイントの座標の比率でもあります。バニラとチェリーはどちらも同じRNSポイントにマッピングされていることに注意してください。

ケーキの RNS は、そのケーキのすべての RNS 点の集合です。上記のケーキでは、この集合には 3 つの点が含まれます: {(0.5,0.5), (1,0), (0.2,0.8)}。これは、線分 (1,0)-(0,1) で表すことができます。

実際には、ケーキはセグメント(1,0)-(0,1)上で分解され、再構築されます。

セットがあります${\displaystyle C}$（「ケーキ」）とセット${\displaystyle \mathbb {C} }$これは、サブセットのシグマ代数である。${\displaystyle C}$。

がある${\displaystyle n}$パートナー。すべてのパートナー${\displaystyle i}$個人的な価値観を持っている${\displaystyle V_{i}:\mathbb {C} \to \mathbb {R} }$この尺度は、各サブセットがどれだけ${\displaystyle C}$それはそのパートナーにとって価値がある。

以下の尺度を定義してください。

${\displaystyle V=\sum _{i=1}^{n}V_{i}}$

各${\displaystyle V_{i}}$は、​${\displaystyle V}$したがって、ラドン・ニコディムの定理により、ラドン・ニコディム微分が存在し、それは関数である。${\displaystyle v_{i}:C\to [0,\infty )}$すべての可測部分集合に対して${\displaystyle X\in \mathbb {C} }$:

${\displaystyle V_{i}(X)=\int _{X}v_{i}\,dV}$

の${\displaystyle v_{i}}$これらは値密度関数と呼ばれます。ケーキのほぼすべての点において、これらは以下の性質を持ちます。${\displaystyle x\in C}$: ^{[ 1 ] : 222}

• ${\displaystyle \sum _{i=1}^{n}v_{i}(x)=1}$
• ${\displaystyle \forall i:0\leq v_{i}(x)\leq 1}$

各ポイントについて${\displaystyle x\in C}$RNSポイント${\displaystyle x}$定義は以下のとおりです。

${\displaystyle v(x)=(v_{1}(x),\dots ,v_{n}(x))}$

ご了承ください${\displaystyle v(x)}$常にポイント${\displaystyle (n-1)}$次元単位単体$\displaystyle \mathbb {R} ^{n}}$、で示される$\displaystyle \Delta ^{n-1}}$（または単に）${\displaystyle \Delta }$いつ${\displaystyle n}$（文脈から明らかである）。

ケーキのRNSとは、そのケーキに含まれるすべてのRNSポイントの集合のことである。

${\displaystyle RNS(C)=\{v(x)\mid x\in C\}}$

ケーキは分解され、内部で再構築される。${\displaystyle \Delta }$. 各頂点${\displaystyle \Delta }$n個のパートナーのうちの 1 つに関連付けられています。ケーキの各部分は、${\displaystyle \Delta }$評価によると、パートナーにとって価値の高いピースほど、そのパートナーの頂点に近くなります。これは上記の例で示されています。${\displaystyle n=2}$パートナー（${\displaystyle \Delta }$は (1,0) と (0,1) の間のセグメントです。Akin ^{[ 2 ]}はRNS の意味を次のように説明しています。${\displaystyle n=3}$パートナー：

正三角形の形をしたテーブルを想像し、各消費者が頂点に座っている様子を思い浮かべます...消費者にとっての魅力${\displaystyle i}$ケーキのかけらの${\displaystyle v\in \Delta }$重心座標によって与えられる${\displaystyle v_{i}}$頂点との近さを測定する${\displaystyle i}$。 したがって、${\displaystyle v_{i}}$頂点では1であり、反対側の面では0まで直線的に減少する。

単位単体${\displaystyle \Delta }$パートナー間で分割することができ、各パートナーに${\displaystyle i}$部分集合$\displaystyle \Delta _{i}}$それぞれの分割によってケーキの分割が生じる。${\displaystyle C}$パートナーが${\displaystyle i}$ビットを受け取る${\displaystyle C}$そのRNSポイントは$\displaystyle \Delta _{i}}$。

2人のパートナーの例の2つのパーティションの例を以下に示します。${\displaystyle \Delta }$は(1,0)と(0,1)の間の線分です

• カット${\displaystyle \Delta }$点(0.4,0.6)において、線分(1,0)-(0.4,0.6)をアリスに、線分(0.4,0.6)-(0,1)をジョージに与えます。これは、レモンとチョコレートをアリスに与え（合計値27）、残りをジョージに与える（合計値12）ことに相当します。
• 同じ点 (0.4,0.6) で線分を切りますが、線分 (1,0)-(0.4,0.6) をジョージに (合計値 18)、線分 (0.4,0.6)-(0,1) をアリスに (合計値 3) 与えます。

最初の分割は2番目の分割よりもはるかに効率的に見えます。最初の分割では、各パートナーは自分にとってより価値のあるピース（単体の頂点に近いピース）を受け取りますが、2番目の分割ではその逆になります。実際、最初の分割はパレート効率的ですが、2番目の分割はそうではありません。たとえば、2番目の分割では、アリスはジョージにチェリーを渡す代わりにチョコレートの2/9を受け取ることができます。これにより、アリスの効用は2、ジョージの効用は4向上します。この例は、以下で定義する一般的な事実を示しています。

各ポイントについて${\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta }$:

• 分割すると、${\displaystyle \Delta =\Delta _{1}\cup \cdots \cup \Delta _{n}}$に属する${\displaystyle w}$、 もし：

すべての人にとって${\displaystyle i,j}$そしてすべての${\displaystyle (v_{1},\dots ,v_{n})\in \Delta _{i}}$:${\displaystyle {\frac {v_{i}}{v_{j}}}\geq {\frac {w_{i}}{w_{j}}}}$

• 分割すると、${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$に属する${\displaystyle w}$分割によって誘発される場合${\displaystyle \Delta }$に属する${\displaystyle w}$例：

すべての人にとって${\displaystyle i,j}$そしてすべての${\displaystyle x\in X_{i}}$:${\displaystyle {\frac {v_{i}(x)}{v_{j}(x)}}\geq {\frac {w_{i}}{w_{j}}}}$

以下のことが証明できる。^{[ 1 ]： 241-244}

仕切り${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$肯定的な点に属する${\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta ^{+}}$、

合計を最大化する場合に限り：${\displaystyle {\frac {V_{1}(X_{1})}{w_{1}}}+\cdots +{\frac {V_{1}(X_{n})}{w_{n}}}}$

すなわち、重みベクトルを持つ重み付き功利主義的最大分割である場合に限る。${\displaystyle w}$。

すべてのパレート効率的な分割は、ある重みの選択に対して重み付き功利主義的に最大化されるため、^{[ 3 ]}次の定理も成り立つ。^{[ 1 ]： 246}

正の分割${\displaystyle C=X_{1}\cup \cdots \cup X_{n}}$何らかの肯定的な点に属する${\displaystyle \Delta ^{+}}$、

パレート効率的である場合に限る。

つまり、パレート効率的な分割の集合と点の間にはマッピングが存在する。${\displaystyle \Delta }$。

上記の例に戻ってみましょう。

• 最初の分割（レモンとチョコレートをアリスに、残りをジョージに与える）は、${\displaystyle (0.4,0.6)}$、その他次のような点にも${\displaystyle (0.3,0.7)}$（一部の分割は複数の点に属する）。実際、これは合計を最大化する功利主義的な分割である。${\displaystyle {\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{George}}}{0.6}}}$さらに、パレート効率的でもある。
• 対照的に、2番目の分割はどの点にも属さず、実際、パレート効率的ではない。
• いくつかの異なるパーティションが属するポイントがあります。たとえば、ポイント${\displaystyle (0.5,0.5)}$これは RNS のポイントであり、それにはケーキの正の質量が関連付けられているため、その質量の分割は、${\displaystyle (0.5,0.5)}$例えば、レモンとチョコレートをアリスに（価値27）、残りをジョージに（価値12）与えることは、${\displaystyle (0.5,0.5)}$アリスにレモンだけを与え（値9）、残りをジョージに与える（値30）のもこれに該当します。アリスにレモンとチョコレートの半分を与え（値18）、残りをジョージに与える（値21）のもこれに該当します。など。これらの分割はすべて合計を最大化します。${\displaystyle {\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{0.5}}}$実際、これらの分割すべてにおいて、この合計は78となる。これらはすべてパレート効率的である。

RNSは、Dubins–Spanierの定理の一部として導入され、 Wellerの定理の証明や、後にEthan Akinによって得られた結果に使用されました。^{[ 2 ]}「Radon–Nikodymセット」という用語はJulius Barbanelによって造語されました。^{[ 1 ]}最終的にはJohann RadonとOtto M. Nikodymにちなんで名付けられました。

• 個々のピースセット