Power Index Calculator ...

... for Weighted and Vector-weighted Majority Games.

In order to start using the software, you should first download a binary version or download the latest source boundle and compile it. After one of these steps, you should read how to use the software and how to write an input file for it.

Indices currently supported are:
If you are looking for some more information on these topics, or if you are looking for online power index calculator, your should take a look at the Power Index Website (University of Turku); especially the comprehensive "Links"- and "Literature"-pages.

Contents

  1. Compilation
  2. Installation
  3. Program usage
  4. Input file format
  5. Sorting and rearranging the players
  6. Computational limits

Compilation

You need some tools and libraries to compile the program:
Compilation was tested only with a recent version of the GNU C++ Compiler (g++). If you have Linux distribution such as Debian or RedHat most of these things should be available using your package management system. Nevertheless, CUDD has to be configured and compiled by yourself. To do this:
  1. Download the CUDD package (see above), e.g. the file cudd-2.4.2.tar.gz .
  2. Extract it into a directory of your choice, say <dir>. A directory with name <dir>/cudd-<version> is created.
  3. Uncomment the ICFLAGS and XCFLAGS line which correspond to your system (*)
  4. Run make
To (*). It is crucial, that the values for SIZEOF_VOID_P, SIZEOF_INT and SIZEOF_LONG correspond to the values of your current environment. You can use the configure script from your current progam to get these values. If you use GNU g++ and have a x86 machine, these values depend on your environment (see here):
-m32
-m64
Generate code for a 32-bit or 64-bit environment. The 32-bit environment sets int, long and pointer to 32 bits and generates code that runs on any i386 system. The 64-bit environment sets int to 32 bits and long and pointer to 64 bits and generates code for AMD's x86-64 architecture. For darwin only the -m64 option turns off the -fno-pic and -mdynamic-no-pic options.


To configure and build the actual program, use:
  1. $ ./configure --with-cudd=<dir>/cudd-<version> CXXFLAGS="-O3 -mtune=native" --prefix=<prefix>
  2. $ make
  3. $ make install 
Depending on you machine and your optimization options, compilation can take a while. This is, because the code uses a lot of templates and inline functions. If your compiler does not support the -mtune option, or the native argument, drop it and/or consult your compiler's manual.

If you don't have superuser permissions, you should set <prefix> to something like $HOME, to install files into your home directory.

Installation

If you got a binary version of the program, no installation is needed. If you build the program from source, you can use 
$ make install
to install the binary and the data files to your system. In the latter case, your files are stored in <prefix>/share/power-indices/, where prefix defaults to /usr/local.

Program usage

Use can use the --help option to get a list of options, which can be passed to the program. Most of them are not relevant in daily work and will not be explained here.

A game can be passed to the program either as a file (using -f <name>, or --file=<name>) or using standard input. E.g.
$ ./power-indices < games/UNSecurityCouncil.txt
By default, all available indices will be computed, i.e. currently abs./norm. Banzhaf, Shapley-Shubik, Holler-Packel and Deegan-Packel. Alternatively, the --indices=<which> or -i <which> option can be used to choose the indices to compute, where <which> is a comma-separated list of abbreviated index names from the following table:
bz
 Banzhaf
ss
 Shapley-Shubik
hp
 Holler-Packel
dp
 Deegan-Packel

E.g. if you want to compute the Banzhaf- and Holler-Packel indices for the UN Security Council, you would type
$ ./prog --file=games/UNSecurityCouncil.txt --indices=bz,hp
Currently, the program is very chatty and dumps a lot of (useless) output. Most lines can be ignored, but some are interesting, depending on the kind of your game and the indices to compute. In case of a weighted majority game, there will be a line, such as
W has 53 inner nodes
 This line means, that the internal data structure used to store the winning coalitions (W) has a size of 53 in this case. The bigger this number is, the more complex is the game. For instance, the International Monetary Fund has a size of more than 15,000,000. In case of a vector-weighted majority game with at least two subgames (e.g. the US Federal Legal System) there is a similar line, with W_all instead of W. Rule of thumb is, that whenever you see a number of nodes, this is a measure of complexity of the game.

The program comes along with some real world games, like the UN Security Council or the International Monetary Fund (2009). A good source for real world games is Wikipedia (search for unicameral, bicameral or multicameral). Nonetheless, most of these real world games are trivial. Some more complex (weighted majority) games can be found on the websites of the World Bank, see here.

Anyway, it is very much appreciated, that you send any real world game to me, so it can be distributed along with upcoming versions of the package.

Input file format

In most cases, the files are self explaining. Let us take a look at a simple example. The prominent UN Security Council, which consists of five permanent members (namely China, England, France, Russia and the United States) and ten non-permanent members. In order to get a majority, nine affirmative votes are required and no permanent member may say "No". Because abstention can (currently) not be modeled in our system, we assume, that all five permanent members have to say "Yes", and thus, they have veto power. As already said, this game is weighted (see e.g. the Book of Taylor (and Pacelli for the 2nd edition)). Corresponding quota and weights are [39;7,7,7,7,7,1,..,1], where each permanent member has weight 7 and all remaning members have weight 1, each. A valid input file would look like:
# UN Security Council - Example
1
# Indention is optional.
    39
    7 China
    7 England
# Another comment
    7 France
    7 Russia
    7 United States
x10 1 Non-permanent Member
Here, all lines beginning with a # are comment lines and are entirely ignored. These lines may appear anywhere in the input. The first non-comment line contains the number of games (say m), which is 1 in this case, because we have a weighted majority game. The second non-comment line contains the m integer quota(s). All remaining non-comment lines contain a class of players. A class consists of:
  1. (optional) The number of players in this class (called quantity),
  2. m integer weights for the players in this class and
  3. (optional) a name for the (players in this) class.
A quantity must be specified at the beginning of the line and starts with an x (for "times"). Only strictly positive values are permitted. If no quantity is given, it is assumed, that the class contains just a single player. E.g. there is one class with name China in our input, which has weight 7. In comparison, the class of non-permanent members in the council contains ten players. The name of a class begins after the m weights and ends with the end of the line or the end of the input. Quotes are allowed and will be removed. Hence, the line
x10 1 "Non-permanent Member"
would have been valid, too.

The more interesting case is, where there are at least two (sub-)games. To this end, let's model the UN Security Council a little bit more intuitively with two games. The first game is [9;1,..1], where each member has weight 1, regardless of it is a permanent or a non-permanent member of the council. Nine votes are required to win this game. The second game is used, to model the veto power of the five permanent members. Here we have [5;1,1,1,1,1,0,..,0]. This game means, that all five votes of the permanent members are required in order to win, while the ten non-permanent members are completely irrelevant. The Council now is the intersection of both of these games and our input looks like:

# UN Security Council (2nd Version)
2
    9 5
    1 1 China
    1 1 England
    1 1 France
    1 1 Russia
    1 1 United States
x10 1 0 Non-permanent Member

The intersection of the winning sets of multiple weighted majority games leads to so called vector-weighted majority games. In order to create the winning coalitions of such a game, the program first computes the winning coalitions of all individual weighted games and then computes the intersection of these sets of winning coalitions. E.g. let [9;1,..,1] be the first, and [5;1,..,1] be the second game, our program computes the winning coalitions W_1 and W_2 (1 and 2 are subscripts) and then computes W_2 AND W_1. Because this case it rather uninteresting, let us say we have m=5 games, with quotas Q_1,..,Q_m and it holds that Q_1>=..>=Q_m. The sets of winning coalitions W_1,..,W_m are interesected using a (left associative) binary AND operation. The problem here is, that temporary results become differently big, when joining them. Thus, it could make a difference to compute W_1 AND .. AND W_m or W_m AND .. AND W_1. In contrast, the result size is always the same. As a rule of thumb, the program joins in order of non-decreasing quotas. Hence, in the current case, ((W_m AND W_(m-1)) .. ) AND W_1is computed.

This order can be changed by the user, using a special command line. These start with a %, directly followed by a command name and a respective value. Command lines may appear anywhere in the input. Lets suppose another example:
5
   2 3 4 1
x5 1 0 1 0
x2 1 1 0 1
   0 2 3 1
   0 1 1 0
In the following, subgames are referenced by indices, starting with 1. Hence, the i'th column (without the quantity and the number of games) denotes the i'th game. The join order in this game would be ((W_4 AND W_1) AND W_2)) AND W_3. We now want to join the games, as they appear in the input. Thus, we add the following line:
5
%join 1 AND 2 AND 3 AND 4
   2 3 4 1
x5 1 0 1 0
x2 2 1 0 1
   0 2 3 1
   0 1 1 0
This line has the effect, that the default join order is omitted and our order is used instead. Remember, that the AND operation is left associative.

Using special joins, also combinations consisting of OR and AND operations are possible. To this end, we gonna model a much more complex, but not less prominent game, namely the US Federal Legal System (see again the Book of Taylor (and Pacelli for the 2nd edition). This is a bicameral system with an upper house (Senate) and a lower house (House of Representatives), which is interesting to model, because there is more than one possibility to win. The following is a quote from the Book of Taylor (p. 45, 1st Ed.):

There are 537 voters in this yes-no voting system: 435 members of the House of Representatives, 100 members of the Senate, the vice president, and the president. The vice president plays the role of tie-breaker in the Senate, and the president has veto power that can be overridden by two-thirds of both the House and the Senate. Thus, for a bill to pass, it must be supported by either:
  1. 218 or more representatives and 51 or more senators (with or without the vice president) and the president.
  2. 218 or more representatives and 50 senators and the vice president and the president
  3. 290 or more representatives and 67 or more senators (with or without either the vice president or the president).
There are four classes of players in this game: The 100 senators, the 435 members of the house of representatives, the vice president and the president. But how many games do we need? Let's start and find out. The first rule can be modeled by a vector-weighted majority game, consisting of three subgames: [218;1,..1] for the senators, [51;1..1] for the representatives and [1;1] for the president. If we take all players into account, input for the first rule would look like:
3
     218 51 1
x100   0  1 0 Senator
x435   1  0 0 Representative
       0  0 0 Vice president
       0  0 1 President
The second rule can be modeled in a similar way. Input is:
4
     218 50 1 1
x100   0  1 0 0 Senator
x435   1  0 0 0 Representative
       0  0 1 0 Vice president
       0  0 0 1 President
Finally, the third rule could be modeled as:
2
     290 67 
x100   0  1 Senator
x435   1  0 Represenative
       0  0 Vice president
       0  0 President
To obtain the whole game, we first have to collect all different columns from the previous games and second have to write an appropriate join description:
7
     218 51 1 50 1 290 67 
%join TODO
x100   0  1 0  1 0   0  1 Senator
x435   1  0 0  0 0   1  0 Representative
       0  0 0  0 1   0  0 Vice president
       0  0 1  0 0   0  0 President
The three games, corresponding to the three rules, are all vector-weighted majority games and thus, are implicitly joined using AND. The rules itself are possibilities to win and hence, have to be joined by OR. Thus, our join description is:
%join (3 AND 2 AND 1) OR (3 AND 5 AND 4 AND 1) OR (6 AND 7)

Sorting and rearranging the players

Ordering may have a big impact on the running time of the software. We shortly describe two mechanisms used in the program. One is used for weighted majority games and the other is used for vector-weighted majority games with at least two subgames.

For a weighted majority game, players are always sorted by non-increasing weights, no matter of the ordering in the input.  This is mandatory due to special algorithms for the computation of the minimal winning coalitions in this case. You can use the option --no-sort to disable this feature. But keep in mind, that running time may increase significantly.

Now, suppose a vector-weighted majority game with at least two subgames. Same weights of a pair of players imply same power indices. Thus, it saves a lot of time to compute indices once for each class of weights. Let's take a look at an example:
2
     51 51
x100  1  0 A
x100  0  1 B
      1  1 C
The ordering in this game is worst possible. Due to the underlying algorithm, all 201 indices would have to be computed, because for any player, all previous players have to be computed. Thus, a better ordering would be:
2
     51 51
      1  1 C
x100  1  0 A
x100  0  1 B
Here, the program would stop after the 102nd player, because the remaining 99 indices for the players in class B are known, due to the same weight. after the first one of the class has been computed. In contrast, an optimal ordering would be:
2
     51 51
      1  0 Any A
      0  1 Any B
      1  1 C
 x99  1  0 A
 x99  0  1 B
There are two important points here to consider. The first is, that ony indices for three players have to be computed. The other point is, that in comparison to the initial game, the relative order of the players is the same: A before B before C. Exactly this method of ordering is established automatically in the program to reduce running time. Thus, in most cases you don't have to care about rearrangement at all. Nonetheless, this feature can be disabled with the --no-rearrange option.

Computational limits

For most practical games, the program can compute at least the Banzhaf and the Holler-Packel indices in a short amount of time. As you will see, the main limitation of the program is the available amount of main memory. If you have a weighted majority game [Q;w1,..,wn] with n players, Quota Q and weights w1,..,wn, the space complexity is O(nQ), if you suppose O(1) space for a integer number. But, the latter assumption is in general not true. Actually, each integer number has size O(n). On the other side, O(nQ) is a somewhat misleading. If you have a game with very huge Q, but e.g. n equals 5, space consumption and thus running time is small, as in the case of the Executive Directors of the International Monetary Fund. Shapley-Shubik and Deegan-Packel are even worse. Here you have space complexity of O(n^3*Q).

Advice: If you are in doubt, that a game is too big, first use the --indices=hp option to get the number of nodes (W has ... inner nodes). In this case, the algorithm to compute the winning coalitions is fast and saves memory. After you have that number, you can abort the calculation with CTRL-C and decide, if you want to continue with Banzhaf. If your game is complex, but you wanna give it a try, you should open a tool to monitor your main memory usage, so you can kill your program if necessary. A rule of thumb is, that if Banzhaf and Holler-Packel aren't work, SS and DP won't, too. If you have a 64 Bit version of the program and not enough main memory the program will become very slow, when your operating system starts swapping. If you have a 32 Bit version, the addressable memory is (theoretically) limited by 4 GiB.