라돈-니코딤 세트

페어케이크 커팅 이론에서 라돈-니코디엠 세트(RNS)는 사람들이 케이크의 다른 부분을 어떻게 평가하느냐에 따라 케이크를 나타내는 기하학적 물체다.

예

네 부분으로 된 케이크가 있다고 가정합시다.취향이 다른 앨리스와 조지 두 사람이 있는데, 사람마다 케이크의 다른 부분을 다르게 중시한다.아래 표에는 부품과 부품 값이 설명되어 있으며, 마지막 행인 "RNS Point"가 뒤에 설명되어 있다.

	초콜릿	레몬	바닐라	체리
앨리스의 가치	18	9	1	2
조지의 가치	18	0	4	8
RNS 포인트	(0.5,0.5)	(1,0)	(0.2,0.8)	(0.2,0.8)

케이크 한 조각의 "RNS 포인트"는 그 조각에 대한 파트너들의 상대적 가치를 설명한다.그것은 두 개의 좌표를 가지고 있다. 하나는 앨리스와 다른 하나는 조지를 위한 것이다.예를 들면 다음과 같다.

• 파트너는 초콜릿 부분의 값에 동의하기 때문에 RNS 포인트의 좌표도 같다(합계가 1이 되도록 정규화된다).
• 레몬 부분은 앨리스에게만 가치가 있으므로, 그 RNS 포인트에서는 앨리스의 좌표만 1인 반면 조지의 좌표는 0이다.
• 바닐라 부분과 체리 부분 모두에서 앨리스의 가치와 조지의 가치 사이의 비율은 1:4이다.따라서, 이것은 또한 RNS 지점의 좌표 사이의 비율이다.바닐라와 체리는 모두 동일한 RNS 포인트에 매핑된다는 점에 유의하십시오.

케이크의 RNS는 모든 RNS 포인트의 집합일 뿐이다. 위의 케이크에서 이 세트는 {(0.5,0.5), (1,0), (0.2,0.8)}의 세 점을 포함한다.세그먼트(1,0)-(0,1)로 나타낼 수 있다.

(1.0,.0)	(.9,.1)	(.8,.2)	(.7,.3)	(.6,.4)	(.5,.5)	(.4,.6)	(.3,.7)	(.2,.8)	(.1,.9)	(.0,1.0)
레몬	-	-	-	-	초콜릿	-	-	바닐라, 체리	-	-

실제로 케이크는 분해되어 세그먼트(1,0)-(0,1)에 다시 구성된다.

정의들

