Vi gör en spel-teoretisk analys av valet av ledare, under antagandet att varje agent föredrar att ha någon ledare än att inte ha någon ledare alls. Vi visar att det är möjligt att uppnå en rättvis Nash jämvikt, där varje agent har en lika stor sannolikhet att bli vald ledare, i ett helt uppkopplat nätverk, i en dubbelriktad ring, och en enkelriktad ring, i synkron inställning. I den asynkrona miljön är Nash jämvikt inte riktigt rätt lösningskoncept. Snarare måste vi överväga ex post Nash jämvikt; detta innebär att vi har en Nash jämvikt oavsett vad en schemaläggning motståndare gör. Vi visar att ex post Nash jämvikt är uppnåelig i den asynkrona inställningen i alla nätverk vi anser, med hjälp av ett protokoll med begränsad körtid. I den asynkrona inställningen kräver vi dock att n > 2. Vi kan få en rättvis -Nash jämvikt om n = 2 i asynkron inställning, under vissa kryptografiska antaganden (specifikt, förekomsten av en pseudo-random nummergenerator och polynomiskt bundna agenter), med hjälp av idéer från bit-åtagande protokoll. Vi generaliserar sedan dessa resultat till en inställning där vi kan ha avvikelser av en koalition av storlek k. I detta fall kan vi få vad vi kallar en rättvis k-resilient jämvikt om n > 2k; under samma kryptografiska antaganden kan vi få en k-resilient jämvikt om n = 2k. Slutligen visar vi att, under minimala antaganden, inte bara våra protokoll ger en Nash jämvikt, de ger också en sekventiell jämvikt [Kreps och Wilson 1982], så spelarna även spela optimalt utanför jämviktsbanan.
Författarna till REF tillhandahåller en spelteoretisk analys av ledarens valalgoritmer på ett antal nätverk för både synkronfallet och asynkronfallet.
Distributed Protocols for Leader Election: a Game-Theoretic Perspective
{'venue': 'DISC', 'journal': None, 'mag_field_of_study': ['Computer Science']}