Robertson-Webb-protokollet

Robertson-Webb- protokollet är ett avundsjukt kakskärningsprotokoll som också är nästan korrekt . Protokollet har följande egenskaper:

Det fungerar för vilket antal ( n ) deltagare som helst.
Det fungerar för alla uppsättningar vikter som representerar de olika insatserna för deltagare.
Delarna som skickas till deltagarna är inte nödvändigtvis anslutna, det vill säga varje deltagare kan få en uppsättning små "smulor".
Antalet förfrågningar är begränsat, men inte känt - det är inte känt i förväg hur många förfrågningar som kommer att krävas.

Protokollet utvecklades av Jack M. Robertson och William A. Webb. Den publicerades 1997 av Robertson [1] och senare 1998 av Robertson och Webb [2] .

Detaljer

Den största svårigheten med att utveckla ett förfarande för att få en uppdelning utan avund bland agenter är att uppgiften inte är "nedbrytbar". Det vill säga, om vi delar hälften av kakan mellan n /2 agenter i frånvaro av avundsjuka, kan vi inte dela den andra halvan av kakan mellan andra n /2 agenter, eftersom medlemmar i den första gruppen kan bli avundsjuka (till exempel, det kan hända att A och B tror att de fick 1/2 av sin halva, vilket är 1/4 av hela kakan. C och D kanske tycker likadant, men A skulle tro att C fick hela hälften och D fick inga, så A skulle vara avundsjuk på C). $n > 2$

Robertson-Webb-protokollet försöker lösa denna svårighet genom att kräva att det inte bara finns ingen avundsjuka i divisionen, utan att den också är nästan exakt. Nedan är den rekursiva delen av protokollet.

Logga in

Vilken som helst bit av kakan X ;
Alla ; $\varepsilon >0$
n deltagare, ; $A_{1},\dots ,A_{n}$
m<n deltagare som accepteras som "aktiva spelare" (andra deltagare accepteras som "observatörer"); ${\displaystyle A_{1},\dots ,A_{m))$ $nm$
Varje uppsättning av m positiva vikter ; ${\displaystyle w_{1},\dots ,w_{m))$

Avsluta

Dela upp X i bitar som tilldelas de m aktiva spelarna så att ${\displaystyle X_{1},\dots ,X_{m))$

Det finns ingen avund i partitionen för de givna vikterna bland de m aktiva deltagarna. Det vill säga för alla aktiva spelare och spelaren tror att värdet på hans pjäs , dividerat med värdet av en annan pjäs , inte är mindre än . $A_{i}$ $A_{j}$ $A_{i}$ $X_{i}$ $X_{j}$ ${\tfrac {w_{i}}{w_{j}}}$
Partitionen är nästan -exakt för givna vikter bland alla n spelare, både aktiva och inaktiva. $\varepsilon$

Procedur

Obs: Beskrivningen av förfarandet här är inte formell och är förenklad. En mer exakt beskrivning ges i boken av Robertson och Webb [2] .

Vi använder den nästan exakta divisionsproceduren för X och får ett snitt som alla n spelare ser som nästan -exakt med vikter . $\varepsilon$ ${\displaystyle w_{1},\dots w_{m))$

Låt en av de aktiva spelarna (låt det vara ) skär bitar på ett sådant sätt att partitionen är exakt för honom, det vill säga för alla . $A_{1}$ ${\displaystyle j:{\tfrac {V_{1}(X_{j})}{V_{1}(X)))=w_{j))$

Om alla andra spelare håller med om en sådan skärning, ger vi helt enkelt pjäsen till den aktiva spelaren . Det blir ingen avundsjuka i denna splittring, så vi fick som vi ville. $X_{i}$ $A_{i}$

Annars finns det någon del av P som det råder oenighet om bland aktiva spelare. Genom att vid behov skära P i mindre bitar kan vi begränsa oenigheten så att alla spelare är överens om att . ${\tfrac {V(P)}{V(X)}}<\varepsilon$

Låt oss dela upp aktiva spelare i två läger: "optimister", som anser att P är mer värt, och "pessimister", som anser att P är mindre värt. Låt vara en sådan skillnad mellan uppskattningarna, så att för varje optimist i och någon pessimist j , . $\delta$ ${\tfrac {V_{i}(P)}{V_{i}(X)))-{\tfrac {V_{j}(P)}{V_{j}(X)))>\ delta$

Låt oss dela upp resten av kakan i bitar Q och R så att uppdelningen blir nästan exakt för alla n spelare. $XP$

Låt oss ge det till optimisterna. Eftersom de tror att P är mer värdefullt, kommer de med nödvändighet att tro att P är tillräckligt värdefullt för att täcka deras aktier. $P\cup Q$ $P\cup Q$

Låt oss ge R till pessimisterna. Eftersom de tror att P är mindre värt, kommer de med nödvändighet att anta att resten av R är tillräckligt värdefull för att täcka deras andel.

Vid det här laget har vi delat upp de aktiva spelarna i två läger, varje läger tror att de delar av kakan som tilldelats dem (för hela lägret) kommer att tillfredsställa dem (kollektivt).

Det återstår att dela upp var och en av dessa delar av kakan inne i lägret. Detta görs genom att rekursivt tillämpa ovanstående procedur:

Vi delar rekursivt upp delen mellan optimisterna (det vill säga optimisterna är aktiva, resten bara tittar). $P\cup Q$
Dela rekursivt R- delen mellan pessimisterna.

I båda applikationerna bör parametern nästan precision inte överstiga . Eftersom den resulterande partitionen är nästan -exakt för alla n spelare, kommer uppdelningen bland optimister inte att väcka avund bland pessimister och vice versa. Avund kommer alltså inte att vara närvarande i den slutliga indelningen och kommer att vara nästan exakt. $\delta$ $\delta$

Se även

Brahms-Taylor- protokollet är ett annat avundsjukt divisionsprotokoll med bortkopplade bitar och ändlig obegränsad körtid. Garanterar inte nära noggrannhet.
Simmons-Su- protokollen är ett avundsjukt divisionsprotokoll som garanterar kopplingen mellan bitarna, men speltiden kan vara oändlig. Nästan precisionsindelning garanteras inte.

Anteckningar

↑ Robertson, Webb, 1997 , sid. 97–108.
↑ 12 Robertson , Webb, 1998 , sid. 128–133.

Litteratur

Jack M. Robertson, William A. Webb. Nära exakt och avundsfri tårta division // Ars Combinatoria. - 1997. - T. 45 .
Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can.. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .