Voting power (6): Polynomial rings
As we have seen previously, it's possible to compute power indices by means of polynomial generating functions. We shall extend previous examples to include the Deegan-Packel index, in a way somewhat different to that of Alonso-Meijide et al (see previous post for reference).
Again, suppose we consider the voting game
\[ [30;28,16,5,4,3,3] \]
What we'll do here though, rather than using just one variable, we'll have a variable for each voter. We'll use Sage for this, as it's open source, and provides a very rich environment for computing with polynomial rings.
We first create the polynomial
\[ p = \prod_{k=0}^5(1+x_k^{w_k}) \]
where \(w_i\) are the weights given above. We are using the Python (and hence Sage) convention that indices are numbered startng at zero.
1sage: q = 30
2sage: w = [28,16,5,4,3,3]
3sage: n = len(w)
4sage: R = PolynomialRing(QQ,'x',n)
5sage: xs = R.gens()
6sage: pr = prod(1+xs[i]^w[1] for i in range(n)
Now we can extract all the monomials, and consider only those for which the degree sum is not less than the quota \(q\):
1sage: pm = pr.monomials()
2sage: pw = [x for x in pr if sum(x.degrees()) >= q]
3sage: pw = pw[::-1]; pw
\begin{aligned} &\left[x_{1}^{16} x_{2}^{5} x_{3}^{4} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{5}^{3},\; x_{0}^{28} x_{4}^{3},\; x_{0}^{28} x_{3}^{4},\; x_{0}^{28} x_{2}^{5},\; x_{0}^{28} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{3}^{4} x_{5}^{3},\; x_{0}^{28} x_{3}^{4} x_{4}^{3},\right.\cr &\qquad x_{0}^{28} x_{2}^{5} x_{5}^{3},\; x_{0}^{28} x_{2}^{5} x_{4}^{3},\; x_{0}^{28} x_{2}^{5} x_{3}^{4},\; x_{0}^{28} x_{3}^{4} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{2}^{5} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{2}^{5} x_{3}^{4} x_{5}^{3},\cr &\qquad x_{0}^{28} x_{2}^{5} x_{3}^{4} x_{4}^{3},\; x_{0}^{28} x_{2}^{5} x_{3}^{4} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{1}^{16},\; x_{0}^{28} x_{1}^{16} x_{5}^{3},\; x_{0}^{28} x_{1}^{16} x_{4}^{3},\; x_{0}^{28} x_{1}^{16} x_{3}^{4},\cr &\qquad x_{0}^{28} x_{1}^{16} x_{2}^{5},\; x_{0}^{28} x_{1}^{16} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{1}^{16} x_{3}^{4} x_{5}^{3},\; x_{0}^{28} x_{1}^{16} x_{3}^{4} x_{4}^{3},\; x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{5}^{3},\cr &\qquad x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{4}^{3},\; x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{3}^{4},\; x_{0}^{28} x_{1}^{16} x_{3}^{4} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{4}^{3} x_{5}^{3},\cr &\qquad \left. x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{3}^{4} x_{5}^{3},\; x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{3}^{4} x_{4}^{3},\; x_{0}^{28} x_{1}^{16} x_{2}^{5} x_{3}^{4} x_{4}^{3} x_{5}^{3}\right] \end{aligned}
As we did with subsets, we can winnow out the monomials which are multiples of others, by writing a recursive function:
1def mwc(q,t,p):
2 if len(p)==0:
3 return(t)
4 else:
5 for x in p[1:]:
6 if p[0].divides(x):
7 p.remove(x)
8 return(mwc(q,t+[p[0]],p[1:]))
We can apply it:
1sage: pw2 = pw.copy()
2sage: mwc1 = mwc(q,[],pw2)
3sage: mwc1
\[ \left[x_{1}^{16} x_{2}^{5} x_{3}^{4} x_{4}^{3} x_{5}^{3},\; x_{0}^{28} x_{5}^{3},\; x_{0}^{28} x_{4}^{3},\; x_{0}^{28} x_{3}^{4},\; x_{0}^{28} x_{2}^{5},\; x_{0}^{28} x_{1}^{16}\right] \]
Now it's just a matter of working out the indices from the variables, and this is most easily done in Python with a dictionary, with the variables as keys and their indices as values.
1sage: dp = {xs[i]:0 for i in range(n)}
2sage: for m in mcw1:
3 mv = m.variables()
4 nm = len(mv)
5 for x in mv:
6 dps[x] += 1/nm
7sage: dp
\[ \left\{x_{0} : \frac{5}{2}, x_{1} : \frac{7}{10}, x_{2} : \frac{7}{10}, x_{3} : \frac{7}{10}, x_{4} : \frac{7}{10}, x_{5} : \frac{7}{10}\right\} \]
And this of course can be normalized:
1sage: s = sum(dps.values())
2 for x in dps.keys():
3 dps[x] = dps[x]/s
\[ \left\{x_{0} : \frac{5}{12}, x_{1} : \frac{7}{60}, x_{2} : \frac{7}{60}, x_{3} : \frac{7}{60}, x_{4} : \frac{7}{60}, x_{5} : \frac{7}{60}\right\} \]
And these are the values we found in the previous post, using Julia and working with subsets.
Back to Banzhaf
Recall that the Banzhaf power indices could be computed from polynomials in two steps. For voter \(i\), define
\[ f_i(x) = \prod_{j\ne i}(1+x^{w_j}) \]
and suppose that the coefficient of \(x^k\) is \(a_k\). Then define
\[ \beta_i=\sum_{j=q-w_i}^{q-1}a_j \]
and these values are normalized for the Banzhaf power indices.
Suppose we define, as for the Deegan-Packel indices,
\[ p = \prod_{k=1}^n(1+x_i^{w_i}). \]
Then reduce \(p\) modulo \(x_i^{w_i}\). This has the effect of setting \(x_i^{w_i}=0\) in \(p\) so simply removes all monomials containing \(x_i^{w_i}\). Then \(\beta_i\) is computed by adding the coefficients of all monomials whose degree sum lies between \(q-w_i\) and \(q-1\).
First define the polynomial ring and the polynomial \(p\):
1sage: w = [28,16,5,4,3,3]
2sage: q = 30
3sage: n = len(w)
4sage: R = PolynomialRing(QQbar,'x',n)
5sage: xs = R.gens()
6sage: p = prod(1+xs[i]^w[i] for i in range(n))
Now for the reeducation and computation:
1sage: ids = [R.ideal(xs[i]^w[i]) for i in range(n)]
2sage: for i in range(n):
3 pri = pr.reduce(ids[i])
4 ms = pri.monomials()
5 cs = pri.coefficients()
6 cds = [(x,sum(y.degrees())) for x,y in zip(cs,ms)]
7 beta += [sum(x for (x,y) in cds if y>=(q-w[i]) and (y<q))]
8sage: print(beta)
\[ [30,2,2,2,2,2] \]
from which the Banzhaf power indices can be computed as
\[ \left[\frac{3}{4},\;\frac{1}{20},\;\frac{1}{20},\;\frac{1}{20},\;\frac{1}{20},\;\frac{1}{20}\right]. \]
Note that this is of course unnecessarily clumsy, as the Banzhaf indices can be easily and readily computed using univariate polynomials. We may thus consider this approach as a proof of concept, rather than a genuine alternative.
In Sage, Banzhaf indices can be computed with polynomials very neatly, given weights and a quota:
1sage: def banzhaf(q,w):
2 n = len(w)
3 beta = []
4 for i in range(n):
5 pp = prod(1+x^w[j] for j in range(n) if j != i)
6 cc = pp.list()
7 beta += [sum(cc[j] for j in range(len(cc)) if j>=(q-w[i]) and (j<q))]
8 return(beta)
These values can then be easily normalized to produce the Banzhaf power indices.