国連理事国のシャープレイ値を計算

　最近シャープレイ値なるものを学んだ。協力ゲームにおいて、ゲームでえられた利得をグループ内のメンバーで公正に分配する方法の一つだ。直感的にはゲームにより貢献したプレイヤーほど多くのシャープレイ値が割り当てられる。

　このシャープレイ値の計算がなかなか面白い。ということでシャープレイ値を計算するプログラムを書いてみた。

[問題設定]

国連の理事国には、常任理事国と非常任理事国が存在する。

常任理事国は５カ国、非常任理事国は１０カ国である。

国連において何かを決める場合、常任理事国すべての賛成に加え、合計９カ国の賛成が必要である。

いま議論している内容が可決となる場合は利得1、否決となる場合は利得0とする。

常任理事国、非常任理事国のシャープレイ値を求めよ。

　以下C++で書いたコード。なんとなくTSPのビットDP解法に似ている気がする。

#include <iostream>

using namespace std;

const int N = 15;  // # of members
const int M = 9;   // required # of members to approve a decision
const int K = 5;   // # of permanent members
long long fac[N+1];

void init() {
  fac[0] = 1;
  for (int i = 1; i <= N; i++)
    fac[i] = i * fac[i-1];
}

inline int payoff(int s) {
  int vetoMask = (1<<K) - 1;

  if ((s & vetoMask) < vetoMask)
    return 0;

  if (__builtin_popcount(s) < M)
    return 0;

  return 1;
}

double sharpleyValue(int p) {

  double ret = 0;
  
  for (int i = 0; i < 1<<N; i++) {
    if (!(i & 1<<p))
      continue;
    
    double tmp = payoff(i) - payoff(i & ~(1<<p));
    int s = __builtin_popcount(i);
    ret += tmp * fac[s-1] * fac[N-s];
  }

  return ret / fac[N];
}

int main() {

  init();

  for (int i = 0; i < N; i++)
    cout << i << " :" << sharpleyValue(i) << endl;

  return 0;
}

結果は、
常任理事国 = 0.1963
非常任理事国　= 0.001865

ということで常任理事国の影響度が非常に高いことが分かる。