Edmonds-Prus-protokollen

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. januar 2021; verifikation kræver 1 redigering .

Edmonds-Prus- protokollen er en retfærdig kageskæringsprotokol . Dens mål er at opnå en delvis proportional opdeling af en heterogen ressource blandt n personer, således at hver deltager modtager en delmængde af kagen (stykket), som hver deltager estimerer mindst 1/ an af det fulde estimat, hvor er en tilstrækkelig stor konstant . Algoritmen er probabilistisk med køretid O( n ) med en sandsynlighed for succes tæt på 1. Protokollen er udviklet af Jeff Edmond og Kirk Prus, som de senere forbedrede med Jaisingh Solanki. $a\geqslant 10$

Motivation

Proportional opdeling af kagen kan opnås ved hjælp af den rekursive bisektionsalgoritme i tid . Nogle resultater om kompleksitet viser, at denne køretid er optimal over en bred vifte af antagelser. Især er rekursiv halvering den hurtigste algoritme til at opnå fuld proportionalitet, når brikkerne skal forbindes, og det er den hurtigst mulige deterministiske algoritme til at opnå selv partiel proportionalitet, og selvom det er tilladt at skære i afbrudte stykker. Der er et tilfælde, der ikke er dækket af resultaterne af kompleksitet, dette er tilfældet med probabilistiske algoritmer , der kun garanterer delvis proportionalitet og muligheden for afbrudte stykker . Edmonds-Prus-protokollen har til formål at give en køretid på O( n ) kun for dette tilfælde. $O(n\log n)$

Protokol

Den generelle ordning, efter Edmunds og Prus, er som følger [1] :

Hver deltager deler kagen privat i et identisk stykke (ifølge hans subjektive vurdering). Disse stykker kaldes kandidatstykker . $n\cdot an$
Hver deltager vælger 2 d kandidatbrikker med samme sandsynlighed og afkast ( d er en konstant og vil blive defineret senere). Kandidater grupperes i d -par, som deltageren rapporterer til algoritmen. Disse parringer kaldes kvartfinale-bindinger . $n\cdot d$
Fra hvert kvartfinalebundt udvælger algoritmen én brik, den der har krydsninger med det mindste antal andre kandidater. Disse brikker kaldes semifinalebrikker . $n\cdot d$
For hver deltager vælger algoritmen en enkelt brik, disse brikker kaldes endelige . De sidste brikker udvælges således, at hvert punkt er dækket af højst to sidste brikker (se nedenfor). Hvis dette lykkes, skal du gå til trin #5. Hvis det mislykkes, skal du gå tilbage til trin #1.
Hver del af kagen, der kun tilhører et enkelt sidste stykke, gives til ejeren af det stykke. Hver del af kagen, der hører til de sidste to stykker, divideres proportionalt med enhver deterministisk proportional divisionsalgoritme.

Algoritmen garanterer, at hver deltager med stor sandsynlighed modtager mindst halvdelen af sit kandidatstykke, hvilket indebærer (hvis præferencefunktionerne er additive), at værdien vil være mindst . ${\tfrac {an}{2))$

Der er O( n ) kandidatstykker og O( n ) yderligere klip i trin #5, der tager O(1) tid. Derfor er den samlede køretid for algoritmen O( n ).

Hovedopgaven i dette skema er valget af de sidste stykker i trin #4:

Lad os starte med at lave en skæringsgraf , en graf, hvis toppunkter er de semi-finale bidder, og en bue fra del I af medlem i til del J af medlem j eksisterer, hvis del I skærer J del af medlem j (derfor, hvis vi vælger chunk I og vil undgå kryds, skal vi også vælge stykke J ).

Lad os vælge en vilkårlig deltager i , som endnu ikke har modtaget sin brik, og vælge en vilkårlig brik I af denne deltager som den endelige brik. Derefter gennemgår vi forbindelsen i skæringsgrafen og vælger som de sidste brikker alle de brikker, der nås fra toppunktet I . Der er to gode scenarier - enten uddeler vi et sidste stykke til hver deltager og afslutter dermed proceduren, eller også når vi et stykke, der ikke har udgående links (hvilket betyder, at det ikke krydser andre stykker). I sidstnævnte tilfælde vælger vi blot et andet stykke fra et af de resterende medlemmer og fortsætter. Det dårlige scenarie sker, når vores rejse fører til to forskellige bidder af det samme medlem, eller tilsvarende en anden luns af medlem i , hvorfra vi startede rejsen. En sådan sti, der fører fra et stykke deltager i til et andet stykke af den samme deltager, kaldes en parret sti . Hvis skæringsgrafen ikke indeholder parrede stier, returnerer den beskrevne algoritme et sæt af n ikke-overlappende slutstykker, og vi har det ønskede resultat. Nu er det tilbage at beregne sandsynligheden for, at skæringsgrafen indeholder en parret sti.

