Edmonds-Prus jegyzőkönyv

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 12-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az Edmonds–Prus protokoll egy tisztességes tortavágási protokoll . Célja egy heterogén erőforrás részlegesen arányos felosztása n ember között úgy, hogy minden résztvevő megkapja a torta egy olyan részhalmazát (darabot), amelyet minden résztvevő a teljes becslés legalább 1/ -ára becsül, ahol van valami kellően nagy konstans. . Az algoritmus valószínűségi O( n ) futási idővel , a siker valószínűsége közel 1. A protokollt Jeff Edmond és Kirk Prus fejlesztette ki, amelyet később Jaisingh Solankival javítottak. $a\geqslant 10$

Motiváció

A torta arányos felosztása a rekurzív időben felező algoritmussal érhető el . A komplexitásra vonatkozó egyes eredmények azt mutatják, hogy ez a futási idő sokféle feltételezés mellett optimális. Különösen a rekurzív felezés a leggyorsabb algoritmus a teljes arányosság elérésére, amikor a darabokat össze kell kötni, és ez a lehető leggyorsabb determinisztikus algoritmus akár részarányosság elérésére, és még akkor is, ha szabad darabokra vágni. Van olyan eset, amelyet a komplexitás eredményei nem fednek le, ez a valószínűségi algoritmusok esete, amelyek csak részarányosságot és a szétválasztott darabok lehetőségét garantálják . Az Edmonds-Prus protokoll célja, hogy O( n ) futási időt biztosítson csak erre az esetre. $O(n\log n)$

Protokoll

Az általános séma Edmunds és Prus nyomán a következő [1] :

A tortát minden résztvevő privátban (szubjektív értékelése szerint) azonos darabokra osztja . Ezeket a darabokat jelölt daraboknak nevezzük . $n\cdot an$
Minden résztvevő 2 d jelölt darabot választ egyenlő valószínűséggel és megtérüléssel ( a d egy állandó, később kerül meghatározásra). A jelöltek d párba vannak csoportosítva , amelyeket a résztvevő jelent az algoritmusnak. Ezeket a párosításokat negyeddöntős összecsapásoknak nevezik . $n\cdot d$
Az algoritmus minden negyeddöntős csomagból kiválaszt egy darabot, azt, amelyiknek a legkevesebb más jelölttel van metszéspontja. Ezeket a darabokat elődöntőknek nevezzük . $n\cdot d$
Az algoritmus minden résztvevő számára egyetlen darabot választ ki, ezeket a darabokat véglegesnek nevezzük . Az utolsó darabokat úgy kell kiválasztani, hogy minden pontot legfeljebb két utolsó darab fedjen le (lásd alább). Ha ez sikerült, folytassa az 5. lépéssel. Ha nem sikerül, térjen vissza az 1. lépéshez.
A torta minden olyan részét, amely csak egy utolsó darabhoz tartozik, a tulajdonosa kapja. A torta minden részét, amely az utolsó két darabhoz tartozik, arányosan elosztjuk bármely determinisztikus arányos osztási algoritmussal.

Az algoritmus garantálja, hogy nagy valószínűséggel minden résztvevő megkapja a jelölt darabjának legalább a felét, ami azt jelenti (ha a preferenciafüggvények összeadódnak), hogy az érték legalább . ${\tfrac {an}{2))$

Az 5. lépésben O( n ) jelölt darab és O( n ) további vágás van, amelyek O(1) időt vesznek igénybe. Ezért az algoritmus teljes futási ideje O( n ).

Ebben a sémában a fő feladat az utolsó darabok kiválasztása a 4. lépésben:

