This program is available for only academic use, basically. Anyone can modify this program, but he/she has to write down the change of the modification on the top of the source code. Neither contact nor appointment to Takeaki Uno is needed. If one wants to re-distribute this code, do not forget to refer the newest code, and show the link to homepage of Takeaki Uno, to notify the news about POWIC for the users. For the commercial use, please make a contact to Takeaki Uno.

This program computes the power indices for weighted majority games. For n players p1,...,pn, having weight w1,...,wn, evaluate the "power" of each player in voting. For a given quota q, a set (coalition) of players is "winning" if the sum of their weights is no less than q. The Banzhaf index of player pi is defined by the probability that a randomly generated player set including pi is winning. The Shapley- Shubik index is the probability that in a given uniformly randomly generated order of players, the set of players preceding pi is not winning but the addition of pi makes it winning. A wining coalition is called "minimal" if we can not remove any its player with keeping it winning. The Deegan-Packel index of pi is x*y where x is the probability that pi belongs to a uniformly randomly selected minimal winning coalition, and y is the average size of minimal winning coalitions including pi.

==== How to Compile ====
Unzip the file into arbitrary directory, and execute "make". Then you can see "powic" (or powic.exe) in the same directory.

==== How to Use ====
The usage of powic is as follows.

   powic [command] input-filename quota\n\

[command] is composed of one letter to indicate the index we want to compute.

   B:Banzhaf index
   S:Shapley Shubik index
   D:Deegan Packel index

The second parameter is for input file, describing the weights of players. The file is just a list of numbers separated by any non-numeric character, such as

1 4 5, 24, 12,
2, 5, 6
1

powic reads the file and understands that the number of player is 9. Further, the weights of players w1,...,w9 are 1, 4, 5, 24, 12, 2, 5, 6 and 1. The first number is the weight player 1, and the last number is the weight of the last player. New lines are allowed between a number and a number. The third parameter is for quota, which is a threshold to be a winning coalition. If quota is 0, the quota is set to be the half of the sum of the weights of all players, (half+0.5 if the sum is odd).

Examples)

% powic B weight-file 200

% powic S ww.dat 0

The output format is just the list of power indices of players. The indices are output to standard output, and each line corresponds to the power index of a player, so that the first line corresponds to player 1, and the i-th line is the index of player i.

The performance of powic is stable, for both computation time and memory use. It needs almost O(n^2q) time and O(nq) memory for Banzhaf index, and O(n^3q) time and O(n^2q) memory for Shapley-Shubik and Deegan-Packel indices.

Takeaki Uno, Efficient Computation of Power Indices for Weighted Majority Games, Technical Report NII-2003-006E, National Institute of Informatics (2003), http://www.nii.ac.jp/TechReports/03-006E.pdf