Rejoignez-Nous sur

Calcul efficace de l'indice de pouvoir de vote Banzhaf

1*eTfyIwr35m4cf2RGZHzJog

News

Calcul efficace de l'indice de pouvoir de vote Banzhaf

Jake Brukhman

Lisez et abonnez-vous à ces messages sur Sous-pile.

Théorie des jeux coopératifs indices de droit de vote deviendra sans aucun doute des outils importants dans les systèmes de gouvernance basés sur la blockchain et la tarification des jetons de gouvernance dans les années à venir.

Dans un article précédent, nous avons démontré la Indice de puissance de Banzhaf et effectué une analyse du pouvoir de vote sur le système de vote pondéré de MolochDAO. Au moment de l’analyse, le système de vote de Moloch comptait moins de 100 membres et moins de 8 000 unités de vote.

Cependant, les fournitures de jetons réels ont des dizaines ou des centaines de milliers d'électeurs et des millions ou des milliards d'unités de pouvoir de vote, ce qui rend les calculs de leurs indices de pouvoir intraitables en utilisant des approches naïves.

Dans cet article, nous présentons des stratégies pratiques pour calculer le pouvoir de vote Banzhaf pour des systèmes de vote en chaîne réalistes. Nous introduisons un projet open source pour des calculs de Banzhaf efficaces qui peut gérer certaines données réelles, implémentées dans Aller.

Cette section est technique. Si vous êtes intéressé par les applications pratiques et les résultats, passez à la dernière section.

Nous examinons maintenant les approches pour des calculs efficaces de l'indice de Banzhaf. Dans la discussion suivante, notons par n le nombre d'électeurs dans le système de vote pondéré. Laisser t être la somme de tous les poids de vote des électeurs – en d'autres termes, le nombre d'unités dans l'offre de jetons. Enfin, le quota du système – le nombre de voix nécessaires pour adopter une proposition – est indiqué par q; nous notons que généralement q = t / 2 + 1 pour les systèmes à règle de majorité simple.

Calcul utilisant une énumération naïve des coalitions

Le calcul du pouvoir de vote implique le comptage des coalitions (sous-ensembles) d'un ensemble d'électeurs, et donc la mise en œuvre naïve est complexe dans O (2ⁿ). Ma tentative originale de calculer un index Banzhaf naïvement dans (Brukhman 2019) deviendrait intraitable autour n = 20. À la lumière des méthodes beaucoup plus intelligentes suivantes, cette méthode n'est pas recommandée pour des calculs réalistes; cependant, il peut être utile pour comprendre la construction de l'indice de puissance.

Calcul utilisant une fonction de génération spéciale

Dans (Heger 2013), une l'approche de la fonction de génération est utilisée pour améliorer la complexité du calcul. Un produit d'un certain ensemble de n les binômes produisent un polynôme P dont le diplôme est t. En raison du choix spécial des binômes, le degré de chaque terme de P représente un poids de vote et le coefficient de chaque terme compte le nombre de coalitions qui ont atteint ce poids.

Bien que Heger énumère O (n²t) quant à la complexité, l'algorithme présenté peut être amélioré en stockant le polynôme dans les calculs pour chaque électeur. Le polynôme peut être calculé en O (nt) temps et O (t) espace. Par la suite, nous pouvons parcourir les coefficients polynomiaux et de somme afin de compter toutes les coalitions dans lesquelles un électeur particulier a été critique, également dans O (nt).

Calcul utilisant la programmation dynamique

Tous les deux (Uno 2003) et (Keijzer 2008) discuter d'une méthode de programmation dynamique pour des calculs précis des indices de Banzhaf. La méthode utilise une fonction définie récursivement F pour calculer le nombre d'oscillations d'électeurs et les enregistre en mémoire. Une fonction récursive symétrique b est introduit, qui calcule les mêmes balançoires mais dans le sens inverse.

L'intuition mathématique ici est que F est étroitement liée à la multiplication polynomiale effectuée dans l'approche de la fonction de génération. Mais en exploitant les symétries, nous pouvons réduire la complexité de O (nt) à O (nq), ce qui correspond à un facteur d'amélioration de 2.

Approximation utilisant l'échantillonnage probabiliste

L'approche d'échantillonnage probabiliste discutée dans (Bachrach 2008) n'est qu'une approximation de l'indice, pas un calcul déterministe. Cependant, comme l'algorithme discuté invoque L'inégalité de Hoeffding, nous pouvons approcher la valeur réelle avec une précision arbitraire.

L'algorithme passe essentiellement par des essais aléatoires où il considère un résultat de vote aléatoire et mesure le nombre d'essais de ce type qu'un électeur donné peut influer sur le résultat. Nous pouvons également calculer un certain nombre d'essais k que nous aurions besoin d'effectuer afin d'obtenir une valeur approximative de Banzhaf dans ε du réel, avec un niveau de confiance de 1-δ.

Par exemple, obtenir à moins de 4 décimales de la valeur réelle avec une confiance de 99% nécessiterait au moins k = 264 915 869 essais. Étant donné que la complexité de cet algorithme est O (nk), la meilleure utilisation de cette technique d'approximation est lorsque l'approvisionnement en jetons est très important et qu'une grande précision est requise – notre algorithme de fonction de génération ci-dessus devient trop lent.

Approximation utilisant la repondération de la distribution

Le pouvoir de Banzhaf est une valeur discrète mais est généralement en corrélation avec le pourcentage de propriété de l'électeur dans l'approvisionnement en jetons. Cela signifie que de petites perturbations et des opérations multiplicatives sur l'ensemble des poids de vote (et des quotas) n'entraîneront généralement que de petites déviations des sorties de Banzhaf.

Cela suggère la stratégie suivante pour rendre les calculs de Banzhaf plus traitables sur les fournitures de jetons avec un très grand t: prendre l'ensemble des poids des jetons W = (w_1,…, w_n) et un vrai diviseur d> 0, et construire un nouveau système de vote W ’= (w_1 / j,… w_n / j) dont les indices de Banzhaf seront sensiblement les mêmes, mais dont la complexité de calcul sera O (nt / d) – une amélioration du temps de fonctionnement d'un facteur de ré.

Github Repo: https://github.com/jbrukh/go-banzhaf

Si vous êtes technique, veuillez Vérifiez go-banzhaf bibliothèque sur Github, qui contient mon implémentation de l'algorithme de fonction de génération ci-dessus. Je recherche des contributeurs de base qui peuvent aider à mettre en œuvre certaines des approches de programmation dynamique et d'approximation des calculs de Banzhaf, en particulier celles de (Uno 2003) et (Keijzer 2008).

  1. (Bachrach 2008) Indices de puissance approximatifs
  2. (Brukhman 2019) Implémentation naïve d'un index de type Banzhaf
  3. (Heger 2013) Utilisation de fonctions de génération pour calculer les indices de puissance
  4. (Uno 2003) Calcul efficace des indices de puissance pour les jeux à majorité pondérée
  5. (Keijzer 2008) Une enquête sur le calcul des indices de puissance



Traduction de l’article de Jake Brukhman : Article Original

BlockBlog

Le Meilleur de l'Actualité Blockchain Francophone & Internationale | News, Guides, Avis & Tutoriels pour s'informer et démarrer facilement avec Bitcoin, les Crypto-Monnaies et le Blockchain. En Savoir Plus sur L'Équipe BlockBlog

Commenter cet Article

Commenter cet Article

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Plus dans News

Les Plus Populaires

Acheter des Bitcoin

Acheter des Alt-Coins

Sécuriser vos Cryptos

Vêtements et Produits Dérivés

Top