Twierdzenie Wellera

Twierdzenie Wellera jest twierdzeniem w ekonomii . Mówi, że heterogeniczny zasób („ciasto”) można podzielić między n partnerów o różnych wycenach w sposób zarówno efektywny w sensie Pareto (PE), jak i wolny od zazdrości (EF). W ten sposób możliwe jest sprawiedliwe podzielenie tortu bez uszczerbku dla efektywności ekonomicznej.

Co więcej, twierdzenie Wellera mówi, że istnieje taka cena, że ​​alokacja i cena są równowagą konkurencyjną (CE) z równymi dochodami (EI). Łączy w ten sposób dwa obszary badawcze, które wcześniej nie były ze sobą powiązane: sprawiedliwe krojenie ciasta i równowagę ogólną .

Tło

Uczciwe krojenie ciasta badano od lat czterdziestych XX wieku. Istnieje heterogeniczny podzielny zasób, taki jak ciasto lub majątek ziemski. Jest n partnerów, z których każdy ma osobistą funkcję gęstości wartości na torcie. Wartość elementu dla partnera jest całką jego gęstości wartości względem tego elementu (oznacza to, że wartość jest miarą nieatomową na torcie). Problem krojenia tortu bez zazdrości polega na podzieleniu tortu na n rozłącznych kawałków, po jednym kawałku na agenta, tak że dla każdego agenta wartość jego kawałka jest nieznacznie większa niż wartości wszystkich pozostałych kawałków (a więc żaden agent nie zazdrości drugiemu agentowi udział).

Następstwem twierdzenia Dubinsa-Spaniera o wypukłości (1961) jest to, że zawsze istnieje „konsensusowy podział” - podział tortu na n kawałków, tak że każdy agent wycenia każdy kawałek dokładnie jako ${\ displaystyle 1/n}$ . Partycja konsensusu to oczywiście EF, ale nie PE. Co więcej, innym następstwem twierdzenia Dubinsa-Spaniera o wypukłości jest to, że gdy co najmniej dwóch agentów ma różne miary wartości, istnieje podział, który daje każdemu agentowi ściśle więcej niż ${\ Displaystyle 1/n}$ . Oznacza to, że partycja konsensusu nie jest nawet słabo PE.

Wolność od zazdrości jako kryterium sprawiedliwej alokacji została wprowadzona do ekonomii w latach sześćdziesiątych i intensywnie badana w latach siedemdziesiątych. Twierdzenia Variana badają ją w kontekście dzielenia dóbr jednorodnych . Przy łagodnych ograniczeniach funkcji użyteczności agentów istnieją alokacje, które są zarówno PE, jak i EF. Dowód wykorzystuje poprzedni wynik dotyczący istnienia równowagi konkurencyjnej z równych dochodów (CEEI). David Gale udowodnił podobny wynik istnienia agentów o użyteczności liniowej .

Krojenie ciasta jest większym wyzwaniem niż jednorodna dobra alokacja, ponieważ ciasto jest niejednorodne. W pewnym sensie ciasto jest kontinuum towarów: każdy punkt ciasta to inne dobro. To jest temat twierdzenia Wellera.

Notacja

Ciasto jest oznaczone przez do $\ displaystyle C}$ . Liczba partnerów jest oznaczona przez ${\ displaystyle n}$ .

Podział ciasta , oznaczony przez , jest n -krotką $podzbiorów$${\ Displaystyle X_ {1}, \ kropki, X_ {n}}$ podzbiorów do { $}$ ; ${\ displaystyle X_ {i}}$ to kawałek przekazany partnerowi ${\ displaystyle i}$ .

Partycja nazywa się PEEF , jeśli spełnia następujące dwa warunki:

• Efektywność Pareto : żaden inny podział nie jest nieznacznie lepszy dla wszystkich partnerów i ściśle lepszy dla co najmniej jednego partnera.
• Wolność od zazdrości : żaden partner nie preferuje kawałka przydzielonego innemu agentowi.

Partycja $)$ ceny na $CEEI$ nazywane są , $gdzie$ spełniają następujące dwa warunki ( $jest$ agentem ${\ displaystyle i}$ jest miarą wartości i jest miarą ceny): ${\ displaystyle P}$

• Równowaga konkurencyjna : dla każdego agenta ja , każdy pozytywny wycinek ${i}}$${\ Displaystyle Z \ subseteq C}$ i każdy pozytywny wycinek : ${\ Displaystyle V_ {i} (Z_ {i}) / P (Z_ {i}) \ geq V_ {i} (Z) / P (Z)}$ .
• Równe dochody: dla każdego agenta ja: ${\ Displaystyle P (X_ {i}) = 1}$ .

CEEI jest znacznie silniejszy niż PEEF: każda alokacja CEEI to PEEF, ale istnieje wiele alokacji PEEF, które nie są CEEI.

Twierdzenie Wellera dowodzi istnienia alokacji CEEI, co implikuje istnienie alokacji PEEF.

Szkic dowodowy

Poniższa prezentacja oparta jest na artykule Wellera i częściowo na .

Dowód Wellera opiera się na podziale ciasta ważonego-utylitarno-maksymalnego (WUM) . Dzielenie WUM to dzielenie maksymalizujące funkcję o postaci:

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

gdzie ${\ displaystyle i}$$}$ indeksem agenta, jest miarą wartości agenta, $displaystyle$$kawałkiem$ , podane $i$ jest $_$ wagą

Następstwem $,$ Dubinsa-Spaniera o zwartości jest to że dla każdego wektora wagi istnieją alokacje WUM. ${V_ {i} (Z) \ ponad w_ {i }}}$ , każdy mały kawałek ciasta powinien być przekazany osobie $,$ której $Displaystyle$ jest największy. Jeśli są dwie lub więcej osób, dla których ta wartość jest taka sama, to każdy dowolny podział tego kawałka między nimi skutkuje podziałem WUM (przydziały WUM można również zdefiniować za pomocą zbioru Radona – Nikodyma . Każdy wektor wag $w}$${\$$-wymiarowej$ , jako punkt na jednostce simplex , indukuje alokację zestawu ciasta Radona – , co indukuje jeden lub więcej przydziałów tortu) .

Każda dywizja WUM to oczywiście PE. Jednak podział WUM może być bardzo niesprawiedliwy; na przykład, jeśli ${ \$ duży, to agent może dostać tylko niewielką część tortu (wektor wagi bardzo zbliżony do $w}$ ja ${$$\ displaystyle i}$ wierzchołek unit-simplex, co oznacza, że tylko punkty zbioru Radon-Nikodym, które są bardzo blisko jego wierzchołka $jest$ . Natomiast jeśli ${\ displaystyle w_ {i}}$$jest$ bardzo mały, wtedy agent dostać cały tort.

Weller udowadnia, że ​​istnieje wektor wag, dla którego dzielnikiem WUM jest również EF. Odbywa się to poprzez zdefiniowanie kilku funkcji:

1. Funkcja ${\ Displaystyle \ operatorname {Par}}$ : dla każdego dodatniego wektora wagi ${\ Displaystyle w = [w_ {1}, \ kropki, w_ {n}] }$ , ${\ Displaystyle \ operatorname {Par} (w)}$ to zbiór partycji WUM z wagami ${\ Displaystyle w}$ . Funkcja ${\ displaystyle \ operatorname {Par}}$ jest funkcją o wartościach ustalonych z unit-simplex-interior w przestrzeń zestawów ciast-przegród PE.

2. Funkcja ${\ Displaystyle \ operatorname {Val}}$ : dla każdej partycji ${\ Displaystyle X = X_ {1}, \ kropki, X_ {n}}$ , ${\ Displaystyle \ operatorname {Val} (X)}$ jest wektorem proporcjonalnym do wartości partnerów: ${\ Displaystyle \ operatorname {Val} (X) = {\ Frac {[V_ {1} (X_ {1}$ . Funkcja ${\ displaystyle \ operatorname {Val}}$ odwzorowuje przestrzeń partycji tortowych na unit-simplex.

3. Funkcja ${\ Displaystyle \ operatorname {Wel} = \ operatorname {Val} \ circ \ operatorname {Par}}$ : dla każdego dodatniego wektora wagi ${\ Displaystyle w}$ , ${\ displaystyle \ operatorname {Wel} (w)}$ to zbiór nowych wektorów wagi. Jest to funkcja o wartościach zestawu z wnętrza simpleksu jednostkowego do zbioru podzbiorów simpleksu jednostkowego. Wektory w ${\ Displaystyle \ operatorname {Wel} (w)}$$w$ pewnym sensie przeciwne do $mały$ jeśli , to partycje w ${\ Displaystyle \ operatorname {Par} (w)}$ nadaj agentowi dużą wartość, a jego waga w ${\ Displaystyle \ operatorname {Wel} (w)}$$.$ duża W przeciwieństwie do tego, ${\ Displaystyle w_ {i}}$ jest duży, a partycje w ${\ Displaystyle \ operatorname {Par} (w)}$ dają agentowi ${\ Displaystyle i}$ małą wartość i jego wagę w ${\ Displaystyle \ operatorname {Wel} (w)}$ jest duży. To sugeruje, że jeśli ${\ displaystyle \ operatorname {Wel}}$ ma punkt stały, to ten punkt stały odpowiada szukanej partycji PEEF.

Aby udowodnić, że funkcja ma punkt $stały$ , chcielibyśmy użyć twierdzenia Kakutaniego punkcie stałym . Istnieje jednak problem techniczny, z którym należy się uporać: funkcja ${\ displaystyle \ operatorname {Wel}}$ jest zdefiniowana tylko we wnętrzu jednostki simpleksowej, podczas gdy jej zakres obejmuje całą jednostkę simpleksową. Na szczęście możliwe jest rozszerzenie ${\ displaystyle \ operatorname {Wel}}$ do granicy unit-simplex, w sposób, który zagwarantuje, że żaden stały punkt NIE będzie na granicy. Rozszerzona funkcja ${\ displaystyle \ operatorname {Wel} '}$ jest rzeczywiście funkcją od jednostki simpleksowej do podzbiorów jednostki simpleksowej. ${\ Displaystyle \ operatorname {Wel} '}$ spełnia wymagania twierdzenia Kakutaniego o punkcie stałym, ponieważ:

• Jest to odwzorowanie punkt-zbiór simpleksu jednostkowego, który jest zwartym i wypukłym podzbiorem przestrzeni euklidesowej;
• Jest górny półciągły ;
• Dla każdego $Wel$ unit-simplex, $\ Displaystyle \ operatorname {Wel} '(w)}$ jest niepusty, zamknięty i wypukły;

Dlatego ${\ Displaystyle \ operatorname {Wel} '}$ ma punkt stały - wektor w jednostce simpleks taki, że $W$$nazwa_operatora {Wel} '(W)}$$\ Displaystyle W \ in$ . Dzięki konstrukcji ${\ displaystyle \ operatorname {Wel} '}$ można pokazać, że punkt stały $musi$ się we wnętrzu jednostki simpleksowej, gdzie ${\ Displaystyle \ nazwa operatora {Wel} '\ równoważnik \ nazwa operatora {Wel}}$ . Stąd:

${\ Displaystyle W \ w \ operatorname {Wel} (W)}$

Wel ${\ Displaystyle \ operatorname {Wel}}$ , $}$ , więc nie istnieje taka partycja , że: ${\ displaystyle X}$

• ${\ Displaystyle X \ w \ nazwa operatora {Par} (W)}$
• ${\ Displaystyle W = \ operatorname {Val} (X)}$

${\ displaystyle X}$ jest wyraźnie PE, ponieważ jest to WUM (z wektorem wagi W). Jest to również EF, ponieważ:

• ${\ Displaystyle X \ in \ operatorname {Par} (W)}$ oznacza, że ​​X maksymalizuje sumę ważoną za pomocą wag ${\ Displaystyle W = [W_ {1},\kropki ,W_{n}]}$ . Oznacza to, że każdy ułamek ciasta jest przekazywany agentowi, dla którego ważona gęstość wartości jest maksymalna. Stąd dla każdych dwóch agentów ${\ displaystyle i, j}$ :

${\ Displaystyle {\ Frac {V_ {j} (X_ {j}}}} {w_ {j}}} \ geq {\ Frac {V_ {i} (X_ {j})} {w_ {i}}} \ implikuje {\frac {V_{j}(X_{j})}{V_{i}(X_{j})}}\geq {\frac {w_{j}}{w_{i}}}.}$

• ${\ Displaystyle W = \ operatorname {Val} (X)}$ oznacza, że ​​stosunek między wartościami każdych dwóch agentów ${\ Displaystyle i, j}$ jest równy stosunkowi ich wag:

${\ Displaystyle {\ Frac {V_ {j} (X_ {j}}} {V_ {i} (X_ {i})}} = {\ Frac {w_ {j}} {w_ {i}}}.}$

Połączenie dwóch ostatnich nierówności daje dla każdych dwóch agentów ${\ displaystyle i, j}$ :

${\ Displaystyle {\ Frac {V_ {j} (X_{j})}{V_{i}(X_{j})}}\geq {\frac {V_{j}(X_{j})}{V_{i}(X_{i})}} \implikuje V_{i}(X_{j})\równoważnik V_{i}(X_{i})}$

co jest dokładnie definicją braku zazdrości.

Obliczanie miary ceny

Gdy mamy alokację PEEF , miarę ceny można obliczyć w następujący sposób: $displaystyle$$X}$

• Z ja $displaystyle Z_ {i}}$ , który jest w całości posiadany przez agenta, ${\ displaystyle i}$ , ${\ Displaystyle P ( Z_{i})=V_{i}(Z_{i})/V_{i}(X_{i})}$
• Dla każdej sztuki podzielonej między kilku agentów cena jest sumą cen jej podzbiorów posiadanych przez tych agentów.

Można udowodnić, że para $spełnia$ warunki równowagi konkurencyjnej przy CEEI) W szczególności dochód każdego agenta, zgodnie z miarą ceny , wynosi dokładnie 1, ponieważ ${\ displaystyle P}$

${\ Displaystyle P (X_ {i}) = V_ {i} (X_ {i}) / V_ {i} (X_ {i})=1.}$

Przykład

Jako ilustrację rozważmy ciasto składające się z dwóch części: czekoladowej i waniliowej oraz dwóch partnerów: Alicji i Jerzego, z następującymi wartościami:

Partner	Czekolada	Wanilia
Alicja	9	1
Jerzy	6	4

${\ displaystyle w}$ dwóch, wektor można przedstawić za pomocą jednej liczby - stosunku wagi Alicji do wagi George'a: w

• Jeśli stosunek jest mniejszy niż 1:4, wówczas dywizja WUM powinna oddać Alicji cały tort. Stosunek wartości, którymi cieszą się ludzie, będzie nieskończony (lub 1:0), więc oczywiście w tym przedziale nie znajdzie się żaden stały punkt.
• Jeśli stosunek wynosi dokładnie 1:4, to całą czekoladę należy podać Alicji, ale wanilię można dowolnie podzielić między Alicję i Jerzego. Stosunek wartości działek WUM mieści się w przedziale od 1:0 do 9:4. Ten zakres nie zawiera stosunku 1:4, stąd nie ma tu punktu stałego.
• Jeśli stosunek wynosi od 1:4 do 9:6, to całą wanilię należy dać George'owi, a całą czekoladę Alicji. Stosunek wartości wynosi 9:4, co nie mieści się w zakresie, więc nie znaleziono jeszcze punktu stałego.
• Jeśli stosunek wynosi dokładnie 9:6, to całą wanilię należy podać George'owi, ale czekoladę można dowolnie podzielić między Alicję i George'a. Stosunek wartości działek WUM zawiera się w przedziale od 9:4 do 0:1. Widzimy, że 9:6 mieści się w przedziale, więc mamy stały punkt. Można to osiągnąć, podając George'owi całą wanilię i 1/6 czekolady (za łączną wartość 5), a Alicji pozostałe 5/6 czekolady (za łączną wartość 7,5). Ten podział to PEEF.

Uogólnienia i rozszerzenia

Berliant, Thomson i Dunz wprowadzili kryterium grupowej wolności od zawiści , które uogólnia zarówno efektywność Pareto, jak i wolność od zawiści. Udowodnili istnienie przydziałów wolnych od zazdrości o grupę z dodatkowymi użytecznościami. Później Berliant i Dunz badali niektóre naturalne nieaddytywne funkcje użyteczności, motywowane problemem podziału gruntów. Gdy narzędzia nie są addytywne, alokacja CEEI nie jest już gwarantowana, ale istnieje z pewnymi ograniczeniami.

Więcej powiązanych wyników można znaleźć w Efektywne krojenie ciasta i Użyteczne krojenie ciasta .

Algorytmy

Twierdzenie Wellera jest czysto egzystencjalne. Niektóre późniejsze prace badały algorytmiczne aspekty znajdowania partycji CEEI. W pracach tych zwykle zakłada się, że miary wartości są częściami stałe , tj. ciasto można podzielić na jednorodne obszary, w których gęstość wartości każdego agenta jest jednakowa.

Pierwszy algorytm znajdowania partycji CEEI w tym przypadku został opracowany przez Reijnierse i Pottersa.

Aziz i Ye opracowali algorytm bardziej wydajny obliczeniowo.

W rzeczywistości każdy podział tortu CEEI maksymalizuje produkt użyteczności i odwrotnie – każdy podział, który maksymalizuje produkt użyteczności, jest CEEI. Dlatego CEEI można znaleźć, rozwiązując program wypukły maksymalizujący sumę logarytmów użyteczności.

W przypadku dwóch agentów procedurę skorygowanego zwycięzcy można zastosować w celu znalezienia alokacji PEEF, która jest również sprawiedliwa (ale niekoniecznie CEEI).

Wszystkie powyższe algorytmy można uogólnić na miary wartości, które są ciągłe Lipschitza . Ponieważ takie funkcje można aproksymować jako funkcje częściowo-stałe „tak blisko, jak nam się podoba”, powyższe algorytmy mogą również przybliżać alokację PEEF „tak blisko, jak nam się podoba”.

Ograniczenia

W podziale CEEI gwarantowanym przez Weller kawałek przydzielony każdemu partnerowi może zostać odłączony. Zamiast jednego ciągłego kawałka każdy partner może otrzymać stos „okruchów”. Rzeczywiście, gdy elementy muszą być połączone, partycje CEEI mogą nie istnieć. Rozważ następujące wyceny częściowo-stałe:

Alicja	2	2	2	2	2	2
Jerzy	1	1	4	4	1	1

Warunek CE implikuje, że wszystkie segmenty peryferyjne muszą mieć tę samą cenę (powiedzmy p ) i oba wycinki centralne muszą mieć tę samą cenę (powiedzmy q ). Warunek EI oznacza, że ​​​​całkowita cena ciasta powinna wynosić 2, więc ${\ displaystyle q + 2p = 1}$ . Warunek EI ponownie implikuje, że w każdym połączonym dziale CEEI tort jest przecięty na środku. Zarówno Alicja, jak i Jerzy otrzymują dwa wycinki peryferyjne i jeden środkowy. Warunek CE dla Alicji oznacza, że ${\ displaystyle q = p}$ ale warunek CE na George'u implikuje, że ${\ displaystyle q = 4p}$ , co jest sprzecznością.

Chociaż warunek CEEI może być nieosiągalny w przypadku połączonych elementów, słabszy warunek PEEF jest zawsze osiągalny, gdy jest dwóch partnerów. Dzieje się tak, ponieważ przy dwóch partnerach brak zazdrości jest równoznaczny z proporcjonalnością, a proporcjonalność jest zachowana dzięki ulepszeniom Pareto. Jednak gdy partnerów jest trzech lub więcej, nawet słabszy stan PEEF może być nieosiągalny. Rozważ następujące wyceny częściowo-stałe:

Alicja	2	0	3	0	2	0	0
Pion	0	0	0	0	0	7	0
Karol	0	2	0	2	0	0	3

WF implikuje, że Bob otrzymuje przynajmniej część swojego wycinka o wartości 7 (PE implikuje wtedy, że otrzymuje całość).

Według łączności istnieją trzy opcje:

• Kawałek Carla znajduje się na prawo od pionu Boba. Tak więc Karol otrzymuje prawy kawałek, a jego wartość to 3. PE implikuje, że Alicja otrzymuje wszystkie pięć kawałków na lewo od kawałka Boba, które są warte 4 dla Carla. Więc Carl zazdrości Alice.
• Figura Carla znajduje się na lewo od figury Boba, a on otrzymuje swoje dwa piony o wartości 2. Wtedy wartość Alicji wynosi najwyżej 2, a figura Karola jest warta 3 dla Alicji. Więc Alice zazdrości Carlowi.
• Bierka Karola znajduje się na lewo od figury Boba, a on dostaje co najwyżej jedną figurę o wartości 2. Wtedy przydział nie jest PE, ponieważ Karol może zwiększyć swoją wartość do 3, przesuwając się na prawo od Boba, nie wyrządzając nikomu krzywdy.

Dlatego żadna alokacja nie jest PEEF.

W powyższym przykładzie, jeśli uznamy ciasto za „ciasto” (tj. jeśli kawałek może przejść wokół granicy ciasta do drugiej granicy), wówczas istnieje alokacja PEEF; jednak Stromquist pokazał bardziej wyrafinowany przykład, w którym alokacja PEEF nie istnieje nawet w cieście.

Zobacz też

• Pareto-efektywny podział wolny od zawiści – analogiczny problem dla jednorodnych dóbr podzielnych.