Udskæring af kagen efter brug

At skære kagen efter nytte (eller skære kagen med maxsum ) er reglen om at dele heterogene ressourcer , såsom en kage eller fast ejendom , mellem flere deltagere med forskellige kvantitative nyttefunktioner , således at summen af nytte for deltagerne bliver så stor som muligt. Sådan skæring var inspireret af utilitarismens filosofi . At skære kagen efter brug er ofte "uretfærdigt". Derfor er utilitarisme i konflikt med bare at skære kagen .

Eksempel

Lad os forestille os en kage bestående af to dele - chokolade og vanilje. Lad der være to deltagere - Alice og George med følgende skøn

Deltager	Chokolade	Vanilje
Alice	9	en
George	6	fire

Nyttereglen giver hver del til deltageren med den højeste nyttescore . I dette tilfælde, ifølge brugsreglen, får Alice al chokoladen, og George får al vaniljen. Den maksimale værdi vil være 13.

Snittet efter nytte er uretfærdigt - det er ikke proportionalt , fordi George får mindre end halvdelen af den fulde karakter. Den er heller ikke fri for misundelse , da George er jaloux på Alice.

Notation

Lad os betegne kagen med bogstavet . Det antages normalt, at det enten er et endeligt endimensionelt segment, en todimensionel polygon eller en endelig delmængde af et højeredimensionelt euklidisk rum . $C$ $\mathbb{R}^d$

Der er deltagere. Hver deltager har en personlig scoringsfunktion, der kortlægger delmængder ("pieces of cake") til tal. $n$ $jeg$ $V_i$ $C$

$C$ skal opdeles i ikke-overlappende dele, én pr. deltager. Den del, der gives til deltageren , betegnes som og . $n$ $jeg$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

En split kaldes en utility split , eller maximum utility (MP), eller maxsum , hvis den maksimerer følgende udtryk: $x$

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

Konceptet generaliseres ofte ved at tildele forskellig vægt til hver deltager. En partition kaldes vægtet-utilitaristisk-maksimal ( WUM ), hvis den maksimerer følgende udtryk: $x$

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

hvor gives positive konstanter. $w_{i}$

Maxsum og Pareto effektivitet

Enhver MVP-partition med positive vægte er naturligvis Pareto-effektive . Hvis partitionen er Pareto-dominerende , så er den vægtede sum af hjælpeprogrammerne i strengt taget større end i , så det kan ikke være en MVP-partition. $Y$ $x$ $Y$ $x$ $x$

Mere overraskende er enhver Pareto-effektiv partition en MVP for nogle valg af vægte [1] [2] .

Funktioner i maxsum- reglen

Christopher P. Chambers foreslog de karakteristiske træk ved MVP-reglen [3] . Funktionerne er baseret på følgende egenskab for opdelingsreglen R :

Pareto-effektivitet (PE, engelsk Pareto-effektivitet , PE): R - reglen returnerer kun partitioner, der er Pareto-effektive.
Division uafhængighed ( ND, engelsk division uafhængighed , DI) : hvis kagen er delt i flere stykker og hver af dem er skåret efter R -reglen , vil resultatet være det samme, som hvis den originale kage blev skåret efter R -reglen .
Independence of infeasible land ( IIL): når en underkage deles efter R-reglen , afhænger resultatet ikke af fordelene for deltagere i andre underkager.
Positiv behandling af ligemænd ( PTE) : hvis alle deltagere har de samme nyttefunktioner, anbefaler R -reglen mindst én opdeling, der giver positiv nytte til hver deltager.
Skala -invarians ( SI) : når deltagerevalueringsfunktionerne ganges med en konstant værdi (forskellige konstanter er tilladt for forskellige deltagere), ændres anbefalingerne fra R -reglen ikke.
Kontinuitet ( kontinuitet , CO ): For et fast stykke kage lukkes det sæt af nytteskemaer, der er knyttet til en bestemt fordeling, ved punktvis konvergens .

Følgende fakta er bevist for deltagere, der tildeler positiv nytte til ethvert stykke kage med en positiv størrelse:

Hvis reglen R har egenskaberne PE, ND og NNS, så er der en sekvens af vægte , således at alle partitioner anbefalet af reglen R er MVP'er med disse vægte (det er blevet vist, at enhver PE partition er en MVP med nogle vægte Det nye er, at alle partitioner anbefalet af regel R er MVP'er med samme vægt (dette følger af ND-egenskaberne). ${\displaystyle w_{1},\dots ,w_{n))$
Hvis reglen R har egenskaberne PE, ND, NNS og POR, så er alle partitioner anbefalet af reglen R maksimalt nyttige (med andre ord skal alle divisioner være MVP, og alle agenter skal have samme vægt. Dette følger af POR'en ejendom).
Hvis regel R har egenskaberne PE, ND, NNS og NS, så er regel R en diktatorisk regel - den giver hele kagen til én deltager.
Hvis en regel R har egenskaberne PE, ND, NNS og LR, så er der en sekvens af vægte , sådan at regel R er en MVP-regel med disse vægte (dvs. R anbefaler kun en MVP-division med disse vægte). ${\displaystyle w_{1},\dots ,w_{n))$

Find den maksimale sum af partitioner

Afbrudte stykker

Hvis scorefunktionerne er additive , eksisterer maxsum divisionerne altid. Intuitivt kan vi give hver del af kagen til den deltager, der vurderer den højest, som i eksemplet ovenfor . På samme måde kan MVP-divisionen findes ved at give hvert stykke af kagen til den partner, for hvem forholdet har den største værdi. $V_{i}/w_{i}$

Denne proces er let at implementere, hvis kagen er stykkevis homogen , det vil sige, at den kan opdeles i et begrænset antal stykker, hvor tætheden af værdifunktionerne for alle deltagere er konstant.

Hvis kagen ikke er stykkevis homogen, svigter ovenstående algoritme, fordi der er et uendeligt antal forskellige "stykker" at overveje.

I dette tilfælde eksisterer maxsum-partitionen stadig. Dette er en konsekvens af Dubins-Spaniers kompaktitetsteoremet og kan bevises ved hjælp af Radon-Nikodim-sættet .

Ingen endelig algoritme kan dog finde maxsum-partitionen. Bevis [4] . Den endelige algoritme har data om værdien af et begrænset antal stykker. Det vil sige, at der kun er et begrænset antal delmængder af kagen, som algoritmen kender deltagernes score for. Lad os antage, at algoritmen stoppede efter at have modtaget data om delmængder. Nu er det muligt, at alle deltagere svarede, at de har samme chunk- score. I dette tilfælde er den højest mulige nytte, der kan opnås af algoritmen, 1. Det er dog muligt, at der dybt inde i en af bidderne er en delmængde, som de to deltagere værdsætter forskelligt. I dette tilfælde er der en superproportional division , hvor hver deltager modtager en værdi større end , så summen af forsyninger er strengt taget større end 1. Derfor vil divisionen returneret af den endelige algoritme ikke være maxsum. $k$ $k$ $1/n$

Forbundne stykker

Hvis kagen er endimensionel, og brikkerne skal forbindes, virker den simple algoritme til at tildele hver mest værdifulde brik til en agent ikke længere, selvom brikkerne er stykkevis konstante. I dette tilfælde er opgaven med at finde MT-imputationen NP-hård , og desuden er ingen FPTAS- ordning mulig, medmindre P=NP.

Der er en 8-fold tilnærmelsesalgoritme og algoritme, der kan løses med faste parametre , der er eksponentiel i antallet af spillere [5] .

For ethvert sæt positive vægte er der en MVP-partition, og den kan findes på en lignende måde.

Maxsum og egenkapital

Maxsum-inddelingen er ikke altid retfærdig, se eksemplet ovenfor . Ligeledes er en retfærdig opdeling ikke altid maxsum.

En tilgang til at løse konflikten er at begrænse "retfærdighedens pris" - vi beregner de øvre og nedre grænser for faldet i mængden af nytte for at opnå en retfærdig opdeling. For detaljer, se artiklen " The Price of Equity ".

En anden tilgang til at kombinere effektivitet og retfærdighed er at søge blandt alle mulige fair divisioner for divisionen med den maksimale nyttemængde:

Find fair maxsum distributioner

Følgende algoritmer kan bruges til at finde et misundelsesfrit snit med den maksimale samlede nytteværdi for en kage i form af et endimensionelt interval, hvis hver deltager kan modtage forskellige (frakoblede) stykker af kagen, og evalueringsfunktionerne er additive [6] :

For deltagere med stykvis konstante skøn: opdel kagen i m helt konstante områder (). Vi løser et lineært programmeringsproblem med nm variable - hvert par (agent, areal) har en variabel, der bestemmer andelen af arealet, der overføres til agenten. For hver region er der en begrænsning, at summen af alle dele af regionen er 1. For hvert par (agent, agent) er der en begrænsning, at den første agent ikke er jaloux på den anden agent. Bemærk, at opdelingen af kagen opnået ved en sådan procedure kan vise sig at være ekstremt lille. $n$
For deltagere med stykvis lineære estimater: For hvert punkt på kagen beregner vi forholdet mellem forsyningsselskaber: . Vi giver deltageren 1 point fra , og deltageren 2 point fra , hvor er tærsklen udregnet så opdelingen bliver fri for misundelse. Generelt kan det ikke beregnes, fordi det kan være irrationelt , men i praksis, når estimaterne er stykkevis lineære, kan det tilnærmes ved den "irrationelle søgning" tilnærmelsesalgoritme. For enhver finder algoritmen en fordeling, der er -SZ (værdien for hver agent er ikke mindre end værdien for enhver anden agent minus ), og summen når mindst den maksimale sum af SZ-fordelinger. Algoritmens køretid afhænger polynomielt af inputdataene og på . $2$ ${\displaystyle r=u_{1}/u_{2))$ $r\geqslant r^{*}$ $r<r^{*}$ $r^{*}$ $r^{*}$ $r^{*}$ $\epsilon > 0$ $\epsilon$ $\epsilon$ $\log(1/\epsilon )$
For deltagere med generelle estimatorer: en additiv tilnærmelse for at opnå en misundelsesfri og effektiv fordeling baseret på en stykkevis lineær scoringsalgoritme. $n$

Egenskaber for maxsum-fair distributioner

Artiklen af Brahms et al . [7] studerer både misundelsesfri (SE, eng. misundelsesfri , EF) og upartisk (DB, eng. equitable , EQ) kagedeling og etablerer deres forbindelse med maxsum og Pareto optimal ( OP, eng. Pareto-optimality , PO) efter divisioner. Som forklaret ovenfor er maxsummen af en fordeling altid OP. Men når maxsum er begrænset af rimelighedsbetingelsen, er dette ikke nødvendigvis sandt. Brahms og medforfattere beviste følgende

Når der er to agenter, vil SZ max, DB max og SZ-DB max distribution altid være OD.
Når der er tre eller flere midler med stykkevis homogene estimatorer, er SZ maksimale fordelinger altid OP (fordi SZ svarer til proportionalitet , som er bevaret under Pareto-forbedringer). Der er dog muligvis ikke en maksimal DB og en maksimal distribution DB-SZ, der ville være OP.
Hvis der er tre eller flere midler med stykkevis konstant evalueringsfunktioner (dvs. har stykkevis konstante tætheder), er der muligvis ikke en SZ maksimal fordeling, der er OP. Overvej f.eks. en kage med tre områder og tre agenter med værdier: Alice : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 . Maxsum-reglen giver område i til agent i, men denne opdeling er ikke uden misundelse, da Carl er jaloux på Alice. Ved hjælp af lineær programmering kan man finde en enkelt SZ maksimal fordeling og vise, at den skal give andele i region 1 og region 2 til både Alice og Bob. En sådan tildeling kan dog ikke være OP, da Alice og Bob kunne drage fordel af aktieswaps i disse regioner.
Hvis alle agenter har stykkevis lineære evalueringsfunktioner, så er summen af utilities af den maksimale fordeling SZ ikke mindre end utilities af den maksimale distribution DB. Dette resultat udvides til generelle scores for additive approksimationer (det vil sige, -SZ-distributioner har en sum af hjælpeprogrammer, der ikke er mindre end hjælpeprogrammerne for DB-fordelingerne minus ). $\epsilon$ $\epsilon$

Se også

Pleasure Counting er et forsøg på at bestemme nytten ved hjælp af matematiske formler.
Effektiv kageskæring
Fair Cake Cutting Challenge
Wellers sætning
Pareto effektiv distribution uden misundelse
Maksimal fordeling efter rang

Noter

↑ Barbanel og Zwicker 1997 , s. 203.
↑ Se også Wellers sætning . For lignende resultater relateret til det uensartede ressourceallokeringsproblem, se Varians sætninger .
↑ Chambers, 2005 , s. 236-258.
↑ Brams og Taylor 1996 , s. 48.
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Brams, Feldman et al., 2012 , s. 1285-1291.

Litteratur

Julius B. Barbanel, William S. Zwicker. To anvendelser af et teorem af Dvoretsky, Wald og Wolfovitz til kagedeling // Teori og beslutning. - 1997. - T. 43 , no. 2 . - doi : 10.1023/a:1004966624893 .
Christopher P. Chambers. Tildelingsregler for jorddeling // Journal of Economic Theory. - 2005. - T. 121 , no. 2 . - doi : 10.1016/j.jet.2004.04.008 .
Steven J. Brams, Alan D. Taylor. retfærdig deling; Fra kageskæring til konfliktløsning. - 1996. - ISBN 978-0521556446 .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Databehandling af socialt effektive kageafdelinger // AAMAS . - 2013.
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Optimal misundelsesfri kageskæring // AAAI . – 2011.
Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, Ariel D. Procaccia. Om Maxsum Fair Cake Divisions // Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12) . – 2012.