Robertson-Web-protokolla

Robertson-Webb- protokolla on kateellinen kakunleikkausprotokolla , joka on myös lähes tarkka . Protokollalla on seuraavat ominaisuudet:

Se toimii mille tahansa määrälle ( n ) osallistujia.
Se toimii kaikilla painoilla, jotka edustavat osallistujien eri panoksia.
Osallistujille välitetyt palat eivät välttämättä liity toisiinsa, eli jokainen osallistuja voi saada joukon pieniä "muruja".
Pyyntöjen määrä on rajallinen, mutta ei tiedossa - ei ole tiedossa etukäteen, kuinka monta pyyntöä tarvitaan.

Protokollan ovat kehittäneet Jack M. Robertson ja William A. Webb. Sen julkaisivat vuonna 1997 Robertson [1] ja myöhemmin vuonna 1998 Robertson ja Webb [2] .

Tiedot

Suurin vaikeus kehitettäessä menettelyä jaon saamiseksi ilman kateutta agenttien keskuudessa on se, että tehtävä ei ole "hajottava". Eli jos jaamme puolet kakusta n /2 agentin kesken ilman kateutta, emme voi jakaa kakun toista puolta muiden n /2 agenttien kesken, koska ensimmäisen ryhmän jäsenet voivat tulla kateellisiksi (esim. voi käydä niin, että A ja B luulevat saavansa 1/2 puolikkaastaan, mikä on 1/4 koko kakusta. C ja D saattavat ajatella samalla tavalla, mutta A luulisi, että C sai koko puolikkaan ja D ei saanut yhtään, joten A olisi kateellinen C). $n > 2$

Robertson-Webb-protokolla yrittää ratkaista tämän ongelman vaatimalla, että jaossa ei ole kateutta, vaan että se on myös lähes tarkka. Alla on protokollan rekursiivinen osa.

Kirjaudu sisään

Mikä tahansa pala kakkua X ;
Mikä tahansa ; $\varepsilon >0$
n osallistujaa, ; $A_{1},\pisteet ,A_{n}$
m<n osallistujaa, jotka hyväksytään "aktiivisiksi pelaajiksi" (muut osallistujat hyväksytään "tarkkailijoiksi"); ${\displaystyle A_{1},\dots ,A_{m))$ $nm$
Mikä tahansa m positiivisen painon joukko ; ${\displaystyle w_{1},\dots ,w_{m))$

Poistu

X :n jakaminen m aktiiviselle pelaajalle määrätyiksi paloiksi siten, että ${\displaystyle X_{1},\dots ,X_{m))$

Osiossa ei ole kateutta annetuille painoille m aktiivisten osallistujien keskuudessa. Toisin sanoen kaikille aktiivisille pelaajille ja pelaaja uskoo, että hänen nappulansa arvo jaettuna toisen nappulan arvolla ei ole pienempi kuin . $A_{i}$ $A_{j}$ $A_{i}$ $X_{i}$ $X_{j}$ ${\tfrac {w_{i}}{w_{j}}}$
Osio on lähes -tarkka annetuilla painoilla kaikkien n pelaajan kesken, sekä aktiivisten että ei-aktiivisten. $\varepsilon$

Toimenpide

Huomautus: Tässä oleva menettelyn kuvaus ei ole muodollinen ja on yksinkertaistettu. Tarkempi kuvaus on annettu Robertsonin ja Webbin kirjassa [2] .

Käytämme X :lle lähes tarkkaa jakomenettelyä ja saamme leikkauksen, jonka kaikki n pelaajaa näkevät painojen kanssa lähes täsmällisenä . $\varepsilon$ ${\displaystyle w_{1},\dots w_{m))$

Leikkaa joku aktiivisista pelaajista (olkoon ) palasia siten, että osio on juuri hänelle, eli mille tahansa . $A_{1}$ ${\displaystyle j:{\tfrac {V_{1}(X_{j})}{V_{1}(X)))=w_{j))$

Jos kaikki muut pelaajat ovat samaa mieltä tällaisesta leikkaamisesta, annamme nappulan aktiiviselle pelaajalle . Tässä erossa ei ole kateutta, joten saimme mitä halusimme. $X_{i}$ $A_{i}$

Muuten P : ssä on pala , josta aktiivisten pelaajien kesken on erimielisyyttä. Leikkaamalla P pienemmiksi paloiksi tarvittaessa voimme rajoittaa erimielisyyttä siten, että kaikki pelaajat ovat samaa mieltä siitä, että . ${\tfrac {V(P)}{V(X)}}<\varepsilon$

Jaetaan aktiiviset pelaajat kahteen leiriin: "optimisteihin", jotka uskovat, että P on arvokkaampi, ja "pessimisteihin", jotka uskovat, että P on vähemmän arvokas. Antaa olla sellainen ero arvioiden välillä, että jokaiselle optimistille i ja mille tahansa pessimistille j , . $\delta$ ${\tfrac {V_{i}(P)}{V_{i}(X)))-{\tfrac {V_{j}(P)}{V_{j}(X)))>\ delta$

Jaetaan loput kakusta paloiksi Q ja R niin, että osio on lähes tarkka kaikille n pelaajalle. $XP$

Annetaan se optimisteille. Koska he uskovat, että P on arvokkaampi, he välttämättä uskovat , että P on tarpeeksi arvokas kattamaan heidän osuutensa. $P\cup Q$ $P\cup Q$

Annetaan R pessimisteille. Koska he uskovat, että P on vähemmän arvokas, he välttämättä olettavat, että loppuosa R : stä on tarpeeksi arvokasta kattamaan heidän osuutensa.

Tässä vaiheessa olemme jakaneet aktiiviset pelaajat kahteen leiriin, jokainen leiri uskoo, että heille (koko leirille) jaettavat kakun osuudet tyydyttävät heidät (yhteisesti).

Jäljelle jää jakaa kukin näistä kakkuosista leirin sisällä. Tämä tehdään rekursiivisesti soveltamalla yllä olevaa menettelyä:

Jaamme osan rekursiivisesti optimistien kesken (eli optimistit ovat aktiivisia, loput vain katsovat). $P\cup Q$
Jaa R -osa rekursiivisesti pessimistien kesken.

Molemmissa sovelluksissa lähes tarkkuusparametri ei saa ylittää arvoa . Koska tuloksena oleva osio on lähes -tarkka kaikille n pelaajalle, optimistien välinen jakautuminen ei herätä kateutta pessimistien keskuudessa ja päinvastoin. Siten kateus ei ole läsnä lopullisessa jaossa ja on melkein tarkkaa. $\delta$ $\delta$

Katso myös

Brahms-Taylor- protokolla on toinen kateellinen jakoprotokolla, jossa on irrotettuja paloja ja rajallinen rajoittamaton käyttöaika. Ei takaa läheskään tarkkuutta.
Simmons-Su- protokollat ovat kateellinen jakoprotokolla, joka takaa kappaleiden liitettävyyden, mutta ajoaika voi olla ääretön. Lähes tarkkaa jakoa ei taata.

Muistiinpanot

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

Kirjallisuus

Jack M. Robertson, William A. Webb. Lähes tarkka ja kateudeton kakkujako // Ars Combinatoria. - 1997. - T. 45 .
Jack Robertson, William Webb. Kakunleikkausalgoritmit: Ole reilu, jos pystyt... - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .