Radon-Nikodym set

I teorin om rättvis tårtskärning är Radon -Nikodym-setet (RNS) ett geometriskt objekt som representerar en tårta, baserat på hur olika människor utvärderar de olika delarna av kakan.

Exempel

Anta att vi har en kaka gjord av fyra delar. Det finns två personer, Alice och George, med olika smak: varje person värderar de olika delarna av kakan olika. Tabellen nedan beskriver delarna och deras värden; den sista raden, "RNS Point", förklaras efteråt.

	Choklad	Citron	Vanilj	Körsbär
Alices värde	18	9	1	2
Georges värde	18	0	4	8
RNS-punkt	(0,5,0,5)	(1,0)	(0.2,0.8)	(0.2,0.8)

"RNS-punkten" för en tårta beskriver de relativa värdena för partnerna till den biten. Den har två koordinater – en för Alice och en för George. Till exempel:

• Partnerna är överens om värdena för chokladdelen, så koordinaterna för dess RNS-punkt är också lika (de är normaliserade så att deras summa är 1).
• Citrondelen är bara värdefull för Alice, så i dess RNS-punkt är bara Alices koordinat 1 medan Georges koordinat är 0.
• I både vanilj- och körsbärsdelen är förhållandet mellan Alices värde och Georges värde 1:4. Därför är detta också förhållandet mellan koordinaterna för deras RNS-punkter. Observera att både vaniljen och körsbären är mappade till samma RNS-punkt.

RNS för en tårta är bara uppsättningen av alla dess RNS-punkter; i kakan ovan innehåller denna uppsättning tre punkter: {(0.5,0.5), (1,0), (0.2,0.8)}. Det kan representeras av segmentet (1,0)-(0,1):

(1,0, 0,0)	(0,9, 0,1)	(0,8, 0,2)	(0,7, 0,3)	(0,6, 0,4)	(0,5, 0,5)	(0,4, 0,6)	(0,3, 0,7)	(0,2, 0,8)	(0,1, 0,9)	(0,0, 1,0)
Citron	–	–	–	–	Choklad	–	–	Vanilj, körsbär	–	–

I själva verket bryts kakan ner och rekonstrueras på segmentet (1,0)-(0,1).

Definitioner

Det finns en uppsättning $C$ ("kakan"), och en uppsättning $\mathbb {C}$ som är en sigma-algebra av delmängder av $C$ .

Det finns $n$ partners. Varje partner $i$ har ett personligt värdemått V $\displaystyle V_{i}:\mathbb {C} \to \mathbb {R} }$ . Detta mått bestämmer hur mycket varje delmängd av $C$ är värd för den partnern.

Definiera följande mått:

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

Observera att varje $V_{i}$ är ett absolut kontinuerligt mått med avseende på $V$ . Därför har den enligt Radon–Nikodyms sats en Radon–Nikodym-derivata, som är en funktion $v_{i}:C\to [0,\infty )$ så att för varje mätbar delmängd $X\in \mathbb {C}$ :

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

V $v_{i}$ kallas värde -densitetsfunktioner De har följande egenskaper, för nästan alla punkter i kakan $x\in C$ :

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

För varje punkt $x\in C$ definieras RNS-punkten för ${\displaystyle x} av:$

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

Observera att $v(x)$ alltid är en punkt i $(n-1)$ -dimensionell enhetssimplex i $\mathbb {R} ^ {n}$ , betecknad med $\Delta ^{n-1}$ (eller bara $\Delta$ när $n$ är fri från sammanhanget).

RNS för en tårta är uppsättningen av alla dess RNS-punkter :

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

Kakan sönderdelas och återskapas sedan inuti $\Delta$ . Varje vertex av $\Delta$ är associerad med en av de n partnerna. Varje bråkdel av kakan mappas till en punkt i $\Delta$ enligt värderingarna: ju mer värdefull en bit är för en partner, desto närmare den partners vertex. Detta visas i exemplet ovan för $n=2$ partners (där $\Delta$ bara är segmentet mellan (1,0) och (0,1)). Akin beskriver betydelsen av RNS för $n=3$ partners:

Vi föreställer oss ett bord format som en liksidig triangel med varje konsument sittande vid en vertex... önskvärdheten för konsumenten $i$ av ett kakfragment vid en punkt $v\in \Delta$ är ges av den barycentriska koordinaten $v_{i}$ som mäter dess närhet till vertex $i$ . Således $v_{i}$ 1 i spetsen och avtar linjärt till värdet 0 på motsatt sida.

Effektiva RNS-partitioner

Enheten simplex $\Delta$ kan delas upp mellan partnerna, vilket ger varje partner $i$ en delmängd $\Delta _{i}$ . Varje sådan partition inducerar en partition av kakan $C$ , där partner $i$ tar emot bitarna av $C$ vars RNS-punkter faller inom $\Delta _{ i}$ .

