Weighted voting systems

In a weighted voting system the voters each have a voting weight (or number of votes) they can use to cast on a motion.  There is also a quota that is the minimum number of votes necessary to carry a resolution.
An example of a weighted voting problem would be:

Voter:	Weight
A	4
B	2
C	1

with a quota of 5.

We will use the notation [q; W] = [q; A B C] = [5; 4 2 1] to denote this weighted voting problem.

A voter is critical in a winning coalition if without that voter’s participation the coalition would not be a winning one.

The power of each voter, takes into account the number of winning coalitions that voter is critical in , and is not necessarily a simple function of the weights.   In this example the power of voter B and C is the same even though C has half the strength. The winning coalitions for this example are  (A,B), (A,C) and  (A,B,C). Notice that B and C participate in the same number of winning coalitions.

There are two common methods used to determine the power of a voter—the Banzhaf power index and the Shapley-Shubik power index. We also discuss a third called the Johnston power index.

1)The Banzhaf power index

The Banzhaf power index for a voter is calculated by finding the total number of coalitions that player is critical in, say B_i, and  then dividing B_i  by the total sum of all B_k

Letting P_i  denote the power index of candidate , we have

Implementing a Scilab program to compute the Banzhaf power index involves computing all 2^10 coalitions and determining those that were winning and the voters critical in each winning coalition.  In Scilab the built in binary conversion routines simplified the program. For example with 4 voters there are 16 coalitions. Coalitions were determined by finding the binary representation  of each coalition. For example 13=1101_2 would be the coalition with A, B and D (not C). In general there are about 2^n  computations. For example with 10 voters there are  2^10 coalitions to consider.


2)The Shapley-Shubik power index

The Shapley-Shubik power index considers all permutations of voters as coalitions using sequential coalitions to measure the order in which that voter entered the coalition.  A critical player is the player in a sequential coalition who changes the coalition from a losing to a winning one. For example in the coalition (A,B,C)  the critical player is B since until the 2nd person, B, entered the coalition A only had 4 voters, 1 less than needed to carry the vote. In the coalition (B,C,A) voter A is critical since before A entered the coalition the prior 2 voters had acquired only 3 voters, 2 less than needed to carry the vote.

In Scilab a routine to calculate the Shapley-Shubik power index was greatly facilitated by the built in combinatorial routines including the “perms,” routine which calculated all possible lexicographic permutations of n voters.  Notice that there n! ordered coalitions to consider in the Shapley-Shubik  power index which becomes computationally intensive beyond n=8 or n=9. For n=10 there are 10!=3,628,800 permutations to consider many orders more than for the Banzhaf power index. To also keep the Scilab code for this routine simple we used the built in Scilab perms routine, which however stores all n! permutations requiring a lot of memory. For this reason the Shapley-Shubik index calculator is restricted to n=8.  

For  8 < n < 21 we present a modified Shapley-Shubik power index calculator routine based on sampling theory. This routine uses a sample of random permutations to approximate the Shapley-Shubik power index vector for n voters.  Use can be made of the Central Limit Theorem to approximate the error in the approximation depending on the sample size.  The sample size is specified by the user. We illustrate, for the voting scenario [q; W]=[12; 9 9 9 9 8 8 8 6 5 5 4 3] with sample size, 100,000 of the 12! total sequential coalitions. 

(See also Screenshots in Appendix 3)

Contestant by Weight	Shapley-Shubik Index (actual)	Randomized Shapley Index Calculation  (sample size 100,000)
9	0.1030	0.10335
9	0.1030	0.1031
9	0.1030	0.10342
9	0.1030	0.10395
8	0.0939	0.0936
8	0.0939	0.09399
8	0.0939	0.09236
6	0.0667	0.06745
5	0.0667	0.0661
5	0.0667	0.06704
4	0.0667	0.06663
3	0.0394	0.03901

The sampling routine illustrates one of the strong features of Scilab—its built-in random number generators.   The Scilab random number generator ‘grand,’ includes capabilities for many distributions (both univariate, and multivariate) as well as for sampling from Markov chains and random permutations.  It also offers a variety of at least six base-generating algorithms to choose from –the default being the Mersenne-Twister of M. Matsumoto and T. Nishimura.

3)The Johnston power index

The Johnston power index is a variation on the Banzhaf power in which a player’s index takes into account the size of the coalition for which that voter is critical.  Small coalitions for which a voter is critical contribute more to the power index of that voter than larger coalitions for which that voter is critical.  A coalition of three in which a voter is critical contributes a weighted critical value of 1/3 to that voters index, whereas a coalition of two in which that voter is critical contributes a weighted critical value of 1/2 to that voter’s index.   A voter’s index  is found by  summing all that voter’s critical values by the total sum of all voters’ critical values. Denote by W_i   the sum of all weighted critical values for candidate i, then again if  P_i  denotes the power index of candidate i  we have

The power indices for the 3 different measures for the voting problem [5; 4 2 1] are summarized below:

Voter	Banzhaf Index	Shapley-Shubik Index	Johnston Index
A	3/5	2/3	4/7
B	1/5	1/6	3/14
C	1/5	1/6	3/14

 The Scilab power index routines/scripts for the 4 weighted voting procedures are provided in Appendix 1 and detailed instructions on how to use them may be found in Appendix 2.

In the next section we describe how to use and become familiar with Scilab and provide information on using the standalone desktop version of Scilab as well as on how to access two Scilab in the cloud servers.