Protokol Edmonds-Prus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. ledna 2021; ověření vyžaduje 1 úpravu .

Protokol Edmonds–Prus je spravedlivý protokol pro krájení koláčů . Jeho cílem je získat částečně proporcionální rozdělení heterogenního zdroje mezi n lidí tak, aby každý účastník obdržel podmnožinu koláče (kus), kterou každý účastník odhadne alespoň na 1/ an úplného odhadu, kde je nějaká dostatečně velká konstanta . Algoritmus je pravděpodobnostní s dobou běhu O( n ) s pravděpodobností úspěchu blízkou 1. Protokol vyvinuli Jeff Edmond a Kirk Prus, který později vylepšili Jaisingh Solanki. $a\geqslant 10$

Motivace

Proporcionální dělení koláče lze získat pomocí algoritmu rekurzivního půlení v čase . Některé výsledky týkající se složitosti ukazují, že tato doba běhu je optimální pro širokou škálu předpokladů. Zejména rekurzivní půlení je nejrychlejší algoritmus pro získání plné proporcionality, když kusy musí být spojeny, a je to nejrychlejší možný deterministický algoritmus pro dosažení i částečné proporcionality, a to i v případě, že je dovoleno řezat na rozpojené kusy. Existuje případ, který není pokryt výsledky složitosti, jedná se o případ pravděpodobnostních algoritmů , které zaručují pouze částečnou proporcionalitu a možnost rozpojených kusů . Protokol Edmonds-Prus má za cíl poskytnout provozní dobu O( n ) právě pro tento případ. $O(n\log n)$

Protokol

Obecné schéma podle Edmundse a Pruse je následující [1] :

Každý účastník si soukromě rozdělí dort na stejné kousky (dle svého subjektivního hodnocení). Tyto kusy se nazývají kandidátské kusy . $n\cdot an$
Každý účastník si vybere 2 d kandidátských kusů se stejnou pravděpodobností a návratností ( d je konstanta a bude definováno později). Kandidáti jsou seskupeni do d párů, které účastník nahlásí algoritmu. Tyto dvojice se nazývají čtvrtfinálové remízy . $n\cdot d$
Z každého čtvrtfinálového balíčku algoritmus vybere jeden kus, ten, který má průsečíky s nejmenším počtem dalších kandidátů. Tyto kusy se nazývají semifinálové kusy . $n\cdot d$
Pro každého účastníka algoritmus vybere jeden kus, tyto kusy se nazývají finální . Finální dílky jsou voleny tak, aby každý bod byl pokryt maximálně dvěma finálními dílky (viz níže). Pokud se to podaří, přejděte ke kroku #5. Pokud selže, vraťte se ke kroku #1.
Každá část dortu, která patří pouze jednomu finálnímu dílku, je dána majiteli tohoto dílku. Každá část koláče, která patří do posledních dvou kusů, je rozdělena proporcionálně libovolným deterministickým algoritmem proporcionálního dělení.

Algoritmus zaručuje, že s vysokou pravděpodobností každý účastník obdrží alespoň polovinu svého kandidáta, což znamená (pokud jsou preferenční funkce aditivní), že hodnota bude alespoň . ${\tfrac {an}{2))$

V kroku #5 je O( n ) kandidátských kusů a O( n ) dalších řezů, které zaberou O(1) čas. Celková doba běhu algoritmu je tedy O( n ).

Hlavním úkolem v tomto schématu je výběr finálních kusů v kroku #4:

Začněme vytvořením průsečíkového grafu, grafu, jehož vrcholy jsou semifinálové části, a oblouk z části I členu i do části J členu j existuje, pokud část I protíná J část členu j (pokud tedy zvolíme kus I a chceme se vyhnout křižovatkám, musíme vybrat i kus J ).

Vyberme libovolného účastníka i , který ještě nedostal svou figurku, a jako finální figurku zvolíme libovolnou figurku I tohoto účastníka. Poté projdeme spojení v průsečíkovém grafu a vybereme jako finální dílky všechny dílky, které jsou dosaženy z vrcholu I . Existují dva dobré scénáře – buď každému účastníkovi rozdáme jeden finální díl a tím dokončíme proceduru, nebo se dostaneme k dílu, který nemá žádné odchozí vazby (což znamená, že neprotíná další díly). V druhém případě jednoduše vybereme další kus z jednoho ze zbývajících členů a pokračujeme. Špatný scénář nastane, když naše cesta vede ke dvěma různým kouskům stejného člena, nebo ekvivalentně k jinému kousku členu i , ze kterého jsme cestu začali. Taková cesta vedoucí od jednoho kusu účastníka i k jinému kusu téhož účastníka se nazývá párová cesta . Pokud graf průniku neobsahuje párové cesty, pak popsaný algoritmus vrátí sadu n nepřekrývajících se finálních kusů a máme požadovaný výsledek. Nyní zbývá vypočítat pravděpodobnost, že graf průsečíku obsahuje spárovanou cestu.

