Problemet med en retfærdig udskæring af kagen

Problemet med retfærdig tærteudskæring er en variant af problemet med retfærdig kagedeling , hvor emnet, der skal opdeles, er en cirkel .

Som et eksempel kan du overveje en fødselsdagskage i form af en cirkel . Kagen skal deles mellem flere børn på en sådan måde, at ingen af dem er jaloux på den anden (som i standard kageopdelingsproblemet). En yderligere betingelse er, at snittene skal være radiale, så hvert barn får en cirkelsektor . Udtrykket "kage" er blot en metafor for en kageskæringsprocedure, der kan bruges til at dele forskellige slags ressourcer. For eksempel: jordejerskab, annonceplads eller sendetid.

Opgaven med at skære kagen blev foreslået af Hugo Steinhaus efter Anden Verdenskrig . Siden da har det været genstand for intense studier i matematik, datalogi, økonomi og statskundskab.

Delingstærtemodellen kan anvendes til at opdele en øs kystlinje i sammenhængende sektioner. En anden mulig anvendelse er opdelingen af periodisk tid - opdelingen af den daglige cyklus i "tjenesteperioder".

Model

Tærten er normalt modelleret som et endimensionelt interval [0,2π] (eller [0,1]), hvori de to endepunkter er identificeret.

Denne model blev foreslået i 1985 og senere i 1993 [1] [2] .

Enhver procedure for en retfærdig deling af kagen kan anvendes til at skære tærten, idet man ignorerer det faktum, at de to endepunkter kan identificeres. For eksempel, hvis Alice får [0,1/3] og George får [1/3,1] som et resultat af kageskæringsproceduren, så vil vi give Alice en 120 graders cirkulær sektor , mens George får de resterende 240 grader sektor.

Tærteskæring bliver mere interessant, når vi overvejer effektivitetsspørgsmål , da flere udskæringer er mulige, når du deler tærten.

To partnere

Division uden misundelse

En division kaldes en misundelsesfri ( EF ) division, hvis hver partner mener, at hans brik er mindst samme pris som alle andre.

Opdeling af tærten fra OP kan gøres ved hjælp af opdel-og-vælg- proceduren - en partner skærer tærten i to sektorer, som han anser for ligeværdige, og den anden partner vælger den sektor, som han anser for den bedste. Men for en tærte kan der være en bedre opdeling.

Division uden misundelse og Pareto effektiv

Inddelingen kaldes Pareto efficient (EP, engelsk Pareto efficient , PE), hvis ingen anden opdeling af kagen er den bedste for den ene partner og den dårligste for den anden. Ofte bestemmes Pareto-effektiviteten kun for delmængder af alle mulige divisioner. Nemlig kun til skæring i to sammenhængende sektorer (skæring med et minimum antal snit).

Inddelingen kaldes EPOS, hvis det både er EP og OZ.

Hvis partnernes score er ( additive ) mål, garanterer følgende "Moving Knife"-procedure en opdeling, der er OC og EP, når de er opdelt i sammenhængende sektorer [3] .

En partner (Rotator) holder to radiale knive over tærten på en sådan måde, at fra hans synspunkt har de to sektorer defineret af disse knive samme værdi. Han roterer disse knive kontinuerligt hele tiden og holder det samme antal sektorer, indtil knivene kommer til startpositionen.

Den anden partner (Vælgeren) observerer denne proces gennem hele cyklussen. Derefter, i den næste cyklus, bestemmer den den position, ved hvilken den maksimale værdi for en af de to sektorer opnås fra sit synspunkt. Vælgeren får denne sektor, og rotatoren får den resterende sektor.

Denne opdeling er åbenbart EP'en, da Rotatoren er ligeglad med hvilke kvadranter Selector vælger. Dette er EP, da der ikke er nogen division, der ville give Selector en større værdi og efterlade en værdi på 1/2 for Rotate.

Additivitetsrestriktioner

Ovenstående procedure virker kun, hvis værdifunktionen Rotating er additiv , så lige dele har altid den samme værdi 1/2. Hvis den ikke er additiv, vil opdelingen forblive misundelsesfri, men ikke nødvendigvis Pareto-effektiv .

Desuden, hvis pointene for begge spillere ikke er additive (så ingen af dem kan fungere som rotatoren), eksisterer opdelingen af EPOS ikke altid [4] .

Konsistent division og vægtet proportional division

Opdelingen kaldes eksakt (eller konsistent ), hvis værdien af brikken er nøjagtig ens i henhold til alle partnere, hvor er foruddefinerede vægte. $jeg$ $w_{i}$ $w_{i}$

Antag, at summen af alle vægte er lig med 1, og værdien af kagen for alle midler også normaliseres til 1. Ifølge Stromquist-Woodall-sætningen , er der for enhver vægt en delmængde , som er foreningen af de maksimale sektorer, hvis værdi alle partnere estimerer nøjagtigt til . For agenters tilfælde følger det, at der altid er en konsekvent opdeling af kagen med forbundne sektorer, hvor agent 1 får en sektor, der koster nøjagtigt for begge agenter, og agent 2 får den resterende sektor, der koster for begge agenter ( se artiklen af Brahms, Jos og Klumler [5] for et alternativt bevis). $w\in [0,1]$ $C_{w}$ $n-1$ $w$ $n=2$ $w_{1}$ ${\displaystyle 1-w_{1}=w_{2))$

Dette kan generaliseres til et hvilket som helst antal agenter - hvert stykke, undtagen den sidste, kræver højst nedskæringer, så det samlede antal udskæringer, der kræves, er . $2(n-1)$ ${\displaystyle 2(n-1)^{2))$

En division siges at være proportional , hvis hver af de to partnere modtager en værdi på mindst 1/2. Delingen kaldes vægtet proportional division ( WPR ), hvis partneren modtager en værdi på mindst , hvor er en foruddefineret vægt, der repræsenterer de forskellige andele af partnerne i kagen. Proceduren beskrevet ovenfor viser, at i kagen eksisterer opdelingen af VPD'en med forbundne stykker altid. Dette står i kontrast til en ikke-cirkulær kage (interval), hvor en vægtet proportional division (WPR, eng. Weighted proportional division , WPR) med forbundne dele muligvis ikke eksisterer. $jeg$ $w_{i}$ $w_{i}$

Vægtet division uden forseelse

Hvis vurderingerne af partnerne er absolut kontinuerlige i forhold til hinanden, så er der en VPD-division, som også er WHO (vægtet i fravær af misundelse, eng. vægtet-misundelse-fri , WEF) og Pareto-effektiv (EP, eng . Pareto efficient , PE), og forholdet mellem partnerværdierne er nøjagtigt w 1 / w 2 [5] .

Bevis . For enhver vinkel t , lad være den vinkel, hvor forholdet . $y(t)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

Funktionen er kontinuerlig i t og når sit maksimum på nogle . Vi skærer tærten med radiale udskæringer på punkter og giver et stykke til partner nr. 1 og en tilføjelse til partner og hoved nr. 2. Opdelingen er WHO, da værdien af hver partner er nøjagtigt lig med dens skøn. Det er også EP, fordi partner #1s andel er maksimeret, så der er ingen måde at give mere til partner #2 uden at miste partner #1. $v_{1}([t,y(t)])$ ${\displaystyle t^{\ast ))$ ${\displaystyle t^{\ast ))$ $y(t^{\ast })$ $[t^{\ast},y(t^{\ast})]$

Retfærdig opdeling

En upartisk division er en division, hvor den subjektive værdi af begge partnere er den samme (dvs. hver partner er lige tilfreds).

Der er altid en opdeling af kagen for to partnere, der er både misundelsesfri og upartisk. Der kendes dog på nuværende tidspunkt ingen procedure til at finde en sådan adskillelse [3] .

Hvis værdierne af partnernes mål er absolut kontinuerte i forhold til hinanden (dvs. enhver brik, der har en positiv værdi for den ene partner, har også en positiv værdi for den anden partner), så er der en misundelsesfri partitionering, der også er upartisk og Pareto-effektiv . Igen er der ingen procedure kendt for en sådan opdeling [3] .

Korrekt opdeling

En divisionsregel siges at være korrekt , hvis visning af sande værdifunktioner er en svagt dominerende strategi i denne regel. Det vil sige, at det ikke er muligt at opnå nogen værdi ved at misrepræsentation af værdier.

En divisionsregel siges at være diktatorisk , hvis den giver hele kagen til en enkelt forudbestemt partner.

EP-delingsreglen er korrekt, hvis og kun hvis den er diktatorisk [4] .

Tre eller flere partnere

Division uden misundelse for 3 partnere

Stromquists Moving Knife-procedure kan bruges til at skære i dimension 1, så den kan naturligvis bruges til at skære en tærte.

Men der er en enklere algoritme , der udnytter den runde form af tærten [6] [3] .

Partner A roterer tre radiale knive kontinuerligt rundt om tærten og sørger for, at sektorerne (efter hans/hendes skøn) er 1/3-1/3-1/3 i størrelse.

Partner B vurderer værdien af disse tre kvadranter. Normalt har de alle forskellige værdier, men på et tidspunkt vil de to sektorer have samme værdi. Dette skyldes, at efter en 120 graders rotation vil den tidligere vigtigste kvadrant nu være af mindre betydning, og den anden kvadrant vil nu være den vigtigste. Derfor skal der ved mellemværdisætningen være en roterende position, når bruger B ser to identiske sektorer. På dette tidspunkt siger partner B "stop".

Partnerne vælger derefter sektorer i rækkefølgen C - B - A. Partner C føler selvfølgelig ikke nogen jalousi, da han vælger først. Partner B har mindst én større sektor at vælge imellem, og partner A mener, at alle brikker har samme værdi.

Misundelsesfrie og Pareto-effektive versioner af division

For 3 partnere er der en tærte og tilsvarende foranstaltninger, for hvilke der ikke vil blive snit EPOS [7] .

Dette gælder også for mere end 3 partnere. Dette er sandt, selvom alle værdifunktioner er additive og strengt taget positive (det vil sige enhver partner værdsætter enhver del af kagen) [3] .

Begge disse eksempler bruger mål, der er næsten identiske, men med en meget subtil raffinement. Fordi målene er næsten ensartede, er det nemt at finde tærteudskæringer, der er næsten misundelsesfrie og næsten ikke-dominerede. Det vides ikke, om det er muligt at finde eksempler, hvor uenighederne er meget større.

Proportional opdeling med forskellige andele

Når der er 3 eller flere partnere med forskellige andele, kræves en vægtet proportional division (WPA). VPD-division med tilsluttede stykker eksisterer ikke altid [5] .

Dette er analogt med umuligheden for en 1-dimensionel intervalkage og 2 partnere (se afsnittet Vægtet Proportional Division i artiklen The Fair Cake Cutting Problem ).

Noter

↑ Stromquist, Woodall, 1985 , s. 241-248.
↑ Gale, 2009 , s. 48–52.
↑ 1 2 3 4 5 Barbanel, Brams, Stromquist, 2009 , s. 496.
↑ 12 Thomson , 2006 , s. 501-521.
↑ 1 2 3 Brams, Jones, Klamler, 2007 , s. 353.
↑ Brams, Taylor, Zwicker, 1997 , s. 547-554.
↑ Stromquist, 2007 .

Litteratur

Stromquist W., Woodall DR Sæt, som flere mål er enige om // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Matematisk underholdning // The Mathematical Intelligencer. - 2009. - T. 15 . - doi : 10.1007/BF03025257 .
Barbanel JB, Brams SJ, Stromquist W. Cutting a Pie is Not a Piece of Cake // American Mathematical Monthly. - 2009. - T. 116 , no. 6 . - doi : 10.4169/193009709X470407 .
Thomson W. Børn, der græder ved fødselsdagsfester. Hvorfor? // Økonomisk teori. - 2006. - T. 31 , no. 3 . - doi : 10.1007/s00199-006-0109-3 .
Brams SJ, Jones MA, Klamler C. Proportional pie-cutting // International Journal of Game Theory. - 2007. - T. 36 , no. 3–4 . - doi : 10.1007/s00182-007-0108-z .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. A Moving-Knife Solution to the Four-Person Envy-Free Cake Division // Proceedings of the American Mathematical Society. - 1997. - T. 125 , no. 2 . - doi : 10.1090/s0002-9939-97-03614-9 .
Walter Stromquist. En tærte, der ikke kan skæres retfærdigt // Dagstuhl Seminar Proceedings 07261 . – 2007.