Robertson-Webb-protokollen

Robertson-Webb- protokollen er en misundelig kageskæreprotokol , der også er næsten nøjagtig . Protokollen har følgende egenskaber:

Det virker for et hvilket som helst antal ( n ) deltagere.
Det virker for ethvert sæt vægte, der repræsenterer de forskellige indsatser, der skyldes deltagere.
De stykker, der sendes til deltagerne, er ikke nødvendigvis forbundet, det vil sige, at hver deltager kan modtage et sæt små "krummer".
Antallet af forespørgsler er begrænset, men ikke kendt - det vides ikke på forhånd, hvor mange anmodninger, der kræves.

Protokollen blev udviklet af Jack M. Robertson og William A. Webb. Den blev udgivet i 1997 af Robertson [1] og senere i 1998 af Robertson og Webb [2] .

Detaljer

Den største vanskelighed ved at udvikle en procedure til at opnå en opdeling uden misundelse blandt agenter er, at opgaven ikke er "nedbrydelig". Det vil sige, at hvis vi deler halvdelen af kagen mellem n /2 agenter i mangel af misundelse, kan vi ikke dele den anden halvdel af kagen blandt andre n /2 agenter, da medlemmer af den første gruppe kan blive jaloux (f.eks. det kan ske, at A og B tror, at de fik 1/2 af deres halvdel, hvilket er 1/4 af hele kagen. C og D tænker måske på samme måde, men A ville tro, at C fik hele halvdelen og D fik ingen, så A ville være jaloux på C). $n > 2$

Robertson-Webb-protokollen forsøger at løse denne vanskelighed ved at kræve, at der ikke kun er nogen misundelse i opdelingen, men at den også er næsten nøjagtig. Nedenfor er den rekursive del af protokollen.

Log ind

Ethvert stykke kage X ;
Enhver ; $\varepsilon >0$
n deltagere, ; $A_{1},\dots ,A_{n}$
m<n deltagere, der accepteres som "aktive spillere" (andre deltagere accepteres som "observatører"); ${\displaystyle A_{1},\dots ,A_{m))$ $nm$
Ethvert sæt af m positive vægte ; ${\displaystyle w_{1},\dots ,w_{m))$

Afslut

Opdeling af X i stykker tildelt til de m aktive spillere, sådan at ${\displaystyle X_{1},\dots ,X_{m))$

Der er ingen misundelse i opdelingen for de givne vægte blandt de m aktive deltagere. Det vil sige, for ethvert par aktive spillere og spilleren mener, at værdien af hans brik , divideret med værdien af en anden brik , ikke er mindre end . $A_{i}$ $A_{j}$ $A_{i}$ $X_{i}$ $X_{j}$ ${\tfrac {w_{i}}{w_{j}}}$
Partitionen er næsten -præcis for givne vægte blandt alle n spillere, både aktive og inaktive. $\varepsilon$

Fremgangsmåde

Bemærk: Beskrivelsen af proceduren her er ikke formel og er forenklet. En mere præcis beskrivelse er givet i bogen af Robertson og Webb [2] .

Vi bruger den næsten nøjagtige divisionsprocedure for X og opnår et snit, som alle n spillere ser som næsten -nøjagtigt med vægte . $\varepsilon$ ${\displaystyle w_{1},\dots w_{m))$

Lad en af de aktive spillere (lad det være ) skære brikker på en sådan måde, at partitionen er præcis til ham, det vil sige for enhver . $A_{1}$ ${\displaystyle j:{\tfrac {V_{1}(X_{j})}{V_{1}(X)))=w_{j))$

Hvis alle andre spillere er enige i en sådan klipning, giver vi simpelthen brikken til den aktive spiller . Der vil ikke være misundelse i denne opdeling, så vi fik, hvad vi ønskede. $X_{i}$ $A_{i}$

Ellers er der et eller andet stykke P , som der er uenighed om blandt aktive spillere. Ved at skære P i mindre stykker, hvis det er nødvendigt, kan vi begrænse uenigheden, så alle spillere er enige om, at . ${\tfrac {V(P)}{V(X)}}<\varepsilon$

Lad os opdele aktive spillere i to lejre: "optimister", som mener, at P er mere værd, og "pessimister", som mener, at P er mindre værd. Lad være sådan en forskel mellem estimaterne, så for enhver optimist i og enhver pessimist j , . $\delta$ ${\tfrac {V_{i}(P)}{V_{i}(X)))-{\tfrac {V_{j}(P)}{V_{j}(X)))>\ delta$

Lad os dele resten af kagen i stykker Q og R , så partitionen er næsten nøjagtig for alle n spillere. $XP$

Lad os give det til optimisterne. Da de mener, at P er mere værdifuldt, vil de nødvendigvis tro , at P er værdifuldt nok til at dække deres aktier. $P\cup Q$ $P\cup Q$

Lad os give R til pessimisterne. Da de mener, at P er mindre værd, vil de nødvendigvis antage, at resten af R er værdifuld nok til at dække deres andel.

På dette tidspunkt har vi delt de aktive spillere op i to lejre, hver lejr mener, at de andele af kagen, der er tildelt dem (for hele lejren), vil tilfredsstille dem (samlet).

Det er tilbage at dele hver af disse portioner af kagen inde i lejren. Dette gøres ved rekursivt at anvende ovenstående procedure:

Vi deler rekursivt delen mellem optimisterne (det vil sige, optimisterne er aktive, resten ser bare på). $P\cup Q$
Opdel rekursivt R -delen blandt pessimisterne.

I begge applikationer bør parameteren for næsten nøjagtighed ikke overstige . Da den resulterende partition er næsten -præcis for alle n spillere, vil opdelingen blandt optimister ikke vække misundelse blandt pessimister og omvendt. Således vil misundelse ikke være til stede i den endelige opdeling og vil være næsten nøjagtig. $\delta$ $\delta$

Se også

Brahms-Taylor- protokollen er en anden misundelig divisionsprotokol med afbrudte bidder og endelig ubegrænset køretid. Garanterer ikke nær nøjagtighed.
Simmons-Su- protokollerne er en misundelig divisionsprotokol, der garanterer brikkernes sammenhæng, men køretiden kan være uendelig. Næsten præcis opdeling er ikke garanteret.

Noter

↑ Robertson, Webb, 1997 , s. 97-108.
↑ 12 Robertson , Webb, 1998 , s. 128-133.

Litteratur

Jack M. Robertson, William A. Webb. Nær nøjagtig og misundelsesfri kageopdeling // Ars Combinatoria. - 1997. - T. 45 .
Jack Robertson, William Webb. Cake-Cutting Algoritmer: Be Fair If You Can.. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .