Wellerova věta

Wellerův teorém [1] je teorém ekonomie . Argumentuje tím, že heterogenní zdroj („ koláč “) lze rozdělit mezi n účastníků s různými odhady významnosti tak, že rozdělení bude jak Pareto- efektivní ( Ing. Pareto-efficient , PE), tak nezávist ( angl. bez závisti , EF). Je tedy možné sdílet dort (heterogenní zdroj) bez narušení ekonomické efektivity .

Wellerův teorém navíc říká, že existuje určitá cena , za kterou jsou distribuce a cena v konkurenční rovnováze ( anglicky competition equilibrium , CE) se stejným příjmem ( anglicky equal incomes , EI). Tento teorém tedy spojuje dvě oblasti studia, které spolu dříve nesouvisely – jde o spravedlivé krájení koláče a všeobecnou rovnováhu .

Pozadí

Spravedlivé krájení dortu bylo studováno od 40. let 20. století. Existuje heterogenní dělitelný zdroj, jako je dort nebo kus země. Účastníků je n , z nichž každý má funkci osobní hodnoty hustoty kousků dortu. Hodnota řezu pro účastníka je integrál hustoty hodnoty přes řez koláče (to znamená, že skóre účastníka je bezatomová míra na koláči). Problém krájení dortu bez závisti spočívá v rozdělení dortu na n neprotínajících se kusů, jeden kus na účastníka, takže pro každého účastníka není hodnota kousku, který obdrží, menší než hodnoty všech ostatních kusů ( aby žádný člen nežárlil na podíl druhého člena).

Důsledkem Dubins-Spanierovy věty o konvexitě (1961) je, že vždy existuje "konzistentní rozdělení" - rozdělení koláče na n kusů tak, že hodnota pro kterýkoli člen kteréhokoli kusu je přesně . Dohodnutý oddíl je samozřejmě EF, ale není to PE. Navíc dalším důsledkem výše uvedeného teorému je, že když mají alespoň dva účastníci různé míry hodnoty, existuje rozdělení, které každému účastníkovi dává striktně více než . To znamená, že konzistentní oddíl není ani slabší než PE. $1/n$ $1/n$

Absence závisti jako kritéria pro spravedlivé rozdělování byla navržena v ekonomii v 60. letech a intenzivně studována během 70. let. Varianův teorém studuje absenci závisti v kontextu sdílení homogenního zboží . Při malých omezeních užitných funkcí agentů existují distribuce, které jsou PE i EF. Důkaz je výsledkem existence konkurenční rovnováhy rovných příjmů ( konkurenční rovnováha ze stejných příjmů , CEEI) . David Gale prokázal podobnou existenci pro agenty s lineární užitečností .

Problém krájení dortu je obtížnější než distribuce homogenního zboží. Částečně má dort širokou škálu výhod – každý bod dortu má jiný význam. To je předmětem Wellerovy věty.

Označení

Dort je označen písmenem . Počet účastníků divize bude označen písmenem . $C$ $n$

Koláčový oddíl , označený , je n -tice podmnožin koláče . Zde je kousek dortu, který je dán účastníkovi . $X$ $X_{1},\dots ,X_{n}$ $C$ $X_{i}$ $i$

Oddíl se nazývá PEEF , pokud splňuje následující dvě podmínky:

Pareto efektivní : žádné jiné rozdělení není horší pro všechny účastníky a přísně lepší pro jednoho z nich.
Nedostatek závisti: žádný člen si nepřeje dostat figurku darovanou jinému členovi.

Oddíl a cenová míra se nazývají CEEI , pokud splňují následující dvě podmínky: $X$ $P$ $C$

Konkurenční rovnováha : Pro každého agenta i jakýkoli blok s kladným odhadema jakýkoli blok s kladným odhadem:. $Z_{i}\subseteq X_{i}$ $Z\subseteq C$ $v_{i}(Z_{i})/P(Z_{i})\geqslant v_{i}(Z)/P(Z)$
Rovné příjmy: Pro každého agenta i: . $P(X_{i})=1$

CEEI je mnohem přísnější než PEEF: jakákoli distribuce CEEI je PEEF, ale existuje mnoho distribucí PEEF mimo CEEI.

Wellerův teorém dokazuje existenci CEEI distribuce, která implikuje existenci PEEF distribuce.

