Robertson–Webb avundsfri kakskärningsalgoritm

Robertson –Webb-protokollet är ett protokoll för avundsfri kakskärning som också är nästan exakt . Den har följande egenskaper:

Det fungerar för vilket antal ( n ) partner som helst.
Det fungerar för alla uppsättningar vikter som representerar olika rättigheter för partnerna.
Delarna är inte nödvändigtvis sammankopplade, dvs varje partner kan få en samling små "smulor".
Antalet frågor är ändligt men obegränsat – det är inte känt i förväg hur många frågor som kommer att behövas.

Protokollet utvecklades av Jack M. Robertson och William A. Webb. Den publicerades första gången 1997 och senare 1998.

Problemdefinition

En kaka C måste delas upp på n agenter. Varje agent jag har:

Ett värde-mått Vi på _; delmängder av C
En vikt w _i representerar den del av C som agenten har rätt till.

Summan av alla w _i är 1. Om alla agenter har samma rättigheter så är w _i = 1/ n för alla i , men i allmänhet kan vikterna vara olika.

Det krävs att C partitioneras i n delmängder, inte nödvändigtvis anslutna, så att för varannan agent i och h :

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

Så jag avundas inte j när man tar hänsyn till deras olika rättigheter.

Detaljer

Den största svårigheten med att utforma en avundsfri procedur för n > 2 agenter är att problemet inte är "delbart". Dvs om vi delar hälften av kakan mellan n /2 agenter på ett avundsfritt sätt, kan vi inte bara låta de andra n /2 agenterna dela den andra hälften på samma sätt, eftersom detta kan orsaka den första gruppen av n / 2 agenter att vara avundsjuka (t.ex. är det möjligt att A och B båda tror att de fick 1/2 av sin hälften vilket är 1/4 av hela kakan; C och D tror också på samma sätt; men A tror att C fick faktiskt hela halvan medan D inte fick någonting, så A avundas C).

Robertson–Webb-protokollet tar itu med denna svårighet genom att kräva att uppdelningen inte bara är avundsfri utan också nästan exakt. Den rekursiva delen av protokollet är följande subrutin.

Ingångar

Vilken som helst bit av kakan X ;
Vilken som helst e > 0;
n spelare, A ₁ , …, A _n ;
m ≤ n spelare som identifieras som "aktiva spelare", A ₁ , …, _Am ( de andra n − m spelarna identifieras som "bevakande spelare");
Varje uppsättning av m positiva vikter w ₁ , …, w _m ;

Produktion

En partition av X till bitar X ₁ , …, X _m , tilldelad de m aktiva spelarna, så att:

För varje aktiv spelare i och varannan spelare h (aktiv eller tittar):
$V_{i}(X_{i})/w_ {i}\geq V_{i}(X_{h})/w_{h}$
Så agent i avundas inte agent h när man tar hänsyn till deras olika rättigheter.
Uppdelningen är ε-nästan-exakt med de givna vikterna bland alla n spelare – både aktiva och tittande.

Procedur

Notera: presentationen här är informell och förenklad. En mer exakt presentation ges i boken.

Använd en nästan exakt divisionsprocedur på X och få en partition som alla n spelare ser som ε-nästan-exakt med vikter w ₁ , …, w _m .

Låt en av de aktiva spelarna (t.ex. A ₁ ) klippa pjäserna så att divisionen blir exakt för honom, dvs för varje j : V ₁ ( X _j )/ V ₁ ( X ) = w _j .

Om alla andra aktiva spelare håller med skäraren, ge bara pjäs X _i till aktiv spelare A _i . Den här divisionen är avundsfri bland de aktiva spelarna, så vi är klara.

Annars finns det någon pjäs P som det råder oenighet om bland de aktiva spelarna. Genom att skära P i mindre bitar om det behövs, kan vi binda oenigheten så att alla spelare är överens om att: V ( P )/ V ( X ) < ε.

Dela upp de aktiva spelarna i två läger: "optimisterna" som tycker att P är mer värdefullt, och "pessimisterna" som tycker att P är mindre värt. Låt δ vara skillnaden mellan värdena, så att för varje optimist i och varje pessimist j : V _i ( P )/ V _i ( X ) – V _j ( P )/ V _j ( X ) > δ .

Dela den återstående kakan, X − P , i bitarna Q och R , så att uppdelningen är nästan exakt mellan alla n spelare.

Tilldela optimisterna P ∪ Q. Eftersom de tror att P är värdefullt, tror de nödvändigtvis att P ∪ Q är tillräckligt värdefullt för att mer än täcka deras andel.

Tilldela R till pessimisterna. Eftersom de tror att P är mindre värt, tror de nödvändigtvis att resten, R , är tillräckligt värdefull för att mer än täcka deras andel.

Vid det här laget har vi delat upp de aktiva spelarna i två läger, som var och en kollektivt gör anspråk på kompletterande delar av kakan och varje läger är mer än nöjda med sin gemensamma del.

Det återstår att dela upp varje del av kakan till spelarna i dess läger. Detta görs genom två rekursiva tillämpningar av proceduren :

P ∪ Q rekursivt bland optimisterna (dvs optimisterna är aktiva och alla andra spelare tittar bara).
Dela upp R rekursivt bland pessimisterna.

I båda applikationerna bör nära-exakthetsfaktorn vara högst δ. Eftersom den resulterande partitionen är δ -nästan-exakt bland alla n spelare, orsakar inte partitionen bland optimisterna avund bland pessimisterna och vice versa. Således är den övergripande uppdelningen både avundsfri och nästan exakt.

Se även

Brams–Taylor-protokoll – ett annat avundsfritt protokoll med frånkopplade delar och ändlig obegränsad körtid. Garanterar inte nästan exakthet.
Simmons–Su-protokoll – avundsfritt protokoll som garanterar anslutna delar men körtiden kan vara oändlig. Garanterar inte nästan exakthet.
Robertson–Webb frågemodell