Efficient computation of the Banzhaf voting power index
Read and subscribe to these posts on Substack.
Introduction
Cooperative game theory’s voting power indices will undoubtedly become important tools in blockchain-based governance systems and the pricing of governance tokens in the years to come.
In a previous post, we demonstrated the Banzhaf power index and performed a voting power analysis on the weighted voting system of MolochDAO. At the time of the analysis, Moloch’s voting system had fewer than 100 members and less than 8,000 units of voting power.
However, real tokens supplies have tens or hundreds of thousands of voters and millions or billions of units of voting power, making computations of their power indices intractable using naïve approaches.
In this post, we present practical strategies for computing Banzhaf voting power for realistic on-chain voting systems. We introduce an open source project for efficient Banzhaf calculations that can handle some real data, implemented in Go.
Computation strategies for the Banzhaf power index
This section is technical. If you are interested in practical applications and results, then skip to the last section.
We now examine approaches for efficient computations of the Banzhaf index. In the following discussion, let us denote by n the number of voters in the weighted voting system. Let t be the sum of all the voting weights of the voters — in other words, the number of units in the token supply. Finally, the quota of the system— the number of votes needed to pass a proposal — is denoted by q; we note that typically q=t/2+1 for systems with simple majority rule.
Computation using naïve enumeration of coalitions
Computing voting power entails counting coalitions (subsets) of a set of voters, and therefore the naïve implementation has complexity in O(2ⁿ). My original attempt at computing a Banzhaf index naïvely in [Brukhman 2019] would become intractable around n = 20. In light of the following much smarter methods, this method is not recommended for realistic computations; however, it may be useful for understanding the power index construct.
Computation using a special generating function
In [Heger 2013], a generating function approach is used to improve the complexity of the calculation. A product of a certain set of n binomials produces a polynomial P whose degree is t. Because of the special choice of binomials, the degree of each term of P represents a voting weight and the coefficient of each term counts the number of coalitions that achieved this weight.
Though Heger lists O(n²t) as the complexity, the algorithm presented can be improved my storing the polynomial across calculations for each voter. The polynomial may be computed in O(nt) time and O(t) space. Subsequently, we can traverse the polynomial and sum coefficients in order to count all the coalitions in which a particular voter was critical, also in O(nt).
Computation using dynamic programming
Both [Uno 2003] and [Keijzer 2008] discuss a dynamic programming method for precise calculations of Banzhaf indices. The method uses a recursively-defined function f to calculate the number of swings of voters and saves them in memory. A symmetric recursive function b is introduced, which calculates the same swings but in the backwards direction.
The mathematical intuition here is that f is closely related to the polynomial multiplication performed in the generating function approach. But by exploiting symmetries, we can get the complexity down from O(nt) to O(nq), which is up to a factor of 2 improvement.
Approximation using probabilistic sampling
The probabilistic sampling approach discussed in [Bachrach 2008] is only an approximation of the index, not a deterministic calculation. However, as the algorithm discussed invokes Hoeffding’s Inequality, we can approach the real value with an arbitrary precision.
The algorithm essentially goes through random trials where it considers a random voting outcome and measures in how many such trials a givˆen voter can swing the outcome. We can also calculate a number of trials k that we would need to perform in order to get an approximate Banzhaf value within ε of the actual one, with a confidence level of 1-δ.
For example, getting within 4 decimal places of the real value with a confidence of 99% would require at least k = 264,915,869 trials. Since the complexity of this algorithm is O(nk), the best use of this approximation technique is when the token supply is very large and high precision is required — our generating function algorithm above becomes too slow.
Approximation using re-weighting of the distribution
Banzhaf power is a discrete value but generally correlates with the voter’s percent ownership in the token supply. That means small perturbations and multiplicative operations on the entire set of voting weights (and quota) will generally result only in small deviations of the Banzhaf outputs.
This suggests the following strategy to make Banzhaf calculations more tractable on token supplies with a very large t: take the set of token weights W = (w_1, …, w_n) and a real divisor d > 0, and construct a new voting system W’ = (w_1/d, … w_n/d) whose Banzhaf indices will be approximately the same, but whose computation complexity will be O(nt/d) — an improvement on running time by a factor of d.
Contribute to open source for Banzhaf index computation
If you are technical, please check out the go-banzhaf library on Github, which contains my implementation of the generating function algorithm above. I am looking for core contributors who can help to implement some of the dynamic programming and approximation approaches to Banzhaf calculations, especially those in [Uno 2003] and [Keijzer 2008].
References
- [Bachrach 2008] Approximating power indices
- [Brukhman 2019] Naïve implementation of a Banzhaf-like index
- [Heger 2013] Using generating functions to compute power indices
- [Uno 2003] Efficient computation of power indices for weighted majority games
- [Keijzer 2008] A survey on the computation of power indices