$세트{\displaystyle }$ C$${\$displaystyle C$}("$$케이크")와 $세트{\displaystyle \mathbb{}}$ C ${\$이(가) 있는데, 이는$$ $C{\displaystyle }$ ${\displaystyle C}$의 하위 집합의 시그마 앨지브라입니다$.$

$파트너$는 $.$모든 파트너 $i{\displaystyle }$ ${\displaystyle i}$은$($는) 개인 가치 $측정{\displaystyle {}_{}{V}_{}}$i$$: ${\displaystyle C\mathbb{}}$ → R {\$displaystyle$ V_${i}:\mathb {C$} $\to$ \mathb ${R}.$이 측정치는 $C{\displaystyle }$ ${\displaysty C}$의 각 하위 집합이 해당 파트너에게 얼마만큼의 가치가 있는지$$ 결정한다.

다음 측정을 정의하십시오.

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

각 ${\displaystyle {Vi}_{}}$ ${\$는 $V{\displaystyle }$ ${\displaystyle V}$에 대해 절대적으로 연속적인 조치라는 점에 유의하십시오. 따라서 라돈-Nikodym 정리에서는 라돈-Nikodym 파생상품이 있는데, 이 파생상품은 $v{\displaystyle {}_{}}$ i :${\displaystyle {}_{}C}$→${\displaystyle }$[ ${\displaystyle 0}$, ${\displaystyle \mathrm{\infty }}$) ${\displaystyle v_{i}:$${\displaystyle 모든}$ $측정{\displaystyle }$ 가능한 부분 집합 X에 대해 C$\to [0$$,\$ )}:$\mathb {C$

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

$v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$를 값 밀도 함수라고 한다.케이크 x ${\displaystyle x}$C ${\displaystyle x\in C}$의 거의 모든 포인트에 대해 다음과 같은 특성이 있다$.$^{[1]: 222}

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

모든 점 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\displaystyle$ x$\in C}$에 대해$,$ $x{\displaystyle }${\$displaystyle$x}의 RNS 점은 다음과 같이 정의된다$$.

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

Note that ${\displaystyle v(x)}$ is always a point in the ${\displaystyle (n-1)}$-dimensional unit simplex in ${\displaystyle \mathbb {R} ^{n}}$, denoted by ${\displaystyle \Delta ^{n-1}}$ (or just ${\displaystyle \Delta }$ when ${\displaystyle n}$ is clear from the con문자 메시지를 보내다

케이크의 RNS는 모든 RNS 포인트의 집합이다.

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

케이크는 분해되었다가 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$ 안에 다시 생성된다$.$ $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta}$의 각 꼭지점은 n 파트너 중 하나와 연결된다$$.케익의 각 부분은 가치에$$ 따라 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$의 한 지점에 매핑된다. 즉, 한 조각이 파트너에게 더 가치 있을수록 해당 파트너의 꼭지점에 더 가깝다.위의 예에서는 $n{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle n=2}$ 파트너$$(여기서 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$은(는) (1,0)과 (0,1) 사이의 세그먼트일 뿐이다.Akin은^[2] $n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$ 파트너에$$ 대한 RNS의 의미를 설명한다.

우리는 각 소비자가 꼭지점에 앉아있는 등변 삼각형 모양의 테이블을 상상한다.$v{\displaystyle }$ v${\displaystyle \mathrm{\Delta }}${\$displaystyle$ v$\in \Delta}$ 지점에서 케이크 조각의$$ $소비자{\displaystyle }$ i$${\$displaystyle i$}에 대한 만족도는 $정점{\displaystyle }$ i$${\$displaystyle$i}에 대한 근접도를 측정하는$$ 편심 $좌표{\displaystyle {}_{}}$ ${\displaystyle v_{}}$ i$${\$displaystyty v_{i}$에 의해 주어진다$$$.$따라서 $v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 정점에 1이고$$ 반대 면에 0 값으로 선형적으로 감소한다.

효율적인 RNS 파티션

심플렉스 ${\displaystyle \Delta }$ 유닛은 파트너 간에 파티션을 분할할 수 있으며$$, 각 파트너 $i{\displaystyle }${\$displaystyle i}$에 하위 ${\displaystyle {집합}_{}}$ $\Delta {\displaystyle {\mathrm{}}_{}}$ i${\$를 부여한다$.$ 이러한 파티션 각각은 ${\$$dyte}$의 파티션을 유도하며, 파트너 $i{\displaystyle }$ ${\$$d$$}$는 $C$의 비트를 받는다$$.RNS 포인트가 $\Delta {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle i_{}}$ ${\$에 포함되는$$ $isplaystyle$ C$\}.$

다음은 2-파트너 예제의 두 가지 예제 파티션으로, 여기서 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta}$은(는) (1,0)과 (0,1) 사이의 세그먼트임

• 점(0.4,0.6)에서$$ $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$을(를) 절단하십시오.세그먼트(1.0)-(0.4,0.6)를 앨리스에게 주고 세그먼트(0.4,0.6)-(0,1)를 조지에게 준다.이것은 레몬과 초콜릿을 앨리스에게 주고, 나머지는 조지에게 주는 것에 해당한다.
• 같은 점(0.4,0.6)을 자르되, 세그먼트(1,0)-(0.4,0.6)를 조지(총값 18)에게, 세그먼트(0.4,0.6)-(0,1)를 앨리스(총값 3)에게 준다.

첫 번째 칸막이는 두 번째 칸막이보다 훨씬 더 효율적이게 보인다. 첫 번째 칸막이는 각 파트너에게 더 가치 있는 부분(단순함의 정점에 더 가까운 부분)이 주어지는 반면, 두 번째 칸막이는 그 반대다.사실 첫 번째 칸막이는 파레토 효율적이지만 두 번째 칸막이는 효율적이지 않다.예를 들어, 두 번째 칸막이의 경우, 앨리스는 초콜릿의 2/9와 교환하여 그 체리를 조지에게 줄 수 있다. 이렇게 하면 앨리스의 효용성은 2가 향상되고 조지의 효용성은 4가 향상된다.이 예는 우리가 아래에 정의한 일반적인 사실을 예시한다.

$\Delta$ }의 모든 $점{\displaystyle }$ w${\displaystyle }$=${\displaystyle }$( ${\displaystyle {w\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle w_{}}$ ${\displaystyle {}_{}}$)${\displaystyle \mathrm{\Delta }}$ ${\displaystyle w=(w_{1},\dots ,w_{n}}\$in \Delta $}$:

• 다음과 $같은{\displaystyle \mathrm{}}$ 경우${\displaystyle {\mathrm{}}_{}}$ =${\displaystyle {}_{}}$Δ ${\displaystyle {1\mathrm{}}_{}}$ ⋯ ${\displaystyle \cdots }$ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\Delta n}_{}}$ ${\$\cdots $\cup \Delta _{n}$의 파티션이 $w{\displaystyle }$ ${\displaysty w$에 속한다고$$ 가정하십시오.

For all ${\displaystyle i,j}$ and for all ${\displaystyle (v_{1},\dots ,v_{n})\in \Delta _{i}}$: ${\displaystyle {\frac {v_{i}}{v_{j}}}\geq {\frac {w_{i}}{w_{j}}}}$

• $C{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$∪ ${\displaystyle \cdots }$ $style$ X n {\$displaystyle C=X_{1}\cdots \cdots X_{n}}$의 파티션이 $w{\displaystyle }$ ${\$displaystyle w$}$에 속하는 $\Delta$${\displaystyle \Delta }$의 파티션에 의해 유도된 경우$$$w{\displaystyle }$ ${\displaystystystystytype$ w$}$에 속한다고$$ 가정합시다$.$ I.

For all ${\displaystyle i,j}$ and for all ${\displaystyle x\in X_{i}}$: ${\displaystyle {\frac {v_{i}(x)}{v_{j}(x)}}\geq {\frac {w_{i}}{w_{j}}}}$

다음을 증명할 수 있다.^{[1]: 241–244}

파티션 $C{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \cdots }$ ∪ ${\displaystyle \cup }$ $∪$X n {\$displaystyle C=X_{1$}\$cdots \cdots$ X_{n}}}컵$X_{$n}}}}은${\displaystyle (}w$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle w_{}}$)${\displaystyle \in }$ ${\displaystyle {\mathrm{}}^{}}$+ ${\$}\dots{n$}}}}}}}}}\delta ^{$n$\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}$

