Radon-sarja - Nikodemus

Reilun kakun leikkaamisen teoriassa Radon- Nikodym - sarja ( RNS) on geometrinen esine, joka edustaa kakkua eri ihmisten arvioiden perusteella kakun eri osista.

Esimerkki

Oletetaan, että meillä on kakku, jossa on neljä osaa. On kaksi ihmistä, Alice ja George, joilla on eri maku, jokainen arvostaa kakun eri osia eri tavalla. Alla oleva taulukko kuvaa osat ja niiden arvot. Viimeinen rivi, "RNS-piste", selitetään myöhemmin.

	Suklaa	Sitruuna	Vanilja	Kirsikat
Alicen pisteet	kahdeksantoista	9	yksi	2
Georgen pisteet	kahdeksantoista	0	neljä	kahdeksan

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

Kakunpalan "RNS-piste" kuvaa näiden palasten jäsenten suhteellisia arvoja. Siinä on kaksi koordinaattia - yksi Alicelle ja toinen Georgelle. Esimerkiksi:

Osallistujat sopivat suklaaosan arvoista, joten myös RNS-pisteen koordinaatit ovat yhtä suuret (ne normalisoidaan niin, että niiden summa on 1).
Sitruunaosalla on merkitystä vain Alicelle, joten RNS-pisteen koordinaatti on Alicelle 1, kun taas Georgelle koordinaatti on 0.
Vaniljaosan ja kirsikkaosan osalta Liisa- ja George-arvojen suhde on 1:4. Siksi sama suhde pätee niiden RNS-pisteiden koordinaatteihin. Huomaa, että sekä vaniljaosa että kirsikkaosa liittyvät samaan RNS-pisteeseen.

Kakun RNS on kaikkien sen RNS-pisteiden joukko. Yllä kuvatussa kakussa tämä sarja koostuu kolmesta pisteestä: {(0.5;0.5), (1;0), (0.2;0.8)}. Se voidaan esittää segmentillä (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)
Sitruuna	-	-	-	-	Suklaa	-	-	Vanilja, kirsikat	-	-

Tämän seurauksena kakku asetetaan ja rekonstruoidaan segmentille (1;0)-(0;1).

Määritelmät

On joukko ("kakku") ja joukko , joka on joukon osajoukkojen sigma-algebra . $C$ $\mathbb {C}$ $C$

Osallistujia on . Jokaisella osallistujalla on henkilökohtainen mitta - arvo . Tämä mitta määrittää kunkin osajoukon pistemäärän kyseiselle jäsenelle. $n$ $i$ $V_{i}:\mathbb {C} \to \mathbb {R}$ $C$

Määritetään seuraava mitta:

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

Huomaa, että jokainen on ehdottoman jatkuva mitta suhteessa . Siksi sillä on Radon-Nikodim-lauseen mukaan Radon-Nikodimin derivaatta, joka on sellainen funktio , että mille tahansa mitattavissa olevalle osajoukolle : $V_i$ $V$ $v_{i}:C\to [0,\infty )$ $X\in \mathbb {C}$

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

Ominaisuuksia kutsutaan arvostustiheysfunktioiksi . Niillä on seuraavat ominaisuudet lähes kaikissa kakun kohdissa [1] : $v_{i}$ $x\in C$

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

Minkä tahansa RNS-pisteen pistepiste määritellään seuraavasti: $x\in C$ $x$

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

Huomaa, että se on aina piste -ulotteisessa yksikössä simplex in , merkitty (tai yksinkertaisesti , jos se viitataan asiayhteyteen). $v(x)$ $(n-1)$ $\mathbb {R} ^{n}$ $\Delta ^{n-1}$ $\Delta$ $n$

Kakun RNS on joukko sen RNS-pisteitä:

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

Kakku murretaan ja kootaan sitten uudelleen sisälle . Jokainen kärkipiste liittyy yhteen n jäsenestä. Jokainen kakun osuus kartoitetaan pisteiden mukaan - mitä arvokkaampi pala on osallistujalle, sitä lähempänä osallistujan kärkeä. Tämä näkyy yllä olevassa osallistujaesimerkissä (jossa vain jana välillä (1,0) ja (0,1)). Akin [2] kuvaa RNS:n merkitystä osallistujille: $\Delta$ $\Delta$ $\Delta$ $n = 2$ $\Delta$ $n = 3$

Kuvitellaan tasasivuisen kolmion muodossa olevaa taulukkoa, jonka kärjessä on kuluttajat ... kakkufragmentin kuluttajan toive pisteessä annetaan barysentrisillä koordinaateilla , jotka heijastavat kärjen läheisyyttä . Sitten on yhtä kuin 1 ylhäällä ja pienenee lineaarisesti arvoon 0 vastakkaiselle puolelle.

i

v\in \Delta

v_{i}

i

v_{i}

Tehokas RNS-osiointi

Yksi simplex voidaan jakaa osallistujien kesken välittämällä osajoukko kullekin osallistujalle . Jokainen divisioona luo kakkujaon , jossa osallistuja saa kakunpalan, jonka RNS-pisteet osuvat . $\Delta$ $i$ $\Delta _{i}$ $C$ $i$ $C$ $\Delta _{i}$

Tässä on kaksi esimerkkiä osioista kahdelle osallistujalle , jossa on segmentti (1;0) - (0;1) $\Delta$

Leikkaamme pisteestä (0,4; 0,6). Annamme segmentin (1; 0) - (0,4; 0,6) Liisalle ja segmentin (0,4; 0,6) - (0; 1) Georgelle. Tämä vastaa sitruuna- ja suklaaosien antamista Alicelle (kokonaisarvo 27) ja lopun antamista Georgelle (kokonaisarvo 12). $\Delta$
Leikkaamme saman pisteen (0,4;0,6), mutta annamme segmentin (1;0)-(0,4;0,6) Georgelle (täysi arvo 18) ja segmentin (0,4;0,6) - (0;1) Alice (täysi) arvo 3).

Ensimmäinen osio näyttää olevan tehokkaampi kuin toinen - ensimmäisessä osiossa jokaiselle osallistujalle annetaan hänelle arvokkaampi pala (lähempänä hänen simplexin yläosaa), kun taas päinvastoin on totta toinen osio. Itse asiassa ensimmäinen osio on Pareto-tehokas , kun taas toinen ei ole tehokas. Esimerkiksi toisessa jaossa Alice voi antaa kirsikoita Georgelle vastineeksi 2/9 suklaapalasta. Tämä voi parantaa Alicen hyödyllisyyttä 2:lla ja Georgen hyödyllisyyttä neljällä. Tämä esimerkki havainnollistaa yleistä tosiasiaa, jonka näytämme alla.

Minkä tahansa kohdan osalta : $w=(w_{1},\dots ,w_{n})\in \Delta$

Sanomme, että osio kuuluu , jos: ${\displaystyle \Delta =\Delta _{1}\cup \cdots \cup \Delta _{n))$ $w$

Kaikille ja kaikille :

i, j

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

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

Sanomme, että osio kuuluu , jos se on luotu osion avulla , joka kuuluu . Tuo on: ${\displaystyle C=X_{1}\cup \cdots \cup X_{n))$ $w$ $\Delta$ $w$

Kaikille ja kaikille :

i, j

{\displaystyle x\in X_{i))

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

Voidaan todistaa, että [3] :

Osio kuuluu positiiviseen pisteeseen ,

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

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

jos ja vain jos se maksimoi summan:

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

eli jos ja vain jos se on maksimihyötypainotettu osio painovektorilla .

w

Koska mikä tahansa Pareton tehokas jako on maksimaalinen hyödyllisyydessään joillekin valituille painoille [4] , myös seuraava lause pitää paikkansa [5] :

Positiivinen osio kuuluu johonkin positiiviseen pisteeseen silloin ja vain, jos se on Pareto-tehokas .

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

{\displaystyle \Delta ^{+))

Siten Pareto-tehokkaiden osioiden joukon ja pisteen välillä on kartoitus . $\Delta$

Palatakseni yllä olevaan esimerkkiin

Ensimmäinen osio (jossa sitruuna- ja suklaaosat annetaan Alicelle ja loput Georgelle) kuuluu pisteeseen (0.4;0.6) sekä muihin pisteisiin, kuten (0.3;0.7) (jotkut osiot kuuluvat useampaan kuin yhteen pisteeseen ). Lisäksi leikkaaminen on kakun hyötyleikkausta , joka maksimoi summan ja on myös Paretotehokas. ${\frac {V_{\text{Alice}}}{0.4}}+{\frac {V_{\text{George}}}{0.6}}$
Samanaikaisesti toinen osio ei kuulu mihinkään pisteeseen eikä ole Pareto-tehokas.
On useita pisteitä, joihin useat erilaiset osiot kuuluvat. Esimerkiksi piste (0,5; 0,5). Tämä on RNS:n piste ja niihin liittyy positiivinen kakkumassa, joten mikä tahansa tämän massan osio johtaa osion, joka kuuluu (0.5;0.5). Esimerkiksi antamalla sitruuna- ja suklaaosat Alicelle (arvo 27) ja loput Georgelle (arvo 12), saamme osion, joka kuuluu (0.5;0.5). Kun Alicelle annetaan koko sitruunaosa (arvo 9) ja loppuosa Georgelle (arvo 30), saadaan jakauma, joka kuuluu myös tähän pisteeseen. Kun koko sitruunaosa ja puolet suklaaosasta annetaan Alicelle (arvo 18) ja loput Georgelle (arvo 21), saadaan jakauma, joka kuuluu myös hänelle, ja niin edelleen. Kaikki nämä osiot maksimoivat summan . Lisäksi tämä summa on 78 kaikissa näissä osioissa. Ne ovat kaikki Pareto-tehokkaita. ${\frac {V_{\text{Alice}}}{0.5}}+{\frac {V_{\text{George}}}{0.5}}$

Historia

RNS-joukot otettiin käyttöön osana Dubins-Spanier-lauseita , ja Ethan Akin käytti niitä todistamaan Wellerin lause ja myöhemmät tulokset [6] . Termin "Radon-Nikodim set" esitteli Julius Barbanel [7] .

Katso myös

Monet yksittäiset osat

Muistiinpanot

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

Kirjallisuus

Julius B. Barbanel. Tehokkaan oikeudenmukaisen jaon geometria. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . Yhteenveto löytyy artikkelista
- Barbanel J. Geometrinen lähestymistapa oikeudenmukaiseen jakoon // College Mathematics Journal. - 2010. - T. 41 , no. 4 . - S. 268 . doi : 10.4169 / 074683410x510263 .
Julius B. Barbanel, William S. Zwicker. Dvoretskyn, Waldin ja Wolfovitzin lauseen kaksi sovellusta kakun jakoon // Teoria ja päätös. - 1997. - T. 43 , no. 2 . - doi : 10.1023/a:1004966624893 .
Ethan Akin. Vilfredo Pareto leikkaa kakun // Journal of Mathematical Economics. - 1995. - T. 24 . - doi : 10.1016/0304-4068(94)00674-y .