Wellers sætning

Wellers sætning [1] er en sætning om økonomi . Hun argumenterer for, at en heterogen ressource (" kage ") kan opdeles blandt n deltagere med forskellige signifikansestimater på en sådan måde, at opdelingen bliver både Pareto- effektiv ( Eng. Pareto-efficient , PE) og misundelsesfri ( eng. misundelsesfri , EF). Det er således muligt at dele en kage (en heterogen ressource) uden at krænke den økonomiske effektivitet .

Desuden siger Wellers sætning, at der er en bestemt pris , hvortil distribution og pris er i konkurrencemæssig ligevægt ( engelsk konkurrenceligevægt , CE) med lige indkomst ( engelsk equal incomes , EI). Således forbinder denne teorem to undersøgelsesområder, der tidligere ikke var relaterede - dette er en rimelig skæring af kagen og generel ligevægt .

Baggrund

Fair udskæring af kagen er blevet undersøgt siden 1940'erne. Der er en heterogen delbar ressource, såsom en kage eller et stykke jord. Der er n deltagere, som hver har en personlig værditæthedsfunktion af kagestykkerne. Skiveværdien for deltageren er tæthedsintegralet af værdien over kageskiven (hvilket betyder, at deltagerens score er et atomløst mål på kagen). Det misundelsesfrie kageskæringsproblem består i at opdele kagen i n ikke-skærende stykker, et stykke pr. deltager, således at værdien af det stykke, han modtager, for hver deltager ikke er mindre end værdien af alle andre stykker ( så intet medlem er jaloux på det andet medlems andel).

En konsekvens af Dubins-Spanier konveksitetsteoremet (1961) er, at der altid er en "konsistent partition" - en opdeling af kagen i n stykker, således at værdien for ethvert medlem af et stykke er nøjagtig . Den aftalte partition er selvfølgelig EF, men det er ikke PE. Desuden er en anden konsekvens af ovenstående teorem , at når mindst to deltagere har forskellige værdimål, er der en division, der giver hver deltager strengt taget mere end . Dette betyder, at den konsistente partition ikke engang er svagere end PE. $1/n$ $1/n$

Fraværet af misundelse , som et kriterium for retfærdig fordeling, blev foreslået i økonomi i 1960'erne og studeret intensivt i løbet af 1970'erne. Varians teorem studerer fraværet af misundelse i forbindelse med deling af homogene varer . Under små restriktioner for agenters nyttefunktioner er der distributioner, der er både PE og EF. Beviset er resultatet af eksistensen af en konkurrencemæssig ligevægt af lige indkomster ( konkurrenceligevægt fra lige indkomster , CEEI) . David Gale beviste en lignende eksistens for agenter med lineær nytte .

Problemet med at skære kagen er sværere end distributionen af homogene varer. Dels har kagen en lang række fordele – hvert punkt på kagen har en forskellig værdi. Dette er emnet for Wellers sætning.

Betegnelse

Kagen er betegnet med bogstavet . Antallet af deltagere i divisionen vil være angivet med bogstavet . $C$ $n$

En kagepartition , betegnet med , er en n -tupel af delmængder af kagen . Her er et stykke kage som gives til deltageren . $x$ $X_{1},\dots ,X_{n}$ $C$ $X_{i}$ $jeg$

En partition kaldes PEEF, hvis den opfylder følgende to betingelser:

Pareto-effektiv : ingen anden opdeling er værre for alle deltagere og strengt taget bedre for en af dem.
Mangel på misundelse: intet medlem ønsker at modtage et stykke givet til et andet medlem.

En skillevæg og et prismål kaldes CEEI, hvis de opfylder følgende to betingelser: $x$ $P$ $C$

Konkurrenceligevægt : For enhver agent i enhver chunk med et positivt estimatog enhver chunk med et positivt estimat:. ${\displaystyle Z_{i}\subseteq X_{i))$ $Z\subseteq C$ $v_{i}(Z_{i})/P(Z_{i})\geqslant v_{i}(Z)/P(Z)$
Lige indkomster: For enhver agent i: . $P(X_{i})=1$

CEEI er meget strengere end PEEF: enhver CEEI distribution er PEEF, men der er mange ikke-CEEI PEEF distributioner.

Wellers teorem beviser eksistensen af en CEEI-fordeling, hvilket indebærer eksistensen af en PEEF-fordeling.

Skitse af beviset

Præsentationen nedenfor er baseret på Wellers artikel og dels på Barbanels artikel [2] .

Wellers bevis er afhængig af vægtet - utilitaristisk-maksimal ( WUM) kageskæring . WUM er en divisionsmaksimerende funktion af følgende form:

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

hvor er agentens indeks, er agentens måleværdi, er det stykke kage, der sendes til agenten, og er en positiv vægt. $jeg$ $V_i$ $X_{i}$ $w_{i}$

En følge af Dubins-Spaniers kompakthedsteoremet siger , at der for enhver vægtvektor eksisterer WUM-fordelinger. Intuitivt bør hvert stykke kage gives til den person, for hvem den største. Hvis der er to eller flere personer, for hvem denne værdi er den samme, så fører enhver vilkårlig opdeling af en brik mellem dem til en WUM-deling ( WUM -fordelinger . Hver vægtvektorRadon-Nikodim-sættetkan også defineres ved hjælp af definerer en partition af denne simplex Denne partition genererer en fordeling af Radon-Nikodim sættet til kagen, som genererer en eller flere distributioner af kagen) . $w$ $Z$ $jeg$ ${V_{i}(Z) \over w_{i}}$ $w$ $(n-1)$

Enhver WUM-division er åbenbart PE. WUM-opdelingen kan dog være meget uretfærdig. For eksempel, hvis den er meget stor, så kan midlet kun give en lille del af kagen (vægtvektoren er meget tæt på midlets toppunkt af simplexenheden, hvilket betyder, at den kun vil modtage point af Radon-Nikodim sæt , der er meget tæt på dets toppunkt) . Til sammenligning, hvis den er meget lille, så kan agenten få hele kagen. $w_{i}$ $jeg$ $w$ $jeg$ $jeg$ $w_{i}$ $jeg$

Weller beviste, at der er en vektor af vægte, for hvilken WUM-divisionen også er EF. Han gjorde det ved at definere flere funktioner:

Funktion : for enhver vektor af positive vægte , er sættet af WUM-partitioner med vægte . Funktionen er en funktion med flere værdier fra det indre af enhedens simplex til den indstillede plads PE af udskæringer af kagen. $Par$ $w=[w_{1},\dots ,w_{n}]$ $Par(w)$ $w$ $Par$
Funktionen : for enhver partition er en vektor proportional med deltagernes værdier: . Funktionen kortlægger rummet af kageudskæringer til unit simplex. $Val$ ${\displaystyle X=X_{1},\dots ,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$
Funktion : for enhver positiv vægtvektor er sættet af nye vægtvektorer. Dette er en funktion med flere værdier fra det indre af identitetssimplexet til sættet af delmængder af identitetssimplexet. Vektorer i er til dels modsatte - hvis små, så giver partitioner i agenten en stor værdi og dens vægt i stor. Til sammenligning, hvis den er stor, så giver partitionen i midlet en lille værdi, og dens vægt er lille. Dette tyder på, at hvis det har et fast punkt, så svarer dette fikspunkt til den PEEF-partition, vi leder efter. $Wel=Val\circ Par$ $w$ $Wel(w)$ $Wel(w)$ $w$ $w_{i}$ $Par(w)$ $jeg$ $Wel(w)$ $w_{i}$ $Par(w)$ $jeg$ $Wel(w)$ $Wel$

For at bevise, at en funktion har et fikspunkt, skal vi bruge Kakutanis fikspunktssætning . Der er dog et teknisk problem, der skal løses - funktionen er kun defineret på de indre punkter i en enkelt simplex, og ikke på hele simplexen. Heldigvis kan det udvides til grænserne af enhedssimplexet på en måde, der sikrer, at det fikserede punkt IKKE er på grænsen [3] . En udvidet funktion er desuden en funktion fra identitetssimplekset til delmængder af identitetssimplexet. opfylder kravene i Kakutanis fikspunktssætning, fordi [4] : $Wel$ $Wel$ $Wel$ $Wel'$ $Wel'$

Det er en punkt-til-sæt-kortlægning af enheden simplex, som er en kompakt og konveks delmængde af det euklidiske rum ;
Den er øvre halvkontinuerlig ;
For enhver , er enheden simplex ikke-tom, lukket og konveks; $w$ $Wel'(w)$

Derfor har den et fast punkt - en vektor i enheden simplex, sådan at . Ved konstruktion kan det vises, at fikspunktet skal være indvendigt i enheden simpleks, hvor . Følgelig: $Wel'$ $W$ $W\in Wel'(W)$ $Wel'$ $W$ $Wel'\equiv Wel$

W\in Wel(W)

Per definition , , så der er en partition sådan, at: $Wel$ $W\in Val(Par(W))$ $x$

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

Det er klart, at det er en PE-partition, da det er WUM (med vægtvektor W). Det er også EF fordi: $x$

det følger, at X maksimerer den vægtede sum med vægte . Dette betyder, at enhver del af kagen sendes til midlet, for hvilket den vægtede vurderingstæthed er maksimal. Derfor, for alle to agenter : $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}}}\ indebærer {\frac {V_{j}(X_{j})}{V_{i}(X_{j))}}\geqslant {\frac {w_{j}}{w_{i}}}

det følger, at forholdet mellem værdierne for alle to midler er lig med forholdet mellem deres vægte: $W=Val(X)$ $i,j$

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

Kombinationen af de sidste to uligheder giver for alle to agenter : $i,j$

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

som netop er definitionen på fraværet af misundelse.

Beregning af prismålet

Hvis vi har en PEEF-fordeling , kan prismålet beregnes som følger: $x$ $P$

For ethvert stykke , der er fuldt ejet af agenten , $Z_{i}$ $jeg$ $P(Z_{i})=V_{i}(Z_{i})/V_{i}(X_{i})$
For ethvert stykke opdelt i flere agenter er prisen lig med summen af priserne på delmængder, der tilhører disse agenter.

Det kan bevises, at parret opfylder konkurrenceligevægten med ( CEEI ) . Især er indkomsten for hver agent for prismålet nøjagtig 1, fordi: $X,P$ $P$

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

Eksempel

Som en illustration kan du overveje en kage med to dele, chokolade og vanilje, og to deltagere, Alice og George, med følgende score:

Deltager	Chokolade	Vanilje
Alice	9	en
George	6	fire

Da der er to midler, kan vektoren repræsenteres af et enkelt tal - forholdet mellem Alices vægt og Georges vægt: $w$

Hvis forholdet er mindre end 1:4, så skal WUM-divisionen give hele kagen til Alice. Forholdet mellem menneskers tilfredshedsværdier vil være uendeligt (eller 1:0), så der vil naturligvis ikke blive fundet nogen faste punkter i dette område.
Hvis forholdet er præcis 1:4, så skal hele chokoladedelen gives til Alice, og vaniljedelen kan deles vilkårligt mellem Alice og George. Forholdet mellem imputationernes WUM-værdier varierer fra 1:0 til 9:4. Dette område indeholder ikke et forhold på 1:4, derfor er fikspunktet ikke placeret her.
Hvis forholdet er mellem 1:4 og 9:6, så skal hele vaniljeportionen gives til George og hele chokoladeportionen skal gives til Alice. Værdiforholdet 9:4 ligger ikke inden for disse grænser, så der findes ikke noget fikspunkt.
Hvis forholdet er præcis 9:6, så skal hele vaniljeportionen gives til George, men chokoladeportionen kan deles vilkårligt mellem Alice og George. Forholdet mellem divisionernes WUM-værdier er mellem 9:4 og 0:1. Vi ser, at 9:6 er inden for disse grænser, så vi har et fast punkt . Det kan fås ved at give George hele vaniljedelen og 1/6 af chokoladedelen (til en samlet værdi af 5) og give Alice de resterende 5/6 af chokoladedelen (til en samlet værdi af 7,5). Denne division er en PEEF-partition.

Generaliseringer og udvidelser

Berlyant, Thomson og Danz [5] introducerede et kriterium for fravær af gruppemisundelse , som generaliserer både Pareto-effektivitet og frihed fra misundelse. De beviste eksistensen af distributioner uden gruppemisundelse for additive nyttefunktioner. For nylig har Berlyant og Danz [6] undersøgt nogle naturlige ikke-additive nyttefunktioner inspireret af jorddelingsproblemer. Når hjælpefunktionerne ikke er additive, er eksistensen af CEEI-distributionen ikke garanteret, men den eksisterer under visse begrænsninger.

Yderligere relaterede resultater kan findes i beskrivelsen af effektiv kageskæring og kageskæring efter brug .

Algoritmer

Wellers sætning hævder en rent teoretisk eksistens (uden antydninger til konstruktionsprincipperne). Nogle nyere arbejde har udforsket aspekter af at finde CEEI-nedbrydningen. Disse værker antager generelt, at værdimålene er stykkevis konstante , dvs. kagen kan opdeles i homogene områder, hvor estimeringsdensiteten af hvert middel er ensartet.

Den første algoritme til at finde CEEI-partitionen i dette tilfælde blev udviklet af Reiniers og Potters [7] .

En mere (beregningsmæssigt) effektiv algoritme blev udviklet af Aziz og Ye [8] .

Faktisk maksimerer ethvert CEEI-udskæring af kagen produktet af forsyningsvirksomheder, og omvendt, ethvert snit, der maksimerer produktet af forsyningsvirksomheder, er en CEEI-afdeling [9] . Derfor kan CEEI-divisionen findes ved at løse det konvekse programmeringsproblem med at maksimere summen af logaritmer af hjælpeprogrammer.

For to agenter kan Adjusting Winner - proceduren bruges til at finde en PEEF-partition, der også er en retfærdig opdeling (men ikke nødvendigvis en CEEI).

Alle ovenstående algoritmer kan generaliseres til Lipschitz kontinuerlige værdimål . Da sådanne funktioner kan tilnærmes ved stykkevis konstante funktioner "så tæt som vi vil", kan ovenstående algoritmer tilnærmes ved PEEF-fordelinger "så tæt som vi vil" [7] .

Begrænsninger

I CEEI-partitionen, der er garanteret af Wellers sætning, kan brikkerne, der sendes til hver deltager, afbrydes. I stedet for et sammenhængende stykke modtager hver deltager et bjerg af "krummer". Desuden, hvis stykkerne skal forbindes, eksisterer CEEI-partitionen muligvis ikke. Overvej følgende stykkevis konstante evalueringsfunktioner:

Alice	2	2	2	2	2	2
George	en	en	fire	fire	en	en

Det følger af CE-betingelsen, at alle perifere skiver skal have samme pris (f.eks. p ) og begge centrale skiver skal have samme pris (f.eks . q ). Det følger af EI-betingelsen, at den samlede pris for kagen skal være lig med 2, så . Betingelse EI indebærer igen, at for enhver tilsluttet CEEI-afdeling deles kagen på midten. Både Alice og George modtager to perifere skiver og en central skive. Af CE-betingelsen for Alice følger det, at , men af samme betingelse for George følger det , at vi har en modsigelse. $q+2p=1$ $q=p$ $q=4p$

Mens CEEI-tilstanden kan være uopnåelig med tilsluttede dele, er den svagere PEEF-tilstand altid opnåelig, hvis der er to deltagere. Dette skyldes, at fraværet af misundelse for to deltagere svarer til proportionalitet, og proportionalitet er bevaret under Pareto-forbedringer. Men når antallet af partnere er tre eller flere, kan selv den svagere PEEF-tilstand være uden for rækkevidde. Overvej følgende stykkevise konstante estimater [10] :

Alice	2	0	3	0	2	0	0
Bønne	0	0	0	0	0	7	0
Charles	0	2	0	2	0	0	3

Fra EF følger det, at Bob får mindst en del af skiven til en pris af 7 (fra PE følger det, at han får det hele).

Forbindelse har tre muligheder:

