はじめに

こんにちは、leisurelyこと悠長です。(Twitterでleisurelyが呼びにくいと言われた。)
協力ゲーム理論の勉強をしたので復習がてらPythonでシャープレイ値の計算を実装しました。別に手計算でできることをプログラミングで実装しただけですし、手計算で求めるのがつらいようなシャープレイ値の計算を実際にすることはないでしょう。なんならシャープレイ値を計算するパッケージがRにはあるらしいのでRを使えばいいじゃんってね(パッケージ名はmatchingRだったかな)。ということで実装するのは完全に趣味です。

シャープレイ値の説明を少しだけしてからコーディングに入ります。

・参考文献
武藤滋夫ゲーム理論入門
 船木由喜彦演習ゲーム理論

いつもの注意書き
※この記事はプログラミングを学ぶのではなく、プログラミングというツールを用いて経済学をより理解するのが目的です。
※不備がありましたらコメントの方よろしくお願いします。
※追記:投稿してから気が付いたのですが、すでにPythonで実装されている方がおられました。
shiibass氏による「貢献値をshapley valueで計算する」

シャープレイ値とは

全員提携の形成において各プレイヤーがどれだけの貢献をしているかを考え、貢献度の度合いに基づいて各プレイヤーへの利得の分配を定めるものです。協力ゲーム理論では、提携した後どのようにして利得を分配するのかが問題となり、その分配の仕方の1つがシャープレイ値であると私は解釈しています。解概念としては交渉集合・仁・カーネルなどもありますが、条件を満たせば一意に配分が定まるシャープレイ値の方が応用しやすいのではないでしょうか。(ここら辺は勉強不足です。)

シャープレイ値は4つの公理から導出されたもので、
・全体合理性
・ナルプレイヤーに関する性質
・対称なプレイヤーに関する性質
・ゲームの和に関する性質
以上の性質を満たします。シャープレイはこの4つの性質を満たす解はただ1つしか存在しないことを証明しました。ではシャープレイ値の数式の定義です。
$v$: 特性関数、$S$: ある提携とします。
ゲーム$(N, v)$におけるプレイヤー$i \in N$のシャープレイ値:
$$ \phi_i(v) = \sum_{S: i \in S \subseteq N} \frac{(s-1)!(n-s)!}{n!}(v(S)-v(S \setminus \{ i \} ))$$
ここで、$s = |S|, n = |N|$としています。また、
$$ v(S)-v(S \setminus \{ i \} ) $$
は提携$S$におけるプレイヤー$i \in S$の限界貢献度を表しています。
このシャープレイ値の計算を実装します。

コーディング

プレイヤー数や提携値などの入力方法はいろいろありますが、私が実装しやすい方法でしました。
また、詳しい説明はコード内のコメントアウトを参照してください。

プレイヤーの人数と提携の集合を生成

まず、プレイヤーの人数を入力し提携の集合を作ります。

import itertools
import math

n = int(input()) # プレイヤー数を入力

seq = [str(i+1) for i in range(n)] # 提携の集合を作る下準備
All_set = []
for i in range(n): # 提携の集合(リスト)を生成
    comb = list(itertools.combinations(seq,i+1)) 
　　#itertools.combinationで重複無しの組み合わせを生成
    All_set.extend(comb)

new_All_set = ['0'] # 後の計算のため0人の提携を入れておく
for i in range(len(All_set)): 
    # 上で生成したリストでは、各提携がタプルになっているのでstrに修正
    s=""
    a = All_set[i]
    for j in a:
        s += j
    new_All_set.append(s)

zero_set = list(0 for _ in range(len(new_All_set))) # 提携値すべてが0の集合(リスト)

S = new_All_set # すべての提携の集合(リスト)
V = zero_set    # すべての提携値の集合(リスト)、このあと提携値を入力する。ここではまだ0

提携値の入力

プレイヤー1と2の提携による提携値が2ならば「12 2」のように入力します。
提携の集合と提携値の集合を別々のリストにしているのが奇麗じゃない気もしますが、個人的にはこの扱い方が楽でした。

for i in range(len(new_All_set)):
    inp = (input().split()) # ここで提携値の入力を処理
    if inp[0] in S: #入力した提携が提携の集合にあれば入力処理
        position = S.index(inp[0])
        V[position] = int(inp[1])
    if inp[0] == "ZERO":
        # 入力する提携値の残りがすべて0になったらZEROと入力することでfor文から抜ける
        break

シャープレイ値の計算

sv = []
for i in range(n):
    res = 0
    i_in = [s for s in S if str(i+1) in s] #iが属する提携の集合(リスト)
    i_not_in = [s for s in S if str(i+1) not in s] #iが属さない提携の集合(リスト)
    for j in range(len(i_in)):
        res += math.factorial(len(i_in[j])-1) * math.factorial(n-len(i_in[j])) / math.factorial(n) \
        * (V[S.index(i_in[j])] - V[S.index(i_not_in[j])])
    # ここでシャープレイ値を計算
    sv.append(["player"+str(i+1) ,res]) # 各プレイヤーのシャープレイ値をリストにまとめる
print(sv)

以上です。実装する前はもっと長いコードになると思っていたのですが、いざ実装してみると思いのほか短いですね。

コード全体をまとめて載せておきます。(Githubにのせればいい気もしますが)
コピペして使えるはずです。エラーが出る場合はコメントで教えてください。

import itertools
import math

n = int(input())

seq = [str(i+1) for i in range(n)]

All_set = []
for i in range(n): 
    comb = list(itertools.combinations(seq,i+1))
    All_set.extend(comb)

new_All_set = ['0']
for i in range(len(All_set)): 
    s=""
    a = All_set[i]
    for j in a:
        s += j
    new_All_set.append(s)

zero_set = list(0 for _ in range(len(new_All_set))) 

S = new_All_set
V = zero_set

for i in range(len(new_All_set)):
    inp = (input().split())
    if inp[0] in S:
        position = S.index(inp[0])
        V[position] = int(inp[1])
    if inp[0] == "ZERO":
        break

sv = []
for i in range(n):
    res = 0
    i_in = [s for s in S if str(i+1) in s]
    i_not_in = [s for s in S if str(i+1) not in s]
    for j in range(len(i_in)):
        res += math.factorial(len(i_in[j])-1) * math.factorial(n-len(i_in[j])) / math.factorial(n) \
        * (V[S.index(i_in[j])] - V[S.index(i_not_in[j])])
    sv.append(["player"+str(i+1) ,res])
print(sv)

実際に問題を解いてみる

定番ではありますが、3人多数決ゲームでのシャープレイ値を求めてみます。(演習ゲーム理論P.173 参照)

プレイヤー数は3人。各提携による提携値は以下のようになっています。

v(123) = v(12) = v(13) = v(23) = 1 \\
v(1) = v(2) = v(3) = 0

このときの入力をまとめると

のようになります。
計算結果は以下の通りです。

[['player1', 0.3333333333333333], ['player2', 0.3333333333333333], ['player3', 0.3333333333333333]]

ちゃんと各プレイヤーのシャープレイ値が$\frac{1}{3}$になっています。
今回の記事は以上です。
間違いや不具合がありましたらコメントにて報告お願いします。