Avundsjuk skärning av tårtan

Avundsjuk kakskärning [1] är en sorts rättvis kakskärning . Detta är skärningen av en heterogen resurs ("kaka") med tillfredsställelsen av kriteriet om frånvaro av avund , nämligen att varje deltagare har känslan av att den del som tilldelats honom (enligt hans egen subjektiva bedömning) inte är mindre än de bitar som ges till andra deltagare.

Om det bara är två deltagare är problemet enkelt och löstes under biblisk tid med Deliver-and-Choose- protokollet . Om det är tre eller fler deltagare blir uppgiften betydligt svårare.

Två huvudvarianter av problemet studerades:

anslutna delar, till exempel, i fallet med ett endimensionellt segment måste varje deltagare få ett separat delintervall. Om det är tre deltagare behöver du totala nedskärningar. $n$ $n-1$
delar av allmän form, till exempel, i fallet med ett endimensionellt segment, måste varje deltagare erhålla en förening av icke-korsande delsegment.

Kort historik

Modern forskning om det rättvisa kakskärningsproblemet började på 1940-talet. Det första kriteriet för rättvisa var proportionell uppdelning , och en procedur för n deltagare hittades snart.

Ett strängare kriterium för frånvaron av avund infördes i kakskärningsproblemet av Georgy Gamow och Marvin Stern på 1950 -talet [2] .

Proceduren för tre deltagare och styckenas allmänna utseende hittades 1960. Förfarandet för tre deltagare och anslutna bitar hittades först 1980.

Den avundsjuka uppdelningen för fyra eller fler personer var ett öppet problem fram till 1990-talet, då tre procedurer för den allmänna formen av pjäser och en procedur för sammanhängande pjäser publicerades. Alla dessa procedurer är obegränsade - de kan kräva ett antal steg som inte är begränsade i förväg. Proceduren för anslutna delar kan till och med kräva ett oändligt antal steg.

Två nedre gränser för hur komplexiteten i det avundsjuka divisionsproblemet är att köra tid publicerades på 2000-talet:

för stycken av allmän form är den nedre gränsen lika med ; $\Omega (n^{2})$
för sammankopplade pjäser är den nedre gränsen lika med oändlighet - kanske finns det inget slutgiltigt protokoll för tre eller fler deltagare.

Under 2010-talet publicerades vissa tillnärmningsförfaranden och förfaranden för specialfall. Frågan om det finns förfaranden med begränsad speltid för stycken av allmän form förblev öppen länge. Problemet löstes slutligen 2016. Haris Aziz och Simon McKenzie har föreslagit ett diskret avundsjuk uppdelningsprotokoll som inte kräver fler förfrågningar. Det finns fortfarande ett stort gap mellan den nedre gränsen och värdet som ges av proceduren. I augusti 2016 förblev den exakta tidskomplexiteten för det avundsjuka divisionsproblemet okänd. ${\displaystyle n^{n^{n^{n^{n^{n))))))))$

När det gäller sammankopplade delar har det observerats att svårighetsresultatet innebär att hela biten måste delas. Om detta krav ersätts av det svagare kravet att någon deltagare får ett proportionellt värde (av åtminstone hela biten enligt egen uppskattning), så är det begränsade förfarandet för tre deltagare känt, men det är fortfarande en öppen fråga om det finns procedurer med begränsad drifttid för fyra eller fler medlemmar. ${\tfrac {1}{n))$

Anslutna delar

Existensbevis

En avundsjuk uppdelning av n agenter med sammankopplade delar existerar alltid under följande antaganden [3] .

ingen agent föredrar en tom pjäs (en tom uppsättning poäng) framför en icke-tom pjäs;
agenternas preferenser är kontinuerliga.

Det krävs inte att agenternas preferenser representeras av en additiv funktion .

Huvudkonceptet för beviset är partitioneringssimplexet . Låt oss anta att kakan är ett segment [0;1]. Varje partition med sammankopplade delar kan representeras unikt av n − 1 nummer i intervallet [0;1], varje nummer representerar platsen för snittet. Föreningen av alla partitioner är en simplex.

För vilken partition som helst har varje agent en eller flera delar som de föredrar. Till exempel, för en partition som representeras av siffrorna "0.3;0.5", kan en agent föredra del #1 (segment [0;0.3]), medan en annan agent kanske föredrar del #2 (segment [0, 3;0.5]) , och den tredje agenten föredrar både bitar #1 och #2 (vilket betyder, enligt hans åsikt, att det inte finns någon skillnad mellan dem, men de är bättre än bit #3).

För vilken agent som helst täcks den partitionerande simplexen av n delar, som eventuellt överlappar varandra längs deras gränser, så att för alla partitioner i del i , föredrar agenten bit i . I det inre av del i föredrar agenten endast del i , även om vid gränsen för del i föredrar agenten även andra delar. Sålunda, för varje i , finns det ett visst område i partitionssimplexet där åtminstone en agent föredrar endast bit i . Låt oss kalla detta område . Med hjälp av något topologiskt lemma (som liknar Knaster-Kuratowski-Mazurkiewicz lemma ), kan man bevisa att skärningspunkten för alla U i är icke- tom. Därför finns det en partition där varje del är den enda som agenten föredrar. Eftersom antalet bitar är lika med antalet agenter kan vi allokera varje bit till en agent som föredrar det och få en avundsfri distribution. $U_{i}$

Procedurer

För tre agenter kan en avundsfri partition hittas med flera olika procedurer:

Stromkvists "Moving Knife"-procedur använder fyra knivar som rör sig samtidigt - en kniv flyttas av domaren och de andra tre - en för varje agent;
Barbanel-Brahms' Moving Knife-procedur använder två knivar som rör sig samtidigt;
Robertson-Webbs "Moving Knife"-procedur kan användas när kakan är tvådimensionell och endast en rörlig kniv används.

Det finns kontinuerliga procedurer - de är beroende av kontinuerliga och samtidiga rörelser av knivar av en person. Dessa procedurer kan inte slutföras i ett begränsat antal diskreta steg.

För n deltagare kan en split utan avund hittas av Simmons-Su tårtskärningsprotokoll . Protokollet använder en partitioneringssimplex , liknande den som används i Stromquists existensbevis. Protokollet bildar en sekvens av partitioner som konvergerar till en partition utan avund. Konvergens kan kräva oändligt många steg.

Det är ingen slump att alla dessa algoritmer kräver ett oändligt antal frågor. Som vi kommer att visa i nästa underavsnitt kanske det inte går att hitta avundsfria tårtsnitt med sammankopplade bitar med ett begränsat antal frågor.

Resultat efter svårighetsgrad

En avundsfri partition med anslutna delar för 3 eller fler agenter kan inte hittas av det finita protokollet [4] . Anledningen till detta resultat motsäger inte de ovan nämnda algoritmerna, eftersom de inte är ändliga i matematisk mening [5] .

Omöjlighetsbeviset använder ett rigid måttsystem ( RMS ) - ett system med n mått för utvärdering, för vilket splittring utan avund bör skära kakan på mycket specifika ställen. Då reduceras sökandet efter splittring utan avund till sökandet efter dessa specifika platser. Om man antar att kakan är ett reellt intervall [0;1], är det att söka efter en partition utan avund med hjälp av frågor på deltagarna lika med att söka efter reella siffror på intervallet [0;1] med ja/nej-frågor. Detta kan kräva ett oändligt antal frågor.

RMS för tre deltagare kan byggas enligt följande. Låt x , y , s och t vara parametrar som uppfyller villkoren

$0<x<y<1,$
$0<s<{\tfrac {1}{3}}<t<{\tfrac {1}{2)),$
$s+2t=1.$

Låt oss konstruera en uppsättning av tre mått med två egenskaper:

densiteten för varje mått är strikt mellan och (så att, för en given del, uppskattningarna av agenterna inte skiljer sig med mer än en faktor två); ${\tfrac {\sqrt {2}}{2}}$ ${\sqrt {2}}$
värdena för bitarna som definieras av talen x och y anges i tabellen:

Ombud	[0; x ]	[ x ; y ]	[ y ;1]
A	t	t	s
B	s	t	t
C	t	s	t

Då måste alla avundsfria partitioner mellan Alice, Bob och Carl ha skärningar vid x och y (det finns exakt två sådana partitioner), eftersom alla andra platser kommer att leda till avund:

om snitt görs till vänster om x och till höger om y , kommer Alice och Bob att insistera på mittstycket;
om snitten görs till höger om x och till vänster om y , kommer ingen av deltagarna att vilja ta mittstycket;
om snitt görs till höger om x och till höger om y (säg vid x* > x och y* > y ), så kommer både Alice och Carl att föredra de vänstra bitarna framför de högra, så Bob måste gå med på att ta den bit som ligger längst till höger. Det betyder att Bob måste utvärdera pjäsen [ x ; x* ] är minst dubbelt så stor som [ y ; y* ]. Men på grund av begränsningen av prisets densitet betyder detta att både Alice och Carl har uppskattningen [ x ; x* ] är större än [ y ; y* ], så de kommer att insistera på vänstra bitar;
det fjärde fallet (snittet till vänster om x och till vänster om y ) liknar det föregående.

För alla RMS, alla agenter i och alla konstanter finns det en något annorlunda RMS med följande egenskaper: $\varepsilon >0$

det nya måttet på agent i :s uppskattningar är helt identiskt med hans gamla uppskattningsmått;
de nya måtten på skattningar för de andra två agenterna är identiska med deras gamla måtten överallt, utom när det gäller områdena x och y . $\varepsilon$

Detta betyder att om en fråga svarar på något utanför x- och y- kvarteren har agent i inget sätt att veta om det var den gamla RMS-en eller den nya RMS-en.

Med denna kunskap är det möjligt att fördunkla vilket som helst avundsjukt divisionsprotokoll så att det varar på obestämd tid:

Låt oss börja med valfri RMS, till exempel med parametrar ; $x={\tfrac {1}{3));y={\tfrac {2}{3));s=0.3;t=0.35$
om protokollet gör snitt utanför x och y , fortsätt bara;
när protokollet ber deltagare i att göra ett klipp vid x eller y , byt till en annan RMS med och och se till att värdena är desamma som för de tidigare snitten. $x'\neq x$ $y'\neq y$

Detta protokoll kan aldrig klippa vid rätt x- och y -punkter som krävs för en avundsfri split.

Approximationer

Eftersom avundslös kakskärning med sammankopplade bitar inte kan göras på ändlig tid, måste kakskärare på något sätt försöka komma runt detta problem.

Ett tillvägagångssätt är att leta efter uppdelningar som bara är ungefär fria från avundsjuka . Det finns två sätt att definiera en approximation - i längdenheter eller i utvärderingsenheter .

Längdbaserad approximation använder följande definitioner.

En kakdelning representeras av n längder av segment som splittringen skapar. Således är (0,2;0,5;0,3) en uppdelning av enhetssegmentet i tre delintervall med längderna 0,2, 0,5 och 0,3 (partitionen bildas genom att skära enhetssegmentet vid punkterna 0,2 och 0, 7).
En multipartition är en uppsättning av flera olika partitioner. En multipartition av X sägs vara avundsfri om det finns en permutation av deltagare så att det för varje i finns ett element från X så att den i -te deltagaren föredrar det i -te segmentet. -multipartition är en multipartition där skillnaden mellan deras koordinater för varje par av partitioner inte överstiger . Till exempel: {(0.2+ ;0.5;0.3), (0.2;0.5+ ;0.3), (0.2;0.5;0.3+ )}. $\delta$ $\delta$ $\delta$ $\delta$ $\delta$

Parametern representerar deltagarnas tolerans i längdenheter. Till exempel, om en bit mark delas och deltagarna är överens om att en 0,01 meters gränsavvikelse inte spelar någon roll för dem, då är det vettigt att titta på en avundsfri 0,01-multi-partition. Deng, Key och Sabery [6] föreslog en modifiering av Simmons kakskärningsprotokoll , som innehåller en avundsfri frågebaserad multi-partition . Dessutom visade de den nedre gränsen i frågor. Även när verktygsfunktionerna ges explicit av polynomtidsalgoritmer, är avundsfri kakskärning ett hårt problem. $\delta$ $\delta$ $O[(1/\delta )^{n-2}]$ $\Omega [{\tfrac {(1/\delta )^{n-2}}{2^{(n-1)(n-2)))}]$

Värdebaserad approximation använder följande notation:

en partition X kallas avundsfri om det finns en permutation av deltagare så att för varje i värdet av den i -te biten plus inte är mindre än värdet av någon annan bit: ; $\varepsilon$ $\varepsilon$ $\forall i,j:V_{i}(X_{i})+\varepsilon \geqslant V_{i}(X_{j})$
ett utvärderingsmått sägs vara Lipschitz kontinuerlig om det finns en konstant K så att skillnaden i deras värden för något par av segment inte överstiger den K - faldiga längden av deras symmetriska skillnad . $\exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leqslant K\cdot \mathrm {length} (X_{i}\ setminus X_{j}\cup X_{j}\setminus X_{i})$

Om alla estimatormått är Lipschitz-kontinuerliga, är de två definitionerna av approximation relaterade. Låt . Då är varje partition i -multipartition utan avundsjuka -fri från avund [6] . Därför bevisar resultaten från Deng, Key och Sabury att om alla deltagare har Lipschitz kontinuerliga gränser, kan en avundsfri partition hittas med hjälp av frågor. $\varepsilon =2K\delta$ $\delta$ $\varepsilon$ $\varepsilon$ $\Theta [(1/\varepsilon )^{n-2}]$

Offlineberäkning är den andra lösningen som hittar distributionen helt utan avund, men bara för en begränsad klass av uppskattningar. Om alla utvärderingsmått är polynom med högst grad d , så finns det en algoritm som är polynom i n och d [7] . Om d ges, ber algoritmen agenter om d + 1 betygsbegäranden, vilket ger d + 1 poäng på betygsmåttet. Det är känt att d +1 punkter räcker för att interpolera ett polynom med grad d . Därför kan algoritmen interpolera alla mått på uppskattningar av alla agenter och hitta en avundsfri distribution autonomt. Antalet förfrågningar som krävs är . $O(n^{2}d)$

Att släppa är en tredje lösning som behåller kravet på att det resulterande snittet ska vara helt avundsfritt och fungerar för alla utvärderingsmått, men kravet på att hela kakan måste delas är utelämnat i detta fall. Det vill säga det är tillåtet att dela en delmängd av kakan och kassera resten. Utan ytterligare krav är problemet trivialt, eftersom det löses genom att kasta ut hela torus utan att tilldela bitar till agenter. Det verkliga målet är alltså att ge varje agent ett strikt positivt värde. Varje kakutdelning kan kännetecknas av en proportionalitetsnivå , vilket är värdet av den minst lyckligt lottade agenten. Att bryta hela kakan utan avund är också en proportionell uppdelning och proportionalitetsnivån i detta fall är inte mindre än , bästa möjliga värde. Men i det fall där släppning är aktiverat kan den avundsfria tilldelningen ha en lägre proportionalitetsnivå, och målet är att hitta en avundsfri uppdelning med högsta möjliga proportionalitet. För närvarande kända gränser: $1/n$

