Protokół Edmondsa-Pruhsa

Protokół Edmondsa-Pruhsa to protokół uczciwego krojenia ciasta . Jego celem jest stworzenie częściowo proporcjonalnego podziału heterogenicznego zasobu między n osób, tak aby każda osoba otrzymała podzbiór ciasta, który ta osoba ceni jako co najmniej 1/ an całości, gdzie ${\ displaystyle a \ geq 10}$ jest pewną dostatecznie dużą stałą. Jest to losowy algorytm , którego czas działania wynosi O( n ) z prawdopodobieństwem bliskim 1. Protokół został opracowany przez Jeffa Edmondsa i Kirka Pruhsa, którzy później ulepszyli go we współpracy z Jaisinghem Solanki.

Motywacja

Proporcjonalny podział ciasta można uzyskać za pomocą rekurencyjnego algorytmu dzielenia na pół w czasie O( n log n ). Kilka wyników twardości pokazuje, że ten czas pracy jest optymalny przy wielu różnych założeniach. W szczególności rekurencyjne dzielenie na pół jest najszybszym możliwym algorytmem do osiągnięcia pełnej proporcjonalności, gdy elementy muszą być ciągłe, i jest najszybszym możliwym algorytmem deterministycznym do osiągnięcia nawet częściowej proporcjonalności, a nawet wtedy, gdy elementy mogą być odłączone. Jednym z przypadków, którego nie obejmują wyniki twardości, jest przypadek algorytmów losowych , gwarantujących tylko częściową proporcjonalność iz możliwymi niepowiązanymi częściami . Protokół Edmondsa-Pruhsa ma na celu dostarczenie algorytmu z czasem wykonywania O( n ) dla tego przypadku.

Protokół

Ogólny schemat jest następujący:

1. Każdy partner prywatnie dzieli tort na kawałki o równej subiektywnej wartości. Te n ⋅ an elementy nazywane są elementami kandydującymi .
2. losowo jednolicie losuje 2 d kandydujących elementów, z zamianą ( d jest stałą do ustalenia później). Kandydaci są pogrupowani w d , które partner zgłasza do algorytmu. Te n⋅d nazywane są nawiasami ćwierćfinałowymi .
3. Z każdej drabinki ćwierćfinałowej algorytm wybiera jedną figurę - figurę, która przecina mniejszą liczbę innych kandydujących figur. Te n ⋅ d utwory nazywane są utworami półfinałowymi .
4. Dla każdego partnera algorytm wybiera pojedynczą sztukę; nazywane są końcowymi kawałkami . Końcowe kawałki wybiera się w taki sposób, aby każdy punkt ciasta był przykryty co najwyżej 2 końcowymi kawałkami (patrz poniżej). Jeśli to się powiedzie, przejdź do kroku 5. Jeśli to się nie powiedzie, rozpocznij od kroku 1.
5. Każda część ciasta, która należy tylko do jednego końcowego kawałka, jest przekazywana właścicielowi tego kawałka. Każda część ciasta, która należy do dwóch końcowych kawałków, jest dzielona proporcjonalnie przez dowolny deterministyczny algorytm podziału proporcjonalnego.

Algorytm gwarantuje, że z dużym prawdopodobieństwem każdy partner otrzyma co najmniej połowę jednej ze swoich kandydujących figur, co implikuje (jeśli wartości są addytywne) wartość co najmniej 1/2 an .

jest O( n ) fragmentów kandydujących i O( n ) dodatkowych podziałów, z których każdy zajmuje O(1) czasu. Stąd całkowity czas działania algorytmu wynosi O( n ).

Głównym wyzwaniem w tym schemacie jest wybranie ostatnich elementów w kroku 4:

Rozpocznij od stworzenia wykresu implikacji : wykresu, którego wierzchołkami są półfinałowe elementy, a krawędź od elementu I partnera i do elementu J partnera j , jeśli element I przecina drugi element partnera j (stąd, jeśli wybierzemy element I i chcemy uniknąć przecięcia, powinniśmy wybrać również element J ).

Wybierz dowolnego partnera i , który nie otrzymał jeszcze figury, i wybierz dowolną figurę I tego partnera jako figurę końcową. Następnie przejdź przez łącza na wykresie implikacji i wybierz jako elementy końcowe wszystkie elementy, które są osiągalne z I . Istnieją dwa dobre scenariusze: albo przydzielamy każdemu partnerowi po jednym ostatnim kawałku i gotowe, albo docieramy do kawałka bez wychodzących linków (co oznacza, że ​​nie przecina się on z innymi kawałkami). W tym drugim przypadku po prostu wybieramy kolejny kawałek jednego z pozostałych partnerów i kontynuujemy. Zły scenariusz jest taki, że nasze przejście prowadzi nas do dwóch różnych kawałków tego samego partnera lub równoważnie do drugiego kawałka partnera i, od którego zaczęliśmy. Taka ścieżka, prowadząca od jednego kawałka partnera i do drugiego kawałka tego samego partnera, nazywana jest ścieżką parową . Jeśli wykres implikacji nie zawiera ścieżek par, to właśnie opisany algorytm selekcji zwraca zbiór n nienakładających się elementów końcowych i gotowe. Teraz pozostaje obliczyć prawdopodobieństwo, że wykres implikacji zawiera ścieżkę pary.

Najpierw rozważmy szczególny przypadek, w którym wszyscy partnerzy mają tę samą funkcję wartości (a zatem ten sam zbiór elementów kandydujących). W tym przypadku prawdopodobieństwo ścieżki pary jest łatwe do obliczenia: ponieważ prawdopodobieństwo każdej krawędzi wynosi 1/ an , a wszystkie krawędzie są niezależne, prawdopodobieństwo określonej ścieżki pary o długości k wynosi 1/( an ) ^k , oraz prawdopodobieństwo dowolnej ścieżki pary wynosi co najwyżej:

${\ Displaystyle \ suma _ {k} {\ Frac {(2dn)!} {(2dn-k)! (an) ^ {k}}} = O \ lewo ({\frac {1}{a^{2}}}\right)}$

Wybierając d = 1 i odpowiednio duże a, możliwe jest, aby to prawdopodobieństwo było tak małe, jak chcemy. Dzieje się tak nawet wtedy, gdy pominiemy półfinałową fazę selekcji (#3) i po prostu weźmiemy wszystkie utwory ćwierćfinałowe jako półfinałowe.

Zauważ, że ten przypadek jest analogiczny do modelu piłek do pojemników . Dowodzi to, że jeśli d pojemników jest wybieranych losowo dla każdej piłki, to możliwe jest wybranie jednego pojemnika dla każdej piłki w taki sposób, że wszystkie pojemniki są różne (maksymalne obciążenie wynosi 1).

W ogólnym modelu ciasta, w którym funkcje wartości są różne, prawdopodobieństwa krawędzi na wykresie implikacji są zależne. ale dzięki półfinałowej fazie selekcji możemy udowodnić, że prawdopodobieństwo, że wykres implikacji zawiera ścieżkę pary o długości co najmniej 3, wynosi co najwyżej ${\ Displaystyle {\ frac {32d^{5}}{a^{2}\cdot (a-4d^{2})}}}$ .

Pozostaje obsłużyć ścieżki par o długości 2. Niestety prawdopodobieństwo posiadania takich par ścieżek na grafie implikacji nie jest pomijalne. Jednak z dużym prawdopodobieństwem można podzielić partnerów na dwie grupy, tak aby w każdej grupie nie było ścieżki pary o długości 2. Dzięki temu algorytm ostatecznej selekcji elementów możemy uruchomić dwukrotnie: raz dla każdej grupy. Przecięcie może wystąpić tylko między końcowymi kawałkami różnych grup; stąd nakładanie się w każdym punkcie ciasta wynosi co najwyżej 2. Prawdopodobieństwo, że taki podział na 2 nie jest możliwe, wynosi co najwyżej ${\ Displaystyle {\ Frac {16d ^ {3 }}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}}$ .

Sumując powyższe dwa wyrażenia i ustawiając d = 2, otrzymujemy, że prawdopodobieństwo niepowodzenia nadal wynosi ${\ Displaystyle O \ lewo ({\ Frac {1} {a ^ {2}}} \ prawo )}$ . Przypomnijmy, że a to współczynnik proporcjonalności – im więcej wartości chcemy zagwarantować każdemu wspólnikowi, tym większe prawdopodobieństwo, że podział się nie powiedzie i będziemy musieli zaczynać od kroku 1 od nowa.

Ten sam algorytm działa również wtedy, gdy cięcia są przybliżone, tzn. partnerzy nie wiedzą, jak zaznaczyć kawałki o dokładnie tej samej wartości; mogą zaznaczyć kawałek o wartości p procent powyżej lub poniżej wymaganej wartości, gdzie dokładny błąd jest wybierany losowo.

Protokół o wysokim poziomie zaufania

Możliwe jest dalsze zmniejszenie prawdopodobieństwa awarii za pomocą następującego schematu:

• Wykonaj dwa niezależne przebiegi oryginalnego protokołu.
• W każdym biegu usuń każdego partnera, który pojawia się na początku ścieżki par i przydziel ostatnie figury tylko pozostałym partnerom, tak jak w oryginalnym protokole.
• Jeśli dla każdego partnera istnieje co najmniej jeden bieg, w którym nie jest on usuwany, to koniec, ponieważ każdy partner ma teraz co najmniej jedną ostatnią figurę.

Prawdopodobieństwo usunięcia określonego partnera w każdym biegu wynosi ${\ Displaystyle O \ lewo ({\ Frac {1} {n}} \ prawej)}$ . Prawdopodobieństwo usunięcia określonego partnera w obu przebiegach wynosi ${\ Displaystyle O \ lewo ({\ Frac {1} {n ^ {2}}} \ prawej)}$ . Stąd prawdopodobieństwo niepowodzenia wynosi ${\ Displaystyle O \ lewo ({\ Frac {n} {n ^ {2}}} \ prawej) = O \ lewo ({\ frac {1}{n}}\right)}$ , które przyjmuje wartość 0, gdy n rośnie, nawet jeśli współczynnik cząstkowej proporcjonalności a jest stały.

Powiązane problemy

Model ciasta można postrzegać jako uogólnienie modelu kulek na pojemniki . Model ten znalazł szerokie zastosowanie w obszarach takich jak równoważenie obciążenia . W takich sytuacjach piłka reprezentuje zadanie, które można przypisać do różnych pojemników/maszyn. Z grubsza mówiąc, równoważenie obciążenia identycznych maszyn ma się do piłek i pojemników, tak jak równoważenie obciążenia na niepowiązanych maszynach ma się do krojenia ciasta. Stąd uzasadnione jest, aby model ciastka i protokół Edmondsa-Pruhsa miały interesujące zastosowania w ustawieniach obejmujących równoważenie obciążenia na niezwiązanych ze sobą maszynach.