Cena uczciwości

W teorii sprawiedliwego podziału cena sprawiedliwego podziału (POF) jest stosunkiem największego dobrobytu ekonomicznego , jaki może osiągnąć podział, do dobrobytu ekonomicznego osiągniętego przez sprawiedliwy podział. POF jest ilościową miarą utraty dobrobytu, którą społeczeństwo musi podjąć, aby zagwarantować sprawiedliwość.

Ogólnie rzecz biorąc, POF jest definiowany za pomocą następującego wzoru:

${\ Displaystyle POF = {\ Frac {\ max _ {D \ in Divisions} {(dobrobyt (D)}}} {\ max _ {D \ in FairDivisions} {(dobrobyt (D))}}} }$

Dokładna cena różni się znacznie w zależności od rodzaju podziału, rodzaju sprawiedliwości i rodzaju pomocy społecznej, która nas interesuje.

Najlepiej zbadanym rodzajem pomocy społecznej jest utylitarystyczna opieka społeczna , zdefiniowana jako suma (znormalizowanych) użyteczności wszystkich agentów. Innym typem jest egalitarna opieka społeczna , definiowana jako minimalna (znormalizowana) użyteczność przypadająca na agenta.

Przykład liczbowy

W tym przykładzie skupiamy się na utylitarnej cenie proporcjonalności lub UPOP.

Rozważmy heterogeniczny majątek ziemski, który należy podzielić między 100 partnerów, z których wszyscy wyceniają go na 100 (lub wartość jest znormalizowana do 100). Najpierw spójrzmy na kilka skrajnych przypadków.

• Maksymalny możliwy dobrobyt utylitarny wynosi 10 000. Dobrobyt ten jest osiągalny tylko w bardzo rzadkim przypadku, gdy każdy ze wspólników chce innej części ziemi.
• W podziale proporcjonalnym każdy partner otrzymuje wartość co najmniej 1, więc dobrostan utylitarny wynosi co najmniej 100.

Górna granica

Opisane powyżej skrajne przypadki już dają nam trywialną górną granicę: UPOP ≤ 10000/100 = 100. Ale możemy uzyskać węższą górną granicę.

Załóżmy, że mamy sprawny podział majątku ziemskiego na 100 wspólników, z dobrobytem utylitarnym U . Chcemy to zamienić na podział proporcjonalny. W tym celu grupujemy partnerów według ich aktualnej wartości:

• Partnerzy, których aktualna wartość wynosi co najmniej 10, nazywani są szczęśliwymi .
• Pozostali partnerzy nazywani są niefortunnymi .

Istnieją dwa przypadki:

• Jeśli jest mniej niż 10 szczęśliwych partnerów, po prostu odrzuć obecny podział i dokonaj nowego podziału proporcjonalnego (np. stosując protokół ostatniego zmniejszania ). W podziale proporcjonalnym każdy partner otrzymuje wartość co najmniej 1, więc łączna wartość wynosi co najmniej 100. Wartość pierwotnego podziału jest mniejsza niż (10*100+90*10)=1900, więc UPOP wynosi większość 19.
• Jeśli jest co najmniej 10 szczęśliwych partnerów, utwórz podział proporcjonalny, korzystając z następującego wariantu protokołu ostatniego zmniejszania :
  • Każdy szczęśliwy partner z kolei odcina 0,1 swojego udziału i pozwala pozostałym nieszczęśliwym partnerom go zmniejszyć. Ten udział otrzymuje albo on, albo jeden z niefortunnych wspólników.
  • Dzieje się tak, dopóki każdy z (co najwyżej) 90 niefortunnych partnerów nie otrzyma udziału. Teraz każdy z (co najmniej) 10 szczęśliwych partnerów ma co najmniej 0,1 swojej poprzedniej wartości, a każdy z nieszczęśliwych partnerów ma co najmniej swoją poprzednią wartość, więc UPOP wynosi co najwyżej 10.

Podsumowując: UPOP jest zawsze mniejszy niż 20, niezależnie od miar wartości partnerów.

Dolna granica

UPOP może wynosić zaledwie 1. Na przykład, jeśli wszyscy partnerzy mają tę samą miarę wartości, to w dowolnym podziale, niezależnie od sprawiedliwości, dobrobyt utylitarny wynosi 100. Stąd UPOP=100/100=1.

Interesuje nas jednak UPOP w najgorszym przypadku, tj. kombinacja miar wartości, w której UPOP jest duży. Oto taki przykład.

Załóżmy, że istnieją dwa rodzaje partnerów:

• 90 jednolitych wspólników, którzy jednakowo wyceniają całą ziemię (tzn. wartość kawałka jest proporcjonalna do jego wielkości).
• 10 skupionych partnerów, z których każdy ceni tylko jedną dzielnicę obejmującą 0,1 ziemi.

Rozważ dwie następujące partycje:

• Sprawiedliwy podział : podziel ziemię równomiernie, dając każdemu partnerowi 0,01 ziemi, gdzie partnerzy skoncentrowani otrzymują swoje 0,01 w wybranej dzielnicy. Ten podział jest sprawiedliwy. Wartość każdego jednolitego partnera wynosi 1, podczas gdy wartość każdego skoncentrowanego partnera wynosi 10, więc dobrostan utylitarny wynosi 190.
• Efektywny podział : Podziel całą krainę między zaangażowanych partnerów, dając każdemu partnerowi całą wybraną dzielnicę. Dobrobyt utylitarny wynosi 100*10=1000.

W tym przykładzie UPOP wynosi 1000/190=5,26. Zatem 5,26 jest dolną granicą najgorszego przypadku UPOP (gdzie „najgorszy przypadek” obejmuje wszystkie możliwe kombinacje miar wartości).

Łączny

Łącząc wszystkie wyniki, otrzymujemy, że najgorszy przypadek UPOP jest ograniczony między 5 a 20.

Ten przykład jest typowy dla argumentów używanych do powiązania POF. Aby udowodnić dolną granicę, wystarczy opisać jeden przykład; aby udowodnić górną granicę, należy przedstawić algorytm lub inny wyrafinowany argument.

Krojenie ciasta z ogólnymi kawałkami

Utylitarna cena proporcjonalności

Opisany powyżej przykład liczbowy można uogólnić od 100 do n partnerów, podając następujące granice dla najgorszego przypadku UPOP:

√ n /2 ≤ UPOP ≤ 2√ n -1

UPOP = Θ(√ n )

Dla dwóch partnerów bardziej szczegółowe obliczenie daje granicę: 8-4*√3 ≅ 1,07.

Utylitarna cena zazdrości

Kiedy cały tort jest podzielony, podział wolny od zazdrości jest zawsze proporcjonalny. Stąd dolna granica najgorszego przypadku UPOP (√ n /2) ma zastosowanie również tutaj. Z drugiej strony, jako górną granicę mamy tylko słabą granicę n -1/2. Stąd:

√ n /2 ≤ UPOV ≤ n -1/2

Ω(√ n ) ≤ UPOV ≤ O( n )

Dla dwóch partnerów bardziej szczegółowe obliczenie daje granicę: 8-4*√3 ≅ 1,07.

Utylitarna cena równości

${\ Displaystyle {(n + 1) ^ {2} \ ponad 4 n} \ równoważnik UPOQ \ równoważnik n}$

${\ styl wyświetlania UPOQ=\Theta (n)}$

W przypadku dwóch partnerów bardziej szczegółowe obliczenia dają granicę: 9/8 = 1,125.

Przydział dóbr niepodzielnych

W przypadku przedmiotów niepodzielnych nie zawsze istnieje przydział spełniający proporcjonalność, brak zazdrości lub równość (dla prostego przykładu wyobraź sobie dwóch partnerów próbujących podzielić jeden cenny przedmiot). Zobacz także sprawiedliwy przydział przedmiotów . W związku z tym w obliczeniach ceny godziwości nie uwzględnia się przypadków, w których żadna cesja nie spełnia odpowiedniego pojęcia godziwości. Krótkie podsumowanie wyników:

UPOP = n - 1 + 1/ n ; dla dwóch osób: 3/2.

(3 n +7)/9-O(1/ n ) ≤ UPOV ≤ n -1/2; dla dwóch osób: 3/2

UPOQ=nieskończoność; dla dwóch osób: 2

Krojenie prac domowych z elementami ogólnymi

Dla problemu krojenia ciasta, gdy „ciasto” jest niepożądane (np. koszenie trawnika), mamy następujące wyniki:

( n +1)^2/4 n ≤ UPOP ≤ n ; dla dwóch osób: 9/8

(n+1)^2/4n ≤ UPOV ≤ nieskończoność; dla dwóch osób: 9/8

UPOQ= n

Niepodzielna alokacja złych

UPOP = n

UPOV = nieskończoność

UPOQ = nieskończoność

Cięcie ciasta z połączonymi kawałkami

Problem sprawiedliwego krojenia ciasta ma odmianę, w której kawałki muszą być połączone. W tym wariancie zarówno licznik, jak i mianownik we wzorze POF są mniejsze (ponieważ maksimum jest przejmowane przez mniejszy zbiór), więc a priori nie jest jasne, czy POF powinien być mniejszy, czy większy niż w przypadku rozłączonym.

Utylitarna cena uczciwości

Mamy następujące wyniki dla dobrobytu utylitarnego:

UPOP = Θ(√ n )

UPOV = Θ(√ n )

n -1+1/ n ≤ EPOQ ≤ n

EPOQ = Θ( n )

Egalitarna cena uczciwości

W podziale proporcjonalnym wartość każdego z partnerów wynosi co najmniej 1/ n sumy. W szczególności wartość najmniej szczęśliwego agenta (nazywana egalitarnym dobrobytem podziału) wynosi co najmniej 1/ n . Oznacza to, że w podziale egalitarno-optymalnym dobrobyt egalitarny wynosi co najmniej 1/ n , a więc podział egalitarno-optymalny jest zawsze proporcjonalny. Stąd egalitarna cena proporcjonalności (EPOP) wynosi 1:

EPPO = 1

Podobne rozważania dotyczą egalitarnej ceny słuszności (EPOQ):

EPOQ = 1

Egalitarna cena braku zawiści jest znacznie większa:

EPOV = n /2

Jest to ciekawy wynik, ponieważ implikuje, że obstawanie przy kryterium braku zazdrości zwiększa różnice społeczne i szkodzi najbardziej nieszczęśliwym obywatelom. Kryterium proporcjonalności jest znacznie mniej szkodliwe.

Cena maksymalizacji dobrobytu

Zamiast obliczać utratę dobrobytu z powodu sprawiedliwości, możemy obliczyć utratę sprawiedliwości z powodu optymalizacji dobrobytu. Otrzymujemy następujące wyniki:

proporcjonalna-cena-egalitaryzmu = 1

zazdrość-cena-egalitaryzmu = n -1

proporcjonalna-cena-utylitaryzmu = nieskończoność

zazdrość-cena-egalitaryzmu = nieskończoność

Alokacja dóbr niepodzielnych z połączonymi blokami

Podobnie jak w przypadku krojenia ciasta, w przypadku niepodzielnego przypisania elementów istnieje odmiana, w której elementy leżą na linii, a każdy przypisany element musi tworzyć blok na linii. Krótkie podsumowanie wyników:

UPOP = n - 1 + 1/ n

UPOV = Θ(√ n )

UPOQ = nieskończoność; dla dwóch osób: 3/2

EPOP = 1

EPOV = n /2

EPOQ = nieskończoność; dla dwóch osób: 1

Cięcie chore z połączonymi elementami

Krótkie podsumowanie wyników:

n /2 ≤ UPOP ≤ n

UPOV = nieskończoność

UPOQ = n

EPOP = 1

EPOV = nieskończoność

EPOQ = 1

Jednorodna alokacja zasobów

Cena uczciwości była również badana w walce o alokację jednorodnych, podzielnych zasobów, takich jak ropa naftowa czy drewno. Znane wyniki to:

UPOV = UPOP = Θ(√ n )

Dzieje się tak, ponieważ reguła równowagi konkurencyjnej z równych dochodów daje alokację wolną od zawiści, a jej utylitarna cena wynosi O(√ n ).

Inne konteksty

Cena godziwa była badana w kontekście problemu sumy godziwej podzbioru .

Ceną uzasadnionej reprezentacji jest utrata przeciętnej satysfakcji z powodu wymogu posiadania uzasadnionej reprezentacji w warunkach głosowania zatwierdzającego.

Zobacz też

• Wydajność ekonomiczna
• Cena anarchii