Banzhaf Power Index(權力投票)

有一項決策要投票表決，一人一票，不得投廢票，過半數贊成則通過，反之則否決。投票者有許多派系組成，各個派系都相當團結，同樣派系的人，要嘛全部 都是投贊成票，要嘛全部都是投反對票。然而有些派系人多，有些派系人少，人多的派系能左右大局，人少的派系卻勢單力薄。於是產生一個問題：有能力對最終決 策造成影響的是哪些派系？影響能力又是多少？

一個派系有能力對決策造成影響，是指所有派系都設定立場之後，此派系一旦改變立場，會馬上顛倒決策結果。換個角度來說，是指此派系之外的所有派系都投完票之後，此派系若全數投贊成票，則會使決策順利通過，反之若全數投反對票，則會使決策無法通過。

Banzhaf Power Index 的計算方式是這樣的：一個派系 X 的 Banzhaf Power Index = 派系 X 影響決策的情況數目 ÷ ( 派系 1 影響決策的情況數目 + ... + 派系 N 影響決策的情況數目 ) 。所有派系的 Banzhaf Power Index 的總和會是 1 。

藉由 Banzhaf Power Index ，可以看出各派系的實力，也可以看出投票表決是否公平。

1.
A派系9票、B派系9票、C派系7票、D派系3票、E派系1票、F派系1票。
總共投票數為30票。過半數之票數為16票。

2.
以A派系為例，A派系影響決策的情況，一共有16種：

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

派系有出現，表示投贊成票；派系無出現，表示投反對票。
拿掉A則會逆轉決策結果。

3.
可以發現D派系、E派系、F派系，
完全無法介入結果，沒有任何影響力：

  | 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

1. int w[6];           // 各種派系的人數


2. int c[(16-1) + 1];  // 算出0票到15票這些未過半數的情形




4. int power[6];   // 各派系影響決策結果的情況數目


5. int sum = 0;    // power[]總和




7. void Banzhaf_power_index()


8. {


9.     for (int k=0; k<N; ++k)


10.     {


11.         // 暫時去除派系k，


12.         // 算出剩餘派系的投票情況種類數目。


13.         memset(c, 0, sizeof(c));


14.         c[0] = 1;




16.         for (int i=0; i<N; ++i)


17.             if (i != k)


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


19.                     c[j] += c[j-w[i]];




21.         // 累計靠近過半票數的情況數目


22.         power[k] = 0;


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


24.             power[k] += c[j];




26.         sum += power[k];


27.     }




29.     for (int i=0; i<N; ++i)


30.         cout << i << "派系的BPI是" << float(power[i]) / sum;


31. }