Náčrt důkazu

Níže uvedená prezentace je založena na Wellerově článku a částečně na Barbanelově článku [2] .

Wellerův důkaz se opírá o vážené – utilitární – maximální ( WUM) krájení dortu . WUM je funkce maximalizující dělení následující formy:

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

kde je index agenta, je naměřená hodnota agenta, je kus koláče předaný agentovi a je kladná váha. $i$ $V_i$ $X_{i}$ $w_{i}$

Důsledek Dubins-Spanierova teorému kompaktnosti říká, že pro jakýkoli váhový vektor existuje rozdělení WUM. Intuitivně by každý kousek dortu měl dostat osoba, pro kterou je největší. Pokud existují dva nebo více lidí, pro které je tato hodnota stejná, pak jakékoli libovolné rozdělení dílu mezi nimi vede k dělení WUM ( rozdělení WUM lze také definovat pomocí . Každý vektor hmotnostisady Radon-Nikodim , definuje oddíl tohoto simplexu Tento oddíl generuje distribuci sady Radon-Nikodim pro koláč, která generuje jedno nebo více rozdělení koláče) . $w$ $Z$ $i$ ${V_{i}(Z) \over w_{i}}$ $w$ $(n-1)$

Jakákoli divize WUM je zjevně PE. Rozdělení WUM však může být velmi nespravedlivé. Pokud je například velmi velký, může agent dát jen malý podíl z koláče (vektor hmotnosti je velmi blízko vrcholu agenta jednotky simplex, což znamená, že obdrží pouze body Radon-Nikodim). množiny , které jsou velmi blízko jeho vrcholu) . Pro srovnání, pokud je velmi malý, může agent získat celý dort. $w_{i}$ $i$ $w$ $i$ $i$ $w_{i}$ $i$

Weller dokázal, že existuje vektor vah, pro který je dělení WUM také EF. Dokázal to definováním několika funkcí:

Funkce : pro libovolný vektor kladných vah je množina oddílů WUM s vahami . Funkce je vícehodnotová funkce od vnitřku jednotky simplex až po nastavený prostor PE řezů dortu. $Par$ $w=[w_{1},\tečky ,w_{n}]$ $Par(w)$ $w$ $Par$
Funkce : pro jakýkoli oddíl je vektor úměrný hodnotám účastníků: . Funkce mapuje prostor řezů dortů na jednotku simplex. $Val$ ${\displaystyle X=X_{1},\tečky ,X_{n))$ $Val(X)$ $Val(X)={\frac {[V_{1}(X_{1}),\dots ,V_{n}(X_{n})]}{V_{1}(X_{1}) +\cdots +V_{n}(X_{n})}}$ $Val$
Funkce : pro jakýkoli kladný vektor vah je sada nových vektorů vah. Jedná se o vícehodnotovou funkci od nitra simplexní identity až po množinu podmnožin simplexní identity. Vektory v jsou částečně opačné - pokud jsou malé, pak oddíly v dávají agentovi velkou hodnotu a jeho váhu velkou. Pro srovnání, pokud je velký, pak oddíl v dává agentovi malou hodnotu a jeho váhy v jsou malé. To naznačuje, že pokud má pevný bod, pak tento pevný bod odpovídá oddílu PEEF, který hledáme. $Wel=Val\circ Par$ $w$ $Wel(w)$ $Wel(w)$ $w$ $w_{i}$ $Par(w)$ $i$ $Wel(w)$ $w_{i}$ $Par(w)$ $i$ $Wel(w)$ $dobře$

Abychom dokázali, že funkce má pevný bod, měli bychom použít Kakutaniho větu o pevném bodě . Existuje však technický problém, který je třeba vyřešit - funkce je definována pouze na vnitřních bodech jednoho simplexu, nikoli na celém simplexu. Naštěstí jej lze rozšířit na hranice jednotky simplex způsobem, který zajistí, že pevný bod NENÍ na hranici [3] . Rozšířená funkce je navíc funkcí od identity simplex po podmnožiny identity simplex. splňuje požadavky Kakutaniho teorému o pevném bodě, protože [4] : $dobře$ $dobře$ $dobře$ $Wel'$ $Wel'$

Je to mapování od bodu k množině jednotky simplex, což je kompaktní a konvexní podmnožina euklidovského prostoru ;
Je horní polokontinuální ;
Pro všechny je jednotka simplex neprázdná, uzavřená a konvexní; $w$ $Wel'(w)$

Proto má pevný bod — vektor v jednotce simplex, takový, že . Konstrukčně lze prokázat, že pevný bod musí být vnitřní v jednotce simplex, kde . Tudíž: $Wel'$ $W$ $W\in Wel'(W)$ $Wel'$ $W$ $Wel'\equiv Wel$

W\in Wel(W)

Podle definice , , takže existuje takový oddíl , že: $dobře$ $W\in Val(Par(W))$ $X$

$X\in Par(W)$
$W=Val(X)$

Je jasné, že se jedná o oddíl PE, protože se jedná o WUM (s váhovým vektorem W). Je to také EF, protože: $X$

z toho vyplývá, že X maximalizuje vážený součet s váhami . To znamená, že jakákoli část koláče je předána činidlu, pro které je vážená hustota hodnocení maximální. Proto pro libovolné dva agenty : $X\in Par(W)$ $W=[W_{1},\dots ,W_{n}]$ $i,j$

{\frac {V_{j}(X_{j})}{w_{j}}}\geqslant {\frac {V_{i}(X_{j})}{w_{i}}}\ implikuje {\frac {V_{j}(X_{j})}{V_{i}(X_{j))}}\geqslant {\frac {w_{j}}{w_{i}}}

z toho vyplývá, že poměr mezi hodnotami pro libovolné dva agenty je roven poměru jejich hmotností: $W=Val(X)$ $i,j$

{\frac {V_{j}(X_{j})}{V_{i}(X_{i})}}={\frac {w_{j}}{w_{i}}}

Kombinace posledních dvou nerovností dává libovolným dvěma agentům : $i,j$

{\frac {V_{j}(X_{j})}{V_{i}(X_{j})}}\geqslant {\frac {V_{j}(X_{j})}{V_ {i}(X_{i})}}\implikuje V_{i}(X_{j})\leqslant V_{i}(X_{i})

což je právě definice absence závisti.

Výpočet cenové míry

Pokud máme distribuci PEEF , lze míru ceny vypočítat následovně: $X$ $P$

Pro každý kus , který je zcela ve vlastnictví agenta , $Z_{i}$ $i$ $P(Z_{i})=V_{i}(Z_{i})/V_{i}(X_{i})$
Pro každý kus rozdělený do několika agentů se cena rovná součtu cen podmnožin patřících těmto agentům.

Lze prokázat, že pár splňuje konkurenční rovnováhu s podmínkami rovných příjmů ( ) . Konkrétně příjem každého agenta za cenové opatření je přesně 1, protože: $X,P$ $P$

P(X_{i})=V_{i}(X_{i})/V_{i}(X_{i})=1

Příklad

Jako ilustraci uvažujme dort se dvěma částmi, čokoládovou a vanilkovou, a dvěma účastníky, Alice a George, s následujícím skóre:

Účastník	Čokoláda	Vanilka
Alice	9	jeden
Jiří	6	čtyři

Vzhledem k tomu, že existují dva agenti, vektor může být reprezentován jediným číslem - poměrem váhy Alice k hmotnosti George: $w$

Pokud je poměr menší než 1:4, pak by divize WUM měla dát celý dort Alici. Poměr hodnot spokojenosti lidí bude nekonečný (nebo 1:0), takže v této oblasti se samozřejmě nenajdou žádné pevné body.
Pokud je poměr přesně 1:4, pak by se celá čokoládová část měla dát Alice a vanilková část se může libovolně rozdělit mezi Alice a George. Poměr hodnot WUM imputací se pohybuje od 1:0 do 9:4. Tato plocha neobsahuje poměr 1:4, proto se zde pevný bod nenachází.
Pokud je poměr mezi 1:4 a 9:6, pak by měla být celá vanilková porce dána Georgeovi a celá čokoládová porce by měla být dána Alici. Poměr hodnot 9:4 není v těchto mezích, takže není nalezen žádný pevný bod.
Pokud je poměr přesně 9:6, pak musí být celá vanilková porce dána Georgeovi, ale čokoládovou porci lze libovolně rozdělit mezi Alici a George. Poměr hodnot WUM dílků je mezi 9:4 a 0:1. Vidíme, že 9:6 je v těchto mezích, takže máme pevný bod . Lze jej získat tak, že dáte Georgovi celou vanilkovou část a 1/6 čokoládové části (v celkové hodnotě 5) a Alici dáte zbývajících 5/6 čokoládové části (v celkové hodnotě 7,5). Toto rozdělení je oddíl PEEF.

Zobecnění a rozšíření

Berlyant, Thomson a Danz [5] zavedli kritérium nepřítomnosti skupinové závisti , které zobecňuje jak Paretovu efektivitu , tak i svobodu od závisti. Prokázali existenci distribucí bez skupinové závisti na aditivní užitkové funkce. V nedávné době Berlyant a Danz [6] studovali některé přirozené neaditivní užitkové funkce inspirované problémy dělení půdy. Pokud užitné funkce nejsou aditivní, není existence distribuce CEEI zaručena, ale existuje za určitých omezení.

Další související výsledky lze nalézt v popisu efektivního krájení dortu a krájení dortu podle užitku .

Algoritmy

Wellerův teorém tvrdí čistě teoretickou existenci (bez náznaků principů konstrukce). Některé novější práce zkoumaly aspekty hledání rozkladu CEEI. Tyto práce obecně předpokládají, že hodnotové míry jsou po částech konstantní , tj. koláč lze rozdělit na homogenní oblasti, ve kterých je hustota odhadu každého činidla jednotná.

První algoritmus pro nalezení oddílu CEEI v tomto případě vyvinuli Reiniers a Potters [7] .

Aziz a Ye [8] vyvinuli (výpočetně) efektivnější algoritmus .

Ve skutečnosti jakýkoli řez CEEI z koláče maximalizuje produkt utilit a naopak každý řez, který maximalizuje produkt utilit, je divizí CEEI [9] . Proto lze divizi CEEI nalézt řešením problému konvexního programování maximalizace součtu logaritmů utilit.

Pro dva agenty lze postup Adjusting Winner použít k nalezení oddílu PEEF, který je také spravedlivým rozdělením (ale nemusí nutně CEEI).

Všechny výše uvedené algoritmy lze zobecnit na Lipschitzova spojitá měřítka hodnoty. Protože takové funkce mohou být aproximovány po částech konstantními funkcemi „tak blízko, jak chceme“, výše uvedené algoritmy lze aproximovat pomocí PEEF distribucí „tak blízko, jak chceme“ [7] .

Omezení

V oddílu CEEI garantovaném Wellerovým teorémem mohou být kusy předané každému účastníkovi odpojeny. Místo jednoho souvislého dílku dostane každý účastník horu „drobků“. Navíc, pokud je nutné jednotlivé kusy spojit, nemusí oddíl CEEI existovat. Zvažte následující po částech konstantní vyhodnocovací funkce:

Alice	2	2	2	2	2	2
Jiří	jeden	jeden	čtyři	čtyři	jeden	jeden

Z podmínky CE vyplývá, že všechny obvodové řezy musí mít stejnou cenu (řekněme p ) a oba středové řezy musí mít stejnou cenu (řekněme q ). Z podmínky EI vyplývá, že celkové náklady na dort se musí rovnat 2, takže . Podmínka EI opět znamená, že pro jakoukoli připojenou divizi CEEI je koláč rozdělen uprostřed. Alice i George obdrží dva obvodové řezy a jeden centrální řez. Z podmínky CE pro Alice vyplývá, že , ale ze stejné podmínky pro George vyplývá, že , máme rozpor. $q+2p=1$ $q=p$ $q=4p$

Zatímco podmínka CEEI může být s připojenými částmi nedosažitelná, slabší podmínka PEEF je vždy dosažitelná, pokud jsou dva účastníci. Je tomu tak proto, že pro dva účastníky je nepřítomnost závisti ekvivalentní proporcionalitě a proporcionalita je zachována v rámci Paretových vylepšení. Pokud je však počet partnerů tři a více, může být i slabší stav PEEF mimo dosah. Uvažujme následující po částech konstantní odhady [10] :

Alice	2	0	3	0	2	0	0
Fazole	0	0	0	0	0	7	0
Charlesi	0	2	0	2	0	0	3