för 3 agenter är proportionaliteten , det vill säga att den avundsjuka uppdelningen och den proportionella uppdelningen är möjliga på en begränsad tid [8] ; $1/3$
för 4 agenter är proportionaliteten [8] ; $1/7$
för n agenter är proportionaliteten [9] . $1/(3n)$

Det är inte känt om det finns ett tidsbegränsat proportionellt delningsförfarande utan avund för fyra eller fler deltagare när det gäller sammankopplade pjäser.

Alternativ

De flesta procedurer för att skära en tårta med sammankopplade bitar förutsätter att kakan är ett endimensionellt segment och att bitarna är delintervall. Ofta är det önskvärt att bitarna har en viss geometrisk form, till exempel en kvadrat. Med en sådan begränsning kanske det inte går att dela upp hela kakan (till exempel kan en ruta inte delas i två rutor), så det måste finnas ofördelade bitar. Som förklarats ovan, när otilldelade bitar tillåts, mäts procedurer utifrån deras proportionalitetsnivå – det värde de garanterar varje deltagare. Följande är för närvarande känt [10] :

för två deltagare, när man delar en fyrkantig tårta och vill få fyrkantiga bitar, är proportionaliteten lika och detta är det bästa som kan garanteras även utan avundsjuka; $1/4$
för tre deltagare, när man delar en fyrkantig tårta och vill få fyrkantiga bitar, är proportionaliteten . Det bästa som kan garanteras i frånvaro av avund är . $1/10$ $1/6$

Frånkopplade stycken

Procedurer

För tre deltagare utför den diskreta Selfridge-Conway-proceduren en avundsjuk division med högst 5 snitt. Andra procedurer som använder rörliga knivar kräver färre snitt:

Levmores Moving Knife-procedur - Cook kräver maximalt 4 snitt;
proceduren för att rotera Brahms-Taylor-Zwicker-knivar för att skära kakan kräver inte mer än 3 snitt (detta är resultatet för tre anslutna bitar när kakan är en cirkel, men i fallet med en kaka i form av ett segment där kommer att vara fyra stycken);
med Austins "Moving Knife"-procedur för två deltagare kan man få en avundsfri separation för 3 deltagare med högst 3 snitt. Denna idé tillskrivs William Webb [11] .

För fyra deltagare utför Brahms-Taylor-Zwicker-proceduren division utan avundsjuka med högst 11 snitt [12] . För fem deltagare gör Sabery och Wangs förfarande uppdelning utan avund till ett begränsat antal snitt [13] . Båda dessa procedurer använder Austin-proceduren för två deltagare och gemensamma divisioner som det första steget. Därför bör dessa procedurer betraktas som oändliga - de kan inte slutföras i ett begränsat antal steg.

För fyra eller fler deltagare finns det tre algoritmer som är ändliga men inte begränsade - det finns ingen fast gräns för antalet nödvändiga klipp [14] . Det finns tre sådana algoritmer:

Brahms-Taylor-proceduren , först publicerad i en tidning från 1995 och senare i en bok från 1996;
Robertson-Webb-protokollet , först publicerat i en artikel från 1997 och senare i en bok från 1998;
Pikhurkos protokoll [15] publicerades 2000.

Även om protokollen skiljer sig åt, förblir deras huvudidé liknande - vi delar upp kakan i ett ändligt, men inte begränsat, antal "smulor", som var och en är så liten att alla deltagare försummar dess värde. Sedan kombinerar vi smulorna på ett sofistikerat sätt för att få önskad uppdelning. William Gassar jämförde tre obegränsade algoritmer med hjälp av ordningstal [16] .

Frågan om kakskärning kan göras utan avundsjuka på en begränsad tid för fyra eller fler deltagare har varit ett öppet problem i många år. Det löstes slutligen 2016 av Hariz Aziz och Simon McKenzie. Till en början utvecklade de en tidsbegränsad algoritm för fyra deltagare [17] . De utökade sedan sin algoritm till att fungera med valfritt antal deltagare [9] . Deras algoritm kräver inga fler frågor. Även om antalet är begränsat är det väldigt långt från den nedre gränsen . Så frågan om hur många frågor som krävs för att skära kakan utan avund förblir öppen. ${\displaystyle n^{n^{n^{n^{n^{n))))))))$ $\Omega (n^{2})$

Approximationer och dellösningar

En stängd version av det sista ned-protokollet hittar en avundsfri additiv approximation av partitionen på en begränsad tid. Speciellt för varje konstant returnerar algoritmen en partition där värdet för varje medlem är åtminstone det största värdet minus , i tiden . $\varepsilon >0$ $\varepsilon$ $n^{2}/\varepsilon$

Om alla mått är bitvis linjära , finns det en algoritm [18] som är polynom i storleken på representationen av utvärderingsfunktionerna . Antalet av hans förfrågningar är , där är lika med antalet luckor i derivatorna av skattningsdensitetsfunktionerna. $O(n^{6}k\ln {k})$ $k$

Resultat efter svårighetsgrad

Varje avundsjuk delningsförfarande för n personer kräver åtminstone förfrågningar [19] . Beviset bygger på noggrann analys av mängden information algoritmen har från varje deltagare. $\Omega (n^{2})$

Antag att kakan är ett endimensionellt intervall [0;1], och att värdet på hela kakan för var och en av deltagarna är normaliserat till 1. Vid varje steg ber algoritmen en viss deltagare att antingen utvärdera ett visst intervall som ingår i [0;1], Eller markera intervallet med ett specifikt värde. I båda fallen samlar algoritmen endast in information om de intervall vars slutpunkter nämndes i förfrågan eller i svaret. Låt oss kalla dessa slutpunkter för milstolpar . Inledningsvis är milstolparna för i bara 0 och 1, eftersom algoritmen bara vet om deltagare i att . Om algoritmen ber deltagare i att utvärdera [0,2;1], är milstolparna för i efter svaret {0;0,2;1}. Algoritmen kan beräkna , men inte vilket intervall som helst vars slutpunkt skiljer sig från 0,2. Antalet milstolpar ökar med max 2 för varje fråga. I synnerhet kan värdet på segmentet [0;0,2] koncentreras nära 0, eller nära 0,2, eller någonstans mellan dessa värden. $v_{i}([0;1])=1$ $v_{i}([0;0,2])$

Intervallet mellan två på varandra följande milstolpar för medlem i kallas milstolpsintervallet för medlem i . När algoritmen bestämmer sig för att allokera en tårta till medlem i , måste den tilldela en bit vars totalpoäng för i inte är mindre än någon av medlem i. milstolpeintervall . Bevis genom motsägelse - anta att det finns ett visst intervall av milstolpar J vars värde för i är större än det faktiska värdet som tilldelats medlem i . Någon annan deltagare, säg j , kommer nödvändigtvis att få någon del av milstolpsintervallet J . Enligt punkt A finns det en möjlighet att hela värdet av intervallet J är koncentrerat inuti den del som tilldelats deltagaren j . Då kommer jag att avundas j och partitionen kommer inte att vara fri från avund.

Låt oss anta att alla deltagare svarade på alla frågor som om deras poäng var homogena (det vill säga värdet på intervallet är lika med dess längd). Enligt punkt B kan algoritmen tilldela en bit till deltagare i endast om den är längre än alla milstolpsintervall för deltagare i . Minst deltagarna måste få ett intervall som inte är längre än 2/ n . Därför måste alla deras milstolpsintervall ha längder som inte överstiger 2/ n . Därför måste de ha minst milstolpsintervall, och därför måste antalet milstolpar vara minst . ${\tfrac {n}{2))$ ${\tfrac {n}{2))$ ${\tfrac {n}{2))$

Varje fråga som besvaras av deltagare i introducerar högst två nya slutpunkter, så att antalet milstolpar för deltagare i ökar med högst 2. Därför, i det fall som beskrivs i punkt C, måste algoritmen polla var och en av deltagarna, vilket ger minst minst n /4 frågor. Det totala antalet frågor blir då inte mindre än . ${\tfrac {n}{2))$ ${\tfrac {n^{2}}{8}}=\Omega (n^{2})$

Det är fortfarande en öppen fråga om det finns en begränsad algoritm för godtyckliga utvärderingsfunktioner. Det finns alltså ett stort gap mellan den nedre gränsen och den bästa algoritmen som för närvarande är känd, som är ändlig men inte begränsad. $\Omega (n^{2})$

Existensbevis och varianter

Förutom existensbevisen i den allmänna formen som följer av algoritmerna som beskrivs ovan, finns det bevis för att det finns avundsfria partitioner med ytterligare egenskaper:

det finns en exakt division , som i synnerhet är fri från avundsjuka ( Dubins-Spaniers satser );
det finns en avundsfri distribution som också är Pareto-effektiv ( Wellers teorem ).

Båda bevisen fungerar endast för additiva icke-atomära värderingsåtgärder och förlitar sig på möjligheten att allokera ett stort antal frånkopplade bitar till varje deltagare.

Avundsjuk division med olika andelar

En generalisering av icke-avundskriteriet är att tillåta varje deltagare att ha olika andelar. Det vill säga, för varje deltagare i finns det en vikt som beskriver andelen av kakan som han är tilldelad att tillhandahålla (summan av alla andelar w i är lika med 1). Då definieras en viktad avundsfri partition enligt följande. För varje agent i med ett mått på uppskattningar och för alla andra agenter k : $w_{i}$ $V_i$

${\displaystyle V_{i}(X_{i})/w_{i}\geqslant V_{i}(X_{j})/w_{j))$

Det vill säga att varje deltagare anser att den av honom tilldelade andelen, motsvarande hans förväntade andel, inte är mindre än den tilldelade andelen, motsvarande den förväntade andelen för andra deltagare.

När alla vikter fortfarande är desamma (och lika ), reduceras denna definition till standarddefinitionen av icke-avundsjuka. ${\tfrac {1}{n))$

Om bitarna kan kopplas bort finns det alltid en viktad avundsfri partition som kan hittas med Robertson-Webb-protokollet för vilken uppsättning vikter som helst. Zeng föreslog en alternativ algoritm för avundslös ungefärlig viktad partitionering som kräver ett litet antal klipp [20] .

Men när bitarna måste kopplas, kanske en viktad avundsfri partition inte existerar. För att förstå detta, notera att alla avundsfria viktade partitioner också viktas proportionellt med samma viktvektor. Detta betyder att varje agent i med ett mått på uppskattningar Vi :

$V_{i}(X_{i})/w_{i}\geqslant V_{i}(C)$

Det är känt att en viktad proportionell fördelning med sammankopplade bitar kanske inte existerar: se till exempel proportionell uppdelning av en kaka med olika delar .

Observera att det finns en alternativ definition av en viktad fördelning utan avund, där vikterna tilldelas pjäserna och inte till agenterna. För denna definition är det känt att en viktad avundsfri fördelning finns i följande fall (varje fall generaliserar föregående fall):

additiv utvärderingsfunktioner, endimensionell kaka (segment), bitar måste kopplas segment [21] ;
additiv utvärderingsfunktioner, flerdimensionell kaka som en simplex , bitar måste vara förenklade [22] . Beviset använder Sperner-satsen , Knaster-Kuratowski-Mazurkiewicz-lemmat , Gale-täckande lemma och Ki Fan coinciding points lemma ;
icke-additiva utvärderingsfunktioner, flerdimensionell simplexkaka , bitar måste vara polyedrar [23] .

Dela den "dåliga" kakan

I vissa fall har den delbara "kakan" ett negativt värde. Det kan till exempel vara en bit gräsmatta som ska klippas, eller en bit ödemark som ska röjas. I det här fallet är kakan ett "heterogent dåligt" och inte ett "heterogent goda".

Vissa avundsfria kakskärningsprocedurer kan anpassas för sådana smala kakor, men anpassningen är ofta inte trivial.

Finaltabeller

Förfaranden efter resultat

namn	Sorts	Kaka	bitar	Antal deltagare ( n )	Antal förfrågningar	Antal snitt	avundas	Proportionalitet [24]	Kommentarer
Delhi-och-välj	diskret procedur	Några	budbärare	2	2	1 (optimalt)	Inte	1/2
Stromquist	Procedur för att flytta kniv	Linjesegmentet	budbärare	3	$\infty$	2 (optimalt)	Inte	1/3
Selfridge-Conway	diskret procedur	Några	Osammanhängande	3	9	5	Inte	1/3
Brahms-Taylor-Zwicker	Procedur för att flytta kniv	Några	Osammanhängande	fyra	$\infty$	elva	Inte	1/4
Sabury-Wonga [13]	diskret procedur	Några	Osammanhängande	fyra	Begränsad	Begränsad	Inte	1/4	möjlig kasserad bit
Aziza - Mackenzie [17]	diskret procedur	Några	Osammanhängande	fyra	203	584	Inte	1/4
Sabury-Wonga [13]	Procedur för att flytta kniv	Några	Osammanhängande	5	$\infty$	Begränsad	Inte	1/5
Stromquist	Existens	Linjesegmentet	budbärare	n	—	n −1	Inte	1/ n
Simmons	diskret procedur	Linjesegmentet	budbärare	n	$\infty$	n −1	Inte	1/ n
Denga - Key - Sabury	diskret procedur	Linjesegmentet	budbärare	n	$\left({\frac {1}{\varepsilon }}\right)^{n-2}$	n −1	$\varepsilon$	$\left({\tfrac {1}{n}}\right)-\varepsilon$	Endast när gränserna är Lipschitz kontinuerliga
Branzei [7]	diskret procedur	Linjesegmentet	budbärare	n	$n^{2}d$	okänd	Inte	1/ n	Endast när estimatordensiteten är polynom med maximal grad d .
" Skynda dig - få folk att skratta "	diskret procedur	Linjesegmentet	budbärare	3	9	fyra	Inte	1/3	Eventuell kasserad bit
" Skynda dig - få folk att skratta "	diskret procedur	Några	budbärare	fyra	16	6	Inte	1/7	Eventuell kasserad bit
" Skynda dig - få folk att skratta "	diskret procedur	Några	budbärare	n	$2^{n}$	$2^{n-1}-1$	Inte	${\displaystyle {\frac {1}{2^{n-1))))$	Eventuell kasserad bit
Aziza - Mackenzie ConnectedPieces [9]	diskret procedur	Några	budbärare	n	$n^{n+1}$	$n^{n+1}$	Inte	${\frac {1}{3n))$	Eventuell kasserad bit
Brahms - Taylor	diskret procedur	Några	Osammanhängande	n	Inte begränsad	Inte begränsad	Inte	1/ n
Robertson-Webb	diskret procedur	Några	Osammanhängande	n	Inte begränsad	Inte begränsad	Inte	1/ n	Viktad avundsfri partition
Pikhurko [15]	diskret procedur	Några	Osammanhängande	n	Inte begränsad	Inte begränsad	Inte	1/ n
Aziza - Mackenzie [9]	diskret procedur	Några	Osammanhängande	n	${\displaystyle n^{n^{n^{n^{n^{n))))))))$	${\displaystyle n^{n^{n^{n^{n^{n))))))))$	Inte	1/ n
Sluten slinga version av det senast reducerade protokollet	diskret procedur	Linjesegmentet	Osammanhängande	n	$n^{2}/\varepsilon$	okänd	$\varepsilon$	1/ n
Kurokawa - Leia - Prokachi [18]	diskret procedur	Linjesegmentet	Osammanhängande	n	$n^{6}k\ln k$	okänd	Inte	1/ n	Endast när värdet på densiteterna är bitvis linjärt med maximalt k diskontinuiteter.
Weller	Existens	Några	Osammanhängande	n	—	$\infty$	Inte	1/ n	Pareto effektiv .
2D	diskret procedur	Fyrkant	Förbundna och fyrkantiga	2	2	2	Inte	1/4	Eventuell kasserad bit
2D	Procedur för att flytta kniv	Fyrkant	Förbundna och fyrkantiga	3	$\infty$	6	Inte	1/10	Eventuell kasserad bit

