Wellersova věta - Wellers theorem - Wikipedia

Wellerova věta[1] je věta v ekonomika. Říká se, že mezi ně lze rozdělit heterogenní zdroj („dort“) n partnery s různými oceněními způsobem, který je obojí Pareto-efektivní (PE) a bez závisti (EF). Je tedy možné rozdělit koláč spravedlivě, aniž by byla ohrožena ekonomická účinnost.

Wellerova věta navíc říká, že existuje cena taková, že alokace a cena jsou a konkurenční rovnováha (CE) se stejnými příjmy (EI). Spojuje tedy dvě oblasti výzkumu, které dříve nesouvisely: spravedlivé krájení dortu a obecná rovnováha.

Pozadí

Spravedlivé krájení dortu byl studován od 40. let 20. století. Existuje heterogenní dělitelný zdroj, například dort nebo pozemek. Existují n partneři, z nichž každý má v rámci dortu funkci osobní hodnoty a hustoty. Hodnota dílu pro partnera je integrálem jeho hodnotové hustoty nad tímto dílem (to znamená, že hodnota je a natomatická míra přes dort). The řezání dortů bez závisti problém je rozdělit dort na n disjunktní kousky, jeden kousek na agenta, například u každého agenta je hodnota jeho kousku slabě větší než hodnoty všech ostatních kousků (takže žádný agent nezávidí podíl jiného agenta).

Důsledkem Dubins – Spanierova věta o konvexitě (1961) je, že vždy existuje „konsenzuální rozdělení“ - rozdělení dortu na n kousky tak, že každý agent hodnotí každý kousek přesně . Konsenzuální oddíl je samozřejmě EF, ale není to PE. Navíc další důsledek Dubins – Spanierova věta o konvexitě je to, že když alespoň dva agenti mají různé hodnotové míry, existuje rozdělení, které dává každému agentovi přísně více než . To znamená, že konsenzuální rozdělení není ani slabě PE.

Závistivost jako kritérium spravedlivého rozdělení byla zavedena do ekonomiky v 60. letech a intenzivně studována v 70. letech. Varianovy věty studujte to v kontextu dělení homogenní zboží. Pod mírnými omezeními na obslužné funkce agentů existují přidělení, která jsou jak PE, tak EF. Důkaz používá předchozí výsledek o existenci a konkurenční rovnováha ze stejných příjmů (CEEI). David Gale prokázal podobný výsledek existence u agentů s lineární nástroje.

Řezání dortu je náročnější než homogenní dobrá alokace, protože dort je heterogenní. V jistém smyslu je dort kontinuem zboží: každý bod v dortu je jiné zboží. Toto je téma Wellerovy věty.

Zápis

Dort je označen . Počet partnerů je označen .

A dortový oddíl, označeno , je n-tuple podskupin ; je kousek daný partnerovi .

Volá se oddíl PEEF pokud splňuje následující dvě podmínky:

  • Paretova účinnost: žádné jiné rozdělení není slabě lepší pro všechny partnery a přísně lepší pro alespoň jednoho partnera.
  • Závistivost: žádný partner striktně nepreferuje kus přidělený jinému agentovi.

Oddíl a cenovou měrou na jsou nazývány CEEI pokud splňují následující dvě podmínky:

  • Konkurenční rovnováha: Pro každého agenta i, každý pozitivní řez a každý pozitivní plátek : .
  • Stejné příjmy: Pro každého agenta i: .

CEEI je mnohem silnější než PEEF: každá alokace CEEI je PEEF, ale existuje mnoho alokací PEEF, které nejsou CEEI.

Wellerova věta dokazuje existenci alokace CEEI, což implikuje existenci alokace PEEF.

Důkazní skica

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

Wellerův důkaz se spoléhá na vážený-utilitární-maximální (WUM) dělení dortů. Divize WUM je divize maximalizující funkci následující formy:

kde je index agenta, je agent měřítko hodnoty, je kousek daný , a je pozitivní váha.

Důsledkem Dubins – Spanierova věta o kompaktnosti je to pro každý váhový vektor , Existují přidělení WUM. Intuitivně každý malý kousek dortu by měla být dané osobě podána pro koho je největší. Pokud existují dva nebo více lidí, pro které je tato hodnota stejná, pak každé svévolné rozdělení tohoto kusu mezi nimi vede k rozdělení WUM (Přidělení WUM lze také definovat pomocí Sada Radon – Nikodym. Každý váhový vektor , jako bod na -dimenzionální jednotka simplex, definuje oddíl tohoto simplexu. Tento oddíl indukuje přidělení sady Radon-Nikodym dortu, což indukuje jedno nebo více přidělení dortu).

Každá divize WUM je zjevně PE. Divize WUM však může být velmi nespravedlivá; například pokud je velmi velký, pak agent může získat jen malý zlomek dortu (váhový vektor je velmi blízký agentovi Vrchol unit-simplex, což znamená, že získá pouze body sady Radon-Nikodym, které jsou velmi blízko jejího vrcholu). Naproti tomu, pokud je velmi malý, pak agent může dostat celý dort.

Weller dokazuje, že existuje vektor vah, pro které je divize WUM také EF. To se provádí definováním několika funkcí:

1. Funkce : pro každý pozitivní vektor hmotnosti , je sada oddílů WUM s váhami . Funkce je funkce se stanovenou hodnotou z unit-simplex-interieru do prostoru sad PE koláčových příček.

2. Funkce : pro každý oddíl , je vektor úměrný hodnotám partnerů: . Funkce mapuje prostor dortových oddílů do unit-simplex.

3. Funkce : pro každý pozitivní váhový vektor , je sada nových váhových vektorů. Tohle je funkce se stanovenou hodnotou z vnitřku unit-simplex do sady podmnožin unit-simplex. Vektory v jsou v jistém smyslu opakem : pokud je malý, pak oddíly v dát agentovi velká hodnota a její váha v je velký. Naproti tomu, pokud je velký než oddíly v dát agentovi malá hodnota a její váha v je velký. To naznačuje, že pokud má pevný bod, pak tento pevný bod odpovídá oddílu PEEF, který hledáme.

Dokázat, že funkce má pevný bod, chtěli bychom použít Kakutaniho věta o pevném bodě. Je však třeba vyřešit technický problém: funkci je definován pouze na vnitřku unit-simplex, zatímco jeho rozsah je celý unit-simplex. Naštěstí je to možné prodloužit na hranici unit-simplex, a to způsobem, který zaručí, že jakýkoli pevný bod NENÍ na hranici.[2]:343–344 Rozšířená funkce, , je skutečně funkcí od unit-simplexu k podmnožinám unit-simplexu. splňuje požadavky Kakutaniho věty o pevném bodě, protože:[2]:345–349

  • Jedná se o mapování point-to-set unit-simplex, což je kompaktní a konvexní podmnožina euklidovského prostoru;
  • to je horní polokontinuální;
  • Pro každého v jednotce simplex, je neprázdná a uzavřená a konvexní;

Proto, má pevný bod - vektor v unit-simplex tak, že . Stavbou , je možné ukázat, že pevný bod musí být v interiéru jednotky simplex, kde . Proto:

Podle definice , , takže existuje oddíl takové, že:

je jasně PE, protože je to WUM (s váhovým vektorem W). Je to také EF, protože:

  • znamená, že X maximalizuje vážený součet s váhami . To znamená, že každá frakce koláče je dána agentu, pro kterého je vážená hodnota-hustota maximální. Proto pro každé dva agenty :
.
  • znamená, že poměr mezi hodnotami každých dvou agentů se rovná poměru jejich hmotností:
.

Kombinace posledních dvou nerovností dává pro každé dva agenty :

což je přesně definice závisti-volnosti.

Výpočet cenové míry

Jakmile máme přiděleno PEEF , cenové měřítko lze vypočítat takto:

  • Za každý kus to je zcela v držení agenta ,
  • U každého kusu rozděleného mezi několik agentů je cena součtem cen jeho podmnožin držených těmito agenty.

Je možné dokázat, že dvojice splňovat podmínky konkurenční rovnováha se stejnými příjmy (CEEI). Konkrétně příjem každého agenta v rámci cenové míry , je přesně 1, protože:

Příklad

Jako příklad zvažte dort se dvěma částmi: čokoládou a vanilkou a dvěma partnery: Alice a George, s následujícími hodnotami:

PartnerČokoládaVanilka
Alice91
Jiří64

Protože existují dva agenti, vektor lze představovat jediným číslem - poměr hmotnosti Alice k hmotnosti George:

  • Pokud je poměr menší než 1: 4, měla by divize WUM dát celý dort Alici. Poměr hodnot, které si lidé užívají, bude nekonečný (nebo 1: 0), takže v tomto rozsahu samozřejmě nebude nalezen žádný pevný bod.
  • Pokud je poměr přesně 1: 4, měla by se celá čokoláda dát Alici, ale vanilku lze libovolně rozdělit mezi Alici a Georgovi. Poměr hodnot divizí WUM se pohybuje mezi 1: 0 a 9: 4. Tento rozsah neobsahuje poměr 1: 4, proto zde není pevný bod.
  • Pokud je poměr mezi 1: 4 a 9: 6, měla by se celá vanilka dát Georgeovi a celá čokoláda Alici. Poměr hodnot je 9: 4, což není v rozsahu, takže pevný bod ještě nebyl nalezen.
  • Pokud je poměr přesně 9: 6, měla by se celá vanilka dát Georgovi, ale čokoládu lze libovolně rozdělit mezi Alici a Georgovi. Poměr hodnot divizí WUM se pohybuje mezi 9: 4 a 0: 1. Vidíme, že 9: 6 je v rozsahu, takže máme pevný bod. Toho lze dosáhnout tak, že George dáte celou vanilku a 1/6 čokolády (v celkové hodnotě 5) a Alice dáte zbývajících 5/6 čokolády (v celkové hodnotě 7,5). Tato divize je PEEF.

Zobecnění a rozšíření

Berliant, Thomson a Dunz[3] představil kritérium skupinová závistivost, což zobecňuje Paretovu účinnost i závistivost. Dokázali existenci alokací bez závisti skupiny pomocí aditivních nástrojů. Později Berliant a Dunz[4] studoval některé přirozené neaditivní užitkové funkce motivované problémem dělení půdy. Pokud nástroje nejsou aditivní, není již zaručeno, že bude přidělena CEEI, ale existuje za určitých omezení.

Další související výsledky naleznete v Efektivní krájení dortu a Utilitární krájení dortu.

Algoritmy

Wellerova věta je čistě existenciální. Některé pozdější práce studovaly algoritmické aspekty hledání oddílu CEEI. Tyto práce obvykle předpokládají, že hodnotové míry jsou po částech konstantníkoláč, tj. koláč lze rozdělit na homogenní oblasti, ve kterých je hustota hodnot každého činidla stejnoměrná.

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

Výpočtově efektivnější algoritmus vyvinuli Aziz a Ye.[6]

Ve skutečnosti každý koláčový oddíl CEEI maximalizuje produkt obslužných programů a naopak - každý oddíl, který maximalizuje produkt obslužných programů, je CEEI.[7] CEEI lze tedy najít řešením a konvexní program maximalizovat součet logaritmů nástrojů.

U dvou agentů upravený postup výherce lze použít k vyhledání alokace PEEF, která je také spravedlivý (ale ne nutně CEEI).

Všechny výše uvedené algoritmy lze zobecnit na hodnotové míry, které jsou Lipschitz kontinuální. Protože tyto funkce lze aproximovat jako funkce konstantní po částech „tak blízko, jak se nám líbí“, výše uvedené algoritmy mohou také aproximovat alokaci PEEF „tak blízko, jak se nám líbí“.[5]

Omezení

V oddílu CEEI zaručeném Wellerem může být část přidělená každému partnerovi odpojena. Namísto jediného souvislého kusu může každý partner dostat hromadu „drobků“. Ve skutečnosti, když musí být kusy připojeny, nemusí oddíly CEEI existovat. Zvažte následující po částech konstantní ocenění:

Alice222222
Jiří114411

Podmínka CE znamená, že všechny periferní řezy musí mít stejnou cenu (řekněme, p) a oba střední řezy musí mít stejnou cenu (řekněme q). Podmínka EI znamená, že celková cena dortu by měla být 2, takže . Podmínka EI opět znamená, že v jakékoli připojené divizi CEEI je koláč krájen uprostřed. Alice i George dostávají dva periferní řezy a jeden centrální plátek. Podmínka CE pro Alici to naznačuje ale podmínka CE na George to naznačuje , což je rozpor.

Zatímco podmínka CEEI může být nedosažitelná u připojených kusů, slabší podmínka PEEF je vždy dosažitelná, pokud existují dva partneři. Důvodem je, že u dvou partnerů je závist-čistota ekvivalentní proporcionalitě a proporcionalita je zachována v rámci Paretových vylepšení. Pokud však existují tři nebo více partnerů, může být i slabší stav PEEF nedosažitelný. Zvažte následující po částech konstantní ocenění:[8]:Příklad 5.1

Alice2030200
Bob0000070
Carle0202003

EF znamená, že Bob obdrží alespoň část svého 7hodnotového řezu (PE pak znamená, že obdrží celý).

Podle připojení existují tři možnosti:

  • Carlův kousek je napravo od Bobova kousku. Carl tedy dostane plátek úplně vpravo a jeho hodnota jeho 3. PE pak znamená, že Alice dostane všech pět plátků nalevo od Bobova kousku, které Carlovi stojí 4. Carl tedy Alice závidí.
  • Carlův kousek je nalevo od Bobova kousku a dostane své dva kousky v hodnotě 2. Pak má Alice hodnotu maximálně 2 a Carlův kousek má pro Alici hodnotu 3. Alice tedy Carlovi závidí.
  • Carlův kousek je nalevo od Bobova kousku a dostane maximálně jeden kousek se dvěma hodnotami. Přidělení pak není PE, protože Carl může zvýšit svoji hodnotu na 3 přesunutím napravo od Boba, aniž by někomu ublížil.

Žádná alokace tedy není PEEF.

Ve výše uvedeném příkladu, pokud koláč považujeme za „koláč“ (tj. Pokud je kousku dovoleno obejít hranici dortu k druhé hranici), pak existuje alokace PEEF; nicméně, Stromquist [9] ukázal složitější příklad, kdy alokace PEEF neexistuje ani v koláčku.

Viz také

Reference

  1. ^ Weller, Dietrich (1985). "Spravedlivé rozdělení měřitelného prostoru". Journal of Mathematical Economics. 14: 5–17. doi:10.1016/0304-4068(85)90023-0.
  2. ^ A b C Barbanel, Julius B .; s úvodem Alana D. Taylora (2005). Geometrie efektivního spravedlivého rozdělení. Cambridge: Cambridge University Press. doi:10.1017 / CBO9780511546679. ISBN  0-521-84248-4. PAN  2132232. Krátké shrnutí je k dispozici na: Barbanel, J. (2010). „Geometrický přístup ke spravedlivému rozdělení“. The College Mathematics Journal. 41 (4): 268. doi:10.4169 / 074683410x510263.
  3. ^ Berliant, M .; Thomson, W .; Dunz, K. (1992). „O spravedlivém rozdělení heterogenní komodity“. Journal of Mathematical Economics. 21 (3): 201. doi:10.1016 / 0304-4068 (92) 90001-n.
  4. ^ Berliant, Marcus; Dunz, Karl (2004). "Základ teorie polohy: Existence rovnováhy, věty o dobrých životních podmínkách a jádro". Journal of Mathematical Economics. 40 (5): 593. doi:10.1016 / s0304-4068 (03) 00077-6.
  5. ^ A b Reijnierse, J. H .; Potters, J. A. M. (1998). „Při hledání Pareto-optimálního rozdělení bez závisti.“ Matematické programování. 83 (1–3): 291–311. doi:10.1007 / bf02680564.
  6. ^ Ye, Chun; Aziz, Haris (2014-12-14). Algoritmy pro krájení dortu pro dílčí konstantní a po částech jednotná ocenění. Ekonomika webu a internetu. Přednášky z informatiky. 8877. Springer, Cham. s. 1–14. CiteSeerX  10.1.1.743.9056. doi:10.1007/978-3-319-13129-0_1. ISBN  978-3-319-13128-3.
  7. ^ Sziklai, Balázs R .; Segal-Halevi, Erel (2018-05-26). „Monotónnost a konkurenční rovnováha při krájení dortů“. Ekonomická teorie. 68 (2): 363–401. arXiv:1510.05229. doi:10.1007 / s00199-018-1128-6. ISSN  0938-2259.
  8. ^ Segal-Halevi, Erel; Sziklai, Balázs R. (01.09.2018). "Zdrojová monotónnost a populační monotónnost při spojeném krájení koláčů". Matematické sociální vědy. 95: 19–30. arXiv:1703.08928. doi:10.1016 / j.mathsocsci.2018.07.001. ISSN  0165-4896.
  9. ^ Stromquist, Walter (2007). „Koláč, který nelze spravedlivě krájet“ (PDF). Sborník seminářů Dagstuhl.