Twierdzenia Dubinsa-Spaniera

Dubinsa -Spaniera to kilka twierdzeń z teorii sprawiedliwego krojenia ciasta . Zostały one opublikowane przez Lestera Dubinsa i Edwina Spaniera w 1961 roku. Chociaż pierwotną motywacją dla tych twierdzeń jest sprawiedliwy podział, w rzeczywistości są one ogólnymi twierdzeniami teorii miary .

Ustawienie

Istnieje zbiór $algebrą$ zbiór , który jest sigma podzbiorów $\ displaystyle U$ $}$ .

Są partnerzy ${\ displaystyle n}$ . Każdy partner $ja$ osobistą miarę wartości ${\ Displaystyle V_ {i}: \ mathbb {U} \ do \ mathbb {R}$ . Ta funkcja określa $,$ ile każdy podzbiór wart dla tego partnera.

Niech $mierzalne$ zbiory będą podzielone $\ sqcup \ cdots \$ 1 ⊔ $⋯$ ${$ . Zdefiniuj macierz jako następującą macierz ${\ displaystyle n \ razy k} :$ ${\ displaystyle M_ {X}}$

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

Ta macierz zawiera wyceny wszystkich graczy do wszystkich fragmentów partycji.

Niech będzie zbiorem wszystkich takich macierzy (dla tych samych miar wartości, tego samego $M$ różnych partycji): $\ displaystyle \ mathbb {M}}$

{\ Displaystyle \ mathbb {M} = \ {M_ {X} \ środkowy X {\ tekst {jest a}} k {\ tekst {-podział} }U\}}

Twierdzenia Dubinsa-Spaniera dotyczą topologicznych właściwości ${\ Displaystyle \ mathbb {M}}$ .

Sprawozdania

Jeśli wszystkie miary wartości są policzalnie addytywne i nieatomowe , to: ${\ displaystyle V_ {i}}$

${\ Displaystyle \ mathbb {M}}$ jest zbiorem zwartym ;
${\ Displaystyle \ mathbb {M}}$ jest zbiorem wypukłym .

Udowodnili to już Dvoretzky, Wald i Wolfowitz.

Wnioski

Podział konsensusu

Partycja ciasta $nazywana$ k sztuk jest partycją konsensusu z wagami ${\ Displaystyle w_ {1}, w_ {2}, \ ldots, w_ {k}}$ (zwany także podziałem dokładnym ), jeśli:

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

Oznacza to, że wszyscy partnerzy są zgodni co do tego, że wartość kawałka j jest dokładnie taka sama jak ${\ displaystyle w_ {j}}$ .

Załóżmy od teraz, że są to wagi, których suma wynosi 1: ${\ Displaystyle w_ {1}, w_ {2}, \ ldots, w_ {k}}$

{\ Displaystyle \ suma _ {j = 1} ^ {k} w_ {j} = 1}

a miary wartości są znormalizowane w taki sposób, że każdy partner ocenia cały tort jako dokładnie 1:

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

Część wypukła twierdzenia DS implikuje, że:

Jeśli wszystkie miary wartości są policzalnie addytywne i nieatomowe,

to istnieje podział konsensusu.

$}$ Dla każdego zdefiniuj partycję w następujący sposób: $\ w \ {1, \ kropki, k \}$

{\ Displaystyle X_ {j} ^ {j} = U}

{\ Displaystyle \ forall r \ neq j: X_ {r} ^ {j} = \ pusty zestaw }

W partycji wszyscy partnerzy cenią $element jako$ $1,$ wszystkie pozostałe elementy jako 0. Stąd w macierzy $\ displaystyle M_ { X ^ {j}}} , w$ $i$ są jedynki wszędzie indziej zera.

Dzięki wypukłości istnieje taki podział, że: ${\ displaystyle X}$

{\ Displaystyle M_ {X} = \ suma _ {j = 1} ^ {k} w_ {j} \ cdot M_ {X ^ {j}}}

W tej macierzy, ${$ kolumna zawiera tylko wartość $\ displaystyle w_ {j}}$ . $w$ $,$ że podziale wszyscy partnerzy cenią $jako$ dokładnie

Uwaga: ten wniosek potwierdza poprzednie twierdzenie Hugo Steinhausa . Daje również twierdzącą odpowiedź na problem Nilu, pod warunkiem, że istnieje tylko skończona liczba wysokości powodzi.

Podział superproporcjonalny

Podział ciasta na $)$ podziałem superproporcjonalnym z wagami ${\ Displaystyle w_ {1}, w_ {2}, ..., w_ {n}}$ nazywa się . :

{\ Displaystyle \ forall ja \ w 1 \ kropki n: V_ {i} (X_ {i})> w_ {i}}

To znaczy kawałek przydzielony partnerowi $jest$ niego zdecydowanie bardziej wartościowy niż to, na co zasługuje. Następujące stwierdzenie jest twierdzeniem Dubinsa-Spaniera o istnieniu dzielenia superproporcjonalnego

Twierdzenie — Przy tych zapisach niech $, w_ {2}, ..., w_ {n}} być$ ${\ Displaystyle w: = (w_ {1}, w_ {2}, ..., w_ {n})}$ , których suma wynosi 1, załóżmy, że punkt jest wewnętrznym punktem (n-1) -wymiarowego simpleksu o współrzędnych parami różnych i załóżmy, że wartość mierzy $, że każdy partner$ całe ciasto na dokładnie 1 (tj. są to nieatomowe miary prawdopodobieństwa Jeśli co najmniej dwa z miar $} \ neq V_ {$ są równe ( $j$ } wówczas istnieją podziały superproporcjonalne.

Hipoteza, że wartość mierzy ${\ Displaystyle V_ {1}, ..., V_ {n}}$ nie są identyczne, jest konieczne. W przeciwnym razie suma ${\ Displaystyle \ suma _ {i = 1} ^ { n}V_{i}(X_{i})=\suma _{i=1}^{n}V_{1}(X_{i})>\suma _{i=1}^{n}w_{ i}=1}$ prowadzi do sprzeczności.

${\ displaystyle i$ $j}$ addytywne i nieatomowe, i jeśli istnieje dwóch partnerów , że , to istnieje podział superproporcjonalny. Oznacza to, że warunek konieczny jest również wystarczający.

Szkic dowodu

Załóżmy, że wlog, że ${\ Displaystyle V_ {1} \ neq V_ {2}}$ . Potem jest jakiś kawałek ciasta, taki, że ${\ Displaystyle V_ {1} (Z)$ $($ . Niech będzie dopełnieniem ${\ displaystyle {\ overline {Z}$ $}$ ; następnie ${\ Displaystyle V_ {2} ({\ overline {Z}})> V_ {1} ({\ overline {Z}})}$ . Oznacza to, że ${\ Displaystyle V_ {1} (Z) + V_ {2} ({\ overline {Z}})> 1}$ . Jednak ${\ Displaystyle w_ {1} + w_ {2} \ równoważnik 1}$ . Stąd albo ${\ Displaystyle V_ {1} (Z)> w_ {1}}$ lub ${\ Displaystyle V_ {2} ({\ overline {Z }})>w_{2}}$ . Załóżmy wlog, że ${\ Displaystyle V_ {1} (Z)> V_ {2} (Z)}$ i ${\ Displaystyle V_ {1} ( Z)>w_{1}}$ są prawdziwe.

Zdefiniuj następujące partycje:

$X ^ {1}}$ $displaystyle$ : partycja, która daje $innym$ 1, partnerowi 2 i nic wszystkim
$\ Displaystyle X ^ {i}}$ ${$ (dla $)$ : partycja, która daje całe ciasto partnerowi .

Tutaj interesują nas tylko przekątne macierzy , które reprezentują wyceny partnerów do ich własnych elementów: ${\ displaystyle M_ {X ^ {j}}}$

W ${\ Displaystyle {\ textrm {diag}} (M_ {X ^ {1}})}$ wpis 1 to ${\ Displaystyle V_ {1} (Z)}$ wpis 2 to ${\ Displaystyle V_ {2} ({\ overline {Z}})}$ , a pozostałe wpisy to 0.
W ${\ Displaystyle {\ textrm {diag}} (M_ {X ^ {i}})}$ (dla ${\ Displaystyle i \ geq 2}$ ), wpis ${\ Displaystyle i}$ wynosi 1, a pozostałe całości to 0.

Przez wypukłość, dla każdego zestawu wag $, z_ {2}, ..., z_ {n}}$ ${\ displaystyle X},$ istnieje taka partycja że:

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

Możliwe jest wybranie wag w $z$ $w$ , aby na przekątnej były w takich samych proporcjach jak wagi $w_{i}}$ $displaystyle$ . ${\ displaystyle \ forall i \ in 1 \ kropki n: V_ {i} (X_ {i})> w_ {i}}$ założyliśmy można $_$ , więc ${\ displaystyle X}$ jest podziałem superproporcjonalnym.

Podział utylitarno-optymalny

Podział ciasta na $)$ nazywa się utylitarnym -optymalnym, jeśli maksymalizuje sumę wartości. To znaczy maksymalizuje:

{\ Displaystyle \ suma _ {i = 1} ^ {n} {V_ {i} (X_ {i})}}

Podziały utylitarno-optymalne nie zawsze istnieją. $.$ na przykład, że jest zbiorem dodatnich liczb całkowitych Partnerów jest dwóch. Obaj cenią cały zbiór $1.$ Partner 1 przypisuje wartość dodatnią każdej liczbie całkowitej, a partner 2 przypisuje wartość zero każdemu skończonemu podzbiorowi. Z utylitarnego punktu widzenia najlepiej jest dać partnerowi 1 duży skończony podzbiór, a resztę partnerowi 2. Kiedy zbiór dany partnerowi 1 staje się coraz większy, suma wartości staje się coraz bliższa 2 , ale nigdy nie zbliża się do 2. Nie ma więc podziału utylitarno-optymalnego.

Problem z powyższym przykładem polega na tym, że miara wartości partnera 2 jest skończenie addytywna, ale nie policzalnie addytywna .

Część twierdzenia DS o zwartości natychmiast implikuje, że:

Jeśli wszystkie miary wartości są policzalnie addytywne i nieatomowe,

to istnieje podział utylitarno-optymalny.

W tym szczególnym przypadku nieatomowość nie jest wymagana: jeśli wszystkie miary wartości są policzalnie addytywne, to istnieje podział utylitarno-optymalny.

Podział optymalny dla leksyminy

Podział ciasta na $)$ leksyminem z wagami ${\ displaystyle w_ {1}, w_ {2}, ..., w_ {n}},$ nazywa się optymalnym 2 jeśli maksymalizuje uporządkowany leksykograficznie wektor wartości względnych To znaczy maksymalizuje następujący wektor:

{\ Displaystyle {V_ {1} (X_ {1}) \ nad w_ {1}}, {V_{2}(X_{2}) \ponad w_{2}},\kropki ,{V_{n}(X_{n}) \ponad w_{n}}}

gdzie partnerzy są indeksowani w taki sposób, że:

{\ Displaystyle {V_ {1} (X_ {1}) \ ponad w_ {1}} \ leq {V_{2}(X_{2}) \over w_{2}}\leq \kropki \leq {V_{n}(X_{n}) \over w_{n}}}

Optymalny podział leksyminowy maksymalizuje wartość najbiedniejszego partnera (w stosunku do jego wagi); pod tym względem maksymalizuje wartość drugiego najbiedniejszego partnera (w stosunku do jego wagi); itp.

Część twierdzenia DS o zwartości natychmiast implikuje, że:

Jeśli wszystkie miary wartości są policzalnie addytywne i nieatomowe,

to istnieje optymalny dla leksymin podział.

Dalsze wydarzenia

Kryterium optymalności leksyminy, wprowadzone przez Dubinsa i Spaniera, było później szeroko badane. W szczególności w problemie krojenia ciasta badał go Marco Dall'Aglio.

Zobacz też