Overvej først det særlige tilfælde, hvor alle deltagere har de samme præferencefunktioner (og dermed det samme sæt kandidatstykker). I dette tilfælde er sandsynligheden for en parret sti let at beregne, da sandsynligheden for hver bue er 1/ an , og alle kanter er uafhængige, så sandsynligheden for en bestemt parret bane af længden k er , og sandsynligheden for evt. parret sti er højst: ${\displaystyle {\tfrac {1}{(an)^{k))))$

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

Ved at vælge d =1 og et tilstrækkeligt stort a , kan denne sandsynlighed gøres vilkårligt lille. Dette er sandt, selvom vi udelader semifinaleudvælgelsesfasen (#3) og betragter alle kvartfinalister som semifinalister.

Bemærk, at denne sag ligner kuglerne i urner model . Dette beviser, at hvis d urner vælges vilkårligt for hver bold, så kan der vælges en urne for hver bold, så alle urner er forskellige (det maksimale antal bolde er 1).

I den generelle kagemodel, når præferencefunktionerne er forskellige, er kantsandsynlighederne i skæringsgrafen afhængige, men takket være semifinalistudvælgelsesfasen kan vi vise, at sandsynligheden for, at skæringsgrafen indeholder en parret længdevej ved mindst 3 overstiger ikke . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Det er tilbage at overveje parrede stier af længde 2. Desværre er sandsynligheden for at opnå en sådan parret vej i skæringsgrafen ikke ubetydelig. Det er dog med stor sandsynlighed muligt at dele deltagerne op i to grupper, som hver ikke har parrede stier af længde 2. Derfor kan vi køre algoritmen til at vælge de sidste brikker to gange, én gang for hver gruppe. Et skæringspunkt kan kun forekomme mellem de sidste stykker af forskellige grupper, hvorfor overlapningen på hvert punkt af kagen ikke overstiger 2. Sandsynligheden for, at en sådan 2-partition er umulig , overstiger ikke . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

Efter at have summeret de to ovenstående udtryk og taget d = 2, får vi, at sandsynligheden for fejl forbliver . Husk på, at a er et forhold mellem proportionalitet - jo større værdi, vi ønsker at garantere hver deltager, jo mere sandsynligt er det, at divisionen mislykkes og bør startes fra trin #1. $O\left({\frac {1}{a^{2))}\right)$

Nogle algoritmer virker også, hvis snittene er omtrentlige, det vil sige, at deltagerne ikke ved, om de markerede brikker er lige store. De kan markere et stykke med en p procent værdi over eller under den påkrævede værdi, og den nøjagtige fejl vælges tilfældigt [1] .

High Confidence Protocol

Du kan yderligere reducere risikoen for fejl ved at bruge følgende skema [2] :

Vi kører den originale protokol to gange.
På hvert løb fjerner vi alle deltagere, der er i begyndelsen af den parrede sti, og fordeler kun de sidste brikker blandt de resterende deltagere, som i den originale algoritme.
Hvis hvert medlem ikke blev fjernet på nogen bane, fik vi det, vi havde brug for, da hvert medlem nu har en sidste brik.

Sandsynligheden for at fjerne en bestemt deltager i hvert pass er . Sandsynligheden for at fjerne en bestemt deltager i begge kørsler er lig med . Derfor er sandsynligheden for fejl , og den har en tendens til 0, når n stiger, selvom det partielle proportionalitetsforhold a holdes 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)$

Relaterede problemer

Kagemodellen kan betragtes som en generalisering af boldproblemmodellen . Denne model finder bred anvendelse inden for områder som belastningsbalancering . I disse situationer repræsenterer bolden arbejde, der kan tildeles forskellige maskiner (i vores terminologi, urner). Groft sagt er fordelingen af belastningen af identiske maskiner kugler og urner, og fordelingen af belastningen af ulige maskiner skærer kagen. Derfor er det helt klart, at kagemodellen og Edmonds-Prus-protokollen bør have interessante anvendelser med hensyn til belastningsfordeling på uens maskiner [1] .

Noter

↑ 1 2 3 Edmonds, Pruhs, 2006 , s. 623.
↑ Edmonds, Pruhs, Solanki, 2008 , s. 155-164.

Litteratur

Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. årlige 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. Selvsikkert at skære en kage i tilnærmelsesvis retfærdige stykker // Algoritmiske aspekter i information og ledelse. - 2008. - T. 5034. - (Lecture Notes in Computer Science). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .