Podział silnie proporcjonalny

Podział silnie proporcjonalny (czasami nazywany podziałem superproporcjonalnym ) jest rodzajem podziału sprawiedliwego . Jest to podział zasobów między n partnerów, w którym wartość otrzymana przez każdego z partnerów jest ściśle większa niż jego/jej należny udział w wysokości 1/ n całkowitej wartości. Formalnie, w silnie proporcjonalnym podziale zasobu C między n partnerów, każdy partner i , z miarą wartości V _i , otrzymuje udział X _i taki, że

${\ Displaystyle V_ {i} (X_ {i})> V_ {i} (C) / n}$ .

Oczywiście podział silnie proporcjonalny nie istnieje, gdy wszyscy partnerzy mają tę samą miarę wartości. Najlepszym warunkiem, który zawsze można zagwarantować, jest ${\ Displaystyle V_ {i} (X_ {i}) \ geq V_ {i} (C) / n} ,$ który jest warunkiem zwykłego podziału proporcjonalnego . Można mieć jednak nadzieję, że przy różnych wycenach różnych agentów uda się wykorzystać ten fakt z korzyścią dla wszystkich graczy i dać każdemu z nich zdecydowanie więcej niż mu się należy.

Istnienie

W 1948 roku Hugo Steinhaus przypuszczał istnienie superproporcjonalnego podziału ciasta :

Przy okazji można stwierdzić, że jeśli jest dwóch (lub więcej) partnerów o różnych ocenach, to istnieje podział dający każdemu więcej niż mu się należy ( Knaster ); fakt ten obala powszechną opinię, że oszacowania różnic utrudniają sprawiedliwy podział.

W 1961 roku Dubins i Spanier udowodnili, że warunek konieczny istnienia jest również wystarczający. Oznacza to, że zawsze, gdy wyceny partnerów są addytywne i nieatomowe i jest co najmniej dwóch partnerów, których funkcja wartości jest choć trochę inna, wówczas istnieje podział superproporcjonalny, w którym wszyscy partnerzy otrzymują więcej niż 1/ n .

Dowód był następstwem twierdzenia Dubinsa-Spaniera o wypukłości . Był to dowód czysto egzystencjalny oparty na argumentach wypukłości.

Algorytmy

W 1986 roku Douglas R. Woodall opublikował pierwszy protokół znajdowania podziału superproporcjonalnego.

Niech C będzie całym tortem. Jeśli wyceny agentów są różne, musi być świadek : świadek to konkretny bułka z masłem, powiedzmy X ⊆ C , który jest wyceniany inaczej przez dwóch partnerów, powiedzmy Alicję i Boba. Niech Y := C \ X. Niech a _x = V _Alicja X) ₍ ay = V _Alicja (Y) i b _x = V _Bob (X) i i b _y = V _Bob (Y) i załóżmy, że:

b _x > a _x , co implikuje: przez _y < a _y .

Chodzi o to, aby podzielić X i Y oddzielnie: dzieląc X , damy nieco więcej Bobowi i nieco mniej Alicji; dzieląc Y , damy nieco więcej Alicji i nieco mniej Bobowi.

Protokół Woodalla dla dwóch agentów

Znajdź liczbę wymierną między b _x i a _x , powiedzmy p/q taką, że b _x > p/q > a _x . To implikuje by _y < (qp)/q < a _y . Poproś Boba, aby podzielił X na p równych części i podzielił Y na qp równych części.

₀₀ Zgodnie z naszymi założeniami, Bob wycenia każdy element X na b _x /p > 1/ q , a każdy element Y na b _y /(qp) < 1/ q . Ale dla Alicji co najmniej jeden element X (powiedzmy X ) musi mieć wartość mniejszą niż 1/ q i co najmniej jeden element Y (powiedzmy Y ) musi mieć wartość większą niż 1/ q .

Więc teraz mamy dwa kawałki, X ₀ i Y ₀ , takie, że:

₀₀ V _Bob (X )> V _Alicja (X )

₀₀ V _Bob (Y )<V _Alicja (Y )

Niech Alicja i Bob podzielą resztę ₀ C \ X \ Y ₀ między siebie w sposób proporcjonalny (np. używając dziel i wybierz ). Dodaj Y ₀ do kawałka Alicji i dodaj X ₀ do kawałka Boba.

Teraz każdy partner uważa, że jego/jej alokacja jest zdecydowanie lepsza niż alokacja drugiego, więc jej wartość jest ściśle większa niż 1/2.

Protokół Woodalla dla n partnerów

Rozszerzenie tego protokołu na n partnerów jest oparte na protokole „Samotny wybór” Finka .

Załóżmy, że mamy już silnie proporcjonalny podział na i -1 partnerów (dla i≥3 ). Teraz do partii wchodzi partner #i i powinniśmy dać mu mały kawałek od każdego z pierwszych partnerów i -1, tak aby nowy podział był nadal mocno proporcjonalny.

Weź pod uwagę np. partnera nr 1. Niech d będzie różnicą między bieżącą wartością partnera nr 1 a (1/( i -1)). Ponieważ obecny podział jest silnie proporcjonalny, wiemy, że d>0 .

Wybierz dodatnią liczbę całkowitą q taką, że: ${\ Displaystyle d> {\ Frac {1} {(i-1) i (q (i- 1)-1)}}}$

$Poproś partnera$ $,$ aby podzielił swój udział na elementy, które uważa za równe wartości, i pozwól nowemu partnerowi wybrać za najcenniejsze

Partner nr 1 pozostaje z wartością ${\ Displaystyle {\ Frac {(qi-1) -q} {qi -1}} = {\ Frac {q (i-1) -1} {qi-1}}}$ jego poprzedniej wartości, która wynosiła ${\ Displaystyle {\ Frac {1} {i- 1}}+d}$ (z definicji d ). $}}}$ ${\ Displaystyle {\ Frac {q (i-1) -1} {(i-1) (qi-1$ ) i d staje się ${\ Displaystyle {\ Frac {1} {i (i-1) (qi-1)}}}$ ; zsumowanie ich daje, że nowa wartość jest większa niż: ${\ Displaystyle {\ Frac {(qi-1) (i-1)} {(i-1) i(qi-1)}}={\frac {1}{i}}}$ całego tortu.

Jeśli chodzi o nowego partnera, po wzięciu q sztuk od każdego z pierwszych i -1 partnerów, jego łączna wartość wynosi co najmniej: ${\ Displaystyle {\ Frac {q} {qi-1} }>{\frac {1}{i}}}$ całego tortu.

Dowodzi to, że nowy podział jest również silnie proporcjonalny.

Protokół Barbanela

Julius Barbanel rozszerzył algorytm Woodalla na agentów z różnymi uprawnieniami , w tym irracjonalnymi uprawnieniami. W tym ustawieniu uprawnienia każdego agenta ${\$ są reprezentowane wagę , przy czym $Displaystyle W: = \ suma _ {i} w_ {i} }$ . Alokacja silnie proporcjonalna to taka, w której dla każdego agenta i :

${\ Displaystyle V_ {i} (X_ {i})> w_ {i} \ cdot V_ {i} (C) / W}$ .

Protokół Janko-Joo

Janko i Joo przedstawili prostszy algorytm dla agentów o różnych uprawnieniach. W rzeczywistości pokazali, jak sprowadzić problem podziału silnie proporcjonalnego (z równymi lub różnymi uprawnieniami) do dwóch problemów podziału proporcjonalnego z różnymi uprawnieniami :

W przypadku kawałka X zmień uprawnienie Alicji na ${\ Displaystyle w_ {A} -1/a_ {x}}$ i uprawnienie Boba na ${\ Displaystyle w_ {B}+1/b_{x}}$ . Ponieważ b _x > a _x_, suma nowych uprawnień jest dokładnie mniejsza niż ${\ Displaystyle w_ {A} + w_ {B}}$ , więc suma wszystkich n uprawnień (oznaczonych przez W _X ) jest ściśle mniejsze niż W.
W przypadku kawałka Y zmień uprawnienia Alicji na $\ Displaystyle w_ {A} + 1/a_ {y}},$ a uprawnienia Boba na ${\ Displaystyle w_ {B}-1/b_{y}}$ . Tutaj również, ponieważ przez _y < a _y_, nowa suma wszystkich uprawnień (z wcięciem W _Y ) jest ściśle mniejsza niż W .
Wartość Alicji to co najmniej ${\ Displaystyle {\ rozpocząć {wyrównane} i (w_ {A} -1 / a_ {x}) \ cdot a_ {x} / W_ {X} + (w_ {A} + 1 / b_ {y}) \ cdot b_{x}/W_{Y}=\\=&(w_{A}a_{x}-1)/W_{X}+(w_{A}a_{y}+1)/W_{Y}\ \>&(w_{A}a_{x}-1)/W+(w_{A}a_{y}+1)/W\\=&w_{A}V_{A}(C)/W\end{ wyrównany}}}$
Podobnie wartość Boba wynosi co najmniej ${\ Displaystyle {\ rozpocząć {wyrównane} i (w_ {B} + 1 / b_ {x}) \ cdot b_ {x} / W_ {X} + (w_ {B} -1 / b_ {y}) \ cdot b_{y}/W_{Y}=\\=&(w_{B}b_{x}+1)/W_{X}+(w_{B}b_{y}-1)/W_{Y}\ \>&(w_{B}b_{x}-1)/W+(w_{B}b_{y}+1)/W\\=&w_{B}V_{B}(C)/W\end{ wyrównany}}}$
Wartość każdego innego agenta i wynosi co najmniej ${\ Displaystyle {\ rozpocząć {wyrównane} & w_ {i} \ cdot V_ {i} (X) / W_ {X} + w_ {i} \ cdot V_ {i} (Y) / W_ {Y} \\ >&w_{i}\cdot V_{i}(X)/W+w_{i}\cdot V_{i}(Y)/W\\=&w_{i}V_{i}(C)/W\end {wyrównany}}}$ Zatem podział jest silnie proporcjonalny.