技術的概要：有向ネットワークによって定義される扱いやすい協力ゲームのクラス

問題提起

本論文は、重み付き有向グラフによって誘発されるゲームに関する協力ゲーム理論に内在する計算上および分析的な課題に取り組んでいる。協力ゲームは通常、プレイヤー数に対して指数関数的な表現サイズを有するため、解概念（シャプレイ値やバンジフ値など）や安定性特性（コアなど）の計算が困難（多くの場合$\sharp$P-完全）となる。

これまでに、無向グラフや特定の部分クラス（例えば、重み付き投票ゲームなど）によって誘発されるゲームが研究されてきたが、有向ネットワークによって定義され、分析的かつ計算的に扱いやすい構造化されたゲームのクラスが必要とされている。著者らは、「信頼ゲーム」と呼ばれる特定のゲームのクラスを導入する。ここで、連合の価値は内部的相互作用と外部への曝露の両方によって決定される。主な課題は、解概念に対する閉形式の多項式時間式を導出し、特に外部成分が非加法的でボトルネックのような振る舞いを導入することを踏まえ、これらのゲームの安定性特性を特徴づけることである。

手法

著者らは、エッジ重み $a_{ij} \in [0, 1]$ を持つ重み付き有向グラフ $G = (N, E)$ によって誘発される信頼ゲーム $(N, v)$ を定義する。連合 $S \subseteq N$ の価値は、以下の 2 つの成分の和として定義される。

1. 内部項: $i, j \in S$ であるすべてのエッジ $(i, j)$ の重みの和。これは誘発部分グラフゲームに対応する。
2. 外部項: $S$ 外のノードから入ってくるエッジを持つ各プレイヤー $i \in S$ について、その入ってくるエッジの重みの最小値が価値に含まれる。$S$ 内のプレイヤーが $S$ 外から入ってくるエッジを持たない場合、この項は 0 に寄与する。

数学的には以下の通りである：
$$v(S) = \sum_{i \in S, j \in S, (i,j) \in E} a_{ij} + \sum_{i \in S^*} \min_{j \notin S: (j,i) \in E} a_{ji}$$
ここで、$S^*$ は $N \setminus S$ からの少なくとも 1 つの入ってくるエッジを持つ $S$ 内のプレイヤーの集合である。

このゲームを分析するために、著者らはゲームを合意ゲーム（unanimity games, $u_T$）の線形結合に分解するメビウス変換を用いる。

• 内部成分は、対の合意ゲームを含む単純なものである。
• 外部成分は $\min$ 演算子のためより複雑である。著者らは、各プレイヤー $i$ の入ってくる隣接ノードをエッジ重みの非減少順に並べる。そして、プレイヤー $i$ に対する外部ゲームは、入ってくる隣接ノードの順位によって決定される包含連鎖を形成する支持集合を持つ合意ゲームの telescopic sum（項消去和）として表現できることを示す。

この分解により、著者らはシャプレイ演算子とバンジフ演算子の線形性を利用し、明示的な式を導出することができる。

主要な貢献と結果

1. 合意分解

本論文は、信頼ゲームに対する閉形式の合意分解を確立する。

• 補題 2.3: プレイヤー $i$ に対する外部ゲーム $w_i(S)$ は、合意ゲーム $u_{T_i(t)}$ の和に分解される。ここで、$T_i(t)$ はプレイヤー $i$ と、重みでソートされた最初の $t-1$ 個の入ってくる隣接ノードから構成される。係数はソートされたエッジ重みの差である。
• 補題 3.2: 全体のゲーム $v(S)$ は、内部的な対の合意ゲームと分解された外部の合意ゲームの和である。

2. 多項式時間解概念

合意分解を用いて、著者らは以下の明示的な多項式時間式を導出した。

• シャプレイ値 ($\phi_i$): 値は 3 つの部分の和として表現される。
  1. 内部エッジ重みの平均（対称な重み付き次数中心性）。
  2. プレイヤー $i$ 自身の入ってくるエッジから導かれる項（外部曝露）。
  3. $i$ のアウト隣接ノードに入ってくるエッジから導かれる項（共有隣接効果）。
     式（定理 3.1）は、他のノードの入ってくる隣接ノードにおける各プレイヤーの順位を明示的に考慮している。
• バンジフ値 ($\beta_i$): 同様に、閉形式の式が導出される（定理 4.2）。これは、合意ゲームの特定のバンジフ値（$2^{1-|T|}$）を利用する。

3. 限界効果分析

本論文は、エッジ重みの局所的な変化が解値にどのように影響するかを分析する。

• 補題 3.5 および 4.3: エッジ重み $a_{kj}$ のプレイヤーの値に対する限界効果は、プレイヤーとエッジの相対的な位置に依存する。
  • 内部エッジ: シャプレイ値とバンジフ値の両方に線形に寄与する。
  • 外部エッジ: 効果は非線形であり、ターゲットノードの入ってくる隣接ノードにおけるプレイヤーの順位に依存する。シャプレイ値の場合、効果には $\frac{1}{r(r+1)}$ のような項が含まれ、バンジフ値の場合、$\frac{1}{2^r}$ が含まれる。
• ヌルプレイヤーの特性: 補題 3.6 は、プレイヤーがヌルプレイヤー（値 0）となるための必要十分条件を提供する。これは、入ってくるエッジがない場合、または入ってくるエッジが特定の構造的意味においてそれ自体がヌルであるプレイヤーから来る場合に発生する。

4. 安定性とコアの特性

著者らは、信頼ゲームの安定性を調査する。

• コアの特性（補題 5.1）: 信頼ゲームのコアは単元集合である。これは、各プレイヤー $i$ がグラフ全体からのすべての入ってくるエッジ重みの和（$\sum_{j} a_{ji}$）を受け取る一意の配分からなる。
• 完全均衡性（補題 5.2）: このゲームは完全に均衡しており、つまり、任意の連合 $S$ に制限された任意の部分ゲームは空でないコアを持つ。これは、任意の部分ゲームに対して明示的なコア配分を構成することで証明される。
• 概念の乖離: 本論文は、一意のコア配分（総入ってくる重みに基づく）が一般的にシャプレイ値やバンジフ値と一致しないことを強調している。これは、安定性に基づく配分と公平性に基づく解概念が乖離する状況を示している。

意義と主張

本論文は、構造化されたネットワークによって誘発される協力ゲームの扱いやすい例を提供すると主張している。その意義は以下の点にある。

1. 計算的扱いやすさ: 一般的な協力ゲームに典型的な指数関数的複雑さを回避し、多項式時間で解概念（シャプレイ、バンジフ）と安定性特性（コア）を計算できるゲームのクラスを提供する。
2. 構造的洞察: 合意分解は、外部成分における複雑な「最小値」演算子が、ネストされた合意ゲームの連鎖を生成し、ゲームを分析的に管理可能にすることを明らかにする。
3. 理論的区別: ゲームが完全に均衡しているにもかかわらず、コア（安定性）とシャプレイ値（公平性/限界貢献）が異なる配分をもたらすシナリオを明示的に示す。
4. 将来の作業の基盤: 著者らは、このクラスが、パラメトリックな一般化、外部成分のための代替集約ルール、およびインセンティブ適合性に関するメカニズム設計の問題を探求するための基準として機能すると提案している。

本作業は新しい実験的応用を提案するものではなく、非対称で局所的な評価を持つ有向ネットワークにおける協力相互作用を分析するための理論的枠組みを確立するものである。