Nejprve zvažte speciální případ, ve kterém mají všichni účastníci stejné preferenční funkce (a tedy stejnou sadu kandidátů). V tomto případě lze snadno vypočítat pravděpodobnost párové cesty, protože pravděpodobnost každého oblouku je 1/ an a všechny hrany jsou nezávislé, takže pravděpodobnost konkrétní spárované cesty délky k je a pravděpodobnost libovolného spárovaná cesta je maximálně: ${\displaystyle {\tfrac {1}{(an)^{k))))$

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

Volbou d = 1 a dostatečně velkého a lze tuto pravděpodobnost libovolně snížit. To platí i v případě, že vynecháme semifinálovou fázi výběru (#3) a všechny čtvrtfinalisty považujeme za semifinalisty.

Všimněte si, že tento případ je podobný jako u koulí v modelu urny . To dokazuje, že pokud jsou urny vybrány pro každý míč libovolně, pak lze pro každý míč vybrat jednu urnu, takže všechny urny jsou různé (maximální počet míčků je 1).

V obecném modelu koláče, kdy jsou preferenční funkce různé, jsou pravděpodobnosti hran v grafu průniku závislé, ale díky fázi semifinalistického výběru můžeme ukázat, že pravděpodobnost, že graf průniku obsahuje párovou cestu délky při alespoň 3 nepřesahuje . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Zbývá uvažovat párové cesty délky 2. Bohužel pravděpodobnost získání takovéto párové cesty v grafu křižovatky není zanedbatelná. S velkou pravděpodobností je však možné rozdělit účastníky do dvou skupin, z nichž každá nemá spárované cesty délky 2. Algoritmus pro výběr finálních kusů tedy můžeme spustit dvakrát, pro každou skupinu jednou. K průsečíku může dojít pouze mezi konečnými kusy různých skupin, proto překrytí v každém bodě koláče nepřesáhne 2. Pravděpodobnost, že takový 2 oddíl není možný , nepřekročí . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

Po sečtení dvou výše uvedených výrazů a převzetí d = 2 dostaneme, že pravděpodobnost selhání zůstává . Připomeňme, že a je poměr proporcionality – čím větší hodnotu chceme každému účastníkovi zaručit, tím je pravděpodobnější, že dělení selže a mělo by se začít od kroku č. 1. $O\left({\frac {1}{a^{2))}\right)$

Některé algoritmy také fungují, pokud jsou řezy přibližné, to znamená, že účastníci nevědí, zda jsou označené kusy stejné. Mohou označit kus s hodnotou p procent nad nebo pod požadovanou hodnotou a přesná chyba je vybrána náhodně [1] .

Protokol High Confidence

Pravděpodobnost selhání můžete dále snížit pomocí následujícího schématu [2] :

Původní protokol spustíme dvakrát.
Při každém běhu odstraníme všechny účastníky, kteří jsou na začátku spárované cesty, a rozdělíme konečné kusy pouze mezi zbývající účastníky, jako v původním algoritmu.
Pokud nebyl každý člen odstraněn v žádném běhu, dostali jsme to, co jsme potřebovali, protože každý člen má nyní jeden poslední kus.

Pravděpodobnost odstranění konkrétního účastníka v každém průchodu je . Pravděpodobnost odstranění konkrétního účastníka v obou běhech je rovna . Pravděpodobnost selhání je tedy , a má tendenci k 0, jak n roste, i když poměr částečné úměrnosti a je udržován konstantní. $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)$

Související problémy

Model koláče lze považovat za zobecnění modelu problému s míčem . Tento model nachází široké uplatnění v oblastech, jako je vyvažování zátěže . Míč v těchto situacích představuje práci, kterou lze přiřadit různým strojům (v naší terminologii urny). Zhruba řečeno, rozložení zátěže identických strojů jsou koule a urny a rozložení zátěže nestejných strojů krájí dort. Proto je zcela jasné, že model koláče a protokol Edmonds-Prus by měly mít zajímavé aplikace z hlediska rozložení zátěže na odlišných strojích [1] .

Poznámky

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

Literatura

Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. výroční sympozium IEEE o základech počítačových věd (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Sebevědomé krájení dortu na přibližně spravedlivé kousky // Algoritmické aspekty v informacích a řízení. - 2008. - T. 5034. - (Poznámky z přednášek z informatiky). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .