Dubins-Spenier-lauseet

Dubins –Spanier-lauseet ovat useita lauseita reilun kakun leikkaamisen teoriassa. Lester Dubins ja Edwin Spanier julkaisivat ne vuonna 1961 [1] . Vaikka näiden lauseiden alkuperäinen tarkoitus oli oikeudenmukaisen jaon ongelma , itse asiassa ne ovat mittateorian yleisiä lauseita .

Ehdot

On joukko ja joukko , joka on joukon osajoukkojen sigma-algebra . $U$ $\mathbb {U}$ $U$

Osallistujia on . Jokaisella osallistujalla on henkilökohtainen mieltymysmitta . Tämä ominaisuus määrittää, kuinka arvokkaita kukin osajoukko on osallistujalle. $n$ $i$ $V_{i}:\mathbb {U} \to \mathbb {R}$ $U$

Olkoon osio mitattavissa oleviksi joukoiksi : . Määritellään matriisi matriisiksi : $X$ $U$ $k$ ${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k))$ $M_{X}$ $n\times k$

M_{X}[i,j]=V_{i}(X_{j})

Tämä matriisi sisältää kaikkien pelaajien pisteet kaikista osion osista.

Olkoon kaikkien tällaisten matriisien joukko (samat etusijamitat, sama arvo ja eri osiot): ${\mathbb {M}}$ $k$

\mathbb {M} =\{M_{X}\mid X

on k -osio

U\}

Dubins-Spanier-lauseet käsittelevät joukon topologisia ominaisuuksia . ${\mathbb {M}}$

Lausunnot

Jos kaikki preferenssimitat ovat laskettavasti additiivisia ja ei -atomisia , niin: $V_i$

${\mathbb {M}}$ kompakti ;
${\mathbb {M}}$ kupera .

Tämän ovat jo todistaneet Dvoretsky, Wald ja Vol'fovich [2] .

Seuraukset

Johdonmukainen jako

Kakun leikkaamista k osaan kutsutaan johdonmukaiseksi leikkaamiseksi painoilla (puhuvat myös tarkasta jaosta ), jos: $X$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

\forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}:V_{i}(X_{j})=w_{j}

Eli: kaikki osallistujat ovat yhtä mieltä siitä, että kappaleen j arvo on täsmälleen yhtä suuri kuin . ${\displaystyle w_{j))$

Oletetaan nyt, että ne ovat painoja, joiden summa on yhtä suuri kuin 1: ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

\sum _{j=1}^{k}w_{j}=1

ja mitta-arvot normalisoidaan siten, että jokainen osallistuja arvioi koko kakun arvon täsmälleen 1:ksi:

\forall i\in \{1,\dots ,n\}:V_{i}(U)=1

Dubins -Spanier-lauseen konveksisuudesta seuraa, että [ 3] :

Jos kaikki mittausarvot ovat laskettavasti additiivisia ja ei-atomisia, silloin on olemassa johdonmukainen osio.

Todistus: Määritämme osion jokaiselle seuraavasti ${\displaystyle j\in \{1,\dots ,k\))$ $X^{j}$

X_{j}^{j}=U

\forall r\neq j:X_{r}^{j}=\emptyset

Osiossa i:nnen palan osallistujien kaikki pisteet ovat yhtä suuria kuin 1 ja kaikkien muiden osien pisteet ovat 0. Siksi matriisi sisältää ykkösiä vain i:nnessä sarakkeessa ja nollia kaikissa muissa paikoissa. $X^{j}$ $j$ $M_{X^{j))$ $j$

Kuperuuden mukaan on olemassa sellainen osio , että $X$

M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j))

Tässä matriisissa sarake sisältää vain arvon . Tämä tarkoittaa, että osiossa kaikki -: nnen palan osallistujien arviot ovat täsmälleen yhtä suuria kuin . $j$ ${\displaystyle w_{j))$ $X$ $j$ ${\displaystyle w_{j))$

Huomautus : Tämä johtopäätös vahvistaa Hugo Steinhausin aiemman väitteen . Se antaa myös myönteisen vastauksen Niilin (joen) ongelmaan, jossa todetaan, että tulvien korkeuksia on vain rajallinen määrä.

Supersuhteellinen jako

Kakun leikkaamista n osaan (yksi jokaiselle jakoon osallistujalle) kutsutaan painotetuksi supersuhteelliseksi jakoksi, jos $X$ ${\displaystyle w_{1},w_{2},...,w_{n))$

\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}

Toisin sanoen osa, joka on tiukasti määrätty osallistujalle, on hänelle parempi kuin teos, johon hänellä on oikeus. Seuraava lausunto on Dubinsin-Spanierin lause supersuhteellisen jaon olemassaolosta. $i$

Lause Olkoon painoja, joiden summa on yhtä suuri kuin 1. Oletetaan, että piste on (n-1)-ulotteisen simpleksin sisäpiste, jolla on pareittain erilliset koordinaatit ja että hyödyllisyysmitat normalisoidaan siten, että jokainen osallistuja arvioi koko kakun täsmälleen 1 (eli suuret ovat ei-atomitodennäköisyysmittauksia). Jos vähintään kaksi mittaa eivät täsmää ( ), on olemassa supersuhteellinen jako. ${\displaystyle w_{1},w_{2},...,w_{n))$ $w:=(w_{1},w_{2},...,w_{n})$ $V_{1},...,V_{n}$ $V_{i},V_{j}$ ${\displaystyle V_{i}\neq V_{j))$

Edellytys, että hyödyllisyystoimet eivät ole kaikki samanlaisia, on välttämätön. Muuten summa johtaa ristiriitaan. $V_{1},...,V_{n}$ $\sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\ summa _{i=1}^{n}w_{i}=1$

Sitten, jos kaikki hyödyllisyysmitat ovat laskettavasti additiivisia ja ei-atomisia, ja osallistujia on myös kaksi siten, että , silloin on olemassa supersuhteellinen jako. Eli välttämätön ehto on myös riittävä. $i, j$ ${\displaystyle V_{i}\neq V_{j))$

Luonnos todisteesta

Oletetaan yleisyyttä menettämättä, että . Sitten on sellainen kakkupala , että . Olkoon se lisäys . Sitten . Tämä tarkoittaa, että . Kuitenkin . Siksi joko , tai . Oletetaan yleisyyttä menettämättä, että epäyhtälöt ja ovat tosia. $V_{1}\neq V_{2}$ $Z\subseteq U$ $V_{1}(Z)>V_{2}(Z)$ ${\overline {Z))$ $Z$ $V_{2}({\overline {Z)))>V_{1}({\overline {Z)))$ $V_{1}(Z)+V_{2}({\overline {Z)))>1$ $w_{1}+w_{2}\leqslant 1$ $V_{1}(Z)>w_{1}$ $V_{2}({\overline {Z)))>w_{2}$ $V_{1}(Z)>V_{2}(Z)$ $V_{1}(Z)>w_{1}$

Määrittelemme seuraavan leikkauksen:

$X^{1}$ : leikkaus, joka antaa pois jäsenen 1, jäsenen 2, eikä mitään muille jäsenille. $Z$ ${\overline {Z))$
$X^{i}$ (for ): leikkaus, joka antaa koko kakun kilpailijalle ja ei mitään muille. $i\geqslant 2$ $i$

Tässä meitä kiinnostaa vain matriisin diagonaali , joka edustaa osallistujien omista osistaan saamia pisteitä: $M_{X^{j))$

Matriisissa ensimmäinen elementti on , toinen elementti ja muut elementit ovat 0. ${\textrm {diag}}(M_{X^{1}})$ $V_{1}(Z)$ $V_{2}({\overline {Z)))$
Matriisissa (for ) elementti on 1 ja muut elementit ovat 0. ${\textrm {diag}}(M_{X^{i}})$ $i\geqslant 2$ $i$

Kuveruusehdon mukaan mille tahansa painojoukolle on olemassa osio , joka $z_{1},z_{2},...,z_{n}$ $X$

M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.

On mahdollista valita painot siten, että diagonaalissa ne ovat samassa suhteessa painojen kanssa . Koska oletimme , että Voimme todistaa, että , Joten se on supersuhteellinen jako. $z_{i}$ $M_{X}$ $w_{i}$ $V_{1}(Z)>w_{1}$ $\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ $X$

Utilitaristisesti optimaalinen jako

Kakun leikkaamisen n osaan (yksi pala jokaiselle osallistujalle) sanotaan olevan hyödyllistä - optimaalista , jos se maksimoi hyötypisteiden summan . Eli maksimoi $X$

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

Utilitaristisesti optimaalisia jakoja ei aina ole olemassa. Oletetaan esimerkiksi, että se on joukko positiivisia kokonaislukuja. Olkoon kaksi osallistujaa, jotka molemmat arvioivat koko joukon arvon 1:ksi. Osallistuja 1 antaa positiivisen arvon jokaiselle kokonaisluvulle ja osallistuja 2 antaa arvon 0 mille tahansa äärelliselle osajoukolle. Utilitaristisesta näkökulmasta on parasta antaa ensimmäiselle jäsenelle suuri äärellinen osajoukko ja antaa loput toiselle jäsenelle. Kun ensimmäiselle osallistujalle annettu joukko kasvaa ja kasvaa, arvojen summa tulee yhä lähemmäksi kahta, mutta emme koskaan saa arvoa 2. Siten ei ole olemassa mitään hyödyllis-optimaalista jakoa. $U$ $U$

Ongelma yllä olevassa esimerkissä on, että hyödyllisyysmitta jäsenelle 2 on äärellisesti additiivinen, mutta ei laskettavasti additiivinen .

Dubins -Spanier-lauseen tiiviys viittaa välittömästi siihen, että [ 4] :

Jos kaikki mieltymysmittaukset ovat luettavassa määrin additiivisia ja ei-atomisia, silloin on olemassa utilitaristinen-optimaalinen jako.

Tässä erikoistapauksessa ei-atomisuutta ei vaadita – jos kaikki preferenssimitat ovat laskettavasti additiivisia, on olemassa utilitaristinen-optimaalinen jako [4] .

Leksimiini-optimaalinen jako

Kakun leikkaamisen n osaan (yksi pala kullekin osallistujalle) sanotaan olevan leksimiinioptimaalista painojen kanssa, jos se maksimoi leksikografisesti järjestetyn suhteellisten arvojen vektorin. Eli se maksimoi seuraavan vektorin: $X$ ${\displaystyle w_{1},w_{2},...,w_{n))$

{V_{1}(X_{1}) \over w_{1)),{V_{2}(X_{2}) \over w_{2)),\dots ,{V_{n}( X_{n}) \over w_{n}}

jossa jäsenet on indeksoitu siten, että:

{V_{1}(X_{1}) \over w_{1}}\leqslant {V_{2}(X_{2}) \over w_{2}}\leqslant \dots \leqslant {V_{ n}(X_{n}) \over w_{n}}

Leksimiinioptimaalinen viipalointi maksimoi köyhimmän jäsenen arvon (painonsa mukaan), sitten toiseksi köyhimmän jäsenen ja niin edelleen.

Dubins -Spanier-lauseen tiiviys viittaa välittömästi siihen, että [ 5] :

Jos kaikki mieltymysmittaukset ovat luettavassa määrin additiivisia ja ei-atomisia, silloin on olemassa leksimiini-optimaalinen jako.

Lisätutkimukset

Dubinsin ja Spanierin esittelemää leksimiinioptimaalisuuden kriteeriä tutkittiin myöhemmin intensiivisesti. Erityisesti reilun kakun leikkaamisen ongelman osalta kriteeriä tutki Marco Del Aglio [6] .

Katso myös

Ljapunovin vektorimittalause [7]
Wellerin lause

Muistiinpanot

↑ Dubins ja Spanier, 1961 , s. yksi.
↑ Dvoretzky, Wald, Wolfowitz, 1951 , s. 59.
↑ Dubins ja Spanier, 1961 , s. 5.
↑ 1 2 Dubins, espanjalainen, 1961 , s. 7.
↑ Dubins ja Spanier, 1961 , s. kahdeksan.
↑ Dall'Aglio, 2001 , s. 17.
↑ Neyman, 1946 , s. 843–845.

Kirjallisuus

Lester Eli Dubins, Edwin Henry Spanier. Kuinka leikata kakku reilusti // The American Mathematical Monthly. - 1961. - T. 68 . - doi : 10.2307/2311357 . — .
Dvoretzky A., Wald A., Wolfowitz J. Suhteet tiettyjen vektorimitta-alueiden välillä // Pacific Journal of Mathematics. - 1951. - T. 1 . - doi : 10.2140/pjm.1951.1.59 .
Marco Dall Aglio. Dubins–Spanier-optimointiongelma reilun jaon teoriassa // Journal of Computational and Applied Mathematics. - 2001. - T. 130 . - doi : 10.1016/S0377-0427(99)00393-3 .
Neyman J. Un théorem dʼexistence // CR Acad. Sci .. - 1946. - T. 222 .