Finalbordet efter antal deltagare och typ av bitar:

antal ombud	Förbundna delar	Allmänna bitar
2	Delhi-och-välj
3	Stromkvists "Moving Knife"-procedur (oändlig tid); " Skynda dig - få folk att skratta " (begränsad tid, begränsat antal klipp, kasserad bit möjlig, proportionell)	Diskret Selfridge-Conway-procedur (begränsad tid, högst 5 snitt).
fyra	" Om du skyndar dig kommer du att få folk att skratta " (begränsad tid, begränsat antal klipp, en kasserad bit är möjlig, proportionalitet 1/7).	Brahms-Taylor-Zwicker-procedur (oändlig tid, inte mer än 11 snitt). Diskret Sabery-Wong-procedur [13] (begränsad tid, begränsat antal snitt, kasserad bit möjlig, proportionell). Aziz-Mackenzie diskret procedur [17] (begränsad tid, begränsat antal snitt, proportionell).
5		Sabury-Wongs "Moving Knife"-procedurer [13] (oändlig tid, begränsat antal snitt).
n	Simmons protokoll (oändlig tid) Deng-Ki-Sabury (ungefär avundsjuk, exponentiell tid). " Skynda dig - få folk att skratta " (helt fri från avund, exponentiell tid, möjlighet att tappa bit, exponentiell proportionalitet) ConnectedPieces Aziz - Mackenzie [9] (helt fri från avund, exponentiell tid, möjlighet att tappa bit, linjär proportionalitet)	Brahms & Taylor (1995) ; Robertson & Webb (1998) . Båda algoritmerna kräver ett begränsat men inte begränsat antal snitt. Diskret Aziz-Mackenzie-procedur [9] (begränsad tid, begränsat antal snitt, proportionell uppdelning).
Svårighet	Alla algoritmer för måste vara oändliga (Stromquist, 2008). $n\geqslant 3$	Alla algoritmer måste använda minst steg (Procaccia, 2009). $\Omega (n^{2})$
alternativ	En viktad avundsfri partition finns för godtyckliga vikter (Idzik, 1995), även när kakan och bitarna är förenklade (Idzik, Ichiishi, 1996), och även med icke-additiva preferenser (Dall'Aglio och Maccheroni, 2009).	Robertson-Webb-protokollet kan hitta en viktad avundsfri partition för godtyckliga vikter. En perfekt uppdelning finns (Dubins & Spanier, 1961). Det finns en avundsfri och effektiv kakskärning ( Wellers sats ).

Se även

Anteckningar

↑ Översätts ofta ordagrant från engelska som Avundsfri kakskärning , även om det är avundsjuka som spelar en nyckelroll i denna uppdelning. Artikeln använder termen "avundsjuk uppdelning", men resultatet av denna uppdelning måste vara en avundsfri distribution .
↑ Gamow, Stern, 1958 .
↑ Stromquist, 1980 , sid. 640–644.
↑ Stromquist, 2008 .
↑ Stromkvists "Moving Knife"-procedur kräver att agenter flyttar sina knivar medan domaren flyttar sitt svärd. Eftersom svärdets rörelse är kontinuerlig, är antalet steg som krävs oräkneligt (och därför, naturligtvis, oändligt). Simmons kakskärningsprotokoll konvergerar till en avundsfri partition, men kan kräva ett oändligt antal steg.
↑ 1 2 Deng, Qi, Saberi, 2012 , sid. 1461–1476
↑ 12 Brânzei , 2015 , sid. 93–95.
↑ 1 2 Segal-Halevi, Hassidim, Aumann, 2016 , sid. 1–32.
↑ 1 2 3 4 5 6 Aziz, MacKenzie, 2016 .
↑ Segal-Halevi, Hassidim, Aumann, 2015 , sid. 1021–1028.
↑ Brams och Taylor 1996 , sid. 124–125.
↑ Brams, Taylor, Zwicker, 1997 , sid. 547–555.
↑ 1 2 3 4 5 Saberi, Wang, 2009 .
↑ SJ Brams, MA Jones, C. Klamler, "Bättre sätt att skära en tårta", Notices of the AMS, 2005. [Online]. Tillgänglig: http://www.ams.org/notices/200611/fea-brams.pdf Arkiverad 30 september 2019 på Wayback Machine
↑ 1 2 Pikhurko, 2000 , sid. 736–738.
↑ Gasarch, William, Vilket Unbounded Protocol for Envy Free Cake Cutting är bättre?, arΧiv : 1507.08497 [math.LO].
↑ 1 2 3 Aziz, MacKenzie, 2016 , sid. 454.
↑ 1 2 Kurokawa, Lai, Procaccia, 2013 .
↑ Procaccia, 2009 , sid. 239–244.
↑ Zeng, 2000 , sid. 259–271.
↑ Idzik, 1995 .
↑ Ichiishi, Idzik, 1999 , sid. 389–400.
↑ Dall'Aglio, MacCheroni, 2009 , sid. 57–77.
↑ Värdet (som andel av hela kakan) som garanteras för varje agent enligt additiva uppskattningar. När det inte finns någon avund och hela kakan är uppdelad, är proportionaliteten alltid den bästa möjliga. ${\tfrac {1}{n))$

Litteratur

George Gamow, Marvin Stern. Pussel-matte . - 1958. - ISBN 978-0670583355 .
Walter Stromquist. Hur man skär en tårta rättvist // The American Mathematical Monthly. - 1980. - T. 87 , nr. 8 . - doi : 10.2307/2320951 . — .
Walter Stromquist. Avundsfria kakindelningar kan inte hittas med ändliga protokoll // Electronic Journal of Combinatorics. - 2008. Arkiverad 11 mars 2016.
Deng X., Qi Q., Saberi A. Algoritmiska lösningar för avundsfri kakskärning // Operations Research. - 2012. - T. 60 , nr. 6 . doi : 10.1287 / opre.1120.1116 .
Brânzei S. En anteckning om avundsfri kakskärning med polynomvärderingar // Information Processing Letters. - 2015. - T. 115 , nr. 2 . - doi : 10.1016/j.ipl.2014.07.005 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Avundsfri kakskärning i två dimensioner // Den 29:e AAAI-konferensen om artificiell intelligens (AAAI-15). - Austin, Texas, 2015. - doi : 10.13140/RG.2.1.5047.7923 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Avfall gör brådska // ACM-transaktioner på algoritmer. - 2016. - T. 13 . - doi : 10.1145/2988232 . - arXiv : 1511.02599 .
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 .
Amin Saberi, Ying Wang. Skär en tårta för fem personer // Algoritmiska aspekter inom information och ledning. - 2009. - doi : 10.1007/978-3-642-02158-9_25 .
Pikhurko O. On Envy-Free Cake Division // The American Mathematical Monthly. - 2000. - T. 107 , nr. 8 . - doi : 10.2307/2695471 . — .
Haris Aziz, Simon MacKenzie. Ett diskret och begränsat avundsfritt kakskärningsprotokoll för fyra agenter // Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. - 2016. - ISBN 9781450341325 . - doi : 10.1145/2897518.2897522 .
Haris Aziz, Simon MacKenzie. Ett diskret och begränsat avundsfritt kakskärningsprotokoll för valfritt antal agenter // FOCS 2016. - 2016.
David Kurokawa, John K. Lai, Ariel D. Procaccia. Hur man skär en tårta innan festen slutar // AAAI. — 2013.
Ariel Procaccia. Thou Shalt Covet Your Neighbour's Cake // IJCAI'09 Proceedings of the 21st International Joint Conference on Artificiell Intelligens. — 2009.
Dao Zhi Zeng. Ungefärliga avundsfria procedurer // Spelövning: Bidrag från tillämpad spelteori . - Springer, 2000. - Vol. 23. - (Teori- och beslutsbibliotek). — ISBN 9781461546276 . - doi : 10.1007/978-1-4615-4627-6_17 .
Adam Idzik. Optimala indelningar av enhetsintervallet // Internationell konferens till ära av Robert J. Aumann på hans 65:e födelsedag. — Jerusalem, 1995.
Ichiishi T., Idzik A. Rättvis fördelning av delbara varor // Journal of Mathematical Economics. - 1999. - T. 32 , nr. 4 . - doi : 10.1016/s0304-4068(98)00053-6 .
Dall'Aglio M., MacCheroni F. Omtvistade länder // Spel och ekonomiskt beteende. - 2009. - T. 66 . - doi : 10.1016/j.geb.2008.04.006 .
Steven J. Brams, Alan D. Taylor. Rättvis uppdelning: från tårtskärning till tvistlösning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .

Länkar

Fair Division Calculator - En avundsfri divisionskalkylator för tårtor, plikter, hushållning och hyra.