Sada Radonu - Nikodém

V teorii poctivého krájení dortu je sada Radon – Nikodym ( RNS) geometrickým objektem, který představuje dort na základě hodnocení různých částí tohoto dortu různými lidmi.

Příklad

Předpokládejme, že máme dort se čtyřmi díly. Jsou dva lidé, Alice a George, s odlišným vkusem, každý si cení jiné části dortu jinak. Níže uvedená tabulka popisuje součásti a jejich hodnocení. Poslední řádek, "RNS Point", je vysvětlen později.

	Čokoláda	Citrón	Vanilka	Třešně
Alicino skóre	osmnáct	9	jeden	2
Georgeovo skóre	osmnáct	0	čtyři	osm

RNS bod	(0,5; 0,5)	(1;0)	(0,2; 0,8)	(0,2; 0,8)

„Bod RNS“ kusu koláče popisuje relativní hodnoty členů těchto kusů. Má dvě souřadnice - jednu pro Alici a jednu pro George. Například:

Účastníci se dohodnou na hodnotách čokoládové části, takže souřadnice bodu RNS jsou také stejné (jsou normalizovány tak, že jejich součet je 1).
Na citronové části záleží pouze Alici, takže bod RNS má pro Alici souřadnici 1, zatímco pro George je souřadnice 0.
U vanilkové a třešňové části je poměr mezi hodnotami Alice a George 1:4. Stejný vztah tedy platí pro souřadnice jejich RNS bodů. Všimněte si, že jak vanilková část, tak třešňová část mapují do stejného bodu RNS.

RNS dortu je soubor všech jeho RNS bodů. Ve výše popsaném koláči se tato množina skládá ze tří bodů: {(0,5;0,5), (1;0), (0,2;0,8)}. Může být reprezentován segmentem (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)
Citrón	-	-	-	-	Čokoláda	-	-	Vanilka, třešně	-	-

V důsledku toho je koláč rozložen a rekonstruován na segmentu (1;0)-(0;1).

Definice

Existuje množina („koláč“) a množina , což je sigma-algebra podmnožin množiny . $C$ $\mathbb {C}$ $C$

Existují účastníci. Každý účastník má osobní hodnotu měření . Tato míra určuje, jaké je skóre každé podmnožiny pro daného člena. $n$ $i$ $V_{i}:\mathbb {C} \to \mathbb {R}$ $C$

Definujme následující míru:

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

Všimněte si, že každá je absolutně spojitá míra s ohledem na . Proto podle Radon-Nikodimovy věty má Radon-Nikodimovu derivaci, což je funkce taková, že pro jakoukoli měřitelnou podmnožinu : $V_i$ $PROTI$ $v_{i}:C\to [0,\infty )$ $X\in \mathbb {C}$

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

Tyto vlastnosti se nazývají funkce hustoty ocenění . Mají následující vlastnosti pro téměř všechny body koláče [1] : $v_{i}$ $x\in C$

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

Pro jakýkoli bod RNS je bod tečky definován jako: $x\in C$ $X$

v(x)=(v_{1}(x),\tečky ,v_{n}(x))

Všimněte si, že je to vždy bod v -dimenzionální jednotce simplex v , označovaném (nebo jednoduše , pokud to vyplývá z kontextu). $v(x)$ $(n-1)$ $\mathbb {R} ^{n}$ $\Delta ^{n-1}$ $\Delta$ $n$

RNS dortu je soubor všech jeho RNS bodů:

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

Dort se rozbije a pak se uvnitř znovu sestaví . Každý vrchol je spojen s jedním z n členů. Každý díl dortu je namapován na bod v podle skóre - čím cennější je dílek pro účastníka, tím blíže je k vrcholu účastníka. To je ukázáno v příkladu účastníka výše (kde je pouze úsečka mezi (1,0) a (0,1)). Akin [2] popisuje význam RNS pro účastníky: $\Delta$ $\Delta$ $\Delta$ $n=2$ $\Delta$ $n=3$

Představme si tabulku ve tvaru rovnostranného trojúhelníku se spotřebiteli ve vrcholech ... touha spotřebitele ve fragmentu koláče v bodě je dána barycentrickými souřadnicemi , odrážejícími blízkost k vrcholu . Pak se rovná 1 nahoře a lineárně klesá na 0 směrem k opačné straně.

i

v\in \Delta

v_{i}

i

v_{i}

Efektivní rozdělení RNS

Jeden simplex lze sdílet mezi účastníky předáním podmnožiny každému účastníkovi . Každá divize generuje dortový split , ve kterém účastník obdrží kousek dortu, jehož body RNS spadají do . $\Delta$ $i$ $\Delta _{i}$ $C$ $i$ $C$ $\Delta _{i}$

Zde jsou dva příklady oddílů pro dva účastníky , kde je segment (1;0) - (0;1) $\Delta$

