Set de Radon - Nicodim

În teoria tăierii echitabile a prăjiturii , setul Radon –Nikodym ( RNS) este un obiect geometric care reprezintă o prăjitură bazată pe evaluările diferitelor persoane ale diferitelor părți ale acelei prăjituri.

Exemplu

Să presupunem că avem un tort cu patru părți. Sunt două persoane, Alice și George, cu gusturi diferite, fiecare persoană prețuind diferite părți ale tortului în mod diferit. Tabelul de mai jos descrie piesele și evaluările acestora. Ultima linie, „RNS Point”, este explicată mai târziu.

	Ciocolată	Lămâie	Vanilie	Cireșe
Scorul lui Alice	optsprezece	9	unu	2
Scorul lui George	optsprezece	0	patru	opt

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

„Punctul RNS” al unei bucăți de tort descrie valorile relative ale membrilor acelor piese. Are două coordonate - una pentru Alice și una pentru George. De exemplu:

Participanții sunt de acord asupra valorilor părții de ciocolată, astfel încât coordonatele punctului RNS sunt de asemenea egale (sunt normalizate astfel încât suma lor să fie 1).
Partea de lămâie contează doar pentru Alice, deci punctul RNS are o coordonată de 1 pentru Alice, în timp ce pentru George, coordonata este 0.
Pentru partea de vanilie și partea de cireșe, raportul dintre valorile Alice și George este de 1:4. Prin urmare, aceeași relație este valabilă pentru coordonatele punctelor lor RNS. Rețineți că atât partea de vanilie, cât și partea de cireș se mapează la același punct RNS.

RNS-ul unui tort este setul tuturor punctelor RNS ale acestuia. În tortul descris mai sus, acest set este format din trei puncte: {(0,5;0,5), (1;0), (0,2;0,8)}. Poate fi reprezentat printr-un 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)
Lămâie	-	-	-	-	Ciocolată	-	-	Vanilie, Cireșe	-	-

Ca rezultat, tortul este așezat și reconstruit pe segmentul (1;0)-(0;1).

Definiții

Există un set („tort”) și un set , care este o sigma-algebră de submulțimi ale mulțimii . $C$ $\mathbb {C}$ $C$

Sunt participanți. Orice participant are o valoare de măsurare personală . Această măsură determină care este scorul fiecărui subset pentru acel membru. $n$ $i$ $V_{i}:\mathbb {C} \to \mathbb {R}$ $C$

Să definim următoarea măsură:

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

Rețineți că fiecare este o măsură absolut continuă în ceea ce privește . Prin urmare, după teorema Radon-Nikodim, are o derivată Radon-Nikodim, care este o funcție astfel încât pentru orice submulțime măsurabilă : $V_i$ $V$ $v_{i}:C\to [0,\infty )$ $X\in \mathbb {C}$

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

Caracteristicile sunt numite funcții de densitate de evaluare . Au următoarele proprietăți pentru aproape toate punctele tortului [1] : $v_{i}$ $x\in C$

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

Pentru orice punct RNS, punctul punct este definit ca: $x\in C$ $X$

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

Rețineți că este întotdeauna un punct în unitatea -dimensională simplex în , notat (sau pur și simplu , dacă este implicat în context). $v(x)$ $(n-1)$ $\mathbb {R} ^{n}$ $\Delta ^{n-1}$ $\Delta$ $n$

RNS-ul unui tort este setul tuturor punctelor RNS ale acestuia:

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

Tortul este spart si apoi reasamblat in interior . Fiecare vârf este asociat cu unul dintre n membri. Fiecare parte a tortului este mapată la un punct în funcție de scoruri - cu cât piesa este mai valoroasă pentru participant, cu atât este mai aproape de vârful participantului. Acest lucru este arătat în exemplul participant de mai sus (unde doar segmentul de linie între (1,0) și (0,1)). Akin [2] descrie semnificația RNS pentru participanți: $\Delta$ $\Delta$ $\Delta$ $n=2$ $\Delta$ $n=3$

Să ne imaginăm un tabel sub forma unui triunghi echilateral cu consumatori la vârfuri ... dorința consumatorului în fragmentul de turtă în punct este dată de coordonatele baricentrice , reflectând apropierea de vârf . Apoi este egal cu 1 în partea de sus și scade liniar la 0 spre partea opusă.

i

v\in \Delta

v_{i}

i

v_{i}

Partiționare RNS eficientă

Un singur simplex poate fi partajat între participanți prin trecerea unui subset fiecărui participant . Fiecare divizie generează o împărțire de tort în care participantul primește o bucată de tort ale cărei puncte RNS se încadrează în . $\Delta$ $i$ $\Delta _{i}$ $C$ $i$ $C$ $\Delta _{i}$

Iată două exemple de partiții pentru doi participanți , unde este segmentul (1;0) - (0;1) $\Delta$

Tăiem în punctul (0,4; 0,6). Dăm segmentul (1; 0) - (0,4; 0,6) lui Alice, iar segmentul (0,4; 0,6) - (0; 1) lui George. Aceasta corespunde oferirii părților de lămâie și ciocolată lui Alice (valoare totală 27) și acordării restului lui George (valoare totală 12). $\Delta$
Tăiem același punct (0,4;0,6), dar dăm segmentul (1;0)-(0,4;0,6) lui George (valoare completă 18) și segmentul (0,4;0,6)- (0;1) Alice (plin). valoarea 3).

Prima partiție pare a fi mai eficientă decât a doua - în prima partiție, fiecărui participant i se dă o piesă care este mai valoroasă pentru el/ea (mai aproape de partea superioară a simplexului), în timp ce opusul este valabil pentru a doua partiție. De fapt, prima partiție este Pareto eficientă , în timp ce a doua nu este eficientă. De exemplu, în a doua împărțire, Alice îi poate da cireșe lui George în schimbul a 2/9 din bucata de ciocolată. Acest lucru poate îmbunătăți utilitatea lui Alice cu 2 și a lui George cu 4. Acest exemplu ilustrează un fapt general pe care îl vom arăta mai jos.

Pentru orice punct : $w=(w_{1},\dots,w_{n})\in \Delta$

Spunem că o partiție îi aparține dacă: $\Delta =\Delta _{1}\cup \cdots \cup \Delta _{n)$ $w$

Pentru toată lumea și pentru toată lumea :

i,j

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

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

Spunem că o partiție îi aparține dacă este generată de o partiție care îi aparține . Acesta este: $C=X_{1}\cup \cdots \cup X_{n)$ $w$ $\Delta$ $w$

Pentru oricine și pentru toată lumea :

i,j

x\in X_{i)

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

Se poate dovedi că [3] :

Partiția aparține punctului pozitiv ,

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

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

dacă și numai dacă maximizează suma:

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

adică dacă și numai dacă este o partiție ponderată cu utilitate maximă cu un vector de greutate .

w

Deoarece orice diviziune Pareto eficientă este maximă ca utilitate pentru unele greutăți alese [4] , următoarea teoremă este, de asemenea, adevărată [5] :

O partiție pozitivă aparține unui punct pozitiv dacă și numai dacă este Pareto eficientă .

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

\Delta ^{+)

Astfel, există o mapare între setul de partiții eficiente Pareto și punctele din . $\Delta$

Revenind la exemplul de mai sus

Prima partiție (dând părțile de lămâie și ciocolată lui Alice și restul lui George) aparține punctului (0,4;0,6) precum și altor puncte precum (0,3;0,7) (unele partiții aparțin mai mult de un punct). Mai mult, tăierea este tăierea utilă a prăjiturii care maximizează suma și este, de asemenea, eficientă Pareto. ${\frac {V_{\text{Alice}}}{0,4}}+{\frac {V_{\text{George}}}{0,6}}$
În același timp, a doua partiție nu aparține niciunui punct și nu este eficientă Pareto.
Există mai multe puncte cărora le aparțin mai multe partiții diferite. De exemplu, punctul (0,5;0,5). Acesta este un punct al RNS și există o masă de turtă pozitivă asociată cu acestea, astfel încât orice partiție a acestei mase are ca rezultat o partiție care aparține (0,5; 0,5). De exemplu, dând părțile de lămâie și ciocolată lui Alice (valoare 27) și dând restul lui George (valoare 12), obținem o partiție care aparține lui (0,5; 0,5). Dându-i lui Alice întreaga parte de lămâie (valoarea 9) și restul lui George (valoarea 30), obținem o distribuție care aparține și el acestui punct. Dând toată partea de lămâie și jumătate din partea de ciocolată lui Alice (valoarea 18) și restul lui George (valoarea 21) are ca rezultat o distribuție care îi aparține și lui și așa mai departe. Toate aceste partiții maximizează suma . În plus, această sumă este egală cu 78 în toate aceste partiții. Toate sunt eficiente Pareto. ${\frac {V_{\text{Alice}}}{0,5}}+{\frac {V_{\text{George}}}{0,5}}$

Istorie

Seturile RNS au fost introduse ca parte a teoremelor Dubins-Spanier și au fost folosite pentru a demonstra teorema lui Weller și rezultatele ulterioare de către Ethan Akin [6] . Termenul „mult Radon-Nikodim” a fost introdus de Julius Barbanel [7] .

Vezi și

Multe părți individuale

Note

↑ Barbanel, 2005 , p. 222.
↑ Akin, 1995 , p. 23.
↑ Barbanel, 2005 , p. 241-244.
↑ Barbanel și Zwicker 1997 , p. 203.
↑ Barbanel, 2005 , p. 246.
↑ Akin, 1995 , p. 23Ethan.
↑ Barbanel, 2005 .

Literatură

Julius B. Barbanel. Geometria împărțirii eficiente a târgului. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . Un rezumat poate fi găsit în articol
- 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. Două aplicații ale unei teoreme a lui Dvoretsky, Wald și Wolfovitz la divizarea tortului // Teorie și decizie. - 1997. - T. 43 , nr. 2 . - doi : 10.1023/a:1004966624893 .
Ethan Akin. Vilfredo Pareto taie tortul // Journal of Mathematical Economics. - 1995. - T. 24 . - doi : 10.1016/0304-4068(94)00674-y .