Banzhaf Power Index (Power Voting)

There is a decision to be voted on, with each person having one vote and no abstentions allowed. If more than half of the votes are in favor, the decision is passed; otherwise, it is rejected. The voters are composed of various factions, each of which is quite united. People from the same faction either all vote in favor or all vote against. However, some factions have more people while others have fewer, and factions with more people have more influence on the outcome, while factions with fewer people have less influence. This raises the question: which factions have the ability to influence the final decision? And how much influence do they have?

A faction has the ability to influence a decision if, after all other factions have set their positions, a change in the faction's position would immediately reverse the decision. In other words, if all factions except this one have voted, and this faction votes in favor, the decision will pass; if this faction votes against, the decision will be rejected.

The calculation of the Banzhaf Power Index is as follows: the Banzhaf Power Index of a faction X is equal to the number of cases in which faction X influences the decision divided by the sum of the number of cases in which each faction influences the decision. The sum of the Banzhaf Power Indexes of all factions will be 1.

By using the Banzhaf Power Index, we can determine the strength of each faction and whether the voting process is fair.

1.
Faction A has 9 votes, Faction B has 9 votes, Faction C has 7 votes, Faction D has 3 votes, Faction E has 1 vote, and Faction F has 1 vote.
The total number of votes is 30. The majority requires 16 votes.

2.
Taking Faction A as an example, there are a total of 16 cases in which Faction A can influence the decision:

   AB AC ABC ABD ABE ABF ACD ACE ACF
   ABDE ABDF ABEF ACDE ACDF ACEF ADEF

If a faction appears in a case, it means they voted in favor. If a faction does not appear, it means they voted against.
Removing Faction A would reverse the decision.

3.
We can see that Faction D, Faction E, and Faction F have no influence on the result and no power at all:

  | votes | power |  BPI
--+-------+-------+-------
A |   9   |  16   | 16/48
B |   9   |  16   | 16/48
C |   7   |  16   | 16/48
D |   3   |   0   |   0
E |   1   |   0   |   0
F |   1   |   0   |   0
--+-------+-------+--------
  |  30   |  48   |  1.0

int w[6]; // Number of people in each faction
int c[(16-1) + 1]; // Calculate the number of cases from 0 votes to 15 votes that are less than the majority
int power[6]; // Number of cases in which each faction influences the decision
int sum = 0; // Sum of power[]
void Banzhaf_power_index()
{
```
 for (int k=0; k<N; ++k)
```
```
 {
```
```
     // Temporarily remove faction k
```

     // Calculate the number of voting cases for the remaining factions

```
     memset(c, 0, sizeof(c));
```
```
     c\[0\] = 1;
```
```
     for (int i=0; i<N; ++i)
```
```
         if (i != k)
```

             for (int j=16-1; j>=w\[i\]; --j)

                 c\[j\] += c\[j-w\[i\]\];

     // Accumulate the number of cases close to the majority

```
     power\[k\] = 0;
```

     for (int j=max(16-w\[k\], 0); j<16; ++j)

```
         power\[k\] += c\[j\];
```
```
     sum += power\[k\];
```
```
 }
```
```
 for (int i=0; i<N; ++i)
```

     cout << "The BPI of Faction " << i << " is " << float(power\[i\]) / sum;

}