Řežeme v bodě (0,4; 0,6). Segment (1; 0) - (0,4; 0,6) dáme Alici a segment (0,4; 0,6) - (0; 1) Georgovi. To odpovídá předání částí citronu a čokolády Alici (celková hodnota 27) a předání zbytku Georgovi (celková hodnota 12). $\Delta$
Ořízli jsme stejný bod (0,4;0,6), ale segment (1;0)-(0,4;0,6) dáme Georgovi (plná hodnota 18) a segment (0,4;0,6)-(0;1) Alice (plná hodnota 3).

První oddíl se zdá být efektivnější než druhý – v prvním oddíle dostane každý účastník kus, který je pro něj cennější (blíže k jeho/její vrcholu simplexu), zatímco u hry je tomu naopak. druhý oddíl. Ve skutečnosti je první oddíl Pareto efektivní , zatímco druhý není efektivní. Například ve druhém rozdělení může Alice dát třešně Georgeovi výměnou za 2/9 kousku čokolády. To může zlepšit užitek Alice o 2 a George o 4. Tento příklad ilustruje obecný fakt, který si ukážeme níže.

Pro jakýkoli bod : $w=(w_{1},\tečky ,w_{n})\in \Delta$

Říkáme, že oddíl patří , pokud: ${\displaystyle \Delta =\Delta _{1}\cup \cdots \cup \Delta _{n))$ $w$

Pro všechny a pro všechny :

i,j

{\displaystyle (v_{1},\tečky ,v_{n})\in \Delta _{i))

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

Říkáme, že oddíl patří , pokud je vygenerován oddílem , který patří do . to je: ${\displaystyle C=X_{1}\cup \cdots \cup X_{n))$ $w$ $\Delta$ $w$

Pro kohokoli a pro všechny :

i,j

{\displaystyle x\in X_{i))

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

Dá se dokázat, že [3] :

Přepážka patří ke kladnému bodu ,

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

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

právě tehdy, pokud maximalizuje součet:

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

tedy tehdy a jen tehdy, pokud se jedná o maximální užitný vážený oddíl s váhovým vektorem .

w

Protože každé Paretovo efektivní dělení má maximální užitečnost pro některé zvolené váhy [4] , platí i následující věta [5] :

Kladný oddíl patří k nějakému pozitivnímu bodu tehdy a jen tehdy, když je Pareto efektivní .

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

{\displaystyle \Delta ^{+))

Existuje tedy mapování mezi sadou Paretových efektivních oddílů a body v . $\Delta$

Vraťme se k výše uvedenému příkladu

První oddíl (dát citronové a čokoládové části Alice a zbytek George) patří k bodu (0,4; 0,6) stejně jako další body, jako je (0,3; 0,7) (některé oddíly patří více než jednomu bodu ). Krájení je navíc užitečné krájení dortu , které maximalizuje součet a je také Pareto efektivní. ${\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{George}}}{0.6}}$
Zároveň druhý oddíl nepatří do žádného bodu a není Pareto efektivní.
Existuje několik bodů, ke kterým patří několik různých oddílů. Například bod (0,5;0,5). Toto je bod RNS a je s nimi spojena kladná hmota koláče, takže jakékoli rozdělení této hmoty vede k rozdělení, které patří k (0,5;0,5). Například, když dáme část citronu a čokolády Alici (hodnota 27) a zbytek dáme Georgovi (hodnota 12), dostaneme oddíl, který patří (0,5;0,5). Dáme-li Alice celou část citronu (hodnota 9) a zbytek Georgovi (hodnota 30), dostaneme rozdělení, které také patří k tomuto bodu. Dáte-li celou část citronu a polovinu čokoládové části Alici (hodnota 18) a zbytek Georgovi (hodnota 21), dojde k rozdělení, které také patří jemu, a tak dále. Všechny tyto oddíly maximalizují součet . Navíc je tento součet roven 78 ve všech těchto oddílech. Všichni jsou Pareto efektivní. ${\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{0.5}}$

Historie

Množiny RNS byly zavedeny jako součást Dubins-Spanierových teorémů a byly použity k prokázání Wellerovy věty a pozdějších výsledků Ethana Akina [6] . Termín „radon-nikodimská sada“ zavedl Julius Barbanel [7] .

Viz také

Mnoho jednotlivých dílů

Poznámky

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

Literatura

Julius B. Barbanel. Geometrie efektivního spravedlivého dělení. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . Shrnutí najdete v článku
- Barbanel J. Geometric Approach to Fair Division // The College Mathematics Journal. - 2010. - T. 41 , č. 4 . - S. 268 . doi : 10.4169 / 074683410x510263 .
Julius B. Barbanel, William S. Zwicker. Dvě aplikace věty Dvoretského, Walda a Wolfovitze na dělení koláče // Teorie a rozhodnutí. - 1997. - T. 43 , no. 2 . - doi : 10.1023/a:1004966624893 .
Ethan Akin. Vilfredo Pareto krájí dort // Journal of Mathematical Economics. - 1995. - T. 24 . - doi : 10.1016/0304-4068(94)00674-y .