Carls stykke er til højre for Bobs stykke. Dermed får Carl den skive længst til højre og dens værdi (i hans estimat) er 3. Af PE følger så, at Alice får alle fem skiver til venstre for Bobs skive, som Carl vurderer er 4 værd, så Carl er jaloux på Alice.
Carls brik er til venstre for Bobs brik, og han får to brikker til en pris af 2. Så er værdien for Alice højst 2, og Alice vurderer Carls brik til 3, så nu er Alice jaloux på Carl.
Carls brik er til venstre for Bobs brik, og han får højst én brik til en pris af 2. Så bliver fordelingen ikke PE, da Carl kan øge sin værdi ved at flytte til højre kant af Bob uden at skade nogen.

Derfor vil ingen tildeling være PEEF.

I eksemplet ovenfor, hvis vi betragter kagen som en "tærte" (normalt antages det, at kagen kan repræsenteres som et segment, så er kagen repræsenteret som en cirkel, det vil sige, kanterne identificeres), så PEEF eksisterer. Men Stromquist [11] gav et mere subtilt eksempel, hvor en PEEF-partition ikke eksisterer selv for en tærte.

Se også

Pareto-effektiv allokering uden misundelse er et lignende problem for et homogent delbart gode.

Noter

↑ Weller, 1985 , s. 5-17.
↑ Barbanel, 2005 , s. 341-351.
↑ Barbanel, 2005 , s. 343-344.
↑ Barbanel, 2005 , s. 345-349.
↑ Berliant, Thomson, Dunz, 1992 , s. 201.
↑ Berliant, Dunz, 2004 , s. 593.
↑ 1 2 Reijnierse, Potters, 1998 , s. 291-311.
↑ Ye, Aziz, 2014 , s. 1-14.
↑ Sziklai, Segal-Halevi, 2018 , s. 1-39.
↑ ScienceDirect . www.sciencedirect.com . Hentet 2. marts 2019. Arkiveret fra originalen 12. juni 2020. (ubestemt) Eksempel 5.1
↑ Stromquist, 2007 .

Litteratur

Dietrich Weller. Fair opdeling af et målbart rum // Journal of Mathematical Economics. - 1985. - T. 14 . - doi : 10.1016/0304-4068(85)90023-0 .
Julius B. Barbanel. Geometrien af effektiv retfærdig opdeling. - Cambridge: Cambridge University Press, 2005. - ISBN 0-521-84248-4 . - doi : 10.1017/CBO9780511546679 . Et resumé kan findes i artiklen
- Barbanel J. A Geometric Approach to Fair Division // The College Mathematics Journal. - 2010. - T. 41 , no. 4 . - S. 268 . doi : 10.4169 / 074683410x510263 .
Reijnierse JH, Potters JAM Om at finde en misundelsesfri Pareto-optimal division // Matematisk programmering. - 1998. - T. 83 , no. 1-3 . - doi : 10.1007/bf02680564 .
Chun Ye, Haris Aziz. Kageskæringsalgoritmer til stykkevis konstante og stykkevise ensartede værdiansættelser . — Web- og internetøkonomi. - Springer, Cham, 2014. - Vol. 8877. - (Forelæsningsnotater i datalogi). — ISBN 978-3-319-13128-3 . - doi : 10.1007/978-3-319-13129-0_1 .
Balazs R. Sziklai, Erel Segal-Halevi. Monotonicitet og konkurrencemæssig ligevægt i kageskæring (engelsk) // Økonomisk teori. - 2018. - ISSN 0938-2259 . - doi : 10.1007/s00199-018-1128-6 . - arXiv : 1510.05229 .
Berliant M., Thomson W., Dunz K. Om den retfærdige opdeling af en heterogen vare // Journal of Mathematical Economics. - 1992. - T. 21 , no. 3 . - doi : 10.1016/0304-4068(92)90001-n .
Marcus Berliant, Karl Dunz. Et grundlag for lokationsteori: Eksistensen af ligevægt, velfærdsteoremer og kerne // Journal of Mathematical Economics. - 2004. - T. 40 . - doi : 10.1016/s0304-4068(03)00077-6 .
Walter Stromquist. En tærte, der ikke kan skæres retfærdigt // Dagstuhl Seminar Proceedings. – 2007.