# 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.