Z EF vyplývá, že Bob dostane alespoň část slice za cenu 7 (z PE pak vyplývá, že dostane celou).

Konektivita má tři možnosti:

Carlův díl je napravo od Bobova dílu. Carl tak dostane plátek úplně vpravo a jeho hodnota (v jeho odhadu) je 3. Z PE pak vyplývá, že Alice dostane všech pět plátků nalevo od Bobova plátku, které podle Carla mají hodnotu 4, takže Carl na Alici žárlí.
Carlova figurka je nalevo od Bobovy figurky a on dostane dvě figurky za cenu 2. Pak je hodnota pro Alici nejvýše 2 a Alice oceňuje Carlovu figurku na 3, takže Alice na Carla žárlí.
Carlova figurka je nalevo od Bobovy figurky a on dostane maximálně jednu figurku za cenu 2. Pak distribuce nebude PE, protože Carl může zvýšit svou hodnotu přesunem k pravému okraji Boba, aniž by někoho zranil.

Žádná alokace tedy nebude PEEF.

Pokud ve výše uvedeném příkladu považujeme dort za „koláč“ (obvykle se předpokládá, že dort může být reprezentován jako segment, dort je pak znázorněn jako kruh, to znamená, že jsou identifikovány okraje), pak PEEF existuje. Stromquist [11] však uvedl jemnější příklad, kdy oddíl PEEF neexistuje ani pro koláč.

Viz také

Paretova efektivní alokace bez závisti je podobný problém pro homogenní dělitelné zboží.

Poznámky

↑ Weller, 1985 , str. 5–17.
↑ Barbanel, 2005 , str. 341–351.
↑ Barbanel, 2005 , str. 343–344.
↑ Barbanel, 2005 , str. 345-349.
↑ Berliant, Thomson, Dunz, 1992 , str. 201.
↑ Berliant, Dunz, 2004 , str. 593.
↑ 1 2 Reijnierse, Potters, 1998 , s. 291–311.
↑ Ye, Aziz, 2014 , str. 1–14.
↑ Sziklai, Segal-Halevi, 2018 , str. 1–39.
↑ ScienceDirect . www.sciencedirect.com . Získáno 2. března 2019. Archivováno z originálu 12. června 2020. (neurčitý) Příklad 5.1
↑ Stromquist, 2007 .

Literatura

Dietrich Weller. Spravedlivé rozdělení měřitelného prostoru // Journal of Mathematical Economics. - 1985. - T. 14 . - doi : 10.1016/0304-4068(85)90023-0 .
Julius B. Barbanel. Geometrie efektivního spravedlivého dělení. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . Shrnutí najdete v článku
- Barbanel J. Geometric Approach to Fair Division // The College Mathematics Journal. - 2010. - T. 41 , č. 4 . - S. 268 . doi : 10.4169 / 074683410x510263 .
Reijnierse JH, Potters JAM O hledání pareto-optimálního rozdělení bez závisti // Matematické programování. - 1998. - T. 83 , no. 1–3 . - doi : 10.1007/bf02680564 .
Chun Ye, Haris Aziz. Algoritmy krájení dortů pro po částech konstantní a po částech jednotné ocenění . — Ekonomika webu a internetu. - Springer, Cham, 2014. - Sv. 8877. - (Poznámky z informatiky). — ISBN 978-3-319-13128-3 . - doi : 10.1007/978-3-319-13129-0_1 .
Balazs R. Sziklai, Erel Segal-Halevi. Monotonie a konkurenční rovnováha v krájení dortů (anglicky) // Ekonomická teorie. - 2018. - ISSN 0938-2259 . - doi : 10.1007/s00199-018-1128-6 . - arXiv : 1510.05229 .
Berliant M., Thomson W., Dunz K. O spravedlivém rozdělení heterogenní komodity // Journal of Mathematical Economics. - 1992. - T. 21 , no. 3 . - doi : 10.1016/0304-4068(92)90001-n .
Marcus Berliant, Karl Dunz. Základ teorie umístění: Existence rovnováhy, teorémy blahobytu a jádro // Journal of Mathematical Economics. - 2004. - T. 40 . - doi : 10.1016/s0304-4068(03)00077-6 .
Walter Stromquist. Koláč, který nelze spravedlivě nakrájet // Sborník semináře Dagstuhl. — 2007.