Lees en abonneer je op deze berichten op subgroep.
Coöperatieve speltheorieën stemkrachtindices zal de komende jaren ongetwijfeld belangrijke tools worden in op blockchain gebaseerde governancesystemen en de prijsstelling van governancetokens.
In een vorige post demonstreerden we de Banzhaf vermogensindex en een stemkrachtanalyse uitgevoerd op de gewogen stemsysteem van MolochDAO. Op het moment van de analyse had het stemsysteem van Moloch minder dan 100 leden en minder dan 8,000 eenheden stemrecht.
Echte tokens-voorraden hebben echter tien- of honderdduizenden kiezers en miljoenen of miljarden eenheden stemkracht, waardoor berekeningen van hun machtsindices onhandelbaar worden met behulp van naïeve benaderingen.
In dit bericht presenteren we praktische strategieën voor het berekenen van Banzhaf-stemkracht voor realistische on-chain stemsystemen. We introduceren een open source-project voor efficiënte Banzhaf-berekeningen die enkele echte gegevens aankan, geïmplementeerd in Go.
Dit gedeelte is technisch. Als u geïnteresseerd bent in praktische toepassingen en resultaten, ga dan naar het laatste gedeelte.
We onderzoeken nu benaderingen voor efficiënte berekeningen van de Banzhaf-index. Laten we in de volgende discussie aanduiden met n het aantal kiezers in het gewogen stemsysteem. Laten t de som zijn van alle stemgewichten van de kiezers - met andere woorden, het aantal eenheden in de tokenvoorraad. Ten slotte wordt het quotum van het systeem - het aantal stemmen dat nodig is om een voorstel goed te keuren - aangegeven met q; merken we dat meestal: q=t/2+1 voor systemen met een gewone meerderheidsregel.
Berekening met behulp van naïeve opsomming van coalities
Het berekenen van stemkracht houdt in dat coalities (subsets) van een reeks kiezers worden geteld, en daarom heeft de naïeve implementatie complexiteit in O(2ⁿ). Mijn oorspronkelijke poging om een Banzhaf-index naïef te berekenen in [Brukhman 2019] zou onhandelbaar worden rond n = 20. In het licht van de volgende veel slimmere methoden, wordt deze methode niet aanbevolen voor realistische berekeningen; het kan echter nuttig zijn om de constructie van de vermogensindex te begrijpen.
Berekening met behulp van een speciale genererende functie
In [Heger 2013], een genererende functiebenadering wordt gebruikt om de complexiteit van de berekening te verbeteren. Een product van een bepaalde set van n binomials produceert een polynoom P wiens diploma is? t. Vanwege de speciale keuze van binomials, de graad van elke term van P vertegenwoordigt een stemgewicht en de coëfficiënt van elke term telt het aantal coalities dat dit gewicht heeft bereikt.
Hoewel Heger lijsten O(n²t) als de complexiteit, kan het gepresenteerde algoritme worden verbeterd door de polynoom op te slaan in berekeningen voor elke kiezer. De polynoom kan worden berekend in O(nt) tijd en O(t) ruimte. Vervolgens kunnen we de polynoom- en somcoëfficiënten doorlopen om alle coalities te tellen waarin een bepaalde kiezer kritisch was, ook in O(nt).
Berekening met behulp van dynamisch programmeren
Te gebruiken zowel [Uno 2003] en [Keijzer 2008] een dynamische programmeermethode bespreken voor nauwkeurige berekeningen van Banzhaf-indices. De methode gebruikt een recursief gedefinieerde functie f om het aantal schommelingen van kiezers te berekenen en op te slaan in het geheugen. Een symmetrische recursieve functie b wordt geïntroduceerd, die dezelfde schommelingen berekent, maar in de achterwaartse richting.
De wiskundige intuïtie hier is dat: f is nauw verwant aan de polynoomvermenigvuldiging uitgevoerd in de genererende functiebenadering. Maar door gebruik te maken van symmetrieën, kunnen we de complexiteit verminderen van O(nt) naar O(nq), dat is tot een factor 2 verbetering.
Benadering met behulp van probabilistische steekproeven
De probabilistische steekproefbenadering besproken in [Bachach 2008] is slechts een benadering van de index, geen deterministische berekening. Echter, zoals het besproken algoritme aanroept: De ongelijkheid van Hoeffding, kunnen we de echte waarde benaderen met een willekeurige precisie.
Het algoritme doorloopt in wezen willekeurige proeven waarbij het een willekeurig stemresultaat beschouwt en meet in hoeveel van dergelijke proeven een bepaalde kiezer de uitkomst kan beïnvloeden. We kunnen ook een aantal proeven berekenen k die we zouden moeten uitvoeren om een geschatte Banzhaf-waarde te krijgen binnen ε van de werkelijke, met een betrouwbaarheidsniveau van 1-δ.
Als u bijvoorbeeld binnen 4 cijfers achter de komma van de werkelijke waarde wilt komen met een betrouwbaarheid van 99%, moet u minimaal k = 264,915,869 proeven. Aangezien de complexiteit van dit algoritme is O(nk), het beste gebruik van deze benaderingstechniek is wanneer de tokenvoorraad erg groot is en hoge precisie vereist is - ons genererende functie-algoritme hierboven wordt te traag.
Benadering met behulp van herweging van de verdeling
Banzhaf-macht is een discrete waarde, maar correleert over het algemeen met het percentage eigendom van de kiezer in de tokenvoorraad. Dat betekent dat kleine verstoringen en multiplicatieve bewerkingen op de hele set stemgewichten (en quota) over het algemeen slechts zullen resulteren in kleine afwijkingen van de Banzhaf-output.
Dit suggereert de volgende strategie om Banzhaf-berekeningen handelbaarder te maken voor tokenvoorraden met een zeer grote t: pak de set symbolische gewichten W = (w_1, …, w_n) en een echte deler d > 0, en bouw een nieuw stemsysteem W' = (w_1/d, … w_n/d) waarvan de Banzhaf-indices ongeveer hetzelfde zullen zijn, maar waarvan de berekeningscomplexiteit zal zijn O(nt/d) — een verbetering van de looptijd met een factor d.
Github-opslagplaats: https://github.com/jbrukh/go-banzhaf
Als je technisch bent, alsjeblieft bekijk de go-banzaf bibliotheek op Github, die mijn implementatie van het bovenstaande genererende functie-algoritme bevat. Ik ben op zoek naar kernbijdragers die kunnen helpen bij het implementeren van enkele van de dynamische programmerings- en benaderingsbenaderingen van Banzhaf-berekeningen, vooral die in [Uno 2003] en [Keijzer 2008].
- [Bachach 2008] Vermogensindexen bij benadering
- [Brukhman 2019] Naïeve implementatie van een Banzhaf-achtige index
- [Heger 2013] Genererende functies gebruiken om vermogensindexen te berekenen
- [Uno 2003] Efficiënte berekening van machtsindices voor gewogen meerderheidsspellen
- [Keijzer 2008] Een onderzoek naar de berekening van machtsindices
