Edmonds-Prus-protokollet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 januari 2021; verifiering kräver 1 redigering .

Edmonds–Prus- protokollet är ett rättvist kakskärningsprotokoll . Dess mål är att få en delvis proportionell uppdelning av en heterogen resurs bland n personer, så att varje deltagare får en delmängd av kakan (bit) som varje deltagare uppskattar minst 1/ an av den fullständiga uppskattningen, där är någon tillräckligt stor konstant . Algoritmen är probabilistisk med körtid O( n ) med en sannolikhet för framgång nära 1. Protokollet utvecklades av Jeff Edmond och Kirk Prus, som de senare förbättrade med Jaisingh Solanki. $a\geqslant 10$

Motivation

Proportionell uppdelning av kakan kan erhållas med den rekursiva bisektionsalgoritmen i tid . Vissa resultat om komplexitet visar att denna körtid är optimal över ett brett spektrum av antaganden. I synnerhet är rekursiv bisektion den snabbaste algoritmen för att erhålla full proportionalitet när bitarna måste kopplas ihop, och det är den snabbaste möjliga deterministiska algoritmen för att uppnå även partiell proportionalitet och även om den tillåts skära i frånkopplade bitar. Det finns ett fall som inte täcks av resultaten av komplexitet, detta är fallet med probabilistiska algoritmer som garanterar endast partiell proportionalitet och möjligheten till frånkopplade bitar . Edmonds-Prus-protokollet syftar till att ge en körtid på O( n ) bara för detta fall. $O(n\log n)$

Protokoll

Det allmänna schemat, efter Edmunds och Prus, är följande [1] :

Varje deltagare delar upp kakan privat i en identisk bit (enligt hans subjektiva bedömning). Dessa pjäser kallas kandidatpjäser . $n\cdot an$
Varje deltagare väljer 2 d kandidatbitar med lika sannolikhet och avkastning ( d är en konstant och kommer att definieras senare). Kandidaterna grupperas i d -par, som deltagaren rapporterar till algoritmen. Dessa parningar kallas kvartsfinal tie-ins . $n\cdot d$
Från varje kvartsfinalpaket väljer algoritmen en bit, den som har korsningar med minst antal andra kandidater. Dessa pjäser kallas semifinalpjäser . $n\cdot d$
För varje deltagare väljer algoritmen en enda bit, dessa bitar kallas final . De sista bitarna väljs så att varje punkt täcks av högst två sista bitar (se nedan). Om detta lyckas, gå till steg #5. Om det misslyckas, gå tillbaka till steg #1.
Varje del av kakan som bara hör till en enda sista bit ges till ägaren av den biten. Varje del av kakan som hör till de två sista bitarna delas proportionellt med valfri deterministisk proportionell divisionsalgoritm.

Algoritmen garanterar att varje deltagare med stor sannolikhet får minst hälften av sin kandidatbit, vilket innebär (om preferensfunktionerna är additiva) att värdet kommer att vara minst . ${\tfrac {an}{2))$

Det finns O( n ) kandidatbitar och O( n ) ytterligare snitt i steg #5 som tar O(1) tid. Därför är den totala körtiden för algoritmen O( n ).

Huvuduppgiften i detta schema är valet av de sista bitarna i steg #4:

Låt oss börja med att skapa en skärningsgraf , en graf vars hörn är semifinalbitarna och en båge från del I av medlem i till del J av medlem j existerar om del I skär J del av medlem j (därav, om vi väljer chunk I och vill undvika korsningar måste vi välja del J också).

Låt oss välja en godtycklig deltagare i , som ännu inte har fått sin del, och välja en godtycklig del I av denna deltagare som den sista biten. Sedan går vi igenom kopplingen i skärningsgrafen och väljer som slutbitar alla de bitar som nås från vertex I . Det finns två bra scenarier – antingen delar vi ut en sista bit till varje deltagare och slutför på så sätt proceduren, eller så når vi en bit som inte har några utgående länkar (vilket innebär att den inte skär andra bitar). I det senare fallet väljer vi helt enkelt en annan bit från en av de återstående medlemmarna och fortsätter. Det dåliga scenariot inträffar när vår resa leder till två olika bitar av samma medlem, eller, motsvarande, en annan del av medlem i som vi började resan från. En sådan väg som leder från en del av deltagare i till en annan del av samma deltagare kallas en parad väg . Om skärningsdiagrammet inte innehåller parade vägar, returnerar den beskrivna algoritmen en uppsättning av n icke-överlappande slutstycken, och vi har det önskade resultatet. Nu återstår att beräkna sannolikheten för att skärningsgrafen innehåller en parad bana.

Tänk först på det speciella fallet där alla deltagare har samma preferensfunktioner (och därmed samma uppsättning kandidatpjäser). I det här fallet är sannolikheten för en parad bana lätt att beräkna, eftersom sannolikheten för varje båge är 1/ an , och alla kanter är oberoende, så sannolikheten för en viss parad bana med längden k är , och sannolikheten för någon parad väg är högst: ${\displaystyle {\tfrac {1}{(an)^{k))))$

\sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k))}=O\vänster({\frac {1}{a^{2 }}}\höger)

Genom att välja d =1 och ett tillräckligt stort a kan denna sannolikhet göras godtyckligt liten. Detta gäller även om vi utelämnar semifinalvalsfasen (#3) och betraktar alla kvartsfinalister som semifinalister.

Observera att det här fallet liknar bollarna i urnor modell . Detta bevisar att om d urnor väljs godtyckligt för varje boll, så kan en urna väljas för varje boll så att alla urnor är olika (max antal bollar är 1).

I den allmänna kakmodellen, när preferensfunktionerna är olika, är kantsannolikheterna i korsningsgrafen beroende, men tack vare semifinalistvalsfasen kan vi visa att sannolikheten för att korsningsgrafen innehåller en parad längdväg vid minst 3 överstiger inte . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Det återstår att överväga parade vägar med längd 2. Tyvärr är sannolikheten att få en sådan parad väg i skärningsdiagrammet inte försumbar. Men med stor sannolikhet är det möjligt att dela upp deltagarna i två grupper, som var och en inte har parade vägar med längd 2. Därför kan vi köra algoritmen för att välja de sista bitarna två gånger, en gång för varje grupp. En skärning kan bara ske mellan de sista delarna av olika grupper, därför överstiger inte överlappningen vid varje punkt av kakan 2. Sannolikheten att en sådan 2-partition är omöjlig överstiger inte . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

Efter att ha summerat de två uttrycken ovan och tagit d = 2 får vi att sannolikheten för misslyckande kvarstår . Kom ihåg att a är ett förhållande mellan proportionalitet - ju större värde vi vill garantera varje deltagare, desto mer sannolikt är det att divisionen misslyckas och bör startas från steg #1. $O\left({\frac {1}{a^{2))}\right)$

Vissa algoritmer fungerar också om snitten är ungefärliga, det vill säga att deltagarna inte vet om de markerade bitarna är lika. De kan markera en bit med ett p -procentvärde över eller under det obligatoriska värdet, och det exakta felet väljs slumpmässigt [1] .

High Confidence Protocol

Du kan ytterligare minska risken för misslyckande genom att använda följande schema [2] :

Vi kör det ursprungliga protokollet två gånger.
På varje körning tar vi bort alla deltagare som är i början av den parade vägen och fördelar de sista bitarna endast bland de återstående deltagarna, som i den ursprungliga algoritmen.
Om varje medlem inte togs bort vid någon körning fick vi det vi behövde, eftersom varje medlem nu har en sista bit.

Sannolikheten att ta bort en viss deltagare i varje pass är . Sannolikheten för att ta bort en viss deltagare i båda körningarna är lika med . Därför är sannolikheten för misslyckande , och den tenderar till 0 när n ökar, även om det partiella proportionalitetsförhållandet a hålls konstant. $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)$

Relaterade frågor

Kakmodellen kan betraktas som en generalisering av bollproblemmodellen . Denna modell finner bred användning inom områden som lastbalansering . I dessa situationer representerar bollen arbete som kan tilldelas olika maskiner (i vår terminologi, urnor). Grovt sett är fördelningen av belastningen av identiska maskiner kulor och urnor, och fördelningen av belastningen av ojämna maskiner skär kakan. Därför är det helt klart att kakmodellen och Edmonds-Prus-protokollet bör ha intressanta tillämpningar när det gäller lastfördelning på olika maskiner [1] .

Anteckningar

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

Litteratur

Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47:e årliga IEEE Symposium on Foundations of Computer Science (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Säkert skära en tårta i ungefär rättvisa bitar // Algoritmiska aspekter i information och ledning. - 2008. - T. 5034. - (Lecture Notes in Computer Science). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .