Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

技術的概要：提携ゲームにおけるグループ評価のための逐次除去とユニオン・シャープリー値

問題定義
協力ゲーム理論およびネットワーク中心性や機械学習のデータ評価などの関連分野において、基本的な課題は、個々のプレイヤーの評価をグループに拡張することである。既存の手法は通常、以下の 2 つの直截的なアプローチに依存している：

1. 総和（Summation）： 個々の値（例：シャープリー値の和）を集約する。これはプレイヤー間の協力の基盤となる構造や依存関係を無視する。
2. 統合（Merging）： グループを単一の統合された要素として扱い、それを評価する（例：マージ・シャープリー値）。これはゲーム構造を変化させ、独立したプレイヤーと高度に依存したプレイヤーを区別できなくする。

どちらのアプローチも、グループ内の依存関係を正確に捉えることに失敗することが多い。例えば、2 つの互いに素なプレイヤーのペアが独立して価値を生成するゲームにおいて、個々の値を総和したりグループを統合したりすると、協力する 2 人のペアと独立した 2 人のペアに誤って同等の重要性を割り当ててしまい、システムへの影響における非対称性を反映できなくなる。

手法
著者は、**逐次除去（sequential elimination）**に基づく第 3 のアプローチを提案し、分析する。この枠組みでは、グループの要素を 1 つずつ除去し、その結果生じる縮小ゲームにおける評価を集約する。核心的な仮説は、この手法が重複する効果を割り引くことでグループの純粋な貢献を自然に測定し、グループの不在によって引き起こされる損害に焦点を当てることである。

本研究は、提携ゲームにおけるグループ値の包括的な公理的分析に基づいている。手法には以下が含まれる：

• 公理的クラスの定義： 著者はグループ（弱一貫性）セミ値のクラスを導入する。これらは、線形性、対称性、弱単調性、Null Player Out、およびダミープレイヤーの公理を満たすグループ値である。また、ダミープレイヤーの公理をDummifying Playerの公理（Grabisch と Roubens によって導入された）に置き換える対応するシナジー・セミ値のクラスも定義する。
• 逐次拡張： 本論文は、プレイヤー値が逐次拡張を許容するかどうかは、バランスド・コントリビューション（Balanced Contributions）の性質を満たすかどうかと同値であることを確立する。また、すべての一貫性のあるセミ値（Null Player Out を満たすもの）が、一意の逐次拡張を許容することを証明する。
• ポテンシャル関数： 著者は、Hart と Mas-Colell によって導入されたポテンシャル関数を用いて、シャープリー値の逐次拡張を特徴づける。

主要な貢献と結果

1. ユニオン・シャープリー値（The Union Shapley Value）：
   著者は、シャープリー値の一意の逐次拡張としてユニオン・シャープリー値を導入する。これは、元のゲームのポテンシャルと、グループが除去された後のゲームのポテンシャルとの差として定義される：
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   ここで、$\Delta v(T)$ はハルサニ・配当である。

   • 解釈： この値は、グループが去ったときにゲームに及ぼされる「損害」を測定する。各提携の配当が、たとえグループにその提携の複数のメンバーが含まれていたとしても、最大 1 回しかカウントされないように貢献を集約する。
   • 公理化： ユニオン・シャープリー値は、ポテンシャル（またはバランスド・コントリビューション）の公理と効率性（Efficiency）の組み合わせによって一意に特徴づけられる。また、グループ・セミ値の中でグループ等価性（合意ゲームにおけるすべてのグループは同等に重要である）によって一意に特徴づけられる。

2. グループ値の公理的分類：
   本論文は、グループ評価の 2 つの変種を区別する：

   • 総価値（Total Worth）： グループの総価値を評価する値（例：総和拡張、マージ・シャープリー、ユニオン・シャープリー）。これらはグループ・セミ値によって捉えられる。
   • シナジー（Synergy）： グループのシナジーを測定する値（例：相互作用指数）。これらはシナジー・セミ値によって捉えられる。
     著者は、これら 2 つのクラス間の機能的対応を提供する。具体的には、マージ・シャープリー値が相互作用指数（シナジー的な対応物）に対応し、ユニオン・シャープリー値がインタセクション・シャープリー値と呼ばれる新しいシナジー的値に対応することを示す。

3. インタセクション・シャープリー値（The Intersection Shapley Value）：
   グループ全体を含む提携の配当の総和として定義される：
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   この値は、貢献の交差を測定する。サイズが 2 のグループの場合、ユニオン・シャープリー値とインタセクション・シャープリー値の和は、個々のシャープリー値の和に等しくなる：
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   この分解により、グループの共同価値を「ユニオン」部分（貢献を 1 回カウント）と「インタセクション」部分（シナジー）に分離できる。

4. 既存の研究との比較：
   分析は、提案された値と既存の文献との関係を明確にする：

   • マージ・シャープリー値（Marichal ら）は、ダミー・コアリション（Dummy Coalition）の公理を満たす唯一のグループ・セミ値であることが示される。
   • 相互作用指数（Grabisch と Roubens）は、標準的なダミープレイヤーの公理に代わって Dummifying Player の公理を優先するため、グループ・セミ値とは区別されるシナジー・セミ値として特定される。
   • 本論文は、逐次拡張アプローチが、すべての一貫性のあるセミ値に適用され、強力な公理的性質を持つ値を生成するため、理論的に堅牢であることを実証する。

重要性
本論文は、逐次拡張アプローチ、特にユニオン・シャープリー値が、提携ゲームにおいてプレイヤー値をグループに拡張する最も自然で理論的根拠に裏打ちされたアプローチの 1 つであると主張する。総価値の評価とシナジーの測定を区別することで、著者は文献における既存の概念間の差異を明確にする統合された枠組みを提供する。ユニオン・シャープリー値とインタセクション・シャープリー値の導入は、貢献の重複を割り引く必要がある場合（ユニオン）や、純粋なシナジーを分離する必要がある場合（インタセクション）の特に、相互作用を分析するための新たなツールを提供する。この研究は、これらの値が恣意的なヒューリスティックではなく、バランスド・コントリビューション、ポテンシャル、グループ等価性といった基本的な公理によって一意に決定されるものであることを確立する。