Teoreme Dubins-Spenier

Teoremele Dubins-Spanier sunt câteva teoreme din teoria tăierii corecte a tortului . Au fost publicate de Lester Dubins și Edwin Spanier în 1961 [1] . Deși scopul inițial al acestor teoreme a fost problema împărțirii corecte , de fapt ele sunt teoreme generale ale teoriei măsurii .

Condiții

Există o mulțime și o mulțime , care este o sigma-algebră de submulțimi ale mulțimii . $U$ $\mathbb {U}$ $U$

Sunt participanți. Fiecare participant are o măsură de preferință personală . Această caracteristică determină cât de valoros este fiecare subset pentru participant. $n$ $i$ $V_{i}:\mathbb {U} \la \mathbb {R}$ $U$

Fie o partiție în seturi măsurabile : . Să definim o matrice ca o matrice : $X$ $U$ $k$ $U=X_{1}\sqcup \cdots \sqcup X_{k)$ $M_{X}$ $n\times k$

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

Această matrice conține scorurile tuturor jucătorilor pentru toate piesele partiției.

Fie mulțimea tuturor acestor matrici (pentru aceleași măsuri de preferință, aceeași valoare și partiții diferite): ${\mathbb {M}}$ $k$

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

este o partiție k

U\}

Teoremele Dubins-Spanier se ocupă de proprietățile topologice ale unei mulțimi . ${\mathbb {M}}$

Declarații

Dacă toate măsurile de preferință sunt numărătoare aditive și non- atomice , atunci: $V_i$

${\mathbb {M}}$ compact ;
${\mathbb {M}}$ convex .

Acest lucru a fost deja dovedit de Dvoretsky, Wald și Vol'fovich [2] .

Consecințele

Diviziune consistentă

Tăierea prăjiturii în k părți se numește tăiere consistentă cu greutăți (se vorbește și despre împărțirea exactă ) dacă: $X$ $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}

Adică: există un acord al tuturor participanților că valoarea piesei j este egală cu exact . $w_{j)$

Să presupunem acum că sunt greutăți, a căror sumă este egală cu 1: $w_{1},w_{2},\ldots,w_{k)$

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

iar valorile măsurătorii sunt normalizate astfel încât fiecare participant să evalueze valoarea întregului tort la exact 1:

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

Din convexitatea din teorema Dubins-Spanier rezultă că [3] :

Dacă toate valorile măsurătorii sunt numărătoare aditive și non-atomice, atunci există o partiție consistentă.

Dovada: Pentru orice definim o partiție după cum urmează $j\in \{1,\dots ,k\}$ $X^{j}$

X_{j}^{j}=U

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

În partiția , toate scorurile participanților din a i-a bucată sunt egale cu 1, iar scorurile tuturor celorlalte bucăți sunt egale cu 0. Prin urmare, matricea conține doar unități în a i-a coloană și zerouri în toate celelalte. locuri. $X^{j}$ $j$ $M_{X^{j)}$ $j$

În funcție de convexitate, există o partiție astfel încât $X$

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

În această matrice , coloana a treia conține doar valoarea . Aceasta înseamnă că în partiție toate estimările participanților din piesa -a sunt exact egale cu . $j$ $w_{j)$ $X$ $j$ $w_{j)$

Notă : Acest corolar confirmă afirmația anterioară a lui Hugo Steinhaus . De asemenea, oferă un răspuns pozitiv la problema Nilului (râului), care afirmă că există doar un număr finit de înălțimi de inundații.

Diviziune superproporțională

Tăierea prăjiturii în n bucăți (una pentru fiecare participant la divizie) se numește diviziune superproporțională ponderată dacă $X$ $w_{1},w_{2},...,w_{n)$

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

Adică, o piesă care este strict atribuită unui participant este mai preferabilă pentru acesta decât o piesă la care are dreptul. Următoarea afirmație este teorema Dubins-Spanier privind existența diviziunii superproporționale. $i$

Teorema Fie greutăți a căror sumă este egală cu 1. Să presupunem că punctul este un punct interior al unui simplex (n-1)-dimensional cu coordonate distincte pe perechi și să fie normalizate măsurile de utilitate astfel încât fiecare participant să estimeze întregul tort la exact 1 (adică măsurile sunt măsuri de probabilitate non-atomică). Dacă cel puțin două măsuri nu coincid ( ), atunci există o diviziune superproporțională. $w_{1},w_{2},...,w_{n)$ $w:=(w_{1},w_{2},...,w_{n})$ $V_{1},...,V_{n}$ $V_{i},V_{j}$ $V_{i}\neq V_{j)$

Este necesară condiția ca măsurile de utilitate să nu fie toate identice. În caz contrar, suma duce la o contradicție. $V_{1},...,V_{n}$ $\sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\ suma _{i=1}^{n}w_{i}=1$

Atunci, dacă toate măsurile de utilitate sunt numărătoare aditive și non-atomice și există, de asemenea, doi participanți astfel încât , atunci există o diviziune superproporțională. Adică o condiție necesară este și una suficientă. $i,j$ $V_{i}\neq V_{j)$

Schița dovezii