Här är två exempelpartitioner för exemplet med två partner , där $\Delta$ är segmentet mellan (1,0) och (0,1)

• Klipp $\Delta$ i punkten (0.4,0.6). Ge segmentet (1,0)-(0,4,0,6) till Alice och segmentet (0,4,0,6)-(0,1) till George. Detta motsvarar att ge citronen och chokladen till Alice (totalt värde 27) och resten till George (totalt värde 12).
• Klipp in samma punkt (0,4,0,6), men ge segmentet (1,0)-(0,4,0,6) till George (totalt värde 18) och segmentet (0,4,0,6)-(0,1) till Alice ( totalt värde 3).

Den första partitionen ser mycket effektivare ut än den andra: i den första partitionen får varje partner de pjäser som är mer värdefulla för honom/henne (närmare hans/hennes hörn av simplexen), medan i den andra partitionen motsatsen är sant. Faktum är att den första partitionen är Pareto-effektiv medan den andra partitionen inte är det. Till exempel, i den andra partitionen kan Alice ge körsbären till George i utbyte mot 2/9 av chokladen; detta kommer att förbättra Alices nytta med 2 och Georges nytta med 4. Detta exempel illustrerar ett allmänt faktum som vi definierar nedan.

För varje punkt $w=(w_{1},\dots ,w_{n})\in \Delta$ :

• Säg att en partition av $\Delta =\Delta _{1}\cup \cdots \cup \Delta _{n}$ tillhör $w$ , om:

För alla $i,j$ och för alla $(v_{1},\dots ,v_{n})\in \Delta _{ i}$ : ${\frac {v_{i}}{v_{j}}}\geq {\frac {w_{i}}{w_{j}}}$

• Säg att en partition med $C=X_{1}\cup \cdots \cup X_{n}$ tillhör $w$ , om den induceras av en partition av $\Delta$ som tillhör $w$ . Dvs:

För alla $i,j$ och för alla $x\in X_{i}$ : ${\ displaystil {\frac {v_{i}(x)}{v_{j}(x)}}\geq {\frac {w_{i}}{w_{j}}}}$

Det är möjligt att bevisa att:

En partition $C=X_{1}\cup \cdots \cup X_{n}$ tillhör en positiv punkt ${\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta ^{+}} ,$ if

-and-only-om det maximerar summan: ${\frac {V_{1}(X_{1})}{w_{1}}}+\cdots +{\frac {V_{1}(X_{ n})}{w_{n}}}$

Dvs, om det är en viktad utilitaristisk-maximal division med viktvektor $w$ .

Eftersom varje Pareto-effektiv division är viktad-utilitaristisk-maximal för vissa urval av vikter, är följande sats också sant:

En positiv partition $C=X_{1}\cup \cdots \cup X_{n}$ tillhör någon positiv punkt i $\Delta ^{+}$ ,

om-och-bara-om den är Pareto-effektiv .

Så det finns en mappning mellan uppsättningen av Pareto-effektiva partitioner och punkterna i $\Delta$ .

För att återgå till exemplet ovan:

• Den första partitionen (som ger citronen och chokladen till Alice och resten till George) tillhör punkten $(0.4,0.6)$ , liksom till andra punkter som ${ \displaystyle (0.3,0.7)}$ (vissa partitioner tillhör mer än en punkt). Det är faktiskt en utilitaristisk kakskärning som maximerar summan ${\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{ George}}}{0.6}}$ och den är också Pareto-effektiv.
• Däremot tillhör den andra partitionen inte någon punkt, och den är faktiskt inte Pareto-effektiv.
• Det finns några punkter som många olika partitioner hör till. Till exempel punkten $(0.5,0.5)$ . Detta är en punkt i RNS och det finns en positiv kakmassa associerad med den, så varje partition av den massan leder till en partition som tillhör ( $\displaystyle (0.5,0.5)}$ . Till exempel, att ge citronen och chokladen till Alice (värde 27) och resten till George (värde 12) tillhör ( $\displaystyle (0.5,0.5)}$ ; att ge bara citronen till Alice (värde 9) och resten till George (värde 30) hör också till det; att ge citronen och hälften av chokladen till Alice (värde 18) och resten till George (värde 21) tillhör också det; etc. Alla dessa partitioner maximerar summan ${\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{ 0,5}}$ ; Denna summa är faktiskt 78 i alla dessa partitioner. De är alla Pareto-effektiva.

Historia

RNS introducerades som en del av Dubins-Spanier-satserna och användes i beviset för Wellers sats och senare resultat av Ethan Akin. Termen "Radon-Nikodym set" myntades av Julius Barbanel.

Se även

• Individuella stycken set