Radonuppsättning - Nikodemus

I rättvis tårtskärningsteori är Radon -Nikodym-uppsättningen ( RNS) ett geometriskt objekt som representerar en tårta baserad på olika människors betyg av olika delar av den kakan.

Exempel

Anta att vi har en tårta med fyra delar. Det finns två personer, Alice och George, med olika smaker, varje person värderar olika delar av kakan olika. Tabellen nedan beskriver delarna och deras klassificering. Den sista raden, "RNS Point", förklaras senare.

	Choklad	Citron	Vanilj	Körsbär
Alices poäng	arton	9	ett	2
Georges poäng	arton	0	fyra	åtta

RNS-punkt	(0,5;0,5)	(1;0)	(0,2;0,8)	(0,2;0,8)

"RNS-punkten" för en tårtbit beskriver de relativa värdena för medlemmarna i dessa bitar. Den har två koordinater - en för Alice och en för George. Till exempel:

Deltagarna är överens om värdena för chokladdelen, så koordinaterna för RNS-punkten är också lika (de är normaliserade så att deras summa är 1).
Citrondelen har bara betydelse för Alice, så RNS-punkten har en koordinat på 1 för Alice, medan för George är koordinaten 0.
För vaniljdelen och körsbärsdelen är förhållandet mellan Alice och George-värdena 1:4. Därför gäller samma relation för koordinaterna för deras RNS-punkter. Observera att både vaniljdelen och körsbärsdelen kartläggs till samma RNS-punkt.

RNS för en tårta är uppsättningen av alla dess RNS-punkter. I kakan som beskrivs ovan består denna uppsättning av tre punkter: {(0.5;0.5), (1;0), (0.2;0.8)}. Det kan representeras av ett segment (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	-	-

Som ett resultat läggs kakan ut och rekonstrueras på segmentet (1;0)-(0;1).

Definitioner

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

Det finns deltagare. Varje deltagare har ett personligt måttvärde . Detta mått bestämmer vad varje delmängds poäng är för den medlemmen. $n$ $i$ $V_{i}:\mathbb {C} \to \mathbb {R}$ $C$

Låt oss definiera följande mått:

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

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

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

Funktionerna kallas värderingstäthetsfunktioner . De har följande egenskaper för nästan alla delar av kakan [1] : $v_{i}$ $x\in C$

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

För varje RNS-punkt definieras punktpunkten som: $x\in C$ $x$

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

Observera att det alltid är en punkt i den -dimensionella enheten simplex i , betecknad (eller helt enkelt , om det antyds i sammanhanget). $v(x)$ $(n-1)$ $\mathbb {R} ^{n}$ $\Delta ^{n-1}$ $\Delta$ $n$

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

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

Kakan bryts sönder och sätts sedan ihop inuti . Varje hörn är associerad med en av n medlemmar. Varje del av kakan mappas till en punkt i enligt poängen - ju mer värdefull biten är för deltagaren, desto närmare är den toppen av deltagaren. Detta visas i deltagarexemplet ovan (där bara linjesegmentet mellan (1,0) och (0,1)). Akin [2] beskriver betydelsen av RNS för deltagare: $\Delta$ $\Delta$ $\Delta$ $n=2$ $\Delta$ $n=3$

Låt oss föreställa oss en tabell i form av en liksidig triangel med konsumenter vid hörnen ... konsumentens önskan i kakfragmentet vid punkten ges av barycentriska koordinater , vilket återspeglar närheten till vertexet . Är då lika med 1 i toppen och minskar linjärt till 0 mot motsatt sida.

i

v\in \Delta

v_{i}

i

v_{i}

Effektiv RNS-partitionering

En enkel simplex kan delas mellan deltagare genom att skicka en delmängd till varje deltagare . Varje division genererar en tårtdelning där deltagaren får en tårtbit vars RNS-poäng faller in i . $\Delta$ $i$ $\Delta _{i}$ $C$ $i$ $C$ $\Delta _{i}$

Här är två exempel på partitioner för två deltagare , där är segmentet (1;0) - (0;1) $\Delta$

Vi skär vid punkten (0,4; 0,6). Vi ger segmentet (1; 0) - (0.4; 0.6) till Alice och segmentet (0.4; 0.6) - (0; 1) till George. Detta motsvarar att ge citron- och chokladdelarna till Alice (totalt värde 27) och att ge resten till George (totalt värde 12). $\Delta$
Vi skär samma punkt (0.4;0.6), men ger segmentet (1;0)-(0.4;0.6) till George (fullt värde 18) och segmentet (0.4;0.6)- (0;1) Alice (fullständigt) värde 3).

Den första partitionen verkar vara effektivare än den andra — i den första partitionen får varje deltagare en bit som är mer värdefull för honom/henne (närmare hans/hennes topp av simplexen), medan motsatsen är sant för andra partitionen. Faktum är att den första partitionen är Pareto-effektiv , medan den andra inte är effektiv. Till exempel, i den andra delningen kan Alice ge körsbär till George i utbyte mot 2/9 av chokladbiten. Detta kan förbättra Alices användbarhet med 2 och Georges med 4. Detta exempel illustrerar ett allmänt faktum som vi kommer att visa nedan.

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

Vi säger att en partition tillhör om: ${\displaystyle \Delta =\Delta _{1}\cup \cdots \cup \Delta _{n))$ $w$

För alla och alla :

I j

{\displaystyle (v_{1},\dots ,v_{n})\in \Delta _{i))

{\frac {v_{i}}{v_{j}}}\geqslant {\frac {w_{i}}{w_{j}}}

Vi säger att en partition tillhör om den genereras av en partition som tillhör . Det är: ${\displaystyle C=X_{1}\cup \cdots \cup X_{n))$ $w$ $\Delta$ $w$

För alla och för alla :

I j

{\displaystyle x\in X_{i))

{\frac {v_{i}(x)}{v_{j}(x)}}\geqslant {\frac {w_{i}}{w_{j}}}

Det kan bevisas att [3] :

Partitionen tillhör den positiva punkten ,

{\displaystyle C=X_{1}\cup \cdots \cup X_{n))

{\displaystyle w=(w_{1},\dots ,w_{n})\in \Delta ^{+))

om och bara om det maximerar summan:

{\frac {V_{1}(X_{1})}{w_{1}}}+\cdots +{\frac {V_{1}(X_{n})}{w_{n}} }

det vill säga om och endast om det är en maximalt nyttoviktad partition med en viktvektor .

w

Eftersom varje Pareto-effektiv division är maximal i användbarhet för vissa valda vikter [4] , är följande teorem också sant [5] :

En positiv partition tillhör någon positiv punkt vid om och endast om den är Pareto-effektiv .

{\displaystyle C=X_{1}\cup \cdots \cup X_{n))

{\displaystyle \Delta ^{+))

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

Återgår till exemplet ovan

Den första skiljeväggen (som ger citron- och chokladdelarna till Alice och resten till George) tillhör punkten (0.4;0.6) såväl som andra punkter som (0.3;0.7) (vissa skiljeväggar tillhör mer än en punkt ). Dessutom är skärning den nyttiga skärningen av kakan som maximerar summan och som också är Pareto-effektiv. ${\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{George}}}{0.6}}$
Samtidigt tillhör inte den andra partitionen någon punkt och är inte Pareto-effektiv.
Det finns flera punkter som flera olika partitioner hör till. Till exempel punkt (0,5;0,5). Detta är en punkt för RNS och det finns en positiv kakmassa associerad med dem, så varje uppdelning av denna massa resulterar i en partition som tillhör (0,5;0,5). Om vi till exempel ger citron- och chokladdelarna till Alice (värde 27) och ger resten till George (värde 12), får vi en partition som tillhör (0,5;0,5). Genom att ge Alice hela citrondelen (värde 9) och resten till George (värde 30), får vi en fördelning som också hör till denna punkt. Att ge hela citrondelen och hälften av chokladdelen till Alice (värde 18) och resten till George (värde 21) resulterar i en fördelning som också tillhör honom, och så vidare. Alla dessa partitioner maximerar summan . Dessutom är denna summa lika med 78 i alla dessa partitioner. De är alla Pareto-effektiva. ${\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{0.5}}$

Historik

RNS-uppsättningar introducerades som en del av Dubins-Spaniers satser och användes för att bevisa Wellers sats och senare resultat av Ethan Akin [6] . Termen "Radon-Nikodim set" introducerades av Julius Barbanel [7] .

Se även

Många enskilda delar

Anteckningar

↑ Barbanel, 2005 , sid. 222.
↑ Akin, 1995 , sid. 23.
↑ Barbanel, 2005 , sid. 241-244.
↑ Barbanel och Zwicker 1997 , sid. 203.
↑ Barbanel, 2005 , sid. 246.
↑ Akin, 1995 , sid. 23 Ethan.
↑ Barbanel, 2005 .

Litteratur

Julius B. Barbanel. Geometrin för effektiv rättvis uppdelning. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . En sammanfattning finns i artikeln
- Barbanel J. A Geometric Approach to Fair Division // The College Mathematics Journal. - 2010. - T. 41 , nr. 4 . - S. 268 . doi : 10.4169 / 074683410x510263 .
Julius B. Barbanel, William S. Zwicker. Två tillämpningar av ett teorem av Dvoretsky, Wald och Wolfovitz på kakdelning // Teori och beslut. - 1997. - T. 43 , nr. 2 . - doi : 10.1023/a:1004966624893 .
Ethan Akin. Vilfredo Pareto skär tårtan // Journal of Mathematical Economics. - 1995. - T. 24 . - doi : 10.1016/0304-4068(94)00674-y .