Dubins-Speniers sætninger

Dubins-Spanier- sætningerne er flere sætninger i teorien om retfærdig kageskæring . De blev udgivet af Lester Dubins og Edwin Spanier i 1961 [1] . Selvom det oprindelige formål med disse teoremer var problemet med retfærdig opdeling , er de faktisk generelle teoremer om måleteori .

Betingelser

Der er et sæt og et sæt , som er en sigma-algebra af delmængder af sættet . $U$ $\mathbb {U}$ $U$

Der er deltagere. Hver deltager har en personlig præferencemål . Denne funktion bestemmer, hvor værdifuld hver delmængde er for deltageren. $n$ $jeg$ $V_{i}:\mathbb {U} \to \mathbb {R}$ $U$

Lad være en opdeling i målbare sæt :. Lad os definere en matrix som en matrix : $x$ $U$ $k$ ${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k))$ $M_{X}$ $n\ gange k$

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

Denne matrix indeholder pointene for alle spillere for alle brikker i partitionen.

Lad være sættet af alle sådanne matricer (for de samme præferencemål, den samme værdi og forskellige partitioner): ${\mathbb {M}}$ $k$

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

er en k -partition

U\}

Dubins-Spanier-sætningerne omhandler et sæts topologiske egenskaber . ${\mathbb {M}}$

Udsagn

Hvis alle præferencemål er tælleligt additive og ikke -atomare , så: $V_i$

${\mathbb {M}}$ kompakt ;
${\mathbb {M}}$ konveks .

Dette er allerede blevet bevist af Dvoretsky, Wald og Vol'fovich [2] .

Konsekvenser

Konsekvent opdeling

At skære kagen i k dele kaldes konsekvent skæring med vægte (de taler også om nøjagtig opdeling ), hvis: $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}

Det vil sige: der er enighed mellem alle deltagere om, at værdien af brikken j er lig med nøjagtig . ${\displaystyle w_{j))$

Antag nu, at det er vægte, hvis sum er lig med 1: ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

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

og måleværdierne normaliseres, så hver deltager vurderer værdien af hele kagen til præcis 1:

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

Fra konveksiteten i Dubins-Spanier-sætningen følger det, at [3] :

Hvis alle måleværdier er tælleligt additive og ikke-atomare, så eksisterer der en konsistent partition.

Bevis: For enhver definerer vi en partition som følger ${\displaystyle j\in \{1,\dots ,k\))$ ${\displaystyle X^{j))$

X_{j}^{j}=U

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

I partitionen er alle scores for deltagerne i den i-te del lig med 1, og scorerne for alle andre dele er lig med 0. Derfor indeholder matricen kun enere i den i-te kolonne og nuller i alle andre. steder. ${\displaystyle X^{j))$ $j$ $M_{X^{j))$ $j$

Ifølge konveksiteten er der en skillevæg sådan, at $x$

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

I denne matrix indeholder den th kolonne kun værdien . Det betyder, at i partitionen er alle estimaterne for deltagerne i det -te stykke nøjagtigt lig med . $j$ ${\displaystyle w_{j))$ $x$ $j$ ${\displaystyle w_{j))$

Bemærk : Denne konsekvens bekræfter den tidligere påstand fra Hugo Steinhaus . Det giver også et positivt svar på Nilen (flod) problemet, som siger, at der kun er et begrænset antal oversvømmelser.

Superproportional inddeling

At skære kagen i n stykker (en for hver deltager i delingen) kaldes en vægtet superproportional division, hvis $x$ ${\displaystyle w_{1},w_{2},...,w_{n))$

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

Det vil sige, at et stykke, der er strengt tildelt en deltager, er mere at foretrække for ham end et stykke, som han er berettiget til. Følgende udsagn er Dubins-Spaniers sætning om eksistensen af superproportional division. $jeg$

Sætning Lad være vægte, hvis sum er lig med 1. Antag, at punktet er et indre punkt i en (n-1)-dimensional simplex med parvis distinkte koordinater, og lad nyttemålene normaliseres, så hver deltager estimerer hele kagen til nøjagtigt 1 (det vil sige, at målene er ikke-atomare sandsynlighedsmål). Hvis mindst to mål ikke er sammenfaldende ( ), så eksisterer der superproportional division. ${\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))$

Betingelsen om, at nytteforanstaltninger ikke alle er identiske, er nødvendig. Ellers fører summen til en modsigelse. $V_{1},...,V_{n}$ $\sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\ sum _{i=1}^{n}w_{i}=1$

Så, hvis alle nyttemål er tælleligt additive og ikke-atomare, og der også er to deltagere , sådan at , så eksisterer der superproportional division. Det vil sige, at en nødvendig betingelse også er tilstrækkelig. $i,j$ ${\displaystyle V_{i}\neq V_{j))$

Skitse af beviset

Antag uden tab af almenhed, at . Så er der et eller andet stykke kage sådan, at . Lad det være en tilføjelse . Så . Det betyder, at . Dog . Derfor enten , eller . Antag uden tab af almenhed, at ulighederne og er sande. $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}$