if-and-only-sum을 최대화하는 경우: $V{\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{{1\mathrm{}}_{}}{}}$( ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{{1\mathrm{}}_{}}{}}$) ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{{1\mathrm{}}_{}}{}}$+ ${\displaystyle \cdots }$+ ${\displaystyle \frac{{V\mathrm{}}_{}}{}}$ ${\displaystyle 1\frac{{}_{}}{}}$( ${\displaystyle \frac{X_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$) ${\displaystyle \frac{{}_{}}{}}$ w ${\displaystyle \frac{w_{}}{}}$ ${\${1}}}+\cdots $+{\v_{1}(X_{n$}}}){n$}}}}}{w_{$w_${$n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}:{w_{

즉, 중량 벡터 $w{\displaystyle }$ ${\displaystyle w}$을(를) 갖는 가중-유용-최대 분할인 경우$.$

모든 파레토 효율적 분할은 일부 가중치 선정에 대해 Weightd-utilitary-maximal이기 때문에 다음과 같은 정리도 사실이다.^{[3][1]: 246}

양의 파티션 $C{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}\cup }$ ⋯ ${\displaystyle \cup }$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$는 $\Delta {\displaystyle {\mathrm{}}^{}}$+ ${\$의 일부 양수에 속한다$$$.$

만약 파레토 효율적이라면, if-and-only.

그래서 파레토 효율적인 파티션 집합과 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$의 포인트 사이에 매핑이 있다$.$

위의 예제로 돌아가기:

• 첫 번째 칸막이(앨리스에게 레몬과 초콜릿을 주고 나머지 칸막이를 조지에게 주는 것$)$는${\displaystyle }$포인트${\displaystyle }({\displaystyle 0.}$4${\displaystyle ,}$ 0.${\displaystyle 6}$ $){\디스플레이$ 스타일 $(0$${\displaystyle .4}$$,$ 0$){\디스플레이$ 스타일 $(0.3,$ 0.7)} (0$.$3,$0.7)})$과 같은 다른 포인트 (일부 칸막이는 1 포인트 이상에 속한다.실제로 V ${\displaystyle \frac{{\text{Alice}}_{}}{}}$ ${\displaystyle \frac{0.}{}}$4${\displaystyle }$+ ${\displaystyle V\frac{{}_{}}{}}$ ${\displaystyle \frac{{\text{George}}_{}}{}}$ ${\displaystyle \frac{{}_{}}{.6}}$ ${\${\text$}$의 합을 최대화하는 실용적인 케이크 커팅이다.$앨리스}}{0.$$4.}+{\frac {V_{\text{George}}{0}{0.$$6$ 그리고 파레토 효율도 있다.
• 대조적으로, 두 번째 칸막이는 어떤 점에도 속하지 않으며, 실제로 파레토 효율적이지 않다.
• 많은 다른 칸막이가 속하는 몇 가지 지점들이 있다.For example, the point ${\displaystyle (.5,.5)}$. This is a point of the RNS and there is a positive mass of cake associated with it, so any partition of that mass leads to a partition that belongs to ${\displaystyle (0.5,0.5)}$. For example, giving the Lemon and Chocolate to Alice (value 27) and the rest to George(값 12)는${\displaystyle }$(${\displaystyle 0.}$5${\displaystyle ,0.5}$ ) ${\displaystyle (0.5,0.5)}$에 속하며$,$ 레몬을 앨리스에게만 주고, 나머지는 조지에게 초콜릿의 절반을 앨리스에게 주고(값 18) 나머지 반은 조지(값 21)에게도 속한다.이러한 모든 파티션은 V ${\displaystyle \frac{{\text{Alice}}_{}}{}}$ ${\displaystyle \frac{0}{}}$.5${\displaystyle }$+ V ${\displaystyle \frac{{\text{George}}_{}}{\mathrm{}}}$.${\displaystyle \frac{5}{}}$의 합을 최대화하며, ${\$$앨리스}}{0.$$5}+{\frac {V_{\text{George}}{0}{0.$$5}}$; 정말, 이 모든 칸막이의 합은 78이다.그들은 모두 파레토 효율적이다.

역사

RNS는 두빈스-스페인어 이론의 일부로서 소개되었고 웰러의 정리 증명과 후에 에단 아킨에 의해 결과에 사용되었다.^[2]라돈-니코디엠 세트라는 용어는 율리우스 바르바넬이 만들었다.^[1]

참고 항목

• 개별 피스 세트

참조