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 divided into 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, with the larger factions having more influence and the smaller factions having less. 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 other factions have voted and the faction in question votes in favor, the decision will pass; if it votes against, the decision will fail.

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.

The Banzhaf Power Index allows us to see 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 influences the decision:

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

If a faction appears in the 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.
It can be observed that Faction D, Faction E, and Faction F have no influence whatsoever:

  | 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 with 0 to 15 votes that are not a majority
int power[6]; // Number of cases in which each faction influences the decision
int sum = 0; // Total 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;

}