シャプレー値

協力ゲーム理論において、シャプレー値は、協力したプレイヤーのグループ間で総利益または総コストを公平に分配する方法（解概念）です。たとえば、各メンバーが異なる貢献をしたチームプロジェクトでは、シャプレー値は各メンバーがどれだけの功績または責任を負うべきかを判断する方法を提供します。これは、 1951年にこれを導入したロイド・シャプレーにちなんで名付けられました。 ^{[ 1 ] [ 2 ]}

シャプレー値は、各プレイヤーが他のプレイヤーの可能な組み合わせに加わったときに全体の結果がどれだけ変化するかを考慮し、それらの変化を平均することによって、各プレイヤーの貢献を決定します。本質的には、すべての可能な連合にわたる各プレイヤーの平均限界貢献を計算します。^{[ 3 ] [ 4 ]}これは、公平な分配を定義するものとして広く受け入れられている、効率性、対称性、加法性、およびダミープレイヤー（またはヌルプレイヤー）特性という4つの基本的な特性を満たす唯一の解です。^{[ 5 ]}

この方法は、ビジネスパートナーシップにおける利益分配から、機械学習における特徴量の重要性の理解まで、多くの分野で使用されています。

プレイヤーが協力（連合を形成する）してタスクを達成することで特定の報酬を獲得できる状況を考えてみましょう。このような状況はしばしば連合ゲームと呼ばれます。連合（プレイヤーの集合）の場合、${\displaystyle S}$ペイオフ関数または価値関数を定義します${\displaystyle v(S)}$メンバーが受け取る報酬の合計として${\displaystyle S}$協力することで得られる。

シャプレー値は、連合によって生み出された価値をそのメンバー間で分配する一つの方法です。これは、特定の望ましい特性（下記参照）を持つ唯一の分配という意味で「公平な」分配です。シャプレー値によれば、^{[ 6 ]}プレイヤーが${\displaystyle i}$連合ゲームで与えられる${\displaystyle (v,N)}$は

${\displaystyle \varphi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))}$

${\displaystyle \quad \quad \quad ={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{n-1 \choose |S|}^{-1}(v(S\cup \{i\})-v(S))}$

どこ${\displaystyle n}$はプレイヤーの総数であり、合計はすべての部分集合にわたって計算されます。${\displaystyle S}$の${\displaystyle N}$プレイヤーを含まない${\displaystyle i}$空集合も含む。また、${\displaystyle {n \choose k}}$は二項係数です。この式は次のように解釈できます。連合が一度に一人ずつアクターによって形成され、各アクターが貢献を要求していると想像してください。${\displaystyle v(S\cup \{i\})-v(S)}$公正な報酬として、各関係者について、連立政権が形成されうる様々な組み合わせにおけるこの貢献額の平均を算出する。

シャプレー値の代替となる同等の式は次のとおりです。

${\displaystyle \varphi _{i}(v)={\frac {1}{n!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]}$

合計がすべての範囲に及ぶ場合${\displaystyle n!}$注文${\displaystyle R}$選手たちと${\displaystyle P_{i}^{R}}$は、${\displaystyle N}$先行する${\displaystyle i}$順番に${\displaystyle R}$。

相乗効果の観点から

特性関数から${\displaystyle v}$各プレーヤーグループが提供するシナジー（ハルサニー配当）を計算することができる。シナジーは独自の関数である。${\displaystyle w\colon 2^{N}\to \mathbb {R} }$、したがって

${\displaystyle v(S)=\sum _{R\subseteq S}w(R)}$

任意の部分集合に対して${\displaystyle S\subseteq N}$プレイヤーの数。言い換えれば、連合の「総価値」${\displaystyle S}$は、考えられる各部分集合の相乗効果を合計することによって得られる。${\displaystyle S}$。

特性関数が与えられた場合${\displaystyle v}$シナジー機能${\displaystyle w}$は以下によって計算されます。

${\displaystyle w(S)=\sum _{R\subseteq S}(-1)^{|S|-|R|}v(R)}$

包含排除原理を用いて。

シャプレー値はシナジー関数に関して^{[ 7 ] [ 8 ]で与えられます。}

${\displaystyle \varphi _{i}(v)=\sum _{i\in S\subseteq N}{\frac {w(S)}{|S|}}}$

ここで、合計はすべての部分集合について取られる。${\displaystyle S}$の${\displaystyle N}$プレイヤーを含む${\displaystyle i}$。

これは次のように解釈できます。

${\displaystyle \varphi _{i}(v)=\sum _{\text{i を含む連合}}{\frac {\text{連合の相乗効果}}{\text{連合のメンバー数}}}$

言い換えれば、各連合の相乗効果は、すべてのメンバー間で均等に分配される。

これはベン図で視覚的に解釈できます。上の最初の例の図では、各領域に、対応する連合のシナジーボーナスがラベル付けされています。連合によって生み出される合計値は、構成するサブ連合のシナジーボーナスの合計です。この例では、「You」と「Emma」とラベル付けされたプレイヤーの連合は、次の利益を生み出します。${\displaystyle 30+20+40=90}$ドル、個々の利益と比較すると${\displaystyle 30}$そして${\displaystyle 20}$それぞれドル建てで計算されます。そして、その相乗効果は、2番目の図に示すように、その相乗効果をもたらしたサブ連合の各メンバー間で均等に分配されます。

シャプレー値には、効率性、対称性、線形性、ヌルプレイヤー（またはダミープレイヤー）の4つの特性を満たすなど、多くの望ましい特性があります。^{[ 5 ]}

ロイド・シャプレーとロバート・オーマンは、1974年の著書で、シャプレー値の概念を無限ゲーム（非原子測度に関して定義される）に拡張し、対角公式を作成した。^{[ 10 ]}これは後にジャン＝フランソワ・メルテンスとアブラハム・ネイマンによって拡張された。

上記のように、n人ゲームの価値は、各プレイヤーに、ランダムな順序で並んだ全プレイヤーの前のプレイヤーの連合の価値に対する貢献度の期待値を関連付けます。プレイヤーが多く、各プレイヤーが小さな役割しか果たさない場合、特定のプレイヤーより前の全プレイヤーの集合は、全プレイヤーの良いサンプルであると直感的に考えられます。この場合、特定の微小プレイヤーdsの価値は、全プレイヤーの「完全な」サンプルの価値に対する「その」プレイヤーの貢献度として定義されます。

象徴的に、v が各連合c をその価値と関連付ける連合価値関数であり、各連合c がすべてのプレイヤーの測定可能な集合Iの測定可能な部分集合であると仮定すると、${\displaystyle I=[0,1]}$一般性を失うことなく、その価値${\displaystyle (Sv)(ds)}$ゲーム内の微小なプレイヤーdsは

${\displaystyle (Sv)(ds)=\int _{0}^{1}(\,v(tI+ds)-v(tI)\,)\,dt.}$

ここで、tIは全プレイヤー集合Iの完全なサンプルであり、全プレイヤーの割合t を含み、${\displaystyle tI+ds}$これはdsがtIに加わった後に得られる連合です。これは対角公式のヒューリスティックな形式です。^{[ 10 ]}

価値関数の何らかの正則性を仮定すると、例えば、v がI 上の非原子測度の微分可能な関数として表現できると 仮定すると、μ、${\displaystyle v(c)=f(\mu (c))}$密度関数${\displaystyle \varphi }$、 と${\displaystyle \mu (c)=\int 1_{c}(u)\varphi (u)\,du,}$どこ${\displaystyle 1_{c}(\bullet )}$はcの特性関数である。このような条件下では

${\displaystyle \mu (tI)=t\mu (I)}$、

密度を階段関数で近似し、密度関数の各レベルの割合tを維持することによって示すことができるように、

${\displaystyle v(tI+ds)=f(t\mu (I))+f'(t\mu (I))\mu (ds).}$

対角線公式は、AumannとShapley（1974）によって開発された形式をとる。

${\displaystyle (Sv)(ds)=\int _{0}^{1}f'_{t\mu (I)}(\mu (ds))\,dt}$

上記のμはベクトル値をとることができます（関数がμの範囲で定義され微分可能である限り、上記の式は意味を持ちます）。

上記の議論において、尺度が原子を含む場合${\displaystyle \mu (tI)=t\mu (I)}$これはもはや真実ではない。これが、対角線公式が主に非原子ゲームに適用される理由である。

関数fが微分不可能になったときにこの対角公式を拡張するために 2 つのアプローチが採用されました。メルテンスは元の公式に戻り、積分の後に導関数を取ることで平滑化効果の恩恵を受けています。ネイマンは別のアプローチを取りました。メルテンス (1980) のメルテンスのアプローチの基本的な適用に戻ると次のようになります。^{[ 11 ]}

${\displaystyle (Sv)(ds)=\lim _{\varepsilon \to 0,\varepsilon >0}{\frac {1}{\varepsilon }}\int _{0}^{1-\varepsilon }(f(t+\varepsilon \mu (ds))-f(t))\,dt}$

これは、例えば多数決ゲームで機能しますが、元の対角公式は直接使用できません。メルテンスは、シャプレー値が不変であるべき対称性を特定し、そのような対称性について平均化することで、上記のように平均と微分演算を交換するさらなる平滑化効果を作成することで、これをさらに拡張します。^{[ 12 ]}非原子値に関する調査は、ネイマン (2002) にあります。 ^{[ 13 ]}

シャプレー値は個々のエージェントにのみ値を割り当てます。これは、エージェントのグループCに適用できるように一般化されています^{[ 14 ] 。}

${\displaystyle \varphi _{C}(v)=\sum _{T\subseteq N\setminus C}{\frac {(n-|T|-|C|)!\;|T|!}{(n-|C|+1)!}}\sum _{S\subseteq C}(-1)^{|C|-|S|}v(S\cup T)\;.}$

相乗効果機能の観点から${\displaystyle w}$上記では、これは^{[ 7 ] [ 8 ]と書かれています。}

${\displaystyle \varphi _{C}(v)=\sum _{C\subseteq T\subseteq N}{\frac {w(T)}{|T|-|C|+1}}}$

ここで、合計はすべての部分集合について取られる。${\displaystyle T}$の${\displaystyle N}$含まれる${\displaystyle C}$。

この式は、連合のシャプレー値は、連合が単一プレイヤーの標準シャプレー値であると考えるべきだという解釈を示唆している。${\displaystyle C}$シングルプレイヤーとして扱われる。

シャプレー値${\displaystyle \varphi _{i}(v)}$^{ハウスケンとマティアス[ 15 ]}によって値の行列に分解された。

${\displaystyle \varphi _{ij}(v)=\sum _{S\subseteq N}{\frac {(|S|-1)!\;(n-|S|)!}{n!}}(v(S)-v(S\setminus \{i\})-v(S\setminus \{j\})+v(S\setminus \{i,j\}))\sum _{t=|S|}^{n}{\frac {1}{t}}}$

各値${\displaystyle \varphi _{ij}(v)}$プレイヤーの価値を表す${\displaystyle i}$プレイヤーへ${\displaystyle j}$この行列は以下を満たす。

${\displaystyle \varphi _{i}(v)=\sum _{j\in N}\varphi _{ij}(v)}$

つまり、プレイヤーの価値${\displaystyle i}$ゲーム全体に対する彼らの価値は、すべての個々のプレイヤーに対する彼らの価値の総和である。

相乗効果の観点から${\displaystyle w}$上記で定義したように、これは次のように読み取れる。

${\displaystyle \varphi _{ij}(v)=\sum _{\{i,j\}\subseteq S\subseteq N}{\frac {w(S)}{|S|^{2}}}}$

ここで、合計はすべての部分集合について取られる。${\displaystyle S}$の${\displaystyle N}$含まれる${\displaystyle i}$そして${\displaystyle j}$。

これは、プレイヤーを含むすべての部分集合の合計として解釈できます。${\displaystyle i}$そして${\displaystyle j}$、各部分集合について${\displaystyle S}$あなた

• 相乗効果を活用する${\displaystyle w(S)}$そのサブセットの
• それをサブセット内のプレイヤー数で割る${\displaystyle |S|}$それを余剰価値プレーヤーと解釈してください${\displaystyle i}$この連立政権による利益
• さらにこれを${\displaystyle |S|}$プレイヤーの役を得る${\displaystyle i}$プレイヤーに帰属する値${\displaystyle j}$

言い換えれば、各連合の相乗効果は全員に均等に分配される。${\displaystyle |S|^{2}}$ペア${\displaystyle (i,j)}$その連合のプレーヤーの中で、${\displaystyle i}$余剰を生み出す${\displaystyle j}$。

シャプレー値回帰は、回帰モデルにおける個々の予測変数の寄与度を測定するために使用される統計的手法です。この文脈では、「プレーヤー」はモデル内の個々の予測変数または変数であり、「ゲイン」はモデルによって説明される分散の合計または予測力です。この手法は、各予測変数にモデルのパフォーマンスへの寄与度を表す値を割り当てることにより、予測変数間で総ゲインが公平に分配されることを保証します。^{[ 16 ]}

シャプレー値貢献度は、安定性と識別力のバランスが優れていることで知られており、市場調査におけるサービス属性の重要性を正確に測定するのに適しています。^{[ 17 ]}いくつかの研究では、マーケティング調査における主要要因分析にシャプレー値回帰を適用しています。Pokryshevskaya と Antipov (2012) は、この方法を使用してオンライン顧客の再購入意向を分析し、消費者の行動を理解する上での有効性を示しました。^{[ 18 ]}同様に、Antipov と Pokryshevskaya (2014) は、シャプレー値回帰を適用して南キプロスのホテルの推奨率の違いを説明し、ホスピタリティ業界におけるその有用性を強調しました。^{[ 19 ]}主要要因分析におけるシャプレー値の利点のさらなる検証は、応用マーケティング分析におけるその利点を強調した Vriens、Vidden、および Bosch (2021) によって提供されています。^{[ 20 ]}

シャプレー値は、機械学習の分野でよく見られる非線形モデルの予測を説明する原理的な方法を提供します。一連の特徴量でトレーニングされたモデルをプレイヤーの連合に対する価値関数として解釈することで、シャプレー値は、どの特徴量が予測に寄与しているか^{[ 21 ]}、または予測の不確実性に寄与しているか [ 22 ] を計算する自然な方法を提供します。^{これにより、}局所的に解釈可能なモデル非依存の説明(LIME) ^{[ 23 ]} 、 DeepLIFT ^{[ 24 ]}、レイヤーごとの関連性伝播^{[ 25 ] [ 26 ]}など、他のいくつかの方法が統合されます。

分布値は、機械学習における予測モデルの確率的出力（ニューラルネットワーク分類器や大規模言語モデルなど）を保持するために設計された、シャプレー値および関連する値演算子の拡張である。^{[ 27 ]}

シャプレー値の統計的理解は、現在も研究が続いている課題である。シャプレー曲線と呼ばれる滑らかなバージョン^{[ 28 ]}は、ミニマックス率を達成し、ノンパラメトリック設定では漸近的にガウス分布になることが示されている。有限サンプルの信頼区間は、ワイルドブートストラップによって得られる。

• 空港の問題
• バンジャフのパワーインデックス
• シャプレー・シュビックのパワー指数

• フリードマン、ジェームズ・W. (1986).ゲーム理論とその経済学への応用. ニューヨーク：オックスフォード大学出版局. pp. 209–215 . ISBN  0-19-503660-3。

• 「シャプレー値」、数学百科事典、EMS Press、2001年 [1994年]
• シャプレー値計算機
• シャプレー値を用いたタクシー料金の計算