Kezdjük azzal, hogy hozzunk létre egy metszéspont gráfot, egy gráfot, amelynek csúcsai a félvégi darabok, és egy ív az i tag I darabjától a j tag J darabjáig létezik, ha az I csonk metszi a j tag J darabját (ezért ha úgy döntünk I. darabot , és el akarjuk kerülni a kereszteződéseket, a J darabot is ki kell választanunk .

Válasszunk egy tetszőleges i résztvevőt , amelyik még nem kapta meg a darabját, és ebből a résztvevőből válasszunk egy tetszőleges I darabot végső darabnak. Ezután a metszésgráfban végigmegyünk a kapcsolaton, és végső darabnak választjuk mindazokat a darabokat, amelyeket az I csúcsból elérünk . Két jó forgatókönyv létezik - vagy kiosztunk egy utolsó darabot minden résztvevőnek, és ezzel befejezzük az eljárást, vagy elérünk egy olyan darabot, amelynek nincs kimenő linkje (ami azt jelenti, hogy nem metszi a többi darabot). Ez utóbbi esetben egyszerűen kiválasztunk egy másik darabot a megmaradt tagok közül, és folytatjuk. A rossz forgatókönyv akkor következik be, amikor utunk ugyanannak a tagnak két különböző darabjához vezet, vagy ennek megfelelően az i tag egy másik darabjához, ahonnan az utazást elkezdtük. Az ilyen utat, amely az i résztvevő egyik darabjától ugyanazon résztvevő másik részéhez vezet, páros útvonalnak nevezzük . Ha a metszéspont gráf nem tartalmaz párosított utakat, akkor a leírt algoritmus n darab nem átfedő végdarab halmazát adja vissza, és megvan a kívánt eredmény. Most már ki kell számítani annak a valószínűségét, hogy a metszésponti gráf páros útvonalat tartalmaz.

Először is vizsgáljuk meg azt a speciális esetet, amikor minden résztvevőnek ugyanazok a preferenciafunkciói (és így a jelölt darabok azonos halmaza). Ebben az esetben a párosított út valószínűsége könnyen kiszámítható, mivel minden ív valószínűsége 1/ an , és minden él független, így egy adott, k hosszúságú páros út valószínűsége , és bármely a páros útvonal legfeljebb: ${\displaystyle {\tfrac {1}{(an)^{k))))$

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

A d =1 és egy kellően nagy a választásával ez a valószínűség tetszőlegesen kicsinyre tehető. Ez akkor is igaz, ha kihagyjuk az elődöntő kiválasztási szakaszát (#3), és az összes negyeddöntőst elődöntősnek tekintjük.

Vegye figyelembe, hogy ez az eset hasonló az urnákban lévő labdákhoz . Ez azt bizonyítja, hogy ha minden labdához tetszőlegesen d urnát választunk, akkor minden labdához választhat egy urnát úgy, hogy minden urna különböző legyen (a golyók maximális száma 1).

Az általános tortamodellben, ha a preferenciafüggvények eltérőek, a metszésponti gráf élvalószínűsége függő, de az elődöntős kiválasztási fázisnak köszönhetően megmutathatjuk, hogy annak a valószínűsége, hogy a metszéspont gráf páros hosszúságú utat tartalmaz legalább 3 nem haladja meg . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Marad a 2-es hosszúságú párosított utak figyelembe vétele. Sajnos nem elhanyagolható annak a valószínűsége, hogy a metszésponti gráfban ilyen páros útvonalat kapjunk. Nagy valószínűséggel azonban lehetséges két csoportra bontani a résztvevőket, amelyeknek nincs 2 hosszúságú párosított útvonala. Ezért a végső darabok kiválasztására szolgáló algoritmust kétszer, minden csoportnál egyszer lefuttathatjuk. Metszéspont csak a különböző csoportok végső darabjai között fordulhat elő, ezért az átfedés a torta egyes pontjaiban nem haladja meg a 2-t. Annak a valószínűsége, hogy egy ilyen 2-partíció lehetetlen , nem haladja meg a -t . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

A fenti két kifejezés összegzése és d = 2 felvétele után azt kapjuk, hogy a meghibásodás valószínűsége megmarad . Emlékezzünk vissza, hogy a az arányosság aránya – minél nagyobb értéket szeretnénk garantálni az egyes résztvevőknek, annál valószínűbb, hogy a felosztás sikertelen lesz, és az 1. lépéstől kell kezdeni. $O\left({\frac {1}{a^{2))}\right)$

Egyes algoritmusok akkor is működnek, ha a vágások közelítőek, vagyis a résztvevők nem tudják, hogy a megjelölt darabok egyenlőek-e. Megjelölhetnek egy darabot a kívánt érték feletti vagy alatti p százalékos értékkel, és véletlenszerűen választják ki a pontos hibát [1] .

High Confidence Protocol

Tovább csökkentheti a meghibásodás esélyét a következő séma [2] használatával :

Az eredeti protokollt kétszer futtatjuk.
Minden futásnál eltávolítjuk az összes résztvevőt, aki a páros útvonal elején áll, és az utolsó darabokat csak a fennmaradó résztvevők között osztjuk szét, az eredeti algoritmus szerint.
Ha nem távolítottak el minden tagot egyetlen futásnál sem, megkaptuk, amire szükségünk volt, mivel most minden tagnak van egy utolsó darabja.

Egy adott résztvevő eltávolításának valószínűsége minden egyes bérletből . Egy adott résztvevő eltávolításának valószínűsége mindkét futásban egyenlő . Ezért a meghibásodás valószínűsége , és az n növekedésével 0-ra hajlik , még akkor is, ha az a részarányossági arányt állandó értéken tartják. $O\left({\frac {1}{n}}\right)$ $O\left({\frac {1}{n^{2))}\jobbra)$ $O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)$

Kapcsolódó kérdések

A torta modell a labdaprobléma modell általánosításának tekinthető . Ez a modell széles körben alkalmazható olyan területeken, mint a terheléselosztás . Ezekben a helyzetekben a labda különböző gépekhez (terminológiánk szerint urnákhoz) rendelhető munkát jelent. Nagyjából az egyforma gépek teherelosztása golyók és urnák, az egyenlőtlen gépek tehereloszlása pedig a tortát. Ezért teljesen egyértelmű, hogy a tortamodellnek és az Edmonds-Prus protokollnak érdekes alkalmazásai lehetnek a terheléselosztás szempontjából eltérő gépeken [1] .

Jegyzetek

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

Irodalom

Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. éves IEEE szimpózium a számítástechnika alapjairól (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Egy torta magabiztos felvágása megközelítőleg tisztességes darabokra // Algoritmikus szempontok az információban és a menedzsmentben. - 2008. - T. 5034. - (Számítástechnikai előadásjegyzetek). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .