SGCライブラリ - 44

ゲーム理論のフロンティア

その思想と展望をひらく

池上高志・松田裕之　共編著

2005年12月25日　初版発行

ゲーム理論の背景

ゲームのプレイヤーのモデル化のアプローチ：

限定合理性：プレイヤーの合理性が限定されていること

ゲーム方程式の数理

ゲーム力学方程式（レプリケータ方程式）

$\frac{dx_i}{dt} = x_i(f_i(\mathbf{x}) - \bar{f}(\mathbf{x}))$

反対称な利得行列（ ${A = -A^T}$ ）をもつものをゼロサムゲームという。

平衡点 ${\mathbf{p} = (p_1,p_2,\dots,p_N)}$ における関数 ${\alpha_i(\mathbf{x}) \equiv f_i(\mathbf{x}) - \bar{f}(\mathbf{x})}$ が以下を満たすとき、飽和であるという：

飽和平衡点で正の個体数をもつ種をパーシステント種、その集合 ${P = \{i\,|\,p_i \gt 0\}}$ をパーシステント集合と呼ぶ。

ゼロサム系における飽和平衡点の条件：

関数 ${L_p(\mathbf{x}) \equiv \sum_i^N p_i\log x_i}$ の時間微分：

$\frac{dL_p(\mathbf{x})}{dt} = -\sum_i^Nf_i(\mathbf{p})(x_i - p_i) \ge 0$

${L_p(\mathbf{x})}$ はリアプノフ関数であり、種 ${i \notin P}$ は ${t \to \infty}$ で必ず絶滅する。

パーシステント種は絶滅しない。

$-\infty \lt \frac{L_p(\mathbf{x}(0))}{p_i} \le \frac{L_p(\mathbf{x}(t))}{p_i} \le \log x_i(t)$

上記の議論は複数の飽和平衡点について同時に満たされることはありえないので、集合 ${P}$ の一意性が示される。

計算可能でない必勝戦略をもつゲームが存在する。

必勝戦略：それをとる限り、相手がどんな戦略をとっても必ず勝てる戦略

集合 ${S \subset Z_+}$ が与えられており、 ${S}$ はそれ自身もその補集合 ${S^c \subset Z_+}$ も無限集合であるとする。

以下で定義されるゲームを考える：

ある ${x_1}$ に対してどんな ${x_2}$ を選んでも ${x_1 + x_2 \notin S^c}$ だとすると、 ${S^c}$ が無限集合であることに反することから、後手が必勝戦略をもつ。

${S}$ は単純集合と呼ばれる集合とする：

は帰納的可算である。
- 以下で定義される関数が計算可能である。
  - ${x \in S}$ のとき ${f(x) = 1}$
  - ${x \notin S}$ のとき undefined
${S^c}$ は無限集合で、帰納的可算な無限部分集合を含まない。

集合 ${A \subset Z_+}$ もその補集合 ${A^c \subset Z_+}$ もともに帰納的可算であるとき、 ${A}$ は帰納的であるという。

${A}$ が帰納的であるとき、関係 ${x \in A}$ は決定可能、または計算可能であるという。

${S}$ が単純集合であれば、 ${S^c}$ のどんな無限部分集合も帰納的可算ではないから、 ${x_1 + x_2 \in S^c}$ であるか否かは決定可能ではない。