Banzhaf Power Index Caculation

Bernard Kolman, Robert Busby, Sharon C. Ross, Discrete Mathematical Structures, 6ed, 2014.

Chapter 1 Experiment 1

https://github.com/gqqnbig/Banzhaf

8.

Run Banzhaf.py.

weights = [6,3,1]
(a) q= 5,6,7

When q = 7,

Winning coalitions: [[0, 1], [0, 1, 2], [0, 2]]
vetoPowers: [0]

(b) q=8

Winning coalitions: [[0, 1], [0, 1, 2]]
vetoPowers: [0, 1]

q=9

Winning coalitions: [[0, 1], [0, 1, 2]]
vetoPowers: [0, 1]

q=10

Winning coalitions: [[0, 1, 2]]
vetoPowers: [0, 1, 2]

(c) q=7,8,9

9.

We have \(v_s, v_2, v_3, v_4\). Assume when any two guys vote yea, the other two vote nay.

Run BanzhafWithSenior.py.

Voter index 0 is senior.
Winning coalitions:  [[0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2], [0, 2, 3], [0, 3], [1, 2, 3]]
No one has veto power.
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/6 = 0.167.
Voter index 2 has power index 1/6 = 0.167.
Voter index 3 has power index 1/6 = 0.167.

We have \(v_j, v_2, v_3, v_4\). Assume when any two guys vote yea, the other two vote nay. That is, any group of two with \(v_j\) will not win.

Run BanzhafWithJunior.py.

Voter index 0 is junior.
Winning coalitions:  [[0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3], [1, 2], [1, 2, 3], [1, 3], [2, 3]]
No one has veto power.
powerIndexes:
Voter index 0 has power index 0 = 0.000.
Voter index 1 has power index 1/3 = 0.333.
Voter index 2 has power index 1/3 = 0.333.
Voter index 3 has power index 1/3 = 0.333.

10.

(a)
Winning coalitions: [[0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
vetoPowers: [0]
powerIndexes:
Voter index 3 has power index 1/10 = 0.100.

(b)
Buy from v_1, weights=[4, 3, 2, 2]

Winning coalitions: [[0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
vetoPowers: [0]
powerIndexes:
Voter index 3 has power index 1/5 = 0.200.

Buy from v_2, weights=[5, 2, 2, 2]

Winning coalitions: [[0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
vetoPowers: [0]
powerIndexes:
Voter index 3 has power index 1/5 = 0.200.

Buy from v_3, weights=[5, 3, 1, 2]

Winning coalitions: [[0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
vetoPowers: [0]
powerIndexes:
Voter index 3 has power index 1/10 = 0.100.

Therefore, buying from \(v_1\) or \(v_2\) boosts my voting power the most.

12.

Run BanzhafW1W2.py.

Assume the system only has two players, with weight \(w_1, w_2\). And according to the question, \(w_1=2w_2\).

Possible coalition (2,) if q >= 2w_2
Possible coalition (1,) if q >= 1w_2
Possible coalition (2, 1) if q >= 3w_2
Stops are [Fraction(1, 3), Fraction(1, 2), Fraction(1, 1)]

case w_2 < 1/3q:
No winning coalitions. No one has power.

case 1/3q <= w_2 < 1/2q:
Winning coalitions:  [[0, 1]]
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/2 = 0.500.

case 1/2q <= w_2 < 1q:
Winning coalitions:  [[0], [0, 1]]
powerIndexes:
Voter index 0 has power index 1 = 1.000.
Voter index 1 has power index 0 = 0.000.

case 1q <= w_2 :
Winning coalitions:  [[0], [0, 1], [1]]
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/2 = 0.500.

(a)

1/3q <= w_2 < 1/2q or 1q <= w_2

(b)
Not possible with two players.

(c)

1/2q <= w_2 < 1q

Next, we find under which conditions (b) is possible. We add a player to the system, \([q: 2w_2,w_2, \frac{w_2}{2}]\).

Possible coalition (2,) if q >= 2w_2
Possible coalition (1,) if q >= 1w_2
Possible coalition (0.5,) if q >= 0.5w_2
Possible coalition (2, 1) if q >= 3w_2
Possible coalition (2, 0.5) if q >= 2.5w_2
Possible coalition (1, 0.5) if q >= 1.5w_2
Possible coalition (2, 1, 0.5) if q >= 3.5w_2
Stops are [Fraction(2, 7), Fraction(1, 3), Fraction(2, 5), Fraction(1, 2), Fraction(2, 3), Fraction(1, 1), Fraction(2, 1)]

case w_2 < 2/7q:
No winning coalitions. No one has power.

case 2/7q <= w_2 < 1/3q:
Winning coalitions:  [[0, 1, 2]]
powerIndexes:
Voter index 0 has power index 1/3 = 0.333.
Voter index 1 has power index 1/3 = 0.333.
Voter index 2 has power index 1/3 = 0.333.

case 1/3q <= w_2 < 2/5q:
Winning coalitions:  [[0, 1], [0, 1, 2]]
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/2 = 0.500.
Voter index 2 has power index 0 = 0.000.

case 2/5q <= w_2 < 1/2q:
Winning coalitions:  [[0, 1], [0, 1, 2], [0, 2]]
powerIndexes:
Voter index 0 has power index 3/5 = 0.600.
Voter index 1 has power index 1/5 = 0.200.
Voter index 2 has power index 1/5 = 0.200.

case 1/2q <= w_2 < 2/3q:
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 2]]
powerIndexes:
Voter index 0 has power index 1 = 1.000.
Voter index 1 has power index 0 = 0.000.
Voter index 2 has power index 0 = 0.000.

case 2/3q <= w_2 < 1q:
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 2], [1, 2]]
powerIndexes:
Voter index 0 has power index 3/5 = 0.600.
Voter index 1 has power index 1/5 = 0.200.
Voter index 2 has power index 1/5 = 0.200.

case 1q <= w_2 < 2q:
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 2], [1], [1, 2]]
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/2 = 0.500.
Voter index 2 has power index 0 = 0.000.

case 2q <= w_2 :
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 2], [1], [1, 2], [2]]
powerIndexes:
Voter index 0 has power index 1/3 = 0.333.
Voter index 1 has power index 1/3 = 0.333.
Voter index 2 has power index 1/3 = 0.333.

Power index of \(v_1\) can be triple of \(v_2\), but no twice.

Next, assume the system has four players, \([q: 2w_2,w_2, w_2, w_2]\).

Possible coalition (2,) if q >= 2w_2
Possible coalition (1,) if q >= 1w_2
Possible coalition (1,) if q >= 1w_2
Possible coalition (1,) if q >= 1w_2
Possible coalition (2, 1) if q >= 3w_2
Possible coalition (2, 1) if q >= 3w_2
Possible coalition (2, 1) if q >= 3w_2
Possible coalition (1, 1) if q >= 2w_2
Possible coalition (1, 1) if q >= 2w_2
Possible coalition (1, 1) if q >= 2w_2
Possible coalition (2, 1, 1) if q >= 4w_2
Possible coalition (2, 1, 1) if q >= 4w_2
Possible coalition (2, 1, 1) if q >= 4w_2
Possible coalition (1, 1, 1) if q >= 3w_2
Possible coalition (2, 1, 1, 1) if q >= 5w_2
Stops are [Fraction(1, 5), Fraction(1, 4), Fraction(1, 3), Fraction(1, 2), Fraction(1, 1)]

case w_2 < 1/5q:
No winning coalitions. No one has power.

case 1/5q <= w_2 < 1/4q:
Winning coalitions:  [[0, 1, 2, 3]]
powerIndexes:
Voter index 0 has power index 1/4 = 0.250.
Voter index 1 has power index 1/4 = 0.250.
Voter index 2 has power index 1/4 = 0.250.
Voter index 3 has power index 1/4 = 0.250.

case 1/4q <= w_2 < 1/3q:
Winning coalitions:  [[0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
powerIndexes:
Voter index 0 has power index 2/5 = 0.400.
Voter index 1 has power index 1/5 = 0.200.
Voter index 2 has power index 1/5 = 0.200.
Voter index 3 has power index 1/5 = 0.200.

case 1/3q <= w_2 < 1/2q:
Winning coalitions:  [[0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2], [0, 2, 3], [0, 3], [1, 2, 3]]
powerIndexes:
Voter index 0 has power index 1/2 = 0.500.
Voter index 1 has power index 1/6 = 0.167.
Voter index 2 has power index 1/6 = 0.167.
Voter index 3 has power index 1/6 = 0.167.

case 1/2q <= w_2 < 1q:
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2], [0, 2, 3], [0, 3], [1, 2], [1, 2, 3], [1, 3], [2, 3]]
powerIndexes:
Voter index 0 has power index 2/5 = 0.400.
Voter index 1 has power index 1/5 = 0.200.
Voter index 2 has power index 1/5 = 0.200.
Voter index 3 has power index 1/5 = 0.200.

case 1q <= w_2 :
Winning coalitions:  [[0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 3], [0, 2], [0, 2, 3], [0, 3], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
powerIndexes:
Voter index 0 has power index 1/4 = 0.250.
Voter index 1 has power index 1/4 = 0.250.
Voter index 2 has power index 1/4 = 0.250.
Voter index 3 has power index 1/4 = 0.250.

(b)

Therefore, for the system \([q: 2w_2,w_2, w_2, w_2]\), if 1/4q <= w_2 < 1/3q or 1/2q <= w_2 < 1q, \(v_1\) has twice power as \(v_2\).