貢献値をshapley valueで計算する

チームで協力して何かをして成果を上げたときに得たものを皆で分配するということは多々あります。
人間関係の話になると面倒なので無難に均等にしたいところですが、個人の貢献を妥当に評価することも重要です。

この問題はゲーム理論で頻出で、応用すれば効果測定や最適化に使えたり使えなかったりします。

shapley value

計算方法として今回はshapley valueを導入します。
shapley valueの定義はぐぐればいくらでも出てくるので省略します。

早速実装します。問題設定はa,b,cの３人がいて、何人かで協力して１つのタスクをこなして成果が利益となります。
下の表がそのときの結果で、例えば１行目はc単独で実行したときの利益は40ということです。
この３人が全員で実行して利益が100の場合にa,b,cに100を配分したいというのが課題です。

a	b	c	利益
0	0	1	40
0	1	0	20
0	1	1	65
1	0	0	0
1	0	1	50
1	1	0	30
1	1	1	100

書いたコードは以下です。

import numpy
import pandas
import math
from itertools import combinations

df1 = pandas.DataFrame(
  {
      "a": [0, 0, 0, 1, 1, 1, 1],
      "b": [0, 1, 1, 0, 0, 1, 1],
      "c": [1, 0, 1, 0, 1, 0, 1],
      "profit": [40, 20, 65, 0, 50, 30, 100]
  }
)
player_list = ["a", "b", "c"]

def power_set(arr):
    return [set(s) for i in range(len(arr)+1) for s in combinations(arr, i)]

powerset = power_set(player_list)

def generate_key_value(df, player_list):
    for i, row in df.iterrows():
        yield "".join(row[player_list].apply(lambda x: str(x)).values), row["profit"]

profit = {k: v for k, v in generate_key_value(df1, player_list)}

def shapley_value(player, player_list, powerset, profit):
    n = len(max(powerset))
    exclude_set = [s for s in powerset if player not in s]
    include_set = [s | set({player}) for s in exclude_set]
    v = 0
    for se, si in zip(exclude_set, include_set):
        key_se = "".join(
            ["0" if p not in se else "1" for p in player_list])
        v_se = profit.get(key_se, 0)
        key_si = "".join(
            ["0" if p not in si else "1" for p in player_list])
        v_si = profit.get(key_si, 0)
        c = math.factorial(len(se)) * math.factorial(n -len(se) - 1) / math.factorial(n)
        v += c * (v_si - v_se)
    return v

evaluation = {
    p: shapley_value(p, player_list, powerset, profit) for p in player_list
}

power_set関数はべき集合を返す関数で例として以下のような結果を返します。

power_set(["a", "b"])
# [set(), {'a'}, {'b'}, {'a', 'b'}]

generate_key_value関数はべき集合の要素に対する表データにある利益を取得するために用意したのですが、実装方法がわからず作ったものでshapley valueの本質的な部分とは一切関係ありません。{'b', 'c'}という集合だったら011という文字列と65を対応させるためのものです。

shapley_value関数で各プレイヤーの貢献値を計算します。
計算方法としてはざっくり言うと自信が参加したときの利益と参加しなかったときの利益の差分を評価するような仕組みになっています。

evaluationが貢献値で15, 32.5, 52.5で利益を配分すればよいという結果を得ました。

evaluation
# {'a': 15.0, 'b': 32.5, 'c': 52.5}

なんとなく妥当というか、単独で行動した場合の利益を考えるとまあそんな感じでしょうね。

計算限界

valueを計算するときにmath.factorialで階乗を計算するので値の上限を超えてしまいますよね、
って書こうとしたらpython3では整数の最大値が存在しないらしいので計算できてしまいました。

math.factorial(100)
# 93326215443944152681699238856266700490715968264381621468592963895217599993229
# 915608941463976156518286253697920827223758251185210916864000000000000000000000000

階乗の計算限界のほかにも計算量爆発もあります。
プレイヤーの人数を$n$としたときにべき集合の要素数は$2^n$となるのでfor文が終わらなくなります。

そういった計算量の問題を解消するために、階乗の部分や繰り返し処理を簡略化した派生形があります。
私が最近読んだ論文だと
https://arxiv.org/ftp/arxiv/papers/1804/1804.05327.pdf
$2^n$の計算を回避するために、緩和したSimplified Shapley Valueを定義し、それを発展させてOrdered Shapley Valueを作っていました。これはa,b,cがどの順番で実行すると貢献値が高いかを評価するために導入されているようです。
論文の目的がDSP広告や有料検索広告などをどのタイミングで出稿すべきかを最適化することなのでshapley value理論の良い応用例だと思います。

線形回帰との違い

そんなことしなくて線形回帰でよくね？っていう意見があるかもしれないです。
そんなことないです。

from sklearn import linear_model
lm = linear_model.LinearRegression(fit_intercept=False)
lm.fit(df1[player_list], df1["profit"])
df1["profit"].max() / sum(lm.coef_) * lm.coef_
# array([10.76923077, 32.30769231, 56.92307692])

係数の合計が100になるように調整したらshapley valueと大差ない結果になりました。

それでは以下の例でそれぞれの結果を出力してみます。

a	b	c	利益
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	100
1	1	0	5
1	1	1	180

結果は以下のようになりました。
shapley value: {'a': 77.5, 'b': 27.499999999999996, 'c': 75.0}
linear regression: array([93.6, -2.4, 88.8])

線形回帰ではbの配分が負の値になり、利益を配分するどころか逆に徴収してaとcで山分けしています。これは問題設定から考えると不自然で、{'a', 'c'}のときに100の利益で{'a', 'b', 'c'}のとき180なら、bがマイナスの働きをしているとは考えにくいからです。線形回帰では与えたデータとの誤差が最小になるような線形結合を計算しているだけなので、今回のような問題設定と必ずしも合致はしないですね。
こういう極端なデータを扱うことがあるのかと言うと案外あるもので、例えば認知度向上のための広告はユーザー数増加のような近いレイヤーの数値を測定したほうが施策効果を判断しやすく、全体の利益にどの程度貢献しているかはわからないです。もっとわかりやすい例だと、MMORPGにおいて、aが回復職、bが盾役（タゲ取りとか）、cが火力職だとしてパーティ狩りした場合の貢献値の配分をどうしようか、であったり、他のゲームでも単体では効果が薄いがコンボ技にすることで絶大な効果を生み出す、というのは多々あるでしょう。そういったサポートポジションの貢献を評価するのがshapley valueで、線形回帰では先ほどのような配分ミスにつながる恐れがあるということです。

まとめ

チームで成果を上げた時の貢献値の配分をshapley valueという計算方法で評価しました。
線形回帰と比較したり、ordered shapley valueを挙げましたが、
どういう計算方法を適用するのかというのは直面している問題ごとに対処する必要がありそうです。それを考えるのがデータサイエンティストの仕事といっても言い過ぎではないかもしれません。

スクリプト全体:https://github.com/shiibashi/qiita/blob/master/3/Untitled.ipynb