Problemet med en rättvis skärning av pajen

Problemet med att skära ut rättvis paj är en variant av problemet med att dela tårtor där föremålet som ska delas är en cirkel .

Som ett exempel, överväga en födelsedagstårta i form av en cirkel . Tårtan ska delas mellan flera barn på ett sådant sätt att ingen av dem är avundsjuk på den andra (som i standardproblemet med tårtdelning). En ytterligare förutsättning är att snitten måste vara radiella så att varje barn får en cirkelsektor . Termen "kaka" är bara en metafor för en tårtskärningsprocedur som kan användas för att dela olika typer av resurser. Till exempel: markägande, annonsutrymme eller sändningstid.

Uppdraget att skära tårtan föreslogs av Hugo Steinhaus efter andra världskriget . Sedan dess har det varit föremål för intensiva studier i matematik, datavetenskap, ekonomi och statsvetenskap.

Delningspajmodellen kan användas för att dela upp en ös kustlinje i sammanhängande sektioner. En annan möjlig tillämpning är uppdelningen av periodisk tid - uppdelningen av den dagliga cykeln i "tjänsteperioder".

Modell

Pajen modelleras vanligtvis som ett endimensionellt intervall [0,2π] (eller [0,1]) där de två ändpunkterna identifieras.

Denna modell föreslogs 1985 och senare 1993 [1] [2] .

Vilken som helst procedur för en rättvis uppdelning av kakan kan tillämpas på att skära pajen, utan att bortse från det faktum att de två slutpunkterna kan identifieras. Till exempel, om Alice får [0,1/3] och George får [1/3,1] som ett resultat av kakskärningsproceduren, kommer vi att ge Alice en 120 - graders cirkulär sektor , medan George får de återstående 240-graderna sektor.

Pajskärning blir mer intressant när vi tar hänsyn till effektivitetsfrågor , eftersom fler skärningar är möjliga när man delar pajen.

Två partners

Division utan avund

En division kallas en envy - free ( EF) division om varje partner tror att hans pjäs är minst samma pris som alla andra.

Att dela pajen från OP kan göras med hjälp av dela-och-välj- proceduren - en partner skär pajen i två sektorer som han anser vara lika, och den andra partnern väljer den sektor som han anser vara bäst. Men för en paj kan det finnas en bättre uppdelning.

Division utan avund och Pareto effektiv

Uppdelningen kallas Pareto efficient (EP, engelska Pareto efficient , PE) om ingen annan uppdelning av kakan är bäst för en partner och sämst för den andra. Ofta bestäms Pareto-effektiviteten endast för delmängder av alla möjliga divisioner. Nämligen endast för skärning i två sammanhängande sektorer (skärning med ett minimum antal snitt).

Uppdelningen kallas EPOS om det är både EP och OZ.

Om poängen för partnerna är ( additiva ) åtgärder, garanterar följande "Moving Knife"-procedur en uppdelning som är OC och EP när de är uppdelade i sammanhängande sektorer [3] .

En partner (Rotator) håller två radiella knivar över pajen på ett sådant sätt att ur hans synvinkel har de två sektorerna som definieras av dessa knivar samma värde. Han roterar dessa knivar kontinuerligt hela tiden, med samma antal sektorer, tills knivarna kommer till startpositionen.

Den andra partnern (Väljaren) observerar denna process under hela cykeln. Sedan, på nästa cykel, bestämmer den den position vid vilken, från dess synvinkel, det maximala värdet för en av de två sektorerna erhålls. Väljaren får denna sektor och Rotatorn får den återstående sektorn.

Denna division är uppenbarligen EP:n, eftersom Rotatorn inte bryr sig om vilka kvadranter Selectorn väljer. Detta är EP eftersom det inte finns någon division som skulle ge Väljaren ett högre värde och lämna ett värde på 1/2 för Rotary.

Additivitetsbegränsningar

Ovanstående procedur fungerar bara om värdefunktionen för Rotating är additiv , så lika delar har alltid samma värde 1/2. Om det inte är additivt skulle uppdelningen förbli avundsfri, men inte nödvändigtvis Pareto-effektiv .

Dessutom, om poängen för båda spelarna är icke-additiva (så att ingen av dem kan agera som rotator), finns inte alltid uppdelningen av EPOS [4] .

Konsekvent division och viktad proportionell division

Uppdelningen kallas exakt (eller konsekvent ) om värdet på pjäsen är exakt lika enligt alla partners, där är fördefinierade vikter. $i$ $w_{i}$ $w_{i}$

Antag att summan av alla vikter är lika med 1, och värdet av kakan för alla agenter är också normaliserat till 1. Enligt Stromquist-Woodalls sats , för vilken vikt som helst finns det en delmängd , som är unionen av de maximala sektorerna, vars värde alla partners uppskattar exakt till . När det gäller agenter följer det att det alltid finns en konsekvent uppdelning av kakan med anslutna sektorer, där agent 1 ges en sektor som kostar exakt för båda agenterna och agent 2 ges den återstående sektorn som kostar för båda agenterna ( se artikeln av Brahms, Jos och Klumler [5] för ett alternativt bevis). $w\in [0,1]$ $C_{w}$ $n-1$ $w$ $n=2$ $w_{1}$ ${\displaystyle 1-w_{1}=w_{2))$

Detta kan generaliseras till valfritt antal agenter - varje del, förutom den sista, kräver som mest klipp, så det totala antalet klipp som krävs är . $2(n-1)$ ${\displaystyle 2(n-1)^{2))$

En delning sägs vara proportionell om var och en av de två partnerna får ett värde på minst 1/2. Uppdelningen kallas viktad proportionell division ( WPR ) om partnern får ett värde på minst , där är en fördefinierad vikt som representerar de olika andelarna av partnerna i kakan. Proceduren som beskrivs ovan visar att i kakan finns alltid uppdelningen av VPD med anslutna delar. Detta står i kontrast till en icke-cirkulär kaka (intervall), där en viktad proportionell division (WPR, eng. Weighted proportional division , WPR) med sammankopplade delar kanske inte existerar. $i$ $w_{i}$ $w_{i}$

Viktad division utan förseelse

Om partnernas betyg är absolut kontinuerliga med avseende på varandra, så finns det en VPD-division som också är WHO (weighted in the absence of envy, eng. weighted-envy-free , WEF) och Pareto efficient (EP, eng . Pareto efficient , PE), och förhållandet mellan partnervärdena är exakt w 1 / w 2 [5] .

Bevis . För varje vinkel t , låt vara den vinkel vid vilken förhållandet . $y(t)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

Funktionen är kontinuerlig i t och når sitt maximum någon gång . Vi skär pajen med radiella snitt vid punkter och ger en bit till partner nr 1 och ett tillägg till partner och huvud nr 2. Uppdelningen är WHO, eftersom värdet på varje partner är exakt lika med dess uppskattning. Det är också EP eftersom partner #1:s andel är maximerad, så det finns inget sätt att ge mer till partner #2 utan att förlora partner #1. $v_{1}([t,y(t)])$ ${\displaystyle t^{\ast ))$ ${\displaystyle t^{\ast ))$ $y(t^{\ast })$ $[t^{\ast },y(t^{\ast })]$

Rättvis uppdelning

En opartisk division är en division där det subjektiva värdet för båda parter är detsamma (dvs varje partner är lika nöjd).

Det finns alltid en uppdelning av kakan för två partners som är både avundsfri och opartisk. För närvarande är dock inget förfarande känt för att hitta en sådan separation [3] .

Om värdena för partnernas mått är absolut kontinuerliga med avseende på varandra (dvs varje del som har ett positivt värde för en partner har också ett positivt värde för den andra partnern), så finns det en avundsfri partitionering som också är opartisk och Pareto-effektiv . Återigen, ingen procedur är känd för en sådan uppdelning [3] .

Korrekt indelning

En divisionsregel sägs vara korrekt om att visa verkliga värdefunktioner är en svagt dominerande strategi i denna regel. Det vill säga att det inte går att få fram något värde genom att missvisa värden.

En divisionsregel sägs vara diktatorisk om den ger hela kakan till en enda förutbestämd partner.

EP:s uppdelningsregel är korrekt om och endast om den är diktatorisk [4] .

Tre eller fler partners

Division utan avund för 3 partners

Stromquists Moving Knife-procedur kan användas för att skära vid dimension 1, så uppenbarligen kan den användas för att skära en paj.

Men det finns en enklare algoritm som drar fördel av pajens runda form [6] [3] .

Partner A roterar tre radiella knivar kontinuerligt runt pajen och ser till att sektorerna är (i hans/hennes uppskattning) 1/3-1/3-1/3 stora.

Partner B utvärderar värdet av dessa tre kvadranter. Vanligtvis har de alla olika värden, men någon gång kommer de två sektorerna att ha samma värde. Detta beror på att efter en 120 graders rotation kommer den tidigare viktigaste kvadranten nu att vara av mindre betydelse, och den andra kvadranten kommer nu att vara den viktigaste. Därför måste det enligt mellanvärdessatsen finnas en roterande position när användare B ser två identiska sektorer. Vid det här laget säger partner B "stopp".

Partnerna väljer sedan sektorer i ordningen C - B - A. Partner C känner naturligtvis ingen svartsjuka, eftersom han väljer först. Partner B har minst en större sektor att välja mellan, och Partner A anser att alla bitar har samma värde.

Avundsfria och Pareto-effektiva versioner av division

För 3 partners finns det en paj och motsvarande åtgärder för vilka ingen nedskärning kommer att vara EPOS [7] .

Detta gäller även för fler än 3 partners. Detta är sant även om alla värdefunktioner är additiva och strikt positiva (det vill säga vilken partner som helst värderar vilken del av kakan som helst) [3] .

Båda dessa exempel använder mått som är nästan identiska, men med en mycket subtil förfining. Eftersom måtten är nästan enhetliga är det lätt att hitta pajsnitt som är nästan avundsjuka och nästan icke-dominerade. Det är inte känt om det går att hitta exempel där meningsskiljaktigheterna är mycket större.

Proportionell uppdelning med olika andelar

När det finns 3 eller fler partners med olika andelar krävs en viktad proportionell delning (WPA). VPD-delning med anslutna delar finns inte alltid [5] .

Detta är analogt med omöjligheten för en 1-dimensionell intervallkaka och 2 partners (se avsnittet Weighted Proportional Division i artikeln The Fair Cake Cutting Problem ).

Anteckningar

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

Litteratur

Stromquist W., Woodall DR Uppsättningar där flera åtgärder överensstämmer // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Matematisk underhållning // 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 , nr. 6 . - doi : 10.4169/193009709X470407 .
Thomson W. Barn som gråter på födelsedagsfester. Varför? // Ekonomisk teori. - 2006. - T. 31 , nr. 3 . - doi : 10.1007/s00199-006-0109-3 .
Brams SJ, Jones MA, Klamler C. Proportionell pajskärning // International Journal of Game Theory. - 2007. - T. 36 , nr. 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 , nr. 2 . - doi : 10.1090/s0002-9939-97-03614-9 .
Walter Stromquist. En paj som inte går att skära rättvist // Dagstuhl Seminar Proceedings 07261 . – 2007.