Vi definerer følgende snit:

$X^{1}$ : et snit, der giver medlem 1, medlem 2 og intet væk til de andre medlemmer. $Z$ ${\overline {Z))$
${\displaystyle X^{i))$ (til ): udskæring, der giver hele kagen til deltageren og intet til de andre. $i\geqslant 2$ $jeg$

Her er vi kun interesseret i diagonalen af matricen , som repræsenterer deltagernes score fra deres egne bidder: $M_{X^{j))$

I en matrix er det første element , det andet element er , og de resterende elementer er 0. ${\textrm {diag}}(M_{X^{1}})$ $V_{1}(Z)$ $V_{2}({\overline {Z)))$
I en matrix (for ) er et element 1 og de andre elementer er 0. ${\textrm {diag}}(M_{X^{i}})$ $i\geqslant 2$ $jeg$

Ved konveksitetsbetingelsen eksisterer der for ethvert sæt vægte en skillevæg , således at $z_{1},z_{2},...,z_{n}$ $x$

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

Det er muligt at vælge vægtene på en sådan måde, at de på diagonalen er i samme forhold som vægtene . Da vi antog det , kan vi bevise det , så det er en superproportional opdeling. $z_{i}$ $M_{X}$ $w_{i}$ $V_{1}(Z)>w_{1}$ $\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ $x$

Utilitarisk-optimal opdeling

At skære kagen i n stykker (et stykke til hver deltager) siges at være utilitaristisk – optimalt , hvis det maksimerer summen af nyttescorerne. Det vil sige, det maksimerer $x$

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

Utilitær-optimale opdelinger eksisterer ikke altid. Lad os f.eks. sige, at det er sættet af positive heltal. Lad der være to deltagere, som begge vurderer værdien af hele sættet til 1. Deltager 1 tildeler en positiv værdi til hvert heltal, og deltager 2 tildeler 0 til enhver endelig delmængde. Fra et utilitaristisk synspunkt er det bedst at give det første medlem en stor begrænset delmængde og give resten til det andet medlem. Efterhånden som sættet givet til den første deltager bliver større og større, kommer summen af værdierne tættere og tættere på 2, men vi får aldrig værdien 2. Der er således ingen utilitaristisk-optimal opdeling. $U$ $U$

Problemet i ovenstående eksempel er, at nyttemålet for element 2 er endeligt additivt, men ikke tælleligt additivt .

Kompaktheden i Dubins-Spanier-sætningen antyder umiddelbart, at [4] :

Hvis alle præferenceforanstaltninger er tælleligt additive og ikke-atomare, så eksisterer en utilitaristisk-optimal opdeling.

I dette specielle tilfælde er ikke-atomicitet ikke påkrævet - hvis alle præferencemål er tælleligt additive, så eksisterer en utilitaristisk-optimal opdeling [4] .

Leximin-optimal division

At skære kagen i n stykker (et stykke for hver deltager) siges at være leksimin-optimalt med vægte , hvis det maksimerer en leksikografisk ordnet vektor af relative værdier. Det vil sige, det maksimerer følgende vektor: $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}}

hvor medlemmer er indekseret således, at:

{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}}

Leximin-optimal udskæring maksimerer værdien af det fattigste medlem (i henhold til deres vægt), derefter det næstfattigste medlem, og så videre.

Kompaktheden i Dubins-Spanier-sætningen antyder umiddelbart, at [5] :

Hvis alle præferenceforanstaltninger er tælleligt additive og ikke-atomare, så eksisterer en leksimin-optimal opdeling.

Yderligere forskning

Kriteriet om leximin-optimalitet, introduceret af Dubins og Spanier, blev efterfølgende undersøgt intensivt. Især for problemet med retfærdig kageskæring blev kriteriet undersøgt af Marco Del Aglio [6] .

Se også

Lyapunovs vektormålsætning [7]
Wellers sætning

Noter

↑ Dubins og Spanier, 1961 , s. en.
↑ Dvoretzky, Wald, Wolfowitz, 1951 , s. 59.
↑ Dubins og Spanier, 1961 , s. 5.
↑ 1 2 Dubins, Spanien, 1961 , s. 7.
↑ Dubins og Spanier, 1961 , s. otte.
↑ Dall'Aglio, 2001 , s. 17.
↑ Neyman, 1946 , s. 843-845.

Litteratur

Lester Eli Dubins, Edwin Henry Spanier. Sådan skærer du en kage retfærdigt // The American Mathematical Monthly. - 1961. - T. 68 . - doi : 10.2307/2311357 . — .
Dvoretzky A., Wald A., Wolfowitz J. Relationer mellem visse rækker af vektormål // Pacific Journal of Mathematics. - 1951. - T. 1 . - doi : 10.2140/pjm.1951.1.59 .
Marco Dall Aglio. Dubins-Spanier-optimeringsproblemet i fair divisionsteori // 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 .