Avundsfri tårtskärning

En avundsfri tårtskärning är en sorts rättvis tårtskärning . Det är en uppdelning av en heterogen resurs ("kaka") som uppfyller det avundsfria kriteriet, nämligen att varje partner upplever att deras tilldelade andel är minst lika bra som vilken annan andel som helst, enligt deras egen subjektiva värdering.

Olöst problem inom datavetenskap :

Vad är runtime-komplexiteten av avundsfri kakskärning?

(fler olösta problem inom datavetenskap)

När det bara finns två partners är problemet lätt och löstes i antiken genom skilje- och välj- protokollet. När det finns tre eller fler partners blir problemet mycket mer utmanande.

Två huvudvarianter av problemet har studerats:

Anslutna delar , t.ex. om kakan är ett 1-dimensionellt intervall måste varje partner få ett enda delintervall. Om det finns ${\displaystyle n} -partners,$ behövs endast ${\displaystyle n-1} snitt.$
Allmänna stycken , t.ex. om kakan är ett 1-dimensionellt intervall kan varje partner få en förening av osammanhängande delintervall.

Kort historia

Modern forskning om det rättvisa kakskärningsproblemet startade på 1940-talet. Det första rättvisekriteriet som studerades var proportionell delning , och en procedur för n partners hittades snart.

Det starkare kriteriet för avundsfrihet infördes i kakskärningsproblemet av George Gamow och Marvin Stern på 1950-talet.

En procedur för tre partners och allmänna pjäser hittades 1960. En procedur för tre partners och anslutna pjäser hittades först 1980.

Avundsfri uppdelning för fyra eller fler partners hade varit ett öppet problem fram till 1990-talet, då tre förfaranden för allmänna stycken och ett förfarande för anslutna stycken publicerades. Alla dessa procedurer är obegränsade - de kan kräva ett antal steg som inte är avgrä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 avundsfrihetens komplexitet under körtid publicerades på 2000-talet.

För allmänna pjäser är den nedre gränsen Ω( n ² ) .
För sammankopplade pjäser är den nedre gränsen oändlighet – det finns bevisligen inget ändligt protokoll för tre eller flera partners.

Under 2010-talet publicerades flera tillnärmningsförfaranden och förfaranden för specialfall . Frågan om det finns förfaranden med begränsad tid för fallet med allmänna pjäser hade varit öppen länge. Problemet löstes slutligen 2016. Haris Aziz och Simon Mackenzie presenterade ett diskret avundsfritt protokoll som kräver högst $n^{n^{n^{n^{n^{n} }}}}$ frågor. Det finns fortfarande ett mycket stort gap mellan den nedre gränsen och proceduren. Från och med augusti 2016 är den exakta runtime-komplexiteten av avundsfrihet fortfarande okänd.

För fallet med sammankopplade bitar noterades att hårdhetsresultatet förutsätter att hela kakan måste delas. Om detta krav ersätts av det svagare kravet att varje partner får ett proportionellt värde (minst 1/ n av det totala kakvärdet enligt deras egen värdering), så är ett begränsat förfarande för tre partners känt, men det har förblivit öppet. problem om det finns tidsbegränsade förfaranden för fyra eller flera partners.

Förbundna delar

Existens bevis

En avundsfri uppdelning för n agenter med anslutna delar existerar alltid under följande milda antaganden:

Ingen agent föredrar en tom pjäs framför en icke-tom pjäs.
Agenternas preferenser är kontinuerliga.

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

Huvudkonceptet i beviset är det simplex av partitioner . Antag att kakan är intervallet [0,1]. Varje partition med anslutna delar kan representeras unikt av n − 1 siffror i [0,1] som representerar klippplatserna. Föreningen av alla partitioner är en simplex.

För varje partition har varje agent en eller flera bitar som de svagt föredrar. Till exempel, för partitionen representerad av "0.3,0.5", kan en agent föredrar del #1 (biten [0,0.3]) medan en annan agent kanske föredrar del #2 (biten [0.3,0.5]) medan en tredje agent kanske föredrar både bit #1 och bit #2 (vilket betyder att de är likgiltiga mellan dem men gillar någon av dem mer än bit #3).

För varje agent täcks partitionssimplexet av n delar, eventuellt överlappande vid 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 bit i , medan i gränsen för del i föredrar agenten även några andra bitar. Så för varje i finns det ett visst område i partitionssimplexet där åtminstone en agent föredrar endast bit i . Kalla denna region U _i . Med hjälp av ett visst topologiskt lemma (som liknar Knaster–Kuratowski–Mazurkiewicz-lemmat ), är det möjligt att bevisa att skärningspunkten mellan alla U _i är icke-tom. Därför finns det en partition där varje del är en agents unika preferens. Eftersom antalet bitar är lika med antalet agenter kan vi allokera varje bit till den agent som föredrar det och få en avundsfri tilldelning.

Förfaranden

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

Stromquists rörliga knivar använder fyra knivar som rör sig samtidigt - en flyttad av en domare och en annan för varje agent.
Barbanel–Brams rörliga knivar använder två knivar som rör sig samtidigt.
Robertson -Webb roterande kniv-proceduren kan användas när kakan är tvådimensionell och endast använder en enda rörlig kniv.

Dessa är kontinuerliga procedurer - de förlitar sig på att människor flyttar knivar kontinuerligt och samtidigt. De kan inte utföras i ett begränsat antal diskreta steg.

För n agenter kan en avundsfri division hittas av Simmons kakskärningsprotokoll . Protokollet använder ett simplex av partitioner som liknar den som används i Stromquists existensbevis. Den genererar en sekvens av partitioner som konvergerar till en avundsfri partition. Konvergensen kan ta oändligt många steg.

Det är inte en slump att alla dessa algoritmer kan kräva oändligt många frågor. Som vi visar i följande underavsnitt kan det vara omöjligt att hitta en avundsfri kakskärning med sammankopplade bitar med ett begränsat antal frågor.

Hårdhetsresultat

En avundsfri division med anslutna delar för 3 eller fler agenter kan inte hittas av ett ändligt protokoll i frågemodellen Robertson–Webb . Anledningen till att detta resultat inte motsäger de tidigare nämnda algoritmerna är att de inte är ändliga i matematisk mening.

Omöjlighetsbeviset använder ett rigid måttsystem (RMS) – ett system med n värdemått, för vilket en avundsfri division måste skära kakan på mycket specifika platser. Sedan, att hitta en avundsfri division minskar till att hitta dessa specifika platser. Om man antar att kakan är det verkliga intervallet [0,1], är det att hitta en avundsfri division med hjälp av frågor till agenterna lika med att hitta ett reellt tal i intervallet [0,1] med ja/nej-frågor. Detta kan kräva ett oändligt antal frågor.

En RMS för tre medel kan konstrueras enligt följande. Låt x , y , s och t vara parametrar som uppfyller:

$0<x<y<1,$
$1/3<t<1/2,$
$s+2t=1.$

Konstruera en uppsättning av tre mått med dessa två egenskaper:

Densiteten för varje mått är alltid strikt mellan √ 2 /2 och √ 2 (så för en given bit skiljer sig agenternas värderingar med en faktor som är mindre än 2).
Värdena på bitarna som bestäms av x och y är som i tabellen:

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

Sedan måste varje avundsfri division bland Alice Bob och Carl ha snitt vid x och y (det finns exakt två sådana divisioner), eftersom alla andra alternativ leder till avundsjuka:

Om x* ≥ x och y* ≤ y , och en av ojämlikheterna är strikt, så värderar alla antingen den högra pjäsen eller den vänstra pjäsen mer än mitten, så den som får mitten kommer att bli avundsjuk.
Om x* ≤ x och y* ≥ y , och en av ojämlikheterna är strikt, så föredrar både Alice och Bob mittstycket framför vilken annan pjäs som helst, så den som inte får ut den av de två kommer att bli avundsjuk på den andra .
Om snitt görs till höger om x och till höger om y (säg, vid x* > x och y* > y ), så föredrar både Alice och Carl den vänstra biten framför den högra biten, så Bob måste acceptera att acceptera stycket längst till höger. Det betyder att Bob måste värdera pjäsen [ x , x* ] minst dubbelt så mycket som [ y , y* ]. Men på grund av begränsningen av värdedensiteterna betyder det att både Alice och Carl värderar [ y , y* ] mindre än dubbelt så mycket som [ x , x* ], så de insisterar på den vänstra biten.
Det fjärde fallet (skär till vänster om x och till vänster om y ) är analogt.

För varje RMS, varje agent i och varje konstant ε>0, finns det en något annorlunda RMS med följande egenskaper:

Det nya värdemåttet på agent i är helt identiskt med hans gamla värdemått;
De nya värdemåtten för de andra två agenterna är identiska med deras gamla värdemått överallt utom i en ε-grannskap av x och y .

Detta innebär att om alla frågor som besvarats hittills var utanför ε -grannskapet av x och y , så har agent i inget sätt att veta om vi är i det gamla RMS eller i det nya RMS.

Utrustad med denna kunskap kan en motståndare lura alla avundsfria divisionsprotokoll att fortsätta för evigt:

Börja med valfri RMS, t.ex. med parametrarna x = 1/3, y = 2/3, s = 0,3 och t = 0,35.
Så länge som protokollet gör nedskärningar vid andra punkter än x och y , låt det fortsätta.
Närhelst protokollet ber agent i att göra ett snitt vid x eller y , byt till en annan RMS med x'≠x och y'≠y , och se till att värdena är desamma för alla tidigare gjorda snitt.

Således kan protokollet aldrig göra snitt vid rätt x och y som krävs för en avundsfri division.

Uppskattningar

Eftersom tårtskärning utan avundsjuka med sammankopplade bitar inte kan göras på ändlig tid, har kakskärare försökt hitta lösningar.

En lösning är att leta efter divisioner som bara är ungefär-avundsfria . Det finns två sätt att definiera approximationen - i längdenheter eller i värdeenheter .

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

En partition av en kaka representeras av de n längderna av intervaller som den skapar. Så (0,2,0,5,0,3) är en uppdelning av enhetsintervallet till tre delintervall med längderna 0,2, 0,5 och 0,3 (det genereras genom att skära enhetsintervallet vid 0,2 och vid 0,7).
En multi-partition är en uppsättning av flera olika partitioner.
En multipartition X kallas avundsfri om det finns en permutation av partnerna så att det för varje i finns ett element av X så att den i -te partnern föredrar det i -te segmentet.
En δ-multipartition är en multipartition där, för varje par av partitioner, skillnaden mellan var och en av deras koordinater är högst δ . Till exempel: {(0,2+ δ ,0,5,0,3), (0,2,0,5+ δ ,0,3), (0,2,0,5,0,3+ δ )}.

Parametern δ representerar partnernas tolerans i längdenheter. T.ex. om mark delas och partnerna är överens om att en skillnad på 0,01 meter i gränsens läge inte är relevant för dem, är det vettigt att leta efter en 0,01-multi-partition som är avundsfri. Deng presenterar överhuvudtaget en modifiering av Simmons kakskärningsprotokoll som hittar en avundsfri δ -multi-partition med $O[(1/\delta )^{n -2}]$ frågor. Dessutom bevisar de en nedre gräns för $\Omega [(1/\delta )^{n-2}/ 2^{(n-1)(n-2)}]$ frågor. Även när verktygsfunktionerna ges explicit av polynomtidsalgoritmer, är det avundsfria kakskärningsproblemet PPAD -komplett.

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

En partition X kallas ε-avundsfri om det finns en permutation av partnerna så att, för varje i , värdet av den i -te biten plus ε är minst lika mycket som värdet av någon annan del: $\forall i,j:V_{i}(X_{i})+\varepsilon \geq V_{i}(X_{j })$ .
Ett värdemått kallas Lipschitz-kontinuerligt om det finns en konstant K så att skillnaden i värden mellan dem för vilket par av intervall som helst är högst K gånger längden på deras symmetriska skillnad $\exists K:\forall j:|V_{i}(X_{i})-V_{i}( X_{j})|\leq K\cdot \mathrm {längd} (X_{i}\setminus X_{j}\cup X_{j}\setminus X_{i})$ .

Om alla värdemått är Lipschitz-kontinuerliga, är de två approximationsdefinitionerna relaterade. Låt $\epsilon =2K\delta$ . Sedan är varje partition i en avundsfri δ -multipartition ε -avundsfri. Därför bevisar Deng et al.s resultat att, om alla partners har Lipschitz-kontinuerliga värderingar, kan en ε -avundsfri partition hittas med $\Theta [( 1/\epsilon )^{n-2}]$ frågor med allmänna värderingar.

Med additiva värderingar, för alla ε > 0, kräver en ε-avundsfri ansluten kakskärning minst Ω(log ε ⁻¹ ) frågor. För 3 agenter finns ett O(log ε ^{−1 )-protokoll.} För 4 eller fler agenter kräver det mest kända protokollet O( n ε ⁻¹ ), vilket visar ett exponentiellt gap i frågekomplexiteten. Dessutom, även om det senare protokollet har frågekomplexitetspolynom i n , är dess beräkningskomplexitet exponentiell i n , även för konstant ε. Om polynom-tidsberäkning krävs är den mest kända approximationen $\displaystyle 1/3}$ {

Offlineberäkning är en andra lösning som hittar en helt avundsfri uppdelning men bara för en begränsad klass av värderingar. Om alla värdemått är polynom med högst grad d , finns det en algoritm som är polynom i n och d . Givet d frågar algoritmen agenterna d +1 utvärderingsfrågor, som ger d +1 poäng i grafen för värdemåttet. Det är känt att d +1 punkter är tillräckliga för att interpolera ett polynom med grad d . Därför kan algoritmen interpolera hela värdemåtten för alla agenter och hitta en avundsfri division offline. Antalet obligatoriska frågor är $O(n^{2}d)$ .

En annan begränsning för värderingarna är att de är styckvis konstanta - för varje agent finns det högst m önskade intervall, och agentens värdedensitet i varje intervall är konstant. Under detta antagande kan en ansluten avundsfri allokering hittas genom att lösa ${\displaystyle {\frac {n\cdot (2mn+n-1)!}{(2mn)!}}\in O(m^{n})} linjära program$ . Således, när n är konstant, är problemet polynom i m .

Fri förfoganderätt är en tredje omgång som håller kravet på att indelningen ska vara totalt avundsfri och fungerar för alla värdemått, men släpper kravet på att hela kakan ska delas. Dvs det gör det möjligt att dela en delmängd av kakan och kassera resten. Utan ytterligare krav är problemet trivialt, eftersom det alltid är avundsfritt att inte ge någonting till alla agenter. Det verkliga målet är alltså att ge varje agent ett strikt positivt värde. Varje kaktilldelning kan kännetecknas av dess proportionalitetsnivå, vilket är värdet av den minst lyckligt lottade agenten. En avundsfri uppdelning av hela kakan är också en proportionell uppdelning , och dess proportionalitetsnivå är minst ${\displaystyle 1/n} ,$ vilket är det bästa möjliga. Men när fritt förfogande tillåts kan en avundsfri indelning ha en lägre proportionalitetsnivå, och målet är att hitta en avundsfri indelning med högsta möjliga proportionalitet. De för närvarande kända gränserna är:

För 3 agenter är proportionaliteten ${\displaystyle 1/3} ,$ dvs en avundsfri och proportionell division kan uppnås i begränsad tid.
För 4 agenter är proportionaliteten $\displaystyle 1/7$ }
För n agenter är proportionaliteten $1/(3n)$ .

Det är inte känt om det finns en tidsgränsad avundsfri och proportionell uppdelningsprocedur för fyra eller flera partners med sammankopplade bitar.

Varianter

De flesta procedurer för tårtskärning med sammankopplade bitar förutsätter att kakan är ett 1-dimensionellt intervall och att bitarna är 1-dimensionella delintervall. Ofta är det önskvärt att bitarna har en viss geometrisk form, till exempel en kvadrat. Med sådana begränsningar kan det vara omöjligt att dela upp hela kakan (t.ex. kan en kvadrat inte delas i två rutor), så vi måste tillåta fri förfogande. Som förklarats ovan mäts förfarandena, när fritt förfogande är tillåtet, utifrån deras proportionalitet - det värde som de garanterar alla ombud. Följande resultat är för närvarande kända:

${\displaystyle 1/4} ,$ och vill ha kvadratiska bitar är proportionaliteten och detta är det bästa som kan garanteras även utan avundsjuka
$1/10$ tårta och vill ha kvadratiska bitar är proportionaliteten det bästa som kan garanteras utan avund är $\displaystyle 1/6$ }

En avundsfri uppdelning existerar även med icke-additiva värdefunktioner, flerdimensionell simplexkaka , och bitarna måste vara polytoper .

Frånkopplade bitar

Förfaranden

För tre partners gör Selfridge–Conways diskreta procedur en avundsfri division med högst 5 snitt. Andra procedurer med rörliga knivar kräver färre skärningar:

Levmore –Cook rörliga knivar kräver högst 4 snitt;
Brams –Taylor–Zwicker roterande knivar för att skära paj kräver högst 3 snitt (detta resulterar i tre sammankopplade bitar när kakan är en cirkel, men när kakan är ett intervall blir det fyra bitar);
Genom att använda Austins flyttknivsprocedure för två partner, är det möjligt att få en avundsfri division för 3 partners med högst 3 snitt. Denna idé tillskrivs William Webb.

För fyra partners gör Brams–Taylor–Zwicker-proceduren en avundsfri division med högst 11 snitt. För fem partners gör en procedur av Saberi och Wang en avundsfri uppdelning med ett begränsat antal snitt. Båda dessa procedurer använder Austins procedur för två partners och allmänna fraktioner som ett första steg. Därför bör dessa procedurer betraktas som oändliga - de kan inte slutföras med ett begränsat antal steg.

För fyra eller fler partners finns det tre algoritmer som är ändliga men obegränsade - det finns ingen fast gräns för antalet klipp som krävs. Det finns tre sådana algoritmer:

Brams –Taylor-protokollet publicerades först i en tidning från 1995 och senare i en bok från 1996.
Robertson –Webb-protokollet publicerades först i en tidning 1997 och senare i en bok från 1998.
Pikhurko-protokollet, publicerat 2000.

Även om protokollen är olika, är huvudidén bakom dem liknande: Dela kakan till ett ändligt men obegränsat antal "smulor", som var och en är så liten att dess värde för alla partners är försumbart. Kombinera sedan smulorna på ett sofistikerat sätt för att få önskad uppdelning. William Gasarch har jämfört de tre obegränsade algoritmerna med hjälp av ordningstal .

Frågan om avundsfri tårtskärning kan ske i begränsad tid för fyra eller fler partners hade varit öppen i många år. Det löstes slutligen 2016 av Hariz Aziz och Simon Mackenzie. Till en början utvecklade de en tidsgränsad algoritm för fyra partners. Sedan utökade de sin algoritm för att hantera hur många partners som helst. Deras algoritm kräver högst $n^{n^{n^{n^{n^{n}}}}}$ frågor. Även om detta tal är begränsat, är det mycket långt från den nedre gränsen för $\Omega (n^{2})$ . Så frågan om hur många förfrågningar som krävs för avundsfri kakskärning är fortfarande öppen.

Approximationer och dellösningar

En återkommande variant av det sista minskande protokollet finner en additiv approximation till en avundsfri uppdelning i begränsad tid. Specifikt, för varje konstant $\epsilon >0$ , returnerar den en division där värdet på varje partner är åtminstone det största värdet minus $\epsilon$ , i tiden ${\ displaystyle n^{2}/\epsilon }$ .

Om alla värdemått är bitvis linjära finns det en algoritm som är polynom i storleken på representationen av värdefunktionerna. Antalet frågor är $O(n^{6}k\ln {k})$ , där $k$ är antalet diskontinuiteter i derivatorna av värdedensitetsfunktioner.

Hårdhetsresultat

Varje avundsfri procedur för n personer kräver minst Ω( n ² )-frågor i Robertson–Webb-frågemodellen . Beviset bygger på en noggrann analys av mängden information algoritmen har om varje partner.

A. Antag att kakan är det 1-dimensionella intervallet [0,1], och att värdet av hela kakan för var och en av partnerna är normaliserat 1. I varje steg ber algoritmen en viss partner att antingen utvärdera en viss intervall som ingår i [0,1], eller för att markera ett intervall med ett specificerat värde. I båda fallen samlar algoritmen endast information om intervall vars slutpunkter nämndes i frågan eller i svaret. Låt oss kalla dessa slutpunkter för landmärken . Inledningsvis är de enda landmärkena för i 0 och 1 eftersom det enda algoritmen vet om partner i är att v _i ([0,1])=1. Om algoritmen ber partner i att utvärdera intervallet [0.2,1], är landmärkena för i efter svaret {0,0.2,1}. Algoritmen kan beräkna v _i ([0,0.2]), men inte värdet för något intervall vars slutpunkt är annorlunda än 0,2. Antalet landmärken ökar med högst 2 i varje fråga. I synnerhet kan värdet på intervallet [0,0,2] vara koncentrerat helt nära 0, eller helt nära 0,2, eller någonstans däremellan.

B. Ett intervall mellan två på varandra följande landmärken för partner i kallas ett landmärke-intervall för partner i . När algoritmen bestämmer sig för att allokera en tårta till partner i måste den allokera en bit vars totala värde för i är minst lika stort som ett landmärke-intervall av i . Beviset är motsägelsefullt: anta att det finns ett visst landmärkesintervall J vars värde för i är mer än det värde som faktiskt tilldelats i . Någon annan partner, säg j , kommer nödvändigtvis att få någon del av landmärkesintervallet J . Enligt stycke A är det möjligt att hela värdet av intervall J är koncentrerat i den andel som tilldelats partner j . Alltså, i avundas j och uppdelningen är inte avundsfri.

C. Antag att alla partners svarar på alla frågor som om deras värdemått är enhetligt (dvs värdet på ett intervall är lika med dess längd). Enligt stycke B kan algoritmen tilldela en del till partner i , endast om den är längre än alla landmärkesintervall för i . Minst n /2 partners måste få ett intervall med en längd på högst 2/ n ; därför måste alla deras landmärkesintervall ha en längd av högst 2/ n ; därför måste de ha minst n /2 landmärkesintervall; därför måste de ha minst n /2 landmärken.

D. Varje fråga som besvaras av partner i involverar högst två nya slutpunkter, så det ökar antalet landmärken för i med högst 2. Därför, i det fall som beskrivs i stycke C, måste algoritmen fråga var och en av n /2 partner, minst n /4 frågor. Det totala antalet frågor är alltså minst n ² /8 = Ω( n ² ).

Existensbevis och varianter

Förutom de allmänna existensbevisen som antyds av algoritmerna som beskrivs ovan, finns det bevis för förekomsten av avundsfria partitioner med ytterligare egenskaper:

Det finns en exakt indelning , som i synnerhet är fri från avundsjuka; se Dubins–Spaniers satser .
Det finns en avundsfri division som också är Pareto-effektiv ; Se Wellers sats .

Båda bevisen fungerar endast för additiva och icke-atomära värdemätningar och förlitar sig på förmågan att ge varje partner ett stort antal frånkopplade delar.

Några andra varianter är:

Stark avundsfrihet kräver att varje agent strikt föredrar sin bunt framför de andra buntarna.
Super avundslöshet kräver att varje agent strikt föredrar sin bunt framför 1/ n av det totala värdet och strikt föredrar 1/ n framför var och en av de andra buntarna. Det är klart att super avundsfrihet innebär stark avundsfrihet vilket innebär avundsfrihet.

Avundsfri uppdelning med olika rättigheter

En vanlig generalisering av avundsfri kriteriet är att var och en av partnerna har olika rättigheter. Dvs, för varje partner i finns det en vikt w _i som beskriver den del av kakan som de har rätt att få (summan av allt w _i är 1). Då definieras en viktad-avundsfri division enligt följande. För varje agent i med värdemått VI _, och för varannan agent j :

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

Dvs varje partner tycker att deras tilldelning i förhållande till sin rätt är minst lika stor som alla andra tilldelningar i förhållande till den andra partners rätt.

När alla vikter är samma (och lika med 1/ n ), reduceras denna definition till standarddefinitionen av avundsfrihet.

När bitarna kan kopplas bort finns det alltid en viktad avundsfri division som kan hittas av Robertson-Webb-protokollet för vilken uppsättning vikter som helst. Zeng presenterade en alternativ algoritm för ungefärlig viktad avundsfri division, som kräver ett mindre antal snitt.

Men när bitarna måste kopplas ihop, kanske en viktad avundsfri division inte existerar. För att se detta, notera att varje viktad-avundsfri division också är viktad-proportionell med samma vikt-vektor; detta betyder att för varje agent i med värdemått V _i :

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

Det är känt att viktad proportionell allokering med sammankopplade bitar kanske inte existerar: se proportionell kakskärning med olika rättigheter för ett exempel.

Observera att det finns en alternativ definition av viktad-avundsfri division, där vikterna tilldelas pjäser snarare än till agenter. Med denna definition är det känt att en viktad avundsfri division finns i följande fall (varje fall generaliserar det föregående fallet):

Additiv värde funktioner, 1-dimensionell kaka (intervall), och bitarna måste kopplas intervall.
Additivvärdefunktioner, flerdimensionell simplexkaka och bitarna måste vara simplexar. Beviset använder Sperners sats , KKM-lemmat , Gales täckande lemma och Ky Fans lemma om sammanträffande punkter .

Dela en "dålig" kaka

I vissa fall har "kakan" som ska delas ett negativt värde. Det kan till exempel vara en bit gräsmatta som måste klippas, eller en bit ödemark som måste rengöras. Då är kakan ett "heterogent dåligt" snarare än ett "heterogent goda".

Vissa procedurer för avundsfri kakskärning kan anpassas för att fungera för en dålig tårta, men anpassningen är ofta inte trivial. Se avundsfri sysslouppdelning för mer information.

Sammanfattningstabeller

Sammanfattning efter resultat
namn	Typ	Kaka	Bitar	#partners ( $n$ )	#frågor	#snitt	avundas	proportionalitet	Kommentarer
Dela och välj	Diskret proc	Några	Ansluten	2	2	1 (optimalt)	Ingen	1/2
Stromquist	Flyttkniv proc	Intervall	Ansluten	3	∞	2 (optimalt)	Ingen	1/3
Selfridge–Conway	Diskret proc	Några	Osammanhängande	3	9	5	Ingen	1/3
Brams–Taylor–Zwicker	Flyttkniv proc	Några	Osammanhängande	4	∞	11	Ingen	1/4
Saberi–Wang	Diskret proc	Några	Osammanhängande	4	Avgränsad	Avgränsad	Ingen	1/4	Fri omhändertagande
Aziz–Mackenzie	Diskret proc	Några	Osammanhängande	4	203	584	Ingen	1/4
Saberi–Wang	Flyttkniv proc	Några	Osammanhängande	5	∞	Avgränsad	Ingen	1/5
Stromquist	Existens	Intervall	Ansluten	$n$	—	$n -1$	Ingen	$1/ n$
Simmons	Diskret proc	Intervall	Ansluten	$n$	∞	$n -1$	Ingen	$1/ n$
Deng-Qi-Saberi	Diskret proc	Intervall	Ansluten	$n$	$\left({\frac {1}{\epsilon }}\right)^{n-2}$	$n -1$	Additiv $\epsilon$	$\left({\tfrac {1}{n}}\right)-\epsilon$	Endast när värderingarna är Lipschitz-kontinuerliga
Branzei	Diskret proc	Intervall	Ansluten	$n$	$n^{2}d$	?	Ingen	$1/ n$	Endast när värdedensiteter är polynom med grad som högst $d$ .
Avfall-gör-brådska	Diskret proc	Intervall	Ansluten	3	9	4	Ingen	1/3	Fri omhändertagande
Avfall-gör-brådska	Diskret proc	Några	Ansluten	4	16	6	Ingen	1/7	Fri omhändertagande
Avfall-gör-brådska	Diskret proc	Några	Ansluten	$n$	$2^{n}$	$2^{n-1}-1$	Ingen	${\frac {1}{2^{n-1}}}$	Fri omhändertagande
Aziz-Mackenzie ConnectedPieces	Diskret proc	Några	Ansluten	$n$	$n^{n+1}$	$n^{n+1}$	Ingen	${\frac {1}{3n}}$	Fri omhändertagande
Brams-Taylor	Diskret proc	Några	Osammanhängande	$n$	Gränslös	Gränslös	Ingen	$1/ n$
Robertson-Webb	Diskret proc	Några	Osammanhängande	$n$	Gränslös	Gränslös	Ingen	$1/ n$	Viktad-fri avundsjuka.
Pikhurko	Diskret proc	Några	Osammanhängande	$n$	Gränslös	Gränslös	Ingen	$1/ n$
Aziz–Mackenzie	Diskret proc	Några	Osammanhängande	$n$	$n^{n^{n^{n^{n^{n}}}}}$	$n^{n^{n^{n^{n^{n}}}}}$	Ingen	$1/ n$
Reentrant sista förminskare	Diskret proc	Intervall	Osammanhängande	$n$	$n^{2}/\epsilon$	?	Additiv $\epsilon$	$1/ n$
Kurokawa-Lai-Procaccia	Diskret proc	Intervall	Osammanhängande	$n$	$n^{6}k\ln k$	?	Ingen	$1/ n$	Endast när värdedensiteter är bitvis linjära med högst $k$ diskontinuiteter.
Weller	Existens	Några	Osammanhängande	$n$	—	∞	Ingen	$1/ n$	Pareto effektiv .
2-D	Diskret proc	Fyrkant	Connected och Square	2	2	2	Ingen	1/4	Fri omhändertagande
2-D	Flyttkniv proc	Fyrkant	Connected och Square	3	∞	6	Ingen	1/10	Fri omhändertagande

Sammanfattning efter antal agenter och typ av bitar:

# agenter	Förbundna delar	Allmänna bitar
2	Dela och välj
3	Stromquist rörliga knivar procedur (oändlig tid); Avfall gör-brådska (avgränsad tid, begränsade nedskärningar, fri omhändertagande, proportionell)	Selfridge–Conway diskret procedur (avgränsad tid, högst 5 snitt).
4	Avfall gör-brådska (avgränsad tid, begränsade nedskärningar, fritt omhändertagande, proportionalitet 1/7).	Brams–Taylor–Zwicker rörliga knivar (oändlig tid, högst 11 snitt). Saberi–Wang diskret procedur (avgränsad tid, avgränsad snitt, fritt förfogande, proportionell). Aziz–Mackenzie diskret procedur (begränsad tid, gränsad snitt, proportionell).
5		Saberi–Wang rörliga knivar (oändlig tid, avgränsade snitt).
$n$	Simmons protokoll (oändlig tid) Deng-Qi-Saberi (ungefär avundsfri, exponentiell tid). Avfall gör-haste (helt avundsfritt, exponentiell tid, fritt förfogande, exponentiell proportionalitet) Aziz-Mackenzie ConnectedPieces (helt avundsfritt, exponentiell tid, fritt förfogande, linjär proportionalitet)	Brams och Taylor (1995) ; Robertson och Webb (1998) . – Båda algoritmerna kräver ett ändligt men obegränsat antal nedskärningar. Aziz-Mackenzie diskret procedur (avgränsad tid, avgränsad skärning, proportionell).
Hårdhet	Alla algoritmer för $n \geq 3$ måste vara oändliga (Stromquist, 2008).	Alla algoritmer måste använda minst $Ω(n 2)$ steg (Procaccia, 2009).
Varianter	En viktad avundsfri uppdelning finns för godtyckliga vikter (Idzik, 1995), även när kakan och bitarna är simplexar (Idzik och Ichiishi, 1996). En avundsfri uppdelning existerar även med icke-additiva preferenser (Dall'Aglio och Maccheroni, 2009).	Robertson-Webb kan hitta viktade-avundsfria divisioner för godtyckliga vikter. En perfekt uppdelning finns (Dubins&Spanier, 1961). En avundsfri och effektiv kakskärning finns ( Wellers sats) .

Se även

externa länkar

Fair Division Calculator – en applet för att beräkna avundsfri division för tårtor, sysslor, rum och hyror.