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

```
sage: q = 30
sage: w = [28,16,5,4,3,3]
sage: n = len(w)
sage: R = PolynomialRing(QQ,'x',n)
sage: xs = R.gens()
sage: 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\):

```
sage: pm = pr.monomials()
sage: pw = [x for x in pr if sum(x.degrees()) >= q]
sage: 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:

```
def mwc(q,t,p):
if len(p)==0:
return(t)
else:
for x in p[1:]:
if p[0].divides(x):
p.remove(x)
return(mwc(q,t+[p[0]],p[1:]))
```

We can apply it:

```
sage: pw2 = pw.copy()
sage: mwc1 = mwc(q,[],pw2)
sage: 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.

```
sage: dp = {xs[i]:0 for i in range(n)}
sage: for m in mcw1:
mv = m.variables()
nm = len(mv)
for x in mv:
dps[x] += 1/nm
sage: 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:

```
sage: s = sum(dps.values())
for x in dps.keys():
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\):

```
sage: w = [28,16,5,4,3,3]
sage: q = 30
sage: n = len(w)
sage: R = PolynomialRing(QQbar,'x',n)
sage: xs = R.gens()
sage: p = prod(1+xs[i]^w[i] for i in range(n))
```

Now for the reeducation and computation:

```
sage: ids = [R.ideal(xs[i]^w[i]) for i in range(n)]
sage: for i in range(n):
pri = pr.reduce(ids[i])
ms = pri.monomials()
cs = pri.coefficients()
cds = [(x,sum(y.degrees())) for x,y in zip(cs,ms)]
beta += [sum(x for (x,y) in cds if y>=(q-w[i]) and (y<q))]
sage: 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:

```
sage: def banzhaf(q,w):
n = len(w)
beta = []
for i in range(n):
pp = prod(1+x^w[j] for j in range(n) if j != i)
cc = pp.list()
beta += [sum(cc[j] for j in range(len(cc)) if j>=(q-w[i]) and (j<q))]
return(beta)
```

These values can then be easily normalized to produce the Banzhaf power indices.