Presupunem fără pierderea generalității că . Apoi există o bucată de tort astfel încât . Să fie un plus . Apoi . Aceasta înseamnă că . Cu toate acestea . Prin urmare, fie , fie . Să presupunem, fără pierderi de generalitate, că inegalitățile și sunt adevărate. $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}$

Definim următoarea tăietură:

$X^{1}$ : o tăietură care oferă membrului 1, membrului 2 și nimic celorlalți membri. $Z$ ${\overline {Z)}$
$X^{i}$ (pentru ): tăietură care dă tot tortul concurentului și nimic celorlalți. $i\geqslant 2$ $i$

Aici ne interesează doar diagonala matricei , care reprezintă scorurile participanților din propriile bucăți: $M_{X^{j)}$

Într-o matrice , primul element este , al doilea element este , iar elementele rămase sunt 0. ${\textrm {diag}}(M_{X^{1}})$ $V_{1}(Z)$ $V_{2}({\overline {Z)))$
Într-o matrice (pentru ), un element este 1, iar celelalte elemente sunt 0. ${\textrm {diag}}(M_{X^{i}})$ $i\geqslant 2$ $i$

Prin condiția de convexitate, pentru orice set de greutăți există o partiție astfel încât $z_{1},z_{2},...,z_{n}$ $X$

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

Este posibil să alegeți greutățile în așa fel încât pe diagonală , să fie în același raport cu greutățile . Deoarece am presupus că , putem demonstra că , deci este o împărțire superproporțională. $z_{i}$ $M_{X}$ $w_{i}$ $V_{1}(Z)>w_{1}$ $\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ $X$

Diviziune utilitar-optimă

Tăierea prăjiturii în n bucăți (o bucată pentru fiecare participant) este considerată a fi utilitară - optimă dacă maximizează suma scorurilor de utilitate. Adică maximizează $X$

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

Diviziunile utilitar-optimale nu există întotdeauna. De exemplu, să presupunem că este mulțimea numerelor întregi pozitive. Să fie doi participanți, ambii evaluând valoarea întregului set la 1. Participantul 1 atribuie o valoare pozitivă fiecărui număr întreg, iar participantul 2 atribuie 0 oricărei submulțimi finite. Din punct de vedere utilitar, cel mai bine este să dai primului membru o submulțime finită mare și să dai restul celui de-al doilea membru. Pe măsură ce setul dat primului participant devine din ce în ce mai mare, suma valorilor se apropie din ce în ce mai mult de 2, dar nu vom obține niciodată valoarea 2. Astfel, nu există o diviziune utilitarist-optimală. $U$ $U$

Problema din exemplul de mai sus este că măsura utilității pentru elementul 2 este aditivă finit, dar nu aditivă numărabil .

Compactitatea din teorema Dubins-Spanier implică imediat că [4] :

Dacă toate măsurile de preferință sunt numărătoare aditive și non-atomice, atunci există o diviziune utilitar-optimală.

În acest caz special, non-atomicitatea nu este necesară - dacă toate măsurile de preferință sunt aditive numărătoare, atunci există o diviziune utilitar-optimală [4] .

Leximin-diviziune optimă

Tăierea tortului în n bucăți (o bucată pentru fiecare participant) se spune că este optimă pentru leximină cu greutăți dacă maximizează un vector ordonat lexicografic de valori relative. Adică maximizează următorul vector: $X$ $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}}

unde membrii sunt indexați astfel încât:

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

Tăierea optimă pentru leximină maximizează valoarea celui mai sărac membru (în funcție de greutatea lor), apoi a celui de-al doilea cel mai sărac membru și așa mai departe.

Compactitatea din teorema Dubins-Spanier implică imediat că [5] :

Dacă toate măsurile de preferință sunt numărătoare aditive și non-atomice, atunci există o diviziune leximină optimă.

Cercetări suplimentare

Criteriul de leximină-optimalitate, introdus de Dubins și Spanier, a fost ulterior studiat intens. În special, pentru problema tăierii corecte a tortului, criteriul a fost studiat de Marco Del Aglio [6] .

Vezi și

Teorema de măsurare vectorială a lui Lyapunov [7]
teorema lui Weller

Note

↑ Dubins și Spanier, 1961 , p. unu.
↑ Dvoretzky, Wald, Wolfowitz, 1951 , p. 59.
↑ Dubins și Spanier, 1961 , p. 5.
↑ 1 2 Dubins, Spanier, 1961 , p. 7.
↑ Dubins și Spanier, 1961 , p. opt.
↑ Dall'Aglio, 2001 , p. 17.
↑ Neyman, 1946 , p. 843–845.

Literatură

Lester Eli Dubins, Edwin Henry Spanier. Cum să tăiați o prăjitură în mod corect // The American Mathematical Monthly. - 1961. - T. 68 . - doi : 10.2307/2311357 . — .
Dvoretzky A., Wald A., Wolfowitz J. Relații între anumite game de măsuri vectoriale // Pacific Journal of Mathematics. - 1951. - T. 1 . - doi : 10.2140/pjm.1951.1.59 .
Marco Dall Aglio. Problema de optimizare Dubins-Spanier în teoria diviziunii corecte // 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 .