ネットワーク形成ゲーム 定義 (ネットワーク形成ゲーム Network Creation Game) $n$ 人のプレイヤー： $[n]=\{1,2,...,n\}$ プレイヤー $i$ の戦略空間： $S_{i}=2^{[n]-\{i\}}$ 戦略： $s=(s_{1},...,s_{n}) \in S_{1} \times \cdots \times S_{n}$ プレイヤー $i$ が最小化するコスト $c_{i}=\alpha \vert s_{i}\vert + \sum_{j=1}^{n}d_{G[s]}(i,j)$ $G_{[s]}=(V,E)$ は無向グラフ $V=[n] , E=\bigcup_{i=1}^{n}\{i\} \times s_{i}$ $d_{G_{[s]}}(i,j)$ はグラフ $G_{[s]}$ における $i$ と $j$ 間の最小距離 定義 (社会的コスト Social Cost) 戦略 $s_{i}$ が切断された/不採用となったときの社会的なコストは以下のようになる． $$C(G)=\sum_{i}c_{i}=\sum_{i}(\alpha \cdot \vert s_{i}\vert + \sum_{j=1}^{n}d_{G}(i,j))$$ (9.1) この関係は、ナッシュ均衡においても社会的最適状態(social optima)においても成立する． 社会的コストの下限(trivial lower bound)は次の通り． $$C(G) \ge \alpha \vert E\vert + 2\vert E\vert + 2(n(n-1)) - 2\vert E\vert)$$ (9.2) $$2n(n-1) + (\alpha - 2)\vert E\vert$$ (9.3)