# Voting power (6): Polynomial rings

Share on:

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 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.divides(x):
p.remove(x)
return(mwc(q,t+[p],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.