Protocolul Edmonds-Prus

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 ianuarie 2021; verificarea necesită 1 editare .

Protocolul Edmonds–Prus este un protocol corect de tăiere a tortului . Scopul său este de a obține o împărțire parțial proporțională a unei resurse eterogene între n oameni, astfel încât fiecare participant să primească un subset al tortului (bucata) pe care fiecare participant îl estimează cel puțin 1/ an din estimarea completă, unde este o constantă suficient de mare . . Algoritmul este probabilistic cu timpul de rulare O( n ) cu o probabilitate de succes apropiată de 1. Protocolul a fost dezvoltat de Jeff Edmond și Kirk Prus, pe care l-au îmbunătățit ulterior cu Jaisingh Solanki. $a\geqslant 10$

Motivație

Împărțirea proporțională a turtei poate fi obținută folosind algoritmul recursiv de bisectare în timp . Unele rezultate privind complexitatea arată că acest timp de rulare este optim într-o gamă largă de ipoteze. În special, bisectia recursivă este cel mai rapid algoritm pentru obținerea proporționalității complete atunci când piesele trebuie conectate și este cel mai rapid algoritm determinist posibil pentru obținerea proporționalității chiar și parțiale și chiar dacă este permisă tăierea în bucăți deconectate. Există un caz care nu este acoperit de rezultatele complexității, acesta este cazul algoritmilor probabilistici care garantează doar proporționalitate parțială și posibilitatea pieselor deconectate . Protocolul Edmonds-Prus își propune să ofere un timp de rulare de O( n ) doar pentru acest caz. $O(n\log n)$

Protocol

Schema generală, după Edmunds și Prus, este următoarea [1] :

Fiecare participant împarte în mod privat tortul în bucăți identice (conform evaluării sale subiective). Aceste piese se numesc piese candidate . $n\cdot an$
Fiecare participant alege 2 d piese candidate cu probabilitate și randament egale ( d este o constantă și va fi definită ulterior). Candidații sunt grupați în d perechi, pe care participantul le raportează algoritmului. Aceste perechi se numesc sferturi de finală . $n\cdot d$
Din fiecare pachet sferturi de finală, algoritmul selectează o piesă, cea care are intersecții cu cel mai mic număr de alți candidați. Aceste piese se numesc piese semifinale . $n\cdot d$
Pentru fiecare participant, algoritmul selectează o singură piesă, aceste piese fiind numite finale . Piesele finale sunt alese astfel încât fiecare punct să fie acoperit de cel mult două piese finale (vezi mai jos). Dacă acest lucru reușește, treceți la pasul #5. Dacă nu reușește, reveniți la pasul #1.
Fiecare parte a tortului care aparține doar unei singure piese finale este dată proprietarului acelei piese. Fiecare parte a tortului care aparține ultimelor două piese este împărțită proporțional de orice algoritm de diviziune proporțională deterministă.

Algoritmul garantează că, cu o probabilitate mare, fiecare participant primește cel puțin jumătate din piesa sa candidată, ceea ce implică (dacă funcțiile de preferință sunt aditive) că valoarea va fi de cel puțin . ${\tfrac {an}{2)}$

Există O( n ) piese candidate și O( n ) tăieturi suplimentare în pasul #5 care durează O(1) timp. Prin urmare, timpul total de rulare al algoritmului este O( n ).

Sarcina principală în această schemă este alegerea pieselor finale în pasul #4:

Să începem prin a crea un grafic de intersecție , un grafic ale cărui vârfuri sunt bucățile semifinale și un arc de la bucățică I a membrului i la bucățica J a membrului j există dacă bucata I intersectează J bucată de membru j (prin urmare, dacă alegem bucata I si vrem sa evitam intersectiile, trebuie sa selectam si piesa J ).

Să alegem un participant arbitrar i , care nu și-a primit încă piesa și să alegem o piesă arbitrară I a acestui participant ca piesă finală. Apoi trecem prin conexiunea din graficul de intersecție și alegem ca piese finale toate piesele la care se ajunge de la vârful I . Există două scenarii bune - fie distribuim câte o piesă finală fiecărui participant și completăm astfel procedura, fie ajungem la o piesă care nu are legături de ieșire (ceea ce înseamnă că nu intersectează alte piese). În acest din urmă caz, pur și simplu selectăm o altă piesă din unul dintre membrii rămași și continuăm. Scenariul rău se întâmplă atunci când călătoria noastră duce la două bucăți diferite ale aceluiași membru sau, echivalent, o bucată diferită de membru i de la care am început călătoria. O astfel de cale care duce de la o bucată a participantului i la o altă bucată a aceluiași participant este numită cale pereche . Dacă graficul de intersecție nu conține căi pereche, atunci algoritmul descris returnează un set de n piese finale nesuprapuse și avem rezultatul dorit. Acum rămâne de calculat probabilitatea ca graficul de intersecție să conțină o cale pereche.

Luați în considerare mai întâi cazul special în care toți participanții au aceleași funcții de preferință (și, prin urmare, același set de piese candidate). În acest caz, probabilitatea unei căi pereche este ușor de calculat, deoarece probabilitatea fiecărui arc este 1/ an și toate muchiile sunt independente, astfel încât probabilitatea unei anumite căi pereche de lungime k este , și probabilitatea oricărei calea pereche este cel mult: ${\tfrac {1}{(un)^{k)}}$

\sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k))}=O\left({\frac {1}{a^{2 }}}\dreapta)

Alegând d =1 și un a suficient de mare , această probabilitate poate fi redusă în mod arbitrar. Acest lucru este adevărat chiar dacă omitem faza de selecție semifinală (nr. 3) și considerăm toți sferturile de finală drept semifinaliști.

Rețineți că această carcasă este similară cu modelul bile în urne . Acest lucru demonstrează că, dacă d urnele sunt alese în mod arbitrar pentru fiecare bilă, atunci poate fi aleasă o urnă pentru fiecare bilă, astfel încât toate urnele să fie diferite (numărul maxim de bile este 1).

În modelul general tort, atunci când funcțiile de preferință sunt diferite, probabilitățile de muchie din graficul de intersecție sunt dependente, dar datorită fazei de selecție semifinaliste, putem arăta că probabilitatea ca graficul de intersecție să conțină o cale pereche de lungime la cel putin 3 nu depaseste . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Rămâne de luat în considerare căi perechi de lungime 2. Din păcate, probabilitatea de a obține o astfel de cale pereche în graficul de intersecție nu este neglijabilă. Cu toate acestea, cu o probabilitate mare, este posibil să împărțiți participanții în două grupuri, fiecare dintre ele neavând căi pereche de lungime 2. Prin urmare, putem rula algoritmul pentru alegerea pieselor finale de două ori, o dată pentru fiecare grup. O intersecție poate avea loc numai între piesele finale ale diferitelor grupuri, prin urmare suprapunerea în fiecare punct al tortului nu depășește 2. Probabilitatea ca o astfel de 2-partiție să fie imposibilă nu depășește . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

După însumarea celor două expresii de mai sus și luând d = 2, obținem că probabilitatea de eșec rămâne . Amintiți-vă că a este un raport de proporționalitate - cu cât valoarea pe care dorim să o garantăm fiecărui participant este mai mare, cu atât este mai probabil ca diviziunea să eșueze și să înceapă de la pasul #1. $O\left({\frac {1}{a^{2)}}\right)$

Unii algoritmi funcționează și dacă tăieturile sunt aproximative, adică participanții nu știu dacă piesele marcate sunt egale. Ei pot marca o piesă cu o valoare p procent peste sau sub valoarea cerută, iar eroarea exactă este aleasă aleatoriu [1] .

Protocol de înaltă încredere

Puteți reduce și mai mult șansa de eșec utilizând următoarea schemă [2] :

Executăm protocolul original de două ori.
La fiecare cursă, eliminăm toți participanții care se află la începutul traseului pereche și distribuim piesele finale numai între participanții rămași, ca în algoritmul original.
Dacă fiecare membru nu a fost înlăturat în nicio cursă, am primit ceea ce ne trebuia, deoarece fiecare membru are acum o piesă finală.

Probabilitatea de a elimina un anumit participant la fiecare trecere este de . Probabilitatea de a elimina un anumit participant în ambele runde este egală cu . Prin urmare, probabilitatea de eșec este , și tinde spre 0 pe măsură ce n crește, chiar dacă raportul de proporționalitate parțială a este menținut constant. $O\left({\frac {1}{n)}\right)$ $O\left({\frac {1}{n^{2)}}\right)$ $O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)$

Probleme conexe

Modelul tort poate fi considerat ca o generalizare a modelului problemei bile . Acest model găsește o aplicație largă în domenii precum echilibrarea sarcinii . În aceste situații, mingea reprezintă o muncă ce poate fi atribuită diverselor mașini (în terminologia noastră, urne). În linii mari, distribuția sarcinii mașinilor identice este bile și urne, iar distribuția sarcinii mașinilor inegale este tăierea tortului. Prin urmare, este destul de clar că modelul tort și protocolul Edmonds-Prus ar trebui să aibă aplicații interesante în ceea ce privește distribuția sarcinii pe mașini diferite [1] .

Note

↑ 1 2 3 Edmonds, Pruhs, 2006 , p. 623.
↑ Edmonds, Pruhs, Solanki, 2008 , p. 155–164.

Literatură

Jeff Edmonds, Kirk Pruhs. Alocări echilibrate de tort // 2006 Cel de-al 47-lea Simpozion anual IEEE privind fundamentele informaticii (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Tăierea cu încredere a unui tort în bucăți aproximativ corecte // Aspecte algoritmice în informare și management. - 2008. - T. 5034. - (Note de curs în Informatică). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .