Problemet med proportionell kakskärning

Problemet med proportionell kakskärning är ett slags rättvist kakskärningsproblem . Detta är en uppdelning av en heterogen resurs ("kaka") som uppfyller proportionalitetskriteriet , nämligen att varje deltagare tror att den del av kakan som tilldelats honom inte är sämre än 1/ n av den totala utvärderingen av kakan.

När proportionalitet diskuteras görs vanligtvis två antaganden:

Betygen för deltagarna är inte atomära , det vill säga det finns inga odelbara element med ett positivt betyg.
Deltagarnas poäng är additiv , det vill säga när en pjäs delas är pjäsens poäng lika med summan av dess delar.

Procedurer

För två personer är Delhi-and-Choose- proceduren en klassisk lösning. En person delar upp resursen i två halvor, som han anser vara lika, och den andra personen väljer den "halva" som han gillar bäst. Det icke-atomära antagandet garanterar att skäraren kan skära (som han tror) i två lika delar. Additivitetsantagandet garanterar att båda deltagarnas uppskattningar kommer att vara minst 1/2 för deras pjäser.

Det finns många sätt att utöka denna procedur till fler än 2 personer. Var och en av dessa metoder har sina egna fördelar och nackdelar.

Enkla procedurer

Det sista minuset är den tidigaste proportionella divisionsproceduren som utvecklats för n personer:

En av deltagarna ombeds välja ett stycke, som han värderar till 1/ n .
Övriga deltagare har i sin tur möjlighet att invända och förklara att pjäsen är större än 1/ n . I det här fallet uppmanas han att minska pjäsen så att den återstående delen av pjäsen enligt hans uppskattning är 1/ n .
Den sista deltagaren som minskar biten får den.
De återstående deltagarna delar upp resten av kakan på samma sätt mellan de återstående personerna. $n-1$

Genom induktion kan det bevisas att varje deltagare som följer reglerna garanteras få 1/ n av kakan, oavsett de andra deltagarnas agerande. Detta är en diskret procedur som kan utföras i omgångar. I värsta fall kommer det att krävas åtgärd – en åtgärd för varje deltagare i varje omgång. De flesta av dessa åtgärder kan dock göras på papper. Endast snitt behövs egentligen. Därför, om kakan är ansluten, kan det garanteras att varje del kommer att anslutas. $n\ gånger (n-1)/2=O(n^{2})$ $n-1$

Proceduren "Moving Knife" Dubins - Spanierär en kontinuerlig version av "Last Reducing" [1] .

Kniven rör sig längs torusen parallellt från ena änden till den andra.
Den tävlande säger "stopp" när han anser att värdet till vänster om kniven har uppnåtts . En tårtbit skärs av och ges till deltagaren som sagt. ${\tfrac {1}{n))$
Denna procedur upprepas med resten av kakan och de återstående deltagarna. Den sista deltagaren får resten av tårtan.

Fink-protokollet är en algoritm som fortsätter att delas upp i tillräckligt små "lika" bitar.

Den första deltagaren delar upp resursen i bitar som han anser vara lika;
Den andra deltagaren väljer hälften och lämnar resten till den första deltagaren;
Var och en av dessa två deltagare delar sin del i tredjedelar;
Den tredje deltagaren väljer två av de resulterande delarna - en vardera från den första och andra deltagaren;
Om det är fyra deltagare delar var och en av de tre första deltagarna upp sin del i kvartal och processen fortsätter.

Fördelen med detta protokoll är att det kan göras online – när nya partners kommer till spel anpassas den befintliga divisionen för det utan att behöva starta hela divisionsprocessen från början. Nackdelen med denna algoritm är att varje deltagare får ett stort antal frånkopplade bitar snarare än en ansluten bit.

Single dividing är en procedur baserad på en lika uppdelning, utförd av en enda agent. Fördelen med proceduren är att den kan generaliseras försymmetrisk rättvis skärning av kakan.

Se även: [2] .

Rekursiv halvering

Med hjälp av dela och erövra-strategin kan proportionell division uppnås i tid [3] . För enkelhetens skull ges proceduren som beskrivs här för ett jämnt antal deltagare, men det kan enkelt anpassas till valfritt antal deltagare: $O(n\log n)$

Varje deltagare ombeds att dra en linje som delar kakan i två delar som han anser är likvärdiga. Det krävs att skären inte skär varandra. Det enklaste sättet att garantera detta är att endast tillåta horisontella linjer eller endast vertikala linjer.
Algoritmen sorterar de n raderna i stigande ordning och skär kakan vid medianen av raderna. Till exempel, om det är 4 deltagare som ritar linjer vid punkter och , skär algoritmen kakan vertikalt vid punkt . $x=1,x=3,x=5$ $x=9$ $x=4$
Algoritmen tilldelar var och en av de två halvorna n /2 deltagare - partners vars linjer är inuti halvan. Till exempel tilldelas medlemmarna som ritade linjer vid prickarna till den västra halvan, medan de återstående medlemmarna tilldelas den östra halvan. Varje halva delas rekursivt mellan de n /2 deltagare som tilldelats den halvan. $x=1$ $x=3$

Det kan visas genom induktion att alla spelare som spelar enligt reglerna är garanterade en pjäs med ett värde på minst 1/ n , oavsett hur de andra spelarna beter sig.

Tack vare divide and conquer-strategin kommer antalet iterationer endast att vara O(log n ), i motsats till O( n )-värdet i den senaste minskningsproceduren. Vid varje iteration är varje deltagare skyldig att göra en anteckning. Därför kommer det totala antalet poäng att vara lika med . $O(n\log n)$

Algoritmen har en randomiserad version som kan användas för att minska antalet bockar. Se artikeln " Even-Paz Algorithm ".

Urvalsprocedurer

Ett annat tillvägagångssätt för att skära tårtan är att låta varje deltagare extrahera något antal bitar beroende på antalet deltagare, p ( n ), och ge varje deltagare en av sina utvalda bitar så att bitarna inte överlappar varandra.

Som ett enkelt exempel på ett urvalsprocedur, föreställ dig en tårta som ett endimensionellt segment, och varje deltagare vill få ett separat kopplat segment. Vi använder följande protokoll:

Varje deltagare delar upp kakan privat i n intervall, som han anser är lika i värde, låt oss kalla dessa bitar för kandidater .
Protokollet ordnar kandidaterna i ordning efter deras östra gränser (från väster till öster) och väljer segmentet med den västligaste östliga änden. Detta segment kallas den sista biten . $n^{2}$
Protokollet ger slutstycket till sin ägare och tar bort alla kandidater som korsar det. Steg #2 upprepas sedan för de återstående segmenten av resten av deltagarna. $n-1$

Urvalsregeln i steg #2 säkerställer att vid varje iteration tas högst ett segment av varje deltagare bort. Därför, efter varje iteration, förblir antalet segment per deltagare lika med antalet deltagare, och processen kan fortsätta tills alla deltagare får ett segment [4] .

Detta protokoll kräver att varje part svarar på n frågor, så frågekomplexiteten är , liknande proceduren för senaste minskning. $O(n^{2})$

Randomiserade versioner

Du kan använda randomisering för att minska antalet frågor. Tanken är att varje deltagare inte rapporterar hela uppsättningen av n kandidater, utan endast ett konstant antal d kandidater valda slumpmässigt. Frågekomplexiteten är O( n ), vilket uppenbarligen kommer att vara den bästa möjliga. I många fall är det fortfarande möjligt att ge varje deltagare en enda kandidat som inte överlappar andra. Det finns dock scenarier där sådan distribution inte är möjlig.

Vi kan skära kakan med O( n ) frågor om vi kompromissar:

Istället för att garantera full proportionalitet garanterar vi partiell proportionalitet , det vill säga att varje deltagare får en viss konstant bråkdel f ( n ) av det totala värdet, där . $f(n)<{\tfrac {1}{n))$
Istället för att ge varje deltagare en separat ansluten bit, skickar vi föreningen av en eller flera icke-korsande bitar till deltagaren.

Det allmänna schemat är följande [5] :

Varje deltagare delar kakan privat i lika delar enligt hans subjektiva bedömning. Dessa bitar kommer att kallas kandidater . $n\cdot an$
Varje deltagare väljer 2 d kandidater likformigt slumpmässigt med en retur. Kandidaterna grupperas i d -par, som deltagaren rapporterar till algoritmen. Dessa par kommer att kallas kvartsfinaluppsättningar . $n\cdot d$
Från varje kvartsfinaluppsättning väljer algoritmen en enda bit, den som skär minst antal andra kandidater. Dessa bitar kommer att kallas semifinal . $n\cdot d$
För varje deltagare väljer algoritmen en enskild del, låt oss kalla det final . De sista bitarna väljs ut så att varje punkt på kakan täcks av maximalt två sista bitar (se nedan). Om detta lyckas, gå till steg nummer 5. Om det misslyckas, gå tillbaka till steg nummer 1.
Varje bit av kakan som bara tillhör en sista bit ges till ägaren av den biten. Varje del av kakan som hör till de två sista bitarna delas proportionellt med valfri deterministisk proportionell divisionsalgoritm.

Algoritmen garanterar att varje deltagare med sannolikhet kommer att få minst hälften från en av sina kandidatbitar, vilket innebär (om uppskattningarna är additiva) att uppskattningen inte kommer att vara mindre än 1/2 an . Det finns O( n ) kandidatbitar och O( n ) extra divisioner i steg #5, var och en tar O(1) tid. Därför är den totala körtiden för algoritmen O( n ). $O(1a^{2})$

Det största problemet i detta schema är valet av de sista bitarna i steg #4. Se Edmonds-Prus-protokollet för detaljer .

Resultat efter svårighetsgrad

Resultaten om komplexitet är formulerade i termer av "standard Robertson-Webb-modellen", det vill säga de hänvisar till procedurer som använder två typer av åtgärder: "Estimate" och "Cut".

Varje deterministisk proportionell divisionsprocedur för deltagare måste använda minst n åtgärder, även om alla poängfunktioner är identiska [3] . $n\geqslant 3$

Dessutom måste varje deterministisk eller randomiserad (probabilistisk) proportionell divisionsprocedur som tilldelar varje deltagare en ansluten pjäs använda åtgärder [6] . $\Omega (n\log n)$

Dessutom måste varje deterministisk proportionell uppdelningsprocedure utföra åtgärder, även om proceduren tillåts att tilldela varje deltagare en del som är föreningen av segment, och även om proceduren tillåts att endast garantera ungefärlig rättvisa . Beviset bygger på en nedre gräns för komplexiteten i att för enskilda spelare hitta en tårta som är av stort värde och tunn i bredd [7] [8] . $\Omega (n\log n)$

Det följer av dessa svårighetsresultat att rekursiv halvering är den snabbaste algoritmen för att uppnå full proportionalitet med anslutna stycken, och det är den snabbaste möjliga deterministiska algoritmen för att uppnå partiell proportionalitet även med frånkopplade stycken. Det enda fallet där det kan förbättras är i randomiserade algoritmer som garanterar partiell proportionalitet med frånkopplade bitar.

Om spelare bara kan skära med ändlig precision, så inkluderar den nedre gränsen också randomiserade protokoll [7] [8] . $\Omega (n\log n)$

Följande tabell innehåller kända resultat [5] :

Proportionalitet ( helt / delvis)	Bitar (ansluten / frånkopplad)	Protokolltyp (deterministisk / randomiserad )	Frågor (exakt/ ungefärlig)	Antal förfrågningar
komplett	budbärare	deterministisk	exakt	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
komplett	budbärare	deterministisk	ungefärlig	$\Omega (n\log n)$ [6]
komplett	budbärare	randomiserat	exakt	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
komplett	budbärare	randomiserat	ungefärlig	$\Omega (n\log n)$ [6]
komplett	osammanhängande	deterministisk	exakt	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
komplett	osammanhängande	deterministisk	ungefärlig	$\Omega (n\log n)$ [7] [8]
komplett	osammanhängande	randomiserat	exakt	$O(n\log n)$ [3]
komplett	osammanhängande	randomiserat	ungefärlig	$\Omega (n\log n)$ [7] [8]
partiell	budbärare	deterministisk	exakt	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
partiell	budbärare	deterministisk	ungefärlig	$\Omega (n\log n)$ [7] [8]
partiell	budbärare	randomiserat	exakt	$\Omega (n\log n)$ [3]
partiell	budbärare	randomiserat	ungefärlig	$\Omega (n\log n)$ [7] [8]
partiell	osammanhängande	deterministisk	exakt	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
partiell	osammanhängande	deterministisk	ungefärlig	$\Omega (n\log n)$ [7] [8]
partiell	osammanhängande	randomiserat	exakt	O( n ) [5]
partiell	osammanhängande	randomiserat	svagt ungefärlig (oberoende av uppskattningsfel )	O( n ) [5]
partiell	osammanhängande	randomiserat	ungefärlig	$\Omega (n\log n)$ [7] [8]

Alternativ

Olika andelar förfaller

Proportionalitetstestet kan generaliseras till en situation där deltagarnas andelar inte är lika. Till exempel kan en resurs ägas av två aktieägare, Alice äger aktier och George äger . Detta leder till ett viktat proportionalitetskriterium (WPR) - det finns några vikter w i , vars summa är 1, och varje deltagare i måste få minst en andel w i av resursen enligt sin egen bedömning. Flera algoritmer kan användas för att hitta WPR-delningen. Det största problemet är att antalet nedskärningar kan vara stort även om det bara är två deltagare. Se Proportionell skärning av kakan med olika andelar på grund . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

Superproportionell division

En superproportionell division är en division där varje deltagare får strikt mer än 1/ n av resursen enligt sin egen subjektiva bedömning.

En sådan uppdelning finns förstås inte alltid - om alla deltagare har exakt samma utvärderingsfunktioner är det bästa vi kan göra att ge alla exakt 1/ n . En nödvändig förutsättning för att det ska finnas en superproportionell uppdelning är således kravet på att inte alla delägare har samma värderingsmått.

Överraskande nog, om utvärderingsfunktionerna är additiva och inte atomära, är detta villkor också tillräckligt. Det vill säga, om det finns minst två deltagare vars utvärderingsfunktioner bara skiljer sig något, så finns det en superproportionell division där alla deltagare får mer än 1/ n . Se Super Proportional Division för detaljer.

Grannskapsbegränsningar

Utöver den vanliga begränsningen att alla delar måste kopplas, finns det ytterligare begränsningar i vissa fall. I synnerhet när kakan som ska delas är ett omtvistat territorium som ligger mellan flera länder, kan det krävas att varje bit som ges till ett land ligger i anslutning till landets nuvarande gräns. Proportionell uppdelning i detta fall finns alltid och kan hittas genom att kombinera Last Decrease-protokollet med geometriska tekniker som använder konforma mappningar . Se artikeln " The Hill-Beck Land Dividing Problem ".

2D geometriska begränsningar

När en "kaka" är uppdelad i tvådimensionellt utrymme (ett plan), till exempel vid uppdelning av tomter eller reklamutrymme i tryckta eller elektroniska medier, krävs det ofta att bitarna uppfyller vissa geometriska begränsningar utöver anslutningsmöjligheter. Till exempel kan det krävas att varje bit är en kvadrat, en tjock rektangel (det vill säga att längden och bredden inte skiljer sig åt flera gånger) eller en tjock figur av allmän form. I närvaro av sådana restriktioner för siffror finns proportionell division vanligtvis inte, men delvis proportionell division finns vanligtvis och kan hittas med hjälp av effektiva algoritmer [9] .

Ekonomiskt effektiv uppdelning

Förutom proportionalitet krävs det ofta att uppdelningen är ekonomiskt effektiv , det vill säga maximera den totala nyttan (definierad som summan av alla agenters nyttigheter).

Tänk till exempel på en tårta som innehåller 500 gram choklad och 500 gram vanilj som delas av två deltagare, varav den ena bara vill ha choklad och den andra föredrar vanilj. Många tårtskärningsprotokoll ger varje medel 250 gram choklad och 250 gram vanilj. Denna uppdelning är proportionell, eftersom varje deltagare får 0,5 av det totala värdet, så den normaliserade totala nyttan är 1. Denna uppdelning kommer dock att vara mycket ineffektiv, eftersom vi kan ge all chokladdel till den första deltagaren och hela vaniljdelen till den andra deltagaren, får en normaliserad total förmån 2.

Det optimala proportionella divisionsproblemet är problemet med att hitta en proportionell partition som maximerar den totala nyttan bland alla möjliga proportionella fördelningar. För närvarande har problemet en lösning endast för mycket speciella kakor när det är ett endimensionellt segment och densitetsfunktionerna är linjära (det vill säga ). I allmänhet är problemet NP-hårt . Om nyttofunktionerna inte är normaliserade (det vill säga vi låter varje deltagare ha olika uppskattningar av kakans totala betydelse) är problemet NP-svårt även för approximation med en faktor [10] . $u(x)=Ax+B$ ${\displaystyle {\tfrac {1}{\sqrt {n))))$

Rättvis uppdelning

Rättvisa är inte en egenskap hos divisionen, utan snarare en egenskap hos protokollet. Alla proportionella delningsprotokoll är svagt rättvisa i den meningen att varje deltagare som agerar enligt sitt verkliga värde garanteras att få minst 1/ n (eller 1/ an i fallet med ett delvis proportionellt protokoll) oavsett hur de andra deltagarna beter sig. Även om de andra medlemmarna bildar en koalition bara för att skada honom, kommer han fortfarande att få sin garanterade andel [11] .

De flesta protokoll är dock inte strikt rättvisa i den meningen att vissa deltagare kan ha incitament att ljuga för att få ännu mer än vad han är garanterad. Detta gäller även för ett enkelt dela-och-välj- protokoll — om skäraren känner till väljarens preferenser kan han skära av en bit som väljaren värderar strax under 1/2, men som skäraren själv värderar långt över 1/2.

Det finns rättvisa mekanismer för att få en perfekt partition . Eftersom perfekt division är proportionell är dessa mekanismer också rättvisa proportionella divisionsmekanismer.

Dessa mekanismer kan utökas för att erhålla en superproportionell uppdelning , om den finns [12] :

Vi ber varje deltagare att ge en fullständig utvärdering.
Vi väljer en slumpmässig partition (se artikeln av Mossel och Tamuz [12] för detaljer).
Om den slumpmässiga partitionen visar sig vara superproportionell enligt de rapporterade åtgärderna, utför vi den. Annars använder vi en rättvis mekanism för att säkerställa en perfekt uppdelning.

Om det finns en superproportionell division finns det en positiv chans att den kommer att erhållas i steg 2. Därför är det förväntade värdet för alla ärliga deltagare strikt större än 1/ n . För att förstå att mekanismen är rättvis, överväg tre fall: (a) Om den valda partitionen verkligen är superproportionell, är det enda möjliga resultatet av att ljuga att lura mekanismen att tro att partitionen inte är superproportionell. Detta kommer att tvinga mekanismen att tillämpa en perfekt uppdelning, vilket är värre för alla inblandade, inklusive kneben. (b) Om den valda partitionen inte är superproportionell bara för att lögnaren specificerar 1/ n eller mindre, är den enda effekten av att ljuga att få motorn att tro att partitionen är superproportionell och använda den, vilket bara kommer att skada lögnaren själv. (c) Om den valda splittringen verkligen inte är superproportionell, vilket ger den andra parten ett värde på 1/ n eller mindre, kommer falskt att inte ha någon effekt, eftersom uppdelningen inte kommer att användas alls.

Proportionell arbetsfördelning

Om resursen som ska delas är oönskad (liknande en arbetsfördelning ) definieras en proportionell delning som en delning som ger varje person högst 1/ n av resursen (d.v.s. ojämlikhetstecknet åt andra hållet).

De flesta proportionella divisionsalgoritmer kan anpassas för att dela uppgifter utan svårighet.

Se även

Exakt uppdelning . Se även "Perfekt indelning"

Anteckningar

↑ Dubins och Spanier, 1961 , sid. 1–17.
↑ Tasnadi, Attila. En ny procedur proportionell för n-persons kakskärningsproblem . researchgate. Hämtad: 24 september 2015. (obestämd)
↑ 1 2 3 4 5 6 7 8 9 Even, Paz, 1984 , sid. 285.
↑ Denna del av proceduren liknar den giriga polynomlösningen )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , sid. 623–634.
↑ 1 2 3 4 5 Woeinger, 2007 , sid. 213–220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , sid. 271–278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , sid. 1–12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , sid. 1–28.
↑ Bei, Chen, Hua et al., 2012 .
↑ Steinhaus, 1948 , sid. 101–4.
↑ 1 2 Mossel, Tamuz, 2010 , sid. 288–299.

Litteratur

En översikt över proportionella och andra uppdelningar dök upp i artikeln:
Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , nr. 437 . — S. 212–215 . - doi : 10.2307/3616548 . — .
Lester Eli Dubins, Edwin Henry Spanier. Hur man skär en tårta rättvist // The American Mathematical Monthly. - 1961. - T. 68 , nr. 1 . - doi : 10.2307/2311357 . — .
Even S., Paz A. A not on cake cutting // Discrete Applied Mathematics. - 1984. - T. 7 , nr. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47:e årliga IEEE Symposium on Foundations of Computer Science (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Gerhard J. Woeinger. Om tårtskärningens komplexitet // Diskret optimering. - 2007. - T. 4 , nr. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Tårtskärning är verkligen inte en plätt // Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Tårtskärning är verkligen inte en piece of cake // ACM Transactions on Algorithms. - 2011. - T. 7 , nr. 4 . - doi : 10.1145/2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Rättvist: Tårtskärning i två dimensioner // Journal of Mathematical Economics. - 2017. - T. 70 . - doi : 10.1016/j.jmateco.2017.01.007 . - arXiv : 1409.4511 .
Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Optimal proportionell tårtskärning med sammankopplade bitar // AAAI Conference Proceedings. — 2012.
Hugo Steinhaus. Problemet med rättvis uppdelning // Econometrica. - 1948. - T. 16 , nr. 1 . — .
Elchanan Mossel, Omer Tamuz. Truthful Fair Division // . - 2010. - T. 6386. - (Lecture Notes in Computer Science). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .