シミレーション工学８

Dublin Core

Rights

CC BY-NC 4.0 - 非営利目的のみ許可

note Item Type Metadata

note

# 意思決定手法

意思決定とは、複数の選択肢の中から、合理的に最も望ましい（効用が最大になる、あるいは損失を最小にする）選択を行うプロセスである。本資料では、意思決定理論の数学的基礎から実践的応用まで、幅広いトピックを扱う。

## 目次

1. [意思決定理論の数学的基礎](#意思決定理論の数学的基礎)

- [期待効用理論](#期待効用理論expected-utility-theory)

- [問題①　期待効用の計算](#問題①期待効用の計算)

- [ベイズ意思決定理論](#ベイズ意思決定理論bayesian-decision-theory)

- [問題②　ベイズ更新の計算](#問題②ベイズ更新の計算)

- [リスク測度と条件付きリスク値](#リスク測度と条件付きリスク値)

- [動的プログラミングとベルマン方程式](#動的プログラミングとベルマン方程式)

2. [意思決定の分類](#意思決定の分類)

3. [多目的・多属性意思決定（MCDM/MAUT）](#多目的多属性意思決定mcdmmaut)

4. [ロバスト最適化と分布ロバスト最適化](#ロバスト最適化と分布ロバスト最適化)

5. [ゲーム理論による意思決定分析](#ゲーム理論による意思決定分析)

- [ゲーム理論の分類](#ゲーム理論の分類)

- [ナッシュ均衡](#ナッシュ均衡nash-equilibrium)

- [問題③　ナッシュ均衡の計算](#問題③ナッシュ均衡の計算)

- [囚人のジレンマ](#囚人のジレンマゲーム理論の有名な例)

- [繰り返し囚人のジレンマ](#繰り返し囚人のジレンマiterated-prisoners-dilemma)

- [ナッシュ均衡の計算複雑性](#ナッシュ均衡の計算複雑性)

- [計算ゲーム理論：Price of AnarchyとPrice of Stability](#計算ゲーム理論price-of-anarchyとprice-of-stability)

6. [確率微分方程式と確率制御](#確率微分方程式と確率制御)

7. [数値解法と機械学習手法](#数値解法と機械学習手法)

8. [まとめ](#まとめ)

---

意思決定とは、複数の選択肢の中から、合理的に最も望ましい（効用が最大になる、あるいは損失を最小にする）選択を行うプロセスである。意思決定主体とは、この決定を行う個人や組織（消費者、企業、政府など）を指す。

システム内での効用主体がどのように意思決定を行うかは、主体の目的や価値観によって異なる。

例えば：

- 消費者：効用（満足度や便益）の最大化を目指す。商品やサービス選択時に得られる満足の総量を増やそうとする。

- 企業：利潤（利益）の最大化を目標とする。販売量や生産コスト、価格設定などに関する意思決定を最適化する。

- 政府：社会全体の福祉や公平性、安全保障などを目的とした意思決定を行うこともある。

また、これ以外にも「リスクの最小化」「責任回避」「持続可能性重視」「社会的評価」「倫理・法令遵守」など、さまざまな評価基準が考えられる。

---

## 意思決定理論の数学的基礎

### 期待効用理論（Expected Utility Theory）

不確実性下での意思決定を分析する際、期待効用理論が基本的な枠組みとなる。選択肢 $i$ の期待効用 $E[U_i]$ は以下のように定義される：

> **実践例**：在庫管理における新聞売り子問題（Newsvendor Problem）は、期待効用最大化の典型的な応用例である。不確実な需要に対して最適な発注量を決定する問題として定式化される。

$$E[U_i] = \sum_{j} p_j \cdot u(x_{ij})$$

ここで、$p_j$ は状態 $j$ の発生確率、$u(x_{ij})$ は状態 $j$ における結果 $x_{ij}$ の効用関数、$x_{ij}$ は選択肢 $i$ を選んだ際に状態 $j$ で得られる結果である。

合理的な意思決定主体は、期待効用を最大化する選択肢を選ぶと仮定される（期待効用最大化仮説）。

### 期待効用理論の詳細フロー

**図1: 期待効用理論の詳細フロー**

```mermaid

graph TB

subgraph "意思決定プロセス"

A[複数の選択肢 Alternatives i=1,2,...,n] --> B[各選択肢の評価]

end

subgraph "不確実性の考慮"

B --> C[状態jの発生確率 p_j = PState j]

C --> D[各状態での結果 x_ij = Outcome 選択肢i 状態j]

end

subgraph "効用の評価"

D --> E[効用関数の適用 u x_ij = Utility]

E --> F[各状態の効用 u x_ij]

end

subgraph "期待効用の計算"

F --> G[期待効用 EU_i = Σ_j p_j×u x_ij Expected Utility]

C --> G

end

subgraph "最適選択"

G --> H[すべての選択肢の 期待効用を比較]

H --> I[最適選択 i* = argmax_i EU_i Optimal Choice]

end

subgraph "意思決定の実行"

I --> J[選択肢i*を実行 Execute Alternative i*]

end

```

### von Neumann-Morgensternの期待効用定理

選好関係 $\succeq$ が以下の公理を満たすとき、効用関数 $u: \mathcal{X} \to \mathbb{R}$ が存在し、任意の確率分布 $P, Q$ について

P \succeq Q \Leftrightarrow \int u(x) \, dP(x) \ge \int u(x) \, dQ(x)

が成立する：

1. **完全性**：$\forall P, Q$ について $P \succeq Q$ または $Q \succeq P$

2. **推移性**：$P \succeq Q, Q \succeq R \Rightarrow P \succeq R$

3. **連続性**：$P \succeq Q \succeq R$ なら、$\exists \alpha \in [0,1]$ で $Q \sim \alpha P + (1-\alpha)R$

4. **独立性**：$P \succeq Q \Rightarrow \alpha P + (1-\alpha)R \succeq \alpha Q + (1-\alpha)R$（$\forall R, \alpha \in (0,1)$）

この効用関数 $u$ は正アフィン変換（$u' = au + b$、$a > 0$）の下で一意である。

## 問題①　期待効用の計算

### 問題文

ある投資家が2つの投資選択肢 $A$ と $B$ を比較している。各選択肢の結果と確率は以下の通りである：

**選択肢 $A$**:

- 状態1（確率 $p_1 = 0.6$）: 利益 $x_{A1} = 100$ 万円

- 状態2（確率 $p_2 = 0.4$）: 損失 $x_{A2} = -50$ 万円

**選択肢 $B$**:

- 状態1（確率 $p_1 = 0.3$）: 利益 $x_{B1} = 200$ 万円

- 状態2（確率 $p_2 = 0.7$）: 損失 $x_{B2} = -30$ 万円

投資家の効用関数は $u(x) = \sqrt{x + 100}$（$x \geq -100$）で与えられる。

1. 各選択肢の期待効用を求めよ

2. どちらの選択肢を選ぶべきか判断せよ

3. リスク中立的な投資家（$u(x) = x$）の場合の期待効用を比較せよ

### 解答

#### 1. 選択肢 $A$ の期待効用

\begin{aligned}

E[U_A] &= p_1 \cdot u(x_{A1}) + p_2 \cdot u(x_{A2}) \\

&= 0.6 \times \sqrt{100 + 100} + 0.4 \times \sqrt{-50 + 100} \\

&= 0.6 \times \sqrt{200} + 0.4 \times \sqrt{50} \\

&= 0.6 \times 14.1421\ldots + 0.4 \times 7.0711\ldots \\

&\approx 0.6 \times 14.14 + 0.4 \times 7.07 \\

&\approx 8.48 + 2.83 = 11.31

\end{aligned}

#### 2. 選択肢 $B$ の期待効用

\begin{aligned}

E[U_B] &= p_1 \cdot u(x_{B1}) + p_2 \cdot u(x_{B2}) \\

&= 0.3 \times \sqrt{200 + 100} + 0.7 \times \sqrt{-30 + 100} \\

&= 0.3 \times \sqrt{300} + 0.7 \times \sqrt{70} \\

&= 0.3 \times 17.3205\ldots + 0.7 \times 8.3666\ldots \\

&\approx 0.3 \times 17.32 + 0.7 \times 8.37 \\

&\approx 5.20 + 5.86 = 11.06

\end{aligned}

#### 3. 選択肢の比較

$E[U_A] = 11.31 > 11.06 = E[U_B]$ であるため、**選択肢 $A$ を選ぶべき**である。

#### 4. リスク中立的な投資家の場合

効用関数が $u(x) = x$ の場合：

**選択肢 $A$ の期待効用**:

E[U_A] = 0.6 \times 100 + 0.4 \times (-50) = 60 - 20 = 40 \text{ 万円}

**選択肢 $B$ の期待効用**:

E[U_B] = 0.3 \times 200 + 0.7 \times (-30) = 60 - 21 = 39 \text{ 万円}

リスク中立的な投資家の場合、選択肢 $A$（期待値40万円）の方が選択肢 $B$（期待値39万円）より優れている。

### 答え

- **選択肢 $A$ の期待効用**: $E[U_A] \approx 11.31$

- **選択肢 $B$ の期待効用**: $E[U_B] \approx 11.06$

- **推奨選択肢**: **選択肢 $A$**

### 検証

リスク回避的な効用関数 $u(x) = \sqrt{x + 100}$ の場合、選択肢 $A$ の方が期待効用が高い。これは、選択肢 $A$ の損失が選択肢 $B$ より大きいものの（-50万円 vs -30万円）、高い確率で利益が得られる（60% vs 30%）ため、リスク回避的な投資家にとって選択肢 $A$ が好ましいことを示している。

リスク中立的な投資家の場合も、期待値の観点から選択肢 $A$ が優れている。

### ベイズ意思決定理論（Bayesian Decision Theory）

状態空間 $\Theta$、観測データ $y$、損失関数 $L(\theta, a)$ を考える。ベイズ意思決定では、事後分布 $p(\theta \mid y)$ に基づき期待損失（ベイズリスク）を最小化する行動 $a^*$ を求める：

a^*(y) = \arg\min_{a \in \mathcal{A}} \int_{\Theta} L(\theta, a) \, p(\theta \mid y)\, d\theta

事前分布 $\pi(\theta)$ に対する事前期待損失は

r(\pi, \delta) = \int_{\Theta} \int_{\mathcal{Y}} L(\theta, \delta(y)) \, p(y \mid \theta) \, dy \, \pi(\theta) \, d\theta

で与えられ、最小ベイズリスクを達成する意思決定規則 $\delta^*$ が最適とされる。シミュレーション工学では、モデルパラメータの不確実性を陽に扱い、意思決定をロバスト化する目的で用いられる。

### ベイズ更新の詳細プロセス

**図2: ベイズ更新の詳細プロセス**

```mermaid

graph TB

subgraph "事前情報"

A[事前分布πθ Prior Distribution パラメータθの不確実性] --> D[ベイズ更新]

end

subgraph "データの観測"

B[観測データy Observed Data y = y₁,y₂,...,yₙ] --> D

B --> E[尤度関数 py given θ Likelihood Function]

end

subgraph "ベイズ更新"

D --> F[ベイズの定理 pθ given y = py given θ πθ / py Bayes Theorem]

A --> F

E --> F

F --> G[事後分布pθ given y Posterior Distribution 更新された不確実性]

end

subgraph "意思決定"

G --> H[期待損失計算 Expected Loss ∫Lθ,a pθ given y dθ]

H --> I[最適行動a* Optimal Action a* = argmin Expected Loss]

I --> J[ベイズリスク最小化 Bayes Risk Minimization rπ,δ* = min]

end

subgraph "結果の解釈"

J --> K[不確実性を考慮した ロバストな意思決定 Robust Decision Making]

end

```

## 問題②　ベイズ更新の計算

### 問題文

ある工場の不良品率 $\theta$ について、事前分布としてベータ分布 $\text{Beta}(2, 8)$ を仮定する。すなわち：

\pi(\theta) = \frac{\Gamma(10)}{\Gamma(2)\Gamma(8)} \theta^{1} (1-\theta)^{7}, \quad 0 \leq \theta \leq 1

ここで、$\Gamma(10) = 9! = 362,880$、$\Gamma(2) = 1! = 1$、$\Gamma(8) = 7! = 5,040$ である。

この工場で100個の製品を検査したところ、5個の不良品が見つかった。

1. 事後分布のパラメータを求めよ

2. 事後分布の平均（事後期待値）を求めよ

3. 事前分布の平均と比較せよ

### 解答

#### 1. 事後分布のパラメータ

**ベータ分布の共役性**：

ベータ分布は二項分布の共役事前分布である。すなわち、事前分布がベータ分布 $\text{Beta}(\alpha, \beta)$ で、尤度が二項分布 $\text{Binomial}(n, \theta)$ の場合、事後分布もベータ分布となる。

ベイズの定理より：

p(\theta \mid y) \propto p(y \mid \theta) \cdot \pi(\theta)

ここで：

- 事前分布：$\pi(\theta) \propto \theta^{\alpha-1}(1-\theta)^{\beta-1}$（ベータ分布）

- 尤度：$p(y \mid \theta) = \binom{n}{s} \theta^s (1-\theta)^{n-s}$（二項分布）

したがって：

\begin{aligned}

p(\theta \mid y) &\propto \theta^s (1-\theta)^{n-s} \cdot \theta^{\alpha-1}(1-\theta)^{\beta-1} \\

&= \theta^{\alpha+s-1} (1-\theta)^{\beta+n-s-1}

\end{aligned}

これはベータ分布 $\text{Beta}(\alpha + s, \beta + n - s)$ の形である。

**本問題への適用**：

- 事前分布: $\text{Beta}(2, 8)$ より $\alpha = 2$、$\beta = 8$

- 観測データ: $n = 100$、不良品数 $s = 5$

したがって、事後分布は：

p(\theta \mid y) \sim \text{Beta}(2 + 5, 8 + 100 - 5) = \text{Beta}(7, 103)

#### 2. 事後分布の平均

ベータ分布 $\text{Beta}(\alpha, \beta)$ の平均は $\frac{\alpha}{\alpha + \beta}$ であるから：

\mathbb{E}[\theta \mid y] = \frac{7}{7 + 103} = \frac{7}{110} \approx 0.0636

#### 3. 事前分布の平均との比較

事前分布の平均は：

\mathbb{E}[\theta] = \frac{2}{2 + 8} = \frac{2}{10} = 0.2

### 答え

- **事後分布**: $\text{Beta}(7, 103)$

- **事後期待値**: $\mathbb{E}[\theta \mid y] \approx 0.0636$（約6.36%）

- **事前期待値**: $\mathbb{E}[\theta] = 0.2$（20%）

### 検証

観測データにより、不良品率の推定値は事前の20%から事後の約6.36%に更新された。これは、実際の検査結果（100個中5個の不良品、実測不良品率5%）が事前の期待値（20%）より低かったため、事後分布がより低い値にシフトしたことを示している。

ベイズ更新により、事前情報と観測データを統合した、より正確な推定が可能となった。

### リスク測度と条件付きリスク値

期待効用では捉えきれない尾部リスクを扱うため、凸リスク測度 $\rho(X)$ を導入する。代表例として条件付きバリュー・アット・リスク（CVaR）がある：

\mathrm{CVaR}_{\alpha}(X) = \frac{1}{1-\alpha} \int_{\alpha}^{1} \mathrm{VaR}_{u}(X) \, du = \min_{t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \mathbb{E}\left[(X - t)_+\right] \right\}

ここで $\alpha \in (0,1)$ は信頼水準、$(\cdot)_+$ は正部分を表す。意思決定問題は

\min_{a \in \mathcal{A}} \mathrm{CVaR}_{\alpha}\bigl( L(X,a) \bigr)

のように定式化され、最悪ケースを重視した保守的な方策を導く。

### コヒーレントリスク測度と表現定理

リスク測度 $\rho: \mathcal{X} \to \mathbb{R}$ が以下の4条件を満たすとき、コヒーレントリスク測度と呼ばれる：

1. **単調性**：$X \le Y \Rightarrow \rho(X) \ge \rho(Y)$

2. **変換不変性**：$\rho(X + c) = \rho(X) - c$（$c \in \mathbb{R}$）

3. **正斉次性**：$\rho(\lambda X) = \lambda \rho(X)$（$\lambda \ge 0$）

4. **劣加法性**：$\rho(X + Y) \le \rho(X) + \rho(Y)$

アーツネル・デルバエン表現定理により、任意のコヒーレントリスク測度は

\rho(X) = \sup_{Q \in \mathcal{Q}} \mathbb{E}_Q[-X]

と表現される。ここで $\mathcal{Q}$ は確率測度の凸集合（リスク中立測度集合）である。CVaRは代表的なコヒーレントリスク測度であり、$\mathcal{Q} = \{Q: \frac{dQ}{dP} \le \frac{1}{1-\alpha}\}$ に対応する。

### エントロピックリスク測度と情報理論

情報理論的アプローチでは、エントロピックリスク測度

\rho_\beta(X) = \frac{1}{\beta} \log \mathbb{E}\left[e^{-\beta X}\right]

が用いられる。$\beta > 0$ はリスク回避パラメータで、$\beta \to 0$ で期待値、$\beta \to \infty$ で最悪ケースに収束する。相互情報量 $I(X;Y) = H(X) - H(X|Y)$ を用いて、情報制約下での意思決定問題

\min_{P_{Y|X}} \mathbb{E}[L(X,Y)] \quad \text{s.t.} \quad I(X;Y) \le C

が定式化される。これはレート歪み理論と密接に関連する。

### カルバック・ライブラー（KL）ダイバージェンスと最大エントロピー原理

確率分布 $P, Q$ の間のKLダイバージェンスは

D_{\mathrm{KL}}(P \| Q) = \int \log \frac{dP}{dQ} \, dP = \mathbb{E}_P\left[\log \frac{dP}{dQ}\right]

で定義される。最大エントロピー原理では、制約条件 $\mathbb{E}_P[f_i(X)] = c_i$（$i=1,\ldots,m$）の下でエントロピー $H(P) = -\int p(x) \log p(x) \, dx$ を最大化する分布

p^*(x) = \frac{1}{Z(\lambda)} \exp\left(\sum_{i=1}^m \lambda_i f_i(x)\right)

が得られる。ここで $Z(\lambda)$ は正規化定数、$\lambda_i$ はラグランジュ乗数である。

### マルチンゲール理論と最適停止

確率過程 $\{X_t\}$ がフィルトレーション $\{\mathcal{F}_t\}$ に関するマルチンゲールであるとは、$\mathbb{E}[X_t | \mathcal{F}_s] = X_s$（$s \le t$）を満たすことである。

最適停止問題では、停止時刻 $\tau$ を選択して $\mathbb{E}[X_\tau]$ を最大化する。スネル包絡線（Snell envelope）は

Y_t = \max\{X_t, \mathbb{E}[Y_{t+1} | \mathcal{F}_t]\}

で定義され、最適停止時刻は $\tau^* = \inf\{t: Y_t = X_t\}$ で与えられる。連続時間では、最適停止境界 $b(t)$ が自由境界問題

\begin{cases}

\mathcal{L}V + \frac{\partial V}{\partial t} = 0 & (x > b(t)) \\

V(x,t) = g(x,t) & (x = b(t)) \\

\frac{\partial V}{\partial x}(b(t), t) = \frac{\partial g}{\partial x}(b(t), t) & \text{(smooth fit)}

\end{cases}

を満たす。ここで $\mathcal{L}$ は生成作用素、$g$ は即時報酬である。

### プロスペクト理論（Prospect Theory）

行動経済学的アプローチでは、価値関数 $v(x)$ と確率加重関数 $w(p)$ を用いて期待効用の非線形化を行う：

V = \sum_{i} w(p_i) \, v(x_i), \quad

v(x) =

\begin{cases}

(x-\mu)^{\alpha} & (x \ge \mu) \\

- \lambda (\mu - x)^{\beta} & (x < \mu)

\end{cases}

ここで $\mu$ は参照点、$\lambda > 1$ は損失回避係数、$0 < \alpha, \beta \le 1$ は感応度係数である。確率加重は $w(p) = \frac{p^{\gamma}}{\left(p^{\gamma} + (1-p)^{\gamma}\right)^{1/\gamma}}$ などの形で記述され、人間の非線形な確率知覚（小確率の過大評価等）をモデル化する。

### 効用関数の性質

効用関数 $u(x)$ は、以下の性質を持つことが多い：

- **単調性**：より多くの財や利益を好む（$u'(x) > 0$）

- **リスク態度**：

- リスク回避的：$u''(x) < 0$（凹関数、限界効用逓減）

- リスク中立的：$u''(x) = 0$（線形関数）

- リスク愛好的：$u''(x) > 0$（凸関数、限界効用逓増）

### リスク態度の可視化

**図3: リスク態度の可視化**

```mermaid

graph TB

subgraph "効用関数の形状"

A[効用関数ux Utility Function] --> B[リスク回避的 u''x < 0 凹関数]

A --> C[リスク中立的 u''x = 0 線形関数]

A --> D[リスク愛好的 u''x > 0 凸関数]

end

subgraph "限界効用"

B --> E[限界効用逓減 Marginal Utility Decreasing u'x > 0 かつ u''x < 0]

C --> F[限界効用一定 Marginal Utility Constant u'x = constant]

D --> G[限界効用逓増 Marginal Utility Increasing u'x > 0 かつ u''x > 0]

end

subgraph "意思決定への影響"

E --> H[確実な結果を好む Prefer Certainty リスクを避ける]

F --> I[期待値で判断 Expected Value Decision リスク中立]

G --> J[不確実な結果を好む Prefer Uncertainty リスクを求める]

end

subgraph "実例"

H --> K[保険の購入 Insurance Purchase]

I --> L[期待値最大化 Expected Value Maximization]

J --> M[ギャンブル Gambling]

end

```

### 意思決定の分類

意思決定は、以下のように分類できる：

1. **決定論的意思決定**：結果が確定的に分かっている場合

2. **リスク下の意思決定**：各結果の発生確率が既知の場合

3. **不確実性下の意思決定**：確率が未知または主観的な場合

4. **多目的意思決定**：複数の評価基準を同時に考慮する場合

5. **多属性意思決定**：複数の属性を持つ選択肢を評価する場合

**図4: 意思決定の分類**

```mermaid

graph TB

A[意思決定 Decision Making] --> B{結果の確実性 Certainty of Outcomes}

B -->|結果が確定的 Deterministic| C[決定論的意思決定 Deterministic Decision 最適化問題]

B -->|確率が既知 Known Probabilities| D[リスク下の意思決定 Decision under Risk 期待効用理論]

B -->|確率が未知 Unknown Probabilities| E[不確実性下の意思決定 Decision under Uncertainty ベイズ意思決定]

A --> F{評価基準の数 Number of Criteria}

F -->|単一基準 Single Criterion| G[単一目的意思決定 Single Objective]

F -->|複数基準 Multiple Criteria| H[多目的意思決定 Multi-Objective Decision パレート最適化]

A --> I{選択肢の属性 Attributes of Alternatives}

I -->|単一属性 Single Attribute| J[単属性意思決定]

I -->|複数属性 Multiple Attributes| K[多属性意思決定 Multi-Attribute Decision MAUT AHP TOPSIS]

```

### 多目的・多属性意思決定（MCDM/MAUT）

複数基準 $f_k(x)$（$k=1,\dots,m$）を同時に最適化する場合、パレート支配の概念が重要となる。解集合 $\mathcal{X}$ から得られるパレート前線 $\mathcal{P}$ は、他のいかなる解にも全基準で劣らない非支配解で構成される：

### 多目的最適化の概念図

**図5: 多目的最適化の概念図**

```mermaid

graph TB

subgraph "目的関数"

A[複数基準 Multiple Criteria f₁x f₂x ... fₘx] --> B[目的関数空間 Objective Space]

end

subgraph "パレート支配"

B --> C[解xが解yを支配 x dominates y f_kx ≤ f_ky for all k and f_k'x < f_k'y for some k']

C --> D[非支配解 Non-dominated Solution 他の解に支配されない]

end

subgraph "パレート前線"

D --> E[パレート前線 Pareto Front 非支配解の集合]

E --> F[パレート最適解 Pareto Optimal Solutions トレードオフの関係]

end

subgraph "意思決定"

F --> G[意思決定者の選好 Decision Maker Preference]

G --> H[重み付け Weighting w₁ w₂ ... wₘ]

H --> I[総合評価 Ux = Σw_k u_kx_k MAUT]

end

subgraph "手法"

I --> J[AHP 階層分析法]

I --> K[TOPSIS 理想解への近接度]

I --> L[MOEA 多目的進化計算]

end

```

\mathcal{P} = \left\{ x \in \mathcal{X} \mid \nexists \, y \in \mathcal{X} \text{ s.t. } f_k(y) \le f_k(x) \, \forall k \text{ and } f_{k'}(y) < f_{k'}(x) \text{ for some } k' \right\}

多属性効用理論（MAUT）では、分離可能性を仮定すると総合効用が加法型で表される：

U(x_1,\dots,x_m) = \sum_{k=1}^{m} w_k \, u_k(x_k), \quad \sum_{k} w_k = 1, \; w_k \ge 0

加法性が成立しない場合は、乗法型 $U = \prod_k [1 + \alpha_k u_k(x_k)] - 1$ などで相互作用を表現する。実務では Analytic Hierarchy Process (AHP) や Technique for Order Preference by Similarity to Ideal Solution (TOPSIS)、多目的最適化進化計算（MOEA）等が用いられる。

### ロバスト最適化と分布ロバスト最適化

不確実性集合 $\mathcal{U}$ を導入し、最悪ケースを最小化するロバスト最適化問題は

\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} f(x, \xi)

と定式化される。$\mathcal{U}$ が多面体（box uncertainty, budget uncertainty）の場合は線形計画問題に帰着される。

分布ロバスト最適化（DRO）では、確率分布 $P$ が不確実性集合 $\mathcal{P}$ 内にあると仮定し、

\min_{x \in \mathcal{X}} \sup_{P \in \mathcal{P}} \mathbb{E}_P[f(x, \xi)]

を解く。$\mathcal{P} = \{P: D(P \| P_0) \le \rho\}$（$D$ はKLダイバージェンス）の場合は、双対問題が凸最適化として求解可能である。

### 動的プログラミングとベルマン方程式

離散時間マルコフ決定過程（MDP）では、状態 $s_t$、行動 $a_t$、報酬 $r_t$ の系列を考える。ベルマン方程式

V^*(s) = \max_{a \in \mathcal{A}(s)} \left\{ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right\}

を満たす最適価値関数 $V^*$ が存在し、最適方策は $\pi^*(s) = \arg\max_a Q^*(s,a)$ で与えられる。ここで $Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s')$ は行動価値関数である。

**図6: MDP（マルコフ決定過程）の構造**

```mermaid

graph LR

A[状態s_t State] --> B[行動a_t選択 Action Selection πs_t]

B --> C[報酬r_t獲得 Reward R s_t,a_t]

C --> D[状態遷移 State Transition P s_t+1 given s_t,a_t]

D --> E[次状態s_t+1 Next State]

E --> F[価値関数V*s Value Function V*s=max_a R s,a+γΣP s' given s,a V*s']

F --> G[最適方策π*s Optimal Policy π*s=argmax_a Q*s,a]

G --> B

H[行動価値関数 Q*s,a Q*s,a=R s,a+γΣP s' given s,a V*s'] --> G

```

### 動的プログラミングの詳細フロー

**図7: 動的プログラミングの詳細フロー**

```mermaid

graph TB

subgraph "MDPの要素"

A[状態s_t State] --> B[行動a_t Action]

B --> C[報酬r_t Reward R s_t,a_t]

C --> D[状態遷移 P s_t+1 given s_t,a_t]

end

subgraph "価値関数の計算"

D --> E[ベルマン方程式 Bellman Equation V*s = max_a R s,a + γΣP s' given s,a V*s']

E --> F[価値反復 Value Iteration V_k+1s = max_a R s,a + γΣP s' given s,a V_ks']

F --> G[収束判定 Convergence Check V_k+1 - V_k < ε]

G -->|未収束| F

G -->|収束| H[最適価値関数V* Optimal Value Function]

end

subgraph "方策の決定"

H --> I[行動価値関数 Q*s,a = R s,a + γΣP s' given s,a V*s']

I --> J[最適方策 π*s = argmax_a Q*s,a Optimal Policy]

end

subgraph "方策反復"

J --> K[方策評価 Policy Evaluation V^πs = R s,πs + γΣP s' given s,πs V^πs']

K --> L[方策改善 Policy Improvement π' = argmax_a Q^πs,a]

L --> M{方策が変化?}

M -->|Yes| K

M -->|No| N[最適方策π* Optimal Policy]

end

```

連続時間制御問題では、ハミルトン–ヤコビ–ベルマン（HJB）方程式

0 = \frac{\partial V}{\partial t} + \max_{u \in \mathcal{U}} \left\{ \nabla_x V^\top f(x,u) + \ell(x,u) \right\}

を解くことで最適制御 $u^*(t,x)$ が得られる。確率過程 $dX_t = f(X_t, u_t) dt + \sigma(X_t, u_t) dW_t$ を扱う場合は、HJB方程式に拡散項が加わり

0 = \frac{\partial V}{\partial t} + \max_{u} \left\{ \mathcal{L}^u V + \ell(x,u) \right\}

となる。ここで $\mathcal{L}^u$ は生成作用素 $\mathcal{L}^u = f^\top \nabla_x + \frac{1}{2}\mathrm{tr}(\sigma\sigma^\top \nabla_x^2)$ である。

---

【ゲーム理論による意思決定分析】

ゲーム理論とは、利害関係者（プレイヤー）が相互に影響し合う状況下（ゲーム）で、どのように最適な意思決定をするかを数学的に分析する理論である。

主な特徴として、以下の点が挙げられる：

- 各主体は自分（自己）と他者（相手）の行動や利得（利益・損失）が互いに依存している状況を考慮する必要がある。

- 自分1人の最適だけでなく、相手がどのような行動をするかを予想した上で最適解（最善の戦略）を求める。

- 競争（利害が対立する）/協調（共通の利益がある）のどちらのケースもモデル化できる。

### ゲーム理論の分類

ゲーム理論は、以下のように分類される：

#### 1. 協力ゲーム vs 非協力ゲーム

- **非協力ゲーム**：プレイヤー間の合意や契約が不可能、または強制力がない場合。各プレイヤーは独立に戦略を選択する。

- **協力ゲーム**：プレイヤー間で拘束力のある合意が可能な場合。提携（coalition）の形成と利得の分配が分析の中心となる。

#### 2. 標準形ゲーム vs 展開形ゲーム

- **標準形ゲーム（戦略形ゲーム）**：全プレイヤーが同時に戦略を選択する場合を表現。利得行列（ペイオフマトリクス）で表現される。

- **展開形ゲーム**：プレイヤーが順番に行動を選択する場合を表現。ゲームの木（game tree）で表現され、情報集合（information set）によって情報構造を記述する。

#### 3. 完全情報ゲーム vs 不完全情報ゲーム

- **完全情報ゲーム**：全プレイヤーがゲームの構造（利得関数、可能な行動など）を完全に知っている場合。

- **不完全情報ゲーム**：一部の情報が非対称な場合。ベイジアンゲームとしてモデル化される。

**図8: ゲーム理論の分類**

```mermaid

graph TB

A[ゲーム理論 Game Theory] --> B{協力の可能性 Cooperation}

B -->|合意不可能 No Binding Agreement| C[非協力ゲーム Non-Cooperative Game ナッシュ均衡]

B -->|合意可能 Binding Agreement| D[協力ゲーム Cooperative Game 提携形成]

A --> E{行動の順序 Order of Actions}

E -->|同時選択 Simultaneous| F[標準形ゲーム Normal Form Game 利得行列]

E -->|順次選択 Sequential| G[展開形ゲーム Extensive Form Game ゲームの木]

A --> H{情報の完全性 Information Completeness}

H -->|完全情報 Complete Information| I[完全情報ゲーム Complete Information Game]

H -->|不完全情報 Incomplete Information| J[不完全情報ゲーム Incomplete Information Game ベイジアンゲーム]

C --> K[ナッシュ均衡 Nash Equilibrium]

D --> L[コアシャプレー値 Core Shapley Value]

F --> K

G --> M[サブゲーム完全均衡 Subgame Perfect Equilibrium]

J --> N[ベイジアン・ナッシュ均衡 Bayesian Nash Equilibrium]

```

### ナッシュ均衡（Nash Equilibrium）

非協力ゲームにおける重要な解概念として、ナッシュ均衡がある。

**定義**：戦略の組 $(s_1^*, s_2^*, \ldots, s_n^*)$ がナッシュ均衡であるとは、すべてのプレイヤー $i$ について、他のプレイヤーの戦略 $(s_{-i}^*)$ を所与として、プレイヤー $i$ が戦略 $s_i^*$ から逸脱しても利得を改善できない状態を指す。

数学的には、各プレイヤー $i$ の利得関数を $u_i$ とすると：

$$u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*) \quad \forall s_i \in S_i, \forall i$$

ここで、$S_i$ はプレイヤー $i$ の戦略集合、$s_{-i}^*$ は他のプレイヤーの均衡戦略を表す。

ナッシュ均衡は、すべてのプレイヤーが最適反応（best response）を選択している状態であり、誰も一方的に戦略を変更する動機を持たない安定した状態である。

### ナッシュ均衡の概念図

**図9: ナッシュ均衡の概念図**

```mermaid

graph TB

subgraph "プレイヤー1の最適反応"

A[プレイヤー2の戦略s₂*] --> B[プレイヤー1の最適反応 BR₁s₂* = argmax u₁s₁,s₂*]

B --> C[戦略s₁*]

end

subgraph "プレイヤー2の最適反応"

D[プレイヤー1の戦略s₁*] --> E[プレイヤー2の最適反応 BR₂s₁* = argmax u₂s₁*,s₂]

E --> F[戦略s₂*]

end

subgraph "ナッシュ均衡の条件"

C --> G[s₁* ∈ BR₁s₂* プレイヤー1の最適反応]

F --> H[s₂* ∈ BR₂s₁* プレイヤー2の最適反応]

G --> I[ナッシュ均衡 s₁*,s₂* 両者が最適反応]

H --> I

end

subgraph "均衡の性質"

I --> J[誰も一方的に 戦略を変更する 動機がない]

I --> K[安定した状態 Stable State]

end

```

## 問題③　ナッシュ均衡の計算

### 問題文

以下の利得行列で表される2人ゲームを考える：

| プレイヤー1 \ プレイヤー2 | プレイヤー2: 左 | プレイヤー2: 右 |

|-----|----------------|----------------|

| プレイヤー1: 上 | 3, 2 | 1, 4 |

| プレイヤー1: 下 | 4, 1 | 2, 3 |

利得は（プレイヤー1の利得, プレイヤー2の利得）の順で表されている。

1. 純粋戦略ナッシュ均衡を求めよ

2. 混合戦略ナッシュ均衡を求めよ（プレイヤー1が「上」を選ぶ確率を $p$、プレイヤー2が「左」を選ぶ確率を $q$ とする）

### 解答

#### 1. 純粋戦略ナッシュ均衡の探索

各戦略の組み合わせについて、最適反応を確認する：

- **$(上, 左)$**: プレイヤー1は「下」に変更すると利得が3→4に増加するため、最適反応ではない

- **$(上, 右)$**: プレイヤー1は「下」に変更すると利得が1→2に増加するため、最適反応ではない

- **$(下, 左)$**: プレイヤー1は「上」に変更すると利得が4→3に減少するため、最適反応。プレイヤー2は「右」に変更すると利得が1→4に増加するため、最適反応ではない

- **$(下, 右)$**: プレイヤー1は「上」に変更すると利得が2→1に減少するため、最適反応。プレイヤー2は「左」に変更すると利得が3→2に減少するため、最適反応

したがって、**$(下, 右)$ が純粋戦略ナッシュ均衡**である。

#### 2. 混合戦略ナッシュ均衡の計算

プレイヤー1が「上」を選ぶ確率を $p$、プレイヤー2が「左」を選ぶ確率を $q$ とする。

**プレイヤー1の期待利得**：

\begin{aligned}

E[u_1] &= pq \cdot 3 + p(1-q) \cdot 1 + (1-p)q \cdot 4 + (1-p)(1-q) \cdot 2 \\

&= 3pq + p - pq + 4q - 4pq + 2 - 2p - 2q + 2pq \\

&= p + 2q - 2pq + 2

\end{aligned}

**プレイヤー2の期待利得**：

\begin{aligned}

E[u_2] &= pq \cdot 2 + p(1-q) \cdot 4 + (1-p)q \cdot 1 + (1-p)(1-q) \cdot 3 \\

&= 2pq + 4p - 4pq + q - pq + 3 - 3p - 3q + 3pq \\

&= p - 2q + 2pq + 3

\end{aligned}

**プレイヤー1の最適反応**：

プレイヤー1の期待利得を $p$ で微分：

\frac{\partial E[u_1]}{\partial p} = 1 - 2q

- $q < \frac{1}{2}$ のとき：$\frac{\partial E[u_1]}{\partial p} > 0$ より $p = 1$（常に「上」を選ぶ）

- $q > \frac{1}{2}$ のとき：$\frac{\partial E[u_1]}{\partial p} < 0$ より $p = 0$（常に「下」を選ぶ）

- $q = \frac{1}{2}$ のとき：任意の $p$ が最適

**プレイヤー2の最適反応**：

プレイヤー2の期待利得を $q$ で微分：

\frac{\partial E[u_2]}{\partial q} = -2 + 2p = 2(p - 1)

- $p < 1$ のとき：$\frac{\partial E[u_2]}{\partial q} < 0$ より $q = 0$（常に「右」を選ぶ）

- $p = 1$ のとき：任意の $q$ が最適

**混合戦略ナッシュ均衡**：

プレイヤー1が $p = 1$（常に「上」）を選ぶ場合、プレイヤー2は任意の $q$ が最適となるが、$p = 1$ のときプレイヤー2は「右」を選ぶ方が利得が高い（$1 < 4$）ため、$q = 0$ が最適反応となる。

しかし、$p = 1, q = 0$ のとき、プレイヤー1は「下」に変更することで利得を増やせる（$1 \to 2$）ため、これは均衡ではない。

実際、純粋戦略ナッシュ均衡 $(下, 右)$ が唯一のナッシュ均衡である。

### 答え

- **純粋戦略ナッシュ均衡**: $(下, 右)$、利得 $(2, 3)$

- **混合戦略ナッシュ均衡**: 存在しない（純粋戦略均衡のみ）

### 検証

$(下, 右)$ がナッシュ均衡であることを確認：

- プレイヤー1が「下」から「上」に変更すると、利得が $2 \to 1$ に減少

- プレイヤー2が「右」から「左」に変更すると、利得が $3 \to 2$ に減少

したがって、両プレイヤーとも戦略を変更する動機がなく、$(下, 右)$ はナッシュ均衡である。

### 純粋戦略 vs 混合戦略

- **純粋戦略**：各プレイヤーが特定の行動を確定的に選択する戦略。

- **混合戦略**：各プレイヤーが複数の行動を確率的に選択する戦略。混合戦略 $\sigma_i$ は、各純粋戦略 $s_i$ に確率 $p_i(s_i)$ を割り当てる関数である。

混合戦略の下での期待利得は：

$$E[u_i(\sigma_i, \sigma_{-i})] = \sum_{s_i \in S_i} \sum_{s_{-i} \in S_{-i}} p_i(s_i) \cdot p_{-i}(s_{-i}) \cdot u_i(s_i, s_{-i})$$

ナッシュの存在定理によれば、有限ゲーム（プレイヤー数と戦略数が有限）には、混合戦略を含めれば必ずナッシュ均衡が存在する。

### ナッシュの存在定理の証明概要

戦略空間 $\Sigma = \prod_{i=1}^n \Delta(S_i)$ は非空・コンパクト・凸であり、最適反応対応

BR_i(\sigma_{-i}) = \arg\max_{\sigma_i \in \Delta(S_i)} u_i(\sigma_i, \sigma_{-i})

は上半連続で非空値・凸値である。したがって、対応 $BR: \Sigma \rightrightarrows \Sigma$ はカクタニの不動点定理を満たし、不動点 $\sigma^* \in BR(\sigma^*)$ が存在する。これがナッシュ均衡である。

### カクタニの不動点定理

対応 $F: X \rightrightarrows X$ が以下の条件を満たすとき、不動点 $x^* \in F(x^*)$ が存在する：

1. $X$ は非空・コンパクト・凸なユークリッド空間の部分集合

2. $F$ は上半連続

3. $\forall x \in X$ について $F(x)$ は非空・凸・コンパクト

この定理は、ナッシュ均衡の存在だけでなく、一般均衡理論、不動点アルゴリズムの収束性解析にも用いられる。

### 相関均衡（Correlated Equilibrium）

アウマンの相関均衡では、外生的メディエータが確率分布 $\pi(s)$ に従って各プレイヤーへ秘密の推奨戦略を送る。プレイヤー $i$ が推奨 $s_i$ に従う方が任意の逸脱 $s_i'$ より有利である条件は

\sum_{s_{-i}} \pi(s_i, s_{-i}) \left[ u_i(s_i, s_{-i}) - u_i(s_i', s_{-i}) \right] \ge 0 \quad \forall i, \forall s_i, s_i'

で与えられ、線形計画問題として求解できる。相関均衡集合は凸であり、マルチエージェント学習（CE-Q学習）や交通均衡分析で重用される。

### ベイジアンゲームとベイジアン・ナッシュ均衡

不完全情報ゲームは、タイプ $\theta_i$ を持つプレイヤーがベイズ的に意思決定する枠組みで記述される。ベイジアン・ナッシュ均衡（BNE）は、タイプ依存戦略 $\sigma_i(\theta_i)$ が

\mathbb{E}_{\theta_{-i}}\!\left[ u_i\bigl(\sigma_i(\theta_i), \sigma_{-i}(\theta_{-i}); \theta_i, \theta_{-i} \bigr) \mid \theta_i \right]

\ge

\mathbb{E}_{\theta_{-i}}\!\left[ u_i\bigl(s_i', \sigma_{-i}(\theta_{-i}); \theta_i, \theta_{-i} \bigr) \mid \theta_i \right]

を全タイプ $\theta_i$・全代替戦略 $s_i'$ について満たすときに成立する。推定理論との結合により、逆向きシミュレーション（inverse problems）のゲーム的解釈が可能となる。

### サブゲーム完全均衡と逐次均衡

展開形ゲームでは、各サブゲームでのナッシュ均衡を要求するサブゲーム完全均衡（SPE）が基準となる。さらに信念体系 $\mu$ を導入し、情報集合ごとに逐次合理性を満たす $(\sigma, \mu)$ の組が逐次均衡（Sequential Equilibrium）である。震え手完全均衡（Trembling-hand Perfect Equilibrium）は、すべての戦略が微小確率で選択される摂動ゲームの極限として定義され、非現実的な弱支配均衡を排除する。

### メカニズムデザインとインセンティブ整合性

社会的選択関数 $f(\theta)$ を実現するメカニズム $(\mathcal{M}, g)$ では、自己申告 $\hat{\theta}_i$ に対して

u_i\bigl(g(\theta_i, \theta_{-i}), \theta_i\bigr) \ge u_i\bigl(g(\hat{\theta}_i, \theta_{-i}), \theta_i\bigr) \quad \forall \hat{\theta}_i

を満たす真実報告インセンティブ整合性（IC）と、参加を保証する個合理性（IR） $u_i(g(\theta),\theta_i) \ge \bar{u}_i$ が必要である。典型例の VCG メカニズムでは、支払い

p_i = - \sum_{j \ne i} v_j(x^*) + h_i(\theta_{-i})

を課すことで真実報告が弱優位戦略となり、効率的配分 $x^*$ が達成される。

### 微分ゲーム・平均場ゲーム

連続時間ダイナミクス

\dot{x}(t) = f\bigl(x(t), u_1(t), \dots, u_n(t)\bigr)

を対象とする微分ゲームでは、ハミルトン–ヤコビ–ベルマン–アイザック（HJBI）方程式

0 = \frac{\partial V}{\partial t} + \sup_{u_1} \inf_{u_2} \left\{ \nabla_x V^\top f(x,u_1,u_2) + \ell(x,u_1,u_2) \right\}

を解くことで値関数 $V$ が得られる。プレイヤー数が膨大な場合は平均場ゲーム（Mean Field Game, MFG）近似を用い、状態密度 $m(t,x)$ と価値関数 $\phi(t,x)$ が連立する

\begin{cases}

\displaystyle -\partial_t \phi - \nu \Delta \phi + H\bigl(x, \nabla \phi\bigr) = F(x, m) \\

\displaystyle \partial_t m - \nu \Delta m - \nabla \cdot \left( m \, \partial_p H\bigl(x, \nabla \phi\bigr) \right) = 0

\end{cases}

を数値的に解く。

### 学習ダイナミクスと平衡選択

実際の意思決定主体は学習を通じて戦略を更新する。代表例：

- **フィクティシャスプレイ**：過去の頻度分布を信じて最適反応

- **勾配ベース学習（Policy Gradient, Mirror Descent）**：パラメータ $\theta$ を $\theta^{t+1} = \theta^t + \eta \nabla_\theta u_i$ で更新

- **レプリケータ動学**：$\dot{p}_i = p_i (u_i - \bar{u})$

これらの動学が収束する平衡は進化的に安定な戦略（ESS）やリスク支配均衡になることが多い。

### 強化学習とゲーム理論の融合

マルチエージェント強化学習では、各エージェント $i$ がQ学習

Q_i^{t+1}(s_i, a_i) = (1-\alpha) Q_i^t(s_i, a_i) + \alpha \left[ r_i + \gamma \max_{a_i'} Q_i^t(s_i', a_i') \right]

を独立に実行する。ナッシュQ学習では、ナッシュ均衡を直接学習するため

Q_i^{t+1}(s, a) = (1-\alpha) Q_i^t(s, a) + \alpha \left[ r_i + \gamma \mathrm{NE}_i(Q_{-i}^t(s')) \right]

を更新する。ここで $\mathrm{NE}_i(Q_{-i})$ は他のエージェントのQ関数を所与としたナッシュ均衡におけるエージェント $i$ の期待利得である。

Actor-Critic法では、方策 $\pi_\theta$ と価値関数 $V_\phi$ を同時に学習し、方策勾配定理

\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \hat{A}_t \right]

に基づいて更新する。$\hat{A}_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$ はアドバンテージ推定値である。

### ナッシュ均衡の計算複雑性

有限ゲームのナッシュ均衡を求める問題は PPAD完全であることが知られている。Lemke-Howsonアルゴリズムは2人ゲームに対して多項式時間で動作するが、3人以上では指数時間を要する可能性がある。

Support Enumeration法は、混合戦略のサポート（正の確率を持つ純粋戦略の集合）を列挙し、各サポートについて線形計画問題を解く。最悪ケースでは $O(2^{|S|})$ の計算量となる。

近似ナッシュ均衡（$\varepsilon$-Nash equilibrium）は、各プレイヤーが $\varepsilon$ 以上の利得改善ができない戦略の組であり、多項式時間で求めることができる。$\varepsilon = O(1/\sqrt{n})$ の精度で、$n$ プレイヤーゲームに対して多項式時間アルゴリズムが存在する。

### Lemke-Howsonアルゴリズムの詳細

2人ゲーム $(A, B)$ に対して、Lemke-Howsonアルゴリズムは補完性問題（Complementarity Problem）として定式化する。プレイヤー1の混合戦略 $x \in \Delta_m$、プレイヤー2の混合戦略 $y \in \Delta_n$ について、スラック変数 $r, s$ を導入し、

\begin{cases}

Ay + r = v \mathbf{1}_m \\

B^\top x + s = u \mathbf{1}_n \\

x^\top r = 0, \quad y^\top s = 0 \\

x, y, r, s \ge 0

\end{cases}

を満たす解を求める。ここで $u, v$ は各プレイヤーの均衡利得である。アルゴリズムは、ラベル付けされた単体上をピボット操作で移動し、完全ラベル（すべてのラベルが使用される）を持つ頂点に到達するまで反復する。計算量は最悪ケースで指数時間だが、平均的には多項式時間で動作する。

### Support Enumeration法の計算量解析

$n$ プレイヤー、各 $m$ 戦略のゲームにおいて、プレイヤー $i$ のサポートサイズを $k_i$ とすると、可能なサポートの組み合わせは $\prod_{i=1}^n \binom{m}{k_i}$ 通りある。各サポートについて、線形計画問題

\begin{aligned}

\max_{x_i, v_i} \quad & v_i \\

\text{s.t.} \quad & \sum_{s_i \in \mathrm{supp}(x_i)} x_i(s_i) u_i(s_i, s_{-i}) \ge v_i \quad \forall s_{-i} \\

& \sum_{s_i} x_i(s_i) = 1, \quad x_i(s_i) \ge 0

\end{aligned}

を解く必要がある。最悪ケースでは全サポートを列挙するため $O(2^{nm})$ の計算量となるが、支配戦略の除去や対称性の利用により効率化できる。

---

【囚人のジレンマ】（ゲーム理論の有名な例）

囚人のジレンマは、典型的な非協力型ゲームであり、次のような状況で説明される。

- 2人の容疑者が逮捕され、別々に取り調べを受ける。

- それぞれが「協力（黙秘）」または「裏切り（自白）」のいずれかを選択できる。

- ここで、2人とも黙秘すれば軽い刑、片方だけ自白すれば自白した方だけが無罪、両方自白すれば両者中程度の刑というような利得（ペイオフ）が設定されている。

この状況は利得表（ペイオフマトリクス）によってまとめることができ、問題の本質は「自分に有利な選択（裏切り）をすると双方損をする場合がある」ことにある。

### 利得表（ペイオフマトリクス）

| 自分 \ 相手 | 相手:協力 | 相手:裏切り |

|-----|-----------|-------------|

| 自分:協力 | －1, －1 | －10, 0 |

| 自分:裏切り | 0, －10 | －5, －5 |

- 上記表は（自分, 相手）の順に利得（例：刑期など、値が小さいほど損）を示す。

- 両者が合理的に自分の利益を最大にしようとすると、最終的には両者とも「裏切り」を選び、結果的にお互いにとって本来よりも悪い結果（中程度の刑）になることが示される。

### 利得構造の可視化

**図10: 囚人のジレンマの利得構造**

```mermaid

graph TB

subgraph "利得の比較"

A[プレイヤー1: 協力] --> B{プレイヤー2の選択}

C[プレイヤー1: 裏切り] --> D{プレイヤー2の選択}

B -->|協力| E[利得: -1,-1 両者協力 R = -1]

B -->|裏切り| F[利得: -10,0 プレイヤー1が損 S = -10]

D -->|協力| G[利得: 0,-10 プレイヤー2が損 T = 0]

D -->|裏切り| H[利得: -5,-5 両者裏切り P = -5 ナッシュ均衡]

end

subgraph "利得の順序"

I[利得構造 T>R>P>S T=0 R=-1 P=-5 S=-10] --> J[裏切りの誘惑 T>R 相手が協力なら 裏切る方が得]

I --> K[協力の相互利益 R>P 両者協力の方が 両者裏切りより良い]

I --> L[支配戦略 T>R かつ P>S 常に裏切りが最適]

end

subgraph "ジレンマの本質"

M[個人合理性 Individual Rationality] --> N[両者とも裏切り D,D = -5,-5]

O[社会的効率性 Social Efficiency] --> P[両者協力 C,C = -1,-1]

N --> Q[ジレンマ 個人合理性と 社会的効率性の矛盾]

P --> Q

end

```

**図11: 囚人のジレンマの構造**

```mermaid

graph TB

A[囚人のジレンマ Prisoner's Dilemma] --> B[プレイヤー1の選択 Player 1 Choice]

A --> C[プレイヤー2の選択 Player 2 Choice]

B --> D[協力C Cooperate]

B --> E[裏切りD Defect]

C --> F[協力C Cooperate]

C --> G[裏切りD Defect]

D --> H[C,C -1,-1 両者協力]

D --> I[C,D -10,0 プレイヤー1が損]

E --> J[D,C 0,-10 プレイヤー2が損]

E --> K[D,D -5,-5 ナッシュ均衡]

F --> H

F --> J

G --> I

G --> K

L[利得構造 T>R>P>S T=0 R=-1 P=-5 S=-10] --> M[支配戦略 Dominant Strategy 両者とも裏切り]

M --> K

```

### 囚人のジレンマの数学的構造

囚人のジレンマは、以下の条件を満たす利得構造を持つ（標準的な記号：$R$ = 両者協力の報酬、$T$ = 裏切りの誘惑、$P$ = 両者裏切りの罰、$S$ = 協力者の損失）：

- **裏切りの誘惑**：$T > R$（相手が協力している場合、裏切る方が得）

- **協力の相互利益**：$R > P$（両者が協力する方が、両者が裏切るより良い）

- **裏切りの罰**：$P > S$（両者裏切りの方が、自分が協力して相手が裏切るより良い）

- **支配戦略**：相手の行動に関わらず、裏切り（$D$）が協力（$C$）より常に高い利得を与える（$T > R$ かつ $P > S$）

まとめると、$T > R > P > S$ の順序が成立する。また、繰り返しゲームで協力が維持されるためには、$2R > T + S$ の条件も必要となる。

上記の利得表では（値が小さいほど良い、例：刑期）：

- $(C, C) = (-1, -1)$：両者協力（$R = -1$）

- $(D, C) = (0, -10)$：自分が裏切り、相手が協力（$T = 0$、$S = -10$）

- $(C, D) = (-10, 0)$：自分が協力、相手が裏切り（$S = -10$、$T = 0$）

- $(D, D) = (-5, -5)$：両者裏切り（$P = -5$）

この利得構造では、$T = 0 > R = -1 > P = -5 > S = -10$ となり、囚人のジレンマの条件を満たしている。この構造では、$(D, D)$ が唯一のナッシュ均衡となるが、社会的には $(C, C)$ の方がパレート効率的（誰の利得も悪化させずに改善できない状態）である。この矛盾が「ジレンマ」の本質である。

### 繰り返し囚人のジレンマ（Iterated Prisoner's Dilemma）

1回限りのゲームでは裏切りが支配戦略となるが、同じプレイヤー同士が繰り返し対戦する場合（繰り返し囚人のジレンマ）、協力が維持される可能性がある。

重要な概念：

- **割引因子（discount factor）** $\delta$：将来の利得を現在価値に換算する際の割引率。$\delta$ が大きいほど（将来を重視するほど）、協力が維持されやすい。

- **フォーク定理（Folk Theorem）**：十分に高い割引因子の下では、様々な利得の組が均衡として実現可能である。

### フォーク定理の数学的定式化

無限繰り返しゲームにおいて、実行可能利得集合 $\mathcal{F}$ 内の任意の利得ベクトル $(v_1, \ldots, v_n)$ が、各プレイヤー $i$ の最小最大利得 $\underline{v}_i = \min_{\sigma_{-i}} \max_{\sigma_i} u_i(\sigma_i, \sigma_{-i})$ を上回る限り、十分に高い割引因子 $\delta$ の下でサブゲーム完全均衡として実現可能である。

### フォーク定理の概念図

**図12: フォーク定理の概念図**

```mermaid

graph TB

subgraph "実行可能利得集合"

A[実行可能利得集合F Feasible Payoff Set v₁,v₂,...,vₙ] --> B[最小最大利得 Minimax Payoff v_i = min max u_i]

end

subgraph "フォーク定理の条件"

B --> C[利得の条件 v_i > v_i for all i]

C --> D[割引因子の条件 δ sufficiently high δ ≥ δ_bar]

end

subgraph "均衡の実現"

D --> E[サブゲーム完全均衡 Subgame Perfect Equilibrium SPE]

E --> F[トリガー戦略 Trigger Strategy 協力からの逸脱で 永久に罰則]

end

subgraph "協力の維持条件"

F --> G[協力の利得 R + δR + δ²R + ... = R/1-δ]

F --> H[裏切りの利得 T + δv_i + δ²v_i + ... = T + δv_i/1-δ]

G --> I[協力維持条件 R/1-δ ≥ T + δv_i/1-δ δ ≥ T-R/T-v_i]

H --> I

end

subgraph "結果"

I --> J[十分に高いδで 様々な利得が 均衡として実現可能]

end

```

数学的には、$\forall v \in \mathcal{F}$ で $v_i > \underline{v}_i$ が成立するなら、$\exists \bar{\delta} < 1$ が存在し、$\forall \delta \in (\bar{\delta}, 1)$ に対して、利得 $v$ を実現するサブゲーム完全均衡が存在する。

トリガー戦略の下では、協力からの逸脱に対する罰則として、以降永久に最小最大利得 $\underline{v}_i$ を獲得する。協力が維持される条件は

R + \delta R + \delta^2 R + \cdots = \frac{R}{1-\delta} \ge T + \delta \underline{v}_i + \delta^2 \underline{v}_i + \cdots = T + \frac{\delta \underline{v}_i}{1-\delta}

すなわち $\delta \ge \frac{T-R}{T-\underline{v}_i}$ である。

### その他の代表的なゲーム

#### チキンゲーム（Chicken Game）

両者が対立する行動を取った場合、最悪の結果が生じるゲーム。利得構造は以下のようになる：

| 自分 \ 相手 | 相手:協力 | 相手:裏切り |

|-----|-----------|-------------|

| 自分:協力 | 3, 3 | 1, 4 |

| 自分:裏切り | 4, 1 | 0, 0 |

このゲームには2つの純粋戦略ナッシュ均衡 $(C, D)$ と $(D, C)$ が存在し、混合戦略均衡も存在する。

#### 協調ゲーム（Coordination Game）

両者が同じ行動を取ることが最適となるゲーム。例：

| 自分 \ 相手 | 相手:A | 相手:B |

|-----|--------|--------|

| 自分:A | 2, 2 | 0, 0 |

| 自分:B | 0, 0 | 1, 1 |

このゲームには2つのナッシュ均衡 $(A, A)$ と $(B, B)$ が存在するが、$(A, A)$ の方がパレート優越的である。

【現実での適用と限界】

このモデルを用いることで現実世界の意思決定状況も分析できるが、実際には「完璧な情報」や「相手の戦略が読める」ことは稀であり、「戦争の霧」と呼ばれるように最適な行動が常に明確とは限らず、不確実性や誤り、心理的要因が意思決定に影響を及ぼすことも多い。

したがって、ゲーム理論は最良の戦略を構築するための分析ツールとして有用だが、その限界や現実状況を考慮する必要がある。

### ゲーム理論の限界と拡張

#### 1. 合理性の仮定

標準的なゲーム理論は、プレイヤーが完全に合理的で、利得を最大化することを仮定する。しかし、現実では：

- **限定合理性（bounded rationality）**：情報処理能力の限界

- **行動経済学の知見**：損失回避、フレーミング効果、時間割引の非一貫性など

#### 2. 情報の非対称性

現実の多くの状況では、プレイヤー間で情報が非対称である：

- **逆選択（adverse selection）**：情報の非対称性による市場の失敗

- **モラルハザード（moral hazard）**：行動が観察できないことによる問題

#### 3. 進化ゲーム理論（Evolutionary Game Theory）

伝統的なゲーム理論が合理性を仮定するのに対し、進化ゲーム理論は：

- 戦略が自然選択や学習によって進化する過程を分析

- **進化的に安定な戦略（ESS: Evolutionarily Stable Strategy）**：集団の大部分がその戦略を採用している場合、他の戦略が侵入できない戦略

- レプリケータ動学（replicator dynamics）による戦略分布の時間変化を分析

#### 4. 実験ゲーム理論

実験室やフィールドでの実験により、理論的予測と実際の行動の乖離を検証：

- 実際の人間は理論的予測よりも協力的であることが多い

- 公平性や互恵性（reciprocity）への選好が観察される

戦略例

1. 全協力（Always Cooperate）

常に協力を選び続ける戦略。たとえ相手が裏切っても，一切裏切らず誠実に協力し続ける。

メリット：相手も協力者の場合に最も高い利得を得られる。

デメリット：裏切る相手に対して一方的に搾取されやすい。

2. 非全協力（Always Defect）

常に裏切りを選び続ける戦略。協力の意思は一切見せず，毎回裏切る。

メリット：純粋な協力者に対しては最大の利得を得られる。

デメリット：互いに裏切ると双方とも利得が小さくなる。

3. トリガー戦略（Grim Trigger）

最初は協力を選び，もし相手が一度でも裏切ったら，以降永久に裏切り続ける。

メリット：相手に「一度でも裏切ると二度と協力しない」という強い抑止力となる。

デメリット：一度だけの裏切りでも回復が難しくなるため，ミスに弱い。

4. TFT（Tit for Tat・しっぺ返し戦略）

第1回目は協力を行い，2回目以降は相手の前回の行動をコピーする（相手が協力すれば協力，裏切れば裏切る）。

メリット：協力的な相手とは協力を継続し，裏切る相手には対抗できる。誤解やミスがあっても比較的早く関係を修復できる。

デメリット：相手が常に裏切る場合にはずっと裏切りが続く場合がある。

これらの戦略は，繰り返し囚人のジレンマなどのゲームにおいてどのように行動するかの例である。それぞれ異なる特性を持ち，状況によって有利・不利が変化する。

**図13: 繰り返し囚人のジレンマ戦略**

```mermaid

graph TB

A[繰り返し囚人のジレンマ戦略 Iterated Prisoner's Dilemma Strategies] --> B[無条件戦略 Unconditional Strategies]

A --> C[条件付き戦略 Conditional Strategies]

B --> D[全協力 Always Cooperate 常に協力]

B --> E[全裏切り Always Defect 常に裏切り]

C --> F[TFT Tit for Tat しっぺ返し]

C --> G[トリガー戦略 Grim Trigger 一度裏切りで永久裏切り]

C --> H[Generous TFT 寛容なしっぺ返し]

C --> I[Pavlov Win-Stay Lose-Shift]

D --> J[メリット 協力者と最高利得]

D --> K[デメリット 裏切り者に搾取]

E --> L[メリット 協力者から最大利得]

E --> M[デメリット 互いに裏切りで低利得]

F --> N[協力的 報復的 寛容的 明確]

F --> O[アクセルロッド トーナメント優勝]

```

### 戦略の詳細分析

#### 戦略の分類

繰り返し囚人のジレンマにおける戦略は、以下のように分類できる：

1. **無条件戦略**：相手の行動に依存しない

- 全協力（Always Cooperate）

- 全裏切り（Always Defect）

2. **条件付き戦略**：相手の過去の行動に依存

- TFT（Tit for Tat）

- トリガー戦略（Grim Trigger）

- TFT with Forgiveness：一定確率で裏切りを許す

- Pavlov（Win-Stay, Lose-Shift）：前回の利得に基づいて戦略を変更

#### アクセルロッドのトーナメント

ロバート・アクセルロッド（Robert Axelrod）が1980年代に実施したコンピュータトーナメントでは：

- 様々な戦略を対戦させ、総利得を競った

- **TFTが最も高い総利得を獲得**した

- TFTの特徴：

- **協力的（nice）**：最初に裏切らない

- **報復的（retaliatory）**：裏切りに対して即座に報復

- **寛容的（forgiving）**：相手が協力に戻れば即座に協力に戻る

- **明確（clear）**：戦略が単純で予測可能

#### 進化的に安定な戦略としてのTFT

進化ゲーム理論の観点から：

- 純粋な協力者集団では、裏切り者が侵入して繁栄できる

- 裏切り者集団では、TFTは侵入できない（裏切り者同士の利得と同じ）

- **TFT同士の集団は、裏切り者の侵入に対して安定**である

ただし、TFTは「誤解」に弱い：ノイズ（誤った行動）がある環境では、TFT同士が誤解の連鎖に陥る可能性がある。この問題を解決するため、**Generous TFT**（一定確率で裏切りを許す）や**Contrite TFT**（自分の誤解を認識して修正する）などの変種が提案されている。

### 多プレイヤーゲームへの拡張

現実の多くの状況では、2人だけでなく複数のプレイヤーが関与する：

- **公共財ゲーム（Public Goods Game）**：複数人が公共財への貢献を決定

- **集合行為のジレンマ**：個人の合理的行動が集団の非効率を生む

- **ネットワーク効果**：プレイヤー間の関係構造が戦略選択に影響

これらの拡張により、より現実的な意思決定状況を分析できる。

### 確率的ゲームとマルコフゲーム

確率的ゲーム（Stochastic Game）は、状態遷移が確率的なマルコフ決定過程を多エージェントに拡張したものである。状態 $s \in \mathcal{S}$、各プレイヤー $i$ の行動 $a_i \in \mathcal{A}_i$、遷移確率 $P(s'|s, a_1, \ldots, a_n)$、利得 $u_i(s, a_1, \ldots, a_n)$ を考える。

マルコフ完全均衡（Markov Perfect Equilibrium, MPE）は、各状態 $s$ においてナッシュ均衡となる戦略の組 $\sigma^*_i(s)$ である。ベルマン方程式は

V_i^*(s) = \max_{a_i} \left\{ u_i(s, a_i, \sigma_{-i}^*(s)) + \delta \sum_{s'} P(s'|s, a_i, \sigma_{-i}^*(s)) V_i^*(s') \right\}

となり、不動点反復（value iteration）や方策反復（policy iteration）で求解される。

### ネットワークゲームとグラフ構造

プレイヤー間の相互作用がネットワーク構造 $G = (V, E)$ で記述される場合、各プレイヤー $i$ の利得は隣接プレイヤー $\mathcal{N}_i = \{j: (i,j) \in E\}$ の行動に依存する：

u_i(a_i, a_{\mathcal{N}_i}) = f_i(a_i) + \sum_{j \in \mathcal{N}_i} g_{ij}(a_i, a_j)

線形影響モデルでは $g_{ij}(a_i, a_j) = \beta_{ij} a_i a_j$ とし、最適反応は

a_i^* = \arg\max_{a_i} \left\{ f_i(a_i) + a_i \sum_{j \in \mathcal{N}_i} \beta_{ij} a_j^* \right\}

となる。グラフラプラシアン $L = D - A$（$D$ は次数行列、$A$ は隣接行列）を用いて、均衡の存在と一意性がグラフのスペクトル特性から導出される。

### 情報設計とベイジアン説得

情報設計（Information Design）では、メディエータが各プレイヤーに異なる信号を送ることで、均衡結果を操作する。信号構造 $\pi: \Theta \to \Delta(\mathcal{S}_1 \times \cdots \times \mathcal{S}_n)$ の下で、ベイジアン・ナッシュ均衡における期待利得を最大化する問題

\max_{\pi} \sum_{i} \lambda_i \mathbb{E}_{\theta, s} \left[ u_i(\sigma^*(\pi(s)), \theta) \right]

を考える。ここで $\sigma^*$ は信号 $s$ に依存するベイジアン・ナッシュ均衡である。

ベイジアン説得（Bayesian Persuasion）では、送り手が受け手の事前信念を操作し、受け手の意思決定を誘導する。最適信号構造は、受け手の事後信念が閾値 $\bar{\theta}$ を超える確率を最大化するように設計される。

### オークション理論

#### Vickrey-Clarke-Groves（VCG）メカニズム

$n$ 人の入札者、$m$ 個のアイテムの組み合わせオークションにおいて、VCGメカニズムは以下のように定義される：

1. **配分ルール**：社会的余剰 $\sum_{i=1}^n v_i(x_i)$ を最大化する配分 $x^*$ を選択

2. **支払いルール**：プレイヤー $i$ の支払いは

p_i = \max_{x_{-i}} \sum_{j \ne i} v_j(x_j) - \sum_{j \ne i} v_j(x_{-i}^*)

ここで $x_{-i}^*$ はプレイヤー $i$ を除いた最適配分である。VCGメカニズムは真実報告が弱優位戦略となり、効率的配分を実現する。

#### 第二価格封印オークション（Vickrey Auction）

単一アイテムの場合、VCGメカニズムは第二価格封印オークションに簡略化される。最高入札者が落札し、支払額は第二高入札額となる。このメカニズムでは、真実評価額を入札することが弱優位戦略である。

#### Combinatorial AuctionとWinner Determination Problem

組み合わせオークションでは、入札者 $i$ がバンドル $S \subseteq \{1,\ldots,m\}$ に対して評価額 $v_i(S)$ を提示する。Winner Determination Problem（WDP）は

\max \sum_{i=1}^n \sum_{S \subseteq [m]} v_i(S) x_{i,S} \quad \text{s.t.} \quad \sum_{i,S: j \in S} x_{i,S} \le 1 \quad \forall j, \quad \sum_S x_{i,S} \le 1 \quad \forall i

と定式化される。これは集合被覆問題の一般化であり、NP困難である。分枝限定法や列生成法で求解される。

### 契約理論とPrincipal-Agent問題

#### Moral Hazardモデル

エージェントが観測不可能な努力 $e \in \mathcal{E}$ を選択し、観測可能な結果 $x \sim F(x|e)$ が得られる。プリンシパルは契約 $w(x)$ を設計し、期待利得

\max_{w(\cdot), e} \int [x - w(x)] f(x|e) \, dx \quad \text{s.t.} \quad \int u(w(x)) f(x|e) \, dx - c(e) \ge \bar{u}

を最大化する。ここで $u$ はエージェントの効用関数、$c$ は努力コスト、$\bar{u}$ は留保効用である。一階条件法（First-Order Approach）では、エージェントの最適化問題の一階条件

\int u(w(x)) f_e(x|e) \, dx = c'(e)

を制約として用いる。Mirrlees条件（単調尤度比特性：$\frac{f_e(x|e)}{f(x|e)}$ が $x$ について単調増加）の下で、一階条件法は正当化される。

#### Adverse Selectionモデル

エージェントのタイプ $\theta \in \Theta$ が非対称情報として存在する場合、メニュー $\{(q(\theta), t(\theta))\}_{\theta \in \Theta}$ を設計する。インセンティブ整合性（IC）制約

u(q(\theta), \theta) - t(\theta) \ge u(q(\hat{\theta}), \theta) - t(\hat{\theta}) \quad \forall \theta, \hat{\theta}

と個合理性（IR）制約

u(q(\theta), \theta) - t(\theta) \ge 0 \quad \forall \theta

の下で、プリンシパルの期待利得を最大化する。単調性条件 $q'(\theta) \ge 0$ が最適契約の特徴となる。

### 計算ゲーム理論：Price of AnarchyとPrice of Stability

非協力ゲームにおける社会的コスト（全プレイヤーのコストの和）を $SC(\sigma) = \sum_{i=1}^n c_i(\sigma)$ とする。最適解（社会的に最適な戦略の組）のコストを $SC^*$ とすると、

- **Price of Anarchy（PoA）**：$\mathrm{PoA} = \frac{\max_{\sigma \in \mathrm{NE}} SC(\sigma)}{SC^*}$

- **Price of Stability（PoS）**：$\mathrm{PoS} = \frac{\min_{\sigma \in \mathrm{NE}} SC(\sigma)}{SC^*}$

が定義される。原子型ネットワーク混雑ゲームでは、線形コスト関数の下で $\mathrm{PoA} \le \frac{5}{2}$ が成立する（Roughgarden-Tardosの定理）。非原子型（無限小プレイヤー）では、$\mathrm{PoA} = \frac{4}{3}$ となる。

### 確率微分方程式と確率制御

確率過程 $X_t$ が確率微分方程式（SDE）

dX_t = b(X_t, u_t) \, dt + \sigma(X_t, u_t) \, dW_t

に従う場合、制御問題の値関数はHJB方程式

0 = \frac{\partial V}{\partial t} + \min_{u \in \mathcal{U}} \left\{ \mathcal{L}^u V + \ell(x, u) \right\}

を満たす。ここで $\mathcal{L}^u$ は生成作用素

\mathcal{L}^u = \sum_{i} b_i(x, u) \frac{\partial}{\partial x_i} + \frac{1}{2} \sum_{i,j} (\sigma\sigma^\top)_{ij}(x, u) \frac{\partial^2}{\partial x_i \partial x_j}

である。解の存在と一意性は、係数 $b, \sigma$ のリプシッツ条件と成長条件の下で保証される。

### 数値解法：有限要素法と変分法

HJB方程式の数値解法として、有限要素法では空間をメッシュに分割し、ガラーキン法で離散化する。変分法では、HJB方程式を変分不等式

\max_{u} \left\{ \mathcal{L}^u V + \ell(x, u) \right\} = 0

として定式化し、ニュートン法や半滑らかニュートン法で求解する。政策反復法では、方策評価ステップと方策改善ステップを交互に実行し、収束まで反復する。

### モンテカルロ法と確率的数値解法

HJB方程式の高次元問題では、モンテカルロ法が有効である。確率表現（Feynman-Kac公式）により、値関数は

V(x,t) = \mathbb{E}\left[ \int_t^T e^{-\int_t^s r(X_\tau, u_\tau) d\tau} \ell(X_s, u_s) ds + e^{-\int_t^T r(X_\tau, u_\tau) d\tau} g(X_T) \mid X_t = x \right]

と表現される。ここで $X_t$ は制御下の確率過程、$r$ は割引率である。深層学習との融合では、ニューラルネットワーク $V_\theta(x,t)$ をパラメータ化し、損失関数

L(\theta) = \mathbb{E}\left[ \left| \frac{\partial V_\theta}{\partial t} + \mathcal{H}(x, \nabla_x V_\theta, \nabla_x^2 V_\theta) \right|^2 \right]

を最小化する。ここで $\mathcal{H}$ はハミルトニアンである。Deep BSDE法では、確率過程の終端条件を満たすように逆方向SDEを解く。

### 大偏差原理とリスク評価

大偏差原理（Large Deviation Principle, LDP）は、確率測度の尾部確率の漸近挙動を記述する。確率過程 $X_t$ がレート関数 $I(x)$ でLDPを満たすとは、

\lim_{\varepsilon \to 0} \varepsilon \log \mathbb{P}(X_t \in A) = -\inf_{x \in A} I(x)

が成立することである。Varadhanの定理により、期待値の対数は

\lim_{t \to \infty} \frac{1}{t} \log \mathbb{E}\left[e^{t F(X_t)}\right] = \sup_{x} \{F(x) - I(x)\}

となる。これを用いて、尾部リスクの漸近評価が可能となる。

### 集中不等式と確率的バウンド

確率変数 $X$ の期待値からの偏差を評価する集中不等式として、Azuma-Hoeffding不等式

\mathbb{P}(|X - \mathbb{E}[X]| \ge t) \le 2 \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right)

がある。マルチンゲール差分列 $d_i$ が $|d_i| \le c_i$ を満たす場合に適用される。McDiarmidの有界差分不等式は、関数 $f(X_1, \ldots, X_n)$ が有界差分条件

|f(x_1, \ldots, x_i, \ldots, x_n) - f(x_1, \ldots, x_i', \ldots, x_n)| \le c_i

を満たすとき、

\mathbb{P}(|f - \mathbb{E}[f]| \ge t) \le 2 \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right)

が成立する。これらは、学習アルゴリズムの一般化誤差解析に用いられる。

### 双対理論とラグランジュ双対

凸最適化問題

\min_{x \in \mathcal{X}} f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \quad h_j(x) = 0

のラグランジュ双対は

\max_{\lambda \ge 0, \nu} \inf_{x \in \mathcal{X}} L(x, \lambda, \nu) = \max_{\lambda \ge 0, \nu} d(\lambda, \nu)

で与えられる。ここで $L(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$ はラグランジュ関数である。強双対性が成立する条件（Slater条件：$\exists x \in \mathrm{relint}(\mathcal{X})$ で $g_i(x) < 0, h_j(x) = 0$）の下で、双対ギャップはゼロとなる。

### 内点法と原始双対アルゴリズム

内点法では、バリア関数 $\phi(x) = -\sum_i \log(-g_i(x))$ を導入し、パラメータ化問題

\min_{x} f(x) + \mu \phi(x)

を解く。$\mu \to 0$ の極限で最適解に収束する。原始双対内点法では、KKT条件

\begin{cases}

\nabla f(x) + \sum_i \lambda_i \nabla g_i(x) + \sum_j \nu_j \nabla h_j(x) = 0 \\

g_i(x) \le 0, \quad \lambda_i \ge 0, \quad \lambda_i g_i(x) = 0 \\

h_j(x) = 0

\end{cases}

を緩和した系をニュートン法で解く。計算量は $O(\sqrt{n} \log(1/\varepsilon))$ 反復で $\varepsilon$ 精度の解が得られる（$n$ は変数の数）。

### 確率的勾配降下法と収束性解析

確率的勾配降下法（SGD）では、勾配の不偏推定 $\tilde{\nabla} f(x)$ を用いて

x^{t+1} = x^t - \eta_t \tilde{\nabla} f(x^t)

と更新する。リプシッツ連続性（$\|\nabla f(x) - \nabla f(y)\| \le L\|x-y\|$）と強凸性（$f(y) \ge f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$）の下で、ステップサイズ $\eta_t = \frac{2}{\mu t + L}$ により

\mathbb{E}[f(x^t) - f^*] \le \frac{2L\|x^0 - x^*\|^2}{\mu t}

の収束率が達成される。Adam法では、モーメント推定

m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t, \quad v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2

を用いて適応的ステップサイズ $\eta_t / (\sqrt{v_t} + \epsilon)$ を設定する。

### ベイズ最適化とガウス過程

未知関数 $f: \mathcal{X} \to \mathbb{R}$ を最小化するため、ガウス過程事前分布 $f \sim \mathcal{GP}(m(x), k(x,x'))$ を仮定する。観測データ $\mathcal{D}_t = \{(x_i, y_i)\}_{i=1}^t$ の下での事後分布は

f(x) \mid \mathcal{D}_t \sim \mathcal{N}(\mu_t(x), \sigma_t^2(x))

となる。ここで

\mu_t(x) = k_t(x)^\top (K_t + \sigma^2 I)^{-1} y_t, \quad \sigma_t^2(x) = k(x,x) - k_t(x)^\top (K_t + \sigma^2 I)^{-1} k_t(x)

である。獲得関数（Acquisition Function）$a_t(x) = \mu_t(x) - \beta_t \sigma_t(x)$（Upper Confidence Bound）を最大化する点を次に評価する。$\beta_t$ は探索と活用のバランスを制御する。

### メタ学習とFew-Shot Learning

メタ学習では、複数のタスクから学習する方法を学習する。Model-Agnostic Meta-Learning（MAML）では、初期パラメータ $\theta$ を更新規則

\theta \leftarrow \theta - \alpha \nabla_\theta \sum_{\mathcal{T}_i \sim p(\mathcal{T})} \mathcal{L}_{\mathcal{T}_i}(f_{\theta - \alpha \nabla_\theta \mathcal{L}_{\mathcal{T}_i}(f_\theta)})

で最適化する。ここで $\mathcal{T}_i$ はタスク、$\mathcal{L}$ は損失関数である。Reptile法では、より単純な更新

\theta \leftarrow \theta + \epsilon \sum_i (\phi_i - \theta)

を用いる。ここで $\phi_i$ はタスク $i$ での数ステップの勾配降下後のパラメータである。

### フェデレーテッド学習と分散最適化

$N$ 個のクライアントがローカルデータ $\mathcal{D}_i$ を持つ場合、フェデレーテッド平均（FedAvg）は

\theta^{t+1} = \sum_{i=1}^N \frac{|\mathcal{D}_i|}{|\mathcal{D}|} \theta_i^{t+1}

で更新する。ここで $\theta_i^{t+1}$ はクライアント $i$ でのローカル更新である。非IIDデータの下では、クライアントドリフトが問題となるため、FedProxでは正則化項

\min_{\theta_i} \mathcal{L}_i(\theta_i) + \frac{\mu}{2} \|\theta_i - \theta^t\|^2

を追加する。SCAFFOLD法では、クライアント間の勾配の不一致を補正する制御変数を導入する。

### 敵対的強化学習とロバスト性

敵対的環境では、報酬関数 $r(s,a)$ が不確実性集合 $\mathcal{R}$ 内にあると仮定する。ロバストMDPでは、最悪ケースの報酬を最大化する：

V^*(s) = \max_{\pi} \min_{r \in \mathcal{R}} \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) \mid s_0 = s\right]

敵対的強化学習では、環境が敵対的に報酬を操作する場合を扱う。Minimax Q学習では、Q関数を

Q^{t+1}(s,a) = (1-\alpha) Q^t(s,a) + \alpha \left[r(s,a) + \gamma \min_{r' \in \mathcal{R}} \max_{a'} Q^t(s', a')\right]

で更新する。これにより、最悪ケースの環境下でも性能を保証できる。

### 確率測度の弱収束とProkhorovの定理

確率測度列 $\{\mu_n\}$ が $\mu$ に弱収束するとは、任意の有界連続関数 $f$ について

\lim_{n \to \infty} \int f \, d\mu_n = \int f \, d\mu

が成立することである。Prokhorovの定理により、確率測度族 $\mathcal{M}$ が相対コンパクトであることと、タイト（tight）であることは同値である。すなわち、$\forall \varepsilon > 0$ に対してコンパクト集合 $K$ が存在し、$\mu(K^c) < \varepsilon$（$\forall \mu \in \mathcal{M}$）が成立する。

### マルコフ連鎖モンテカルロ（MCMC）法

目標分布 $\pi(x)$ からサンプリングするため、遷移核 $P(x, dy)$ が詳細釣り合い条件

\pi(x) P(x, dy) = \pi(y) P(y, dx)

を満たすマルコフ連鎖を構築する。Metropolis-Hastings法では、提案分布 $q(y|x)$ から候補 $y$ を生成し、受容確率

\alpha(x, y) = \min\left\{1, \frac{\pi(y) q(x|y)}{\pi(x) q(y|x)}\right\}

で受容する。Gibbsサンプリングでは、条件付き分布 $\pi(x_i | x_{-i})$ から順次サンプリングする。収束性は、連鎖が既約（irreducible）、非周期的（aperiodic）、再帰的（recurrent）であることで保証される。

### 変分推論とELBO

事後分布 $p(\theta | x)$ の近似分布 $q(\theta)$ を、KLダイバージェンス $D_{\mathrm{KL}}(q \| p)$ を最小化することで求める。Evidence Lower BOund（ELBO）は

\log p(x) \ge \mathbb{E}_{q(\theta)}[\log p(x|\theta)] - D_{\mathrm{KL}}(q(\theta) \| p(\theta)) = \mathrm{ELBO}(q)

で与えられ、$D_{\mathrm{KL}}(q \| p) = \log p(x) - \mathrm{ELBO}(q)$ の関係がある。平均場近似では $q(\theta) = \prod_i q_i(\theta_i)$ と仮定し、座標降下法で各 $q_i$ を更新する。

### Wasserstein距離と最適輸送

確率測度 $\mu, \nu$ の間のWasserstein-$p$距離は

W_p(\mu, \nu) = \left(\inf_{\gamma \in \Gamma(\mu, \nu)} \int d(x,y)^p \, d\gamma(x,y)\right)^{1/p}

で定義される。ここで $\Gamma(\mu, \nu)$ は周辺分布が $\mu, \nu$ である結合分布の集合である。Kantorovich双対性により、

W_1(\mu, \nu) = \sup_{\|f\|_{\mathrm{Lip}} \le 1} \left\{\int f \, d\mu - \int f \, d\nu\right\}

が成立する。Wasserstein GANでは、この距離を目的関数として用いる。

### スパース最適化とLasso正則化

Lasso回帰では、$L_1$正則化項を追加した

\min_{\beta} \frac{1}{2}\|y - X\beta\|^2 + \lambda \|\beta\|_1

を解く。$L_1$正則化はスパース解（多くの成分がゼロ）を誘導する。座標降下法では、各成分 $\beta_j$ を逐次更新する：

\beta_j \leftarrow S_\lambda\left(\frac{1}{n}\sum_{i=1}^n x_{ij}(y_i - \sum_{k \ne j} x_{ik}\beta_k)\right)

ここで $S_\lambda(t) = \mathrm{sign}(t)(|t| - \lambda)_+$ はソフト閾値関数である。Group Lassoでは、グループ単位でスパース性を誘導する。

### 凸共役とFenchel双対

関数 $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ の凸共役は

f^*(y) = \sup_{x \in \mathbb{R}^n} \{x^\top y - f(x)\}

で定義される。Fenchel双対定理により、凸最適化問題

\min_{x} f(x) + g(Ax)

の双対は

\max_{y} -f^*(A^\top y) - g^*(-y)

となる。Fenchel-Young不等式 $f(x) + f^*(y) \ge x^\top y$ が成立し、等号は $y \in \partial f(x)$ のときである。

### 近接勾配法とFISTA

非滑らかな目的関数 $f(x) + g(x)$（$f$ は滑らか、$g$ は非滑らか）を最小化するため、近接勾配法は

x^{t+1} = \mathrm{prox}_{\eta g}(x^t - \eta \nabla f(x^t))

で更新する。ここで近接作用素は

\mathrm{prox}_{\eta g}(z) = \arg\min_x \left\{\frac{1}{2\eta}\|x - z\|^2 + g(x)\right\}

である。Fast Iterative Shrinkage-Thresholding Algorithm（FISTA）では、モーメンタム項を追加し、

y^{t+1} = x^{t+1} + \frac{t-1}{t+2}(x^{t+1} - x^t)

で加速する。収束率は $O(1/t^2)$ となる。

### リーマン最適化と多様体上の最適化

多様体 $\mathcal{M}$ 上の最適化問題では、接空間 $T_x\mathcal{M}$ 上で勾配を計算し、リトラクション（retraction）$R_x: T_x\mathcal{M} \to \mathcal{M}$ で多様体上に戻す。リーマン勾配は

\mathrm{grad} f(x) = \mathrm{Proj}_{T_x\mathcal{M}}(\nabla f(x))

で与えられる。リーマン共役勾配法では、接空間上の共役勾配方向を計算し、Armijo条件を満たすステップサイズを選択する。

### 分散ロバスト最適化とWasserstein距離

分布ロバスト最適化で、Wasserstein距離による不確実性集合

\mathcal{P} = \{P: W_p(P, P_0) \le \rho\}

を用いると、双対問題は有限次元の凸最適化問題に帰着される。Kantorovich-Rubinstein双対性により、

\sup_{P: W_1(P, P_0) \le \rho} \mathbb{E}_P[f(X)] = \inf_{\lambda \ge 0} \left\{\lambda \rho + \mathbb{E}_{P_0}[\sup_x \{f(x) - \lambda d(x, X)\}]\right\}

が成立する。

### 部分観測マルコフ決定過程（POMDP）

状態 $s_t$ が直接観測できず、観測 $o_t \sim O(o_t|s_t)$ のみが得られる場合、信念状態（belief state）$b_t(s) = \mathbb{P}(s_t = s | o_{1:t}, a_{1:t-1})$ を管理する。信念更新は

b_{t+1}(s') = \frac{O(o_{t+1}|s') \sum_s P(s'|s, a_t) b_t(s)}{\sum_{s'} O(o_{t+1}|s') \sum_s P(s'|s, a_t) b_t(s)}

で行われる。値関数は信念空間上で定義され、Pineauらの点ベース値反復法で近似される。

### 階層的強化学習とオプション

オプション $\omega = (I_\omega, \pi_\omega, \beta_\omega)$ は、開始集合 $I_\omega$、方策 $\pi_\omega$、終了確率 $\beta_\omega$ で定義される。オプション価値関数は

Q_\Omega(s, \omega) = \mathbb{E}\left[\sum_{t=0}^\tau \gamma^t r_{t+1} + \gamma^\tau \max_{\omega'} Q_\Omega(s_\tau, \omega') \mid s_0 = s, \omega_0 = \omega\right]

で与えられる。ここで $\tau$ はオプションの終了時刻である。階層的強化学習では、高レベル方策がオプションを選択し、低レベル方策がプリミティブ行動を選択する。

### 逆強化学習と模倣学習

専門家の軌跡 $\tau_E = \{(s_t, a_t)\}_{t=1}^T$ から報酬関数 $r(s,a)$ を推定する逆強化学習では、最大エントロピー原理に基づき

P(\tau | r) = \frac{1}{Z(r)} \exp\left(\sum_{t} r(s_t, a_t)\right)

を仮定する。最尤推定により、報酬関数は

r^* = \arg\max_r \sum_{\tau \in \mathcal{D}} \log P(\tau | r) - \lambda \|r\|^2

で推定される。模倣学習では、方策 $\pi_\theta$ を専門家の行動分布に近づけるため、KLダイバージェンス

\min_\theta D_{\mathrm{KL}}(\pi_E \| \pi_\theta)

を最小化する。Generative Adversarial Imitation Learning（GAIL）では、判別器と生成器の敵対的訓練により模倣を行う。

## まとめ

本章では、意思決定手法の理論的基礎から実践的応用まで、幅広いトピックを扱った。主な内容は以下の通りである：

### 主要な理論的枠組み

1. **期待効用理論**：不確実性下での意思決定の基本理論

- von Neumann-Morgensternの期待効用定理

- 効用関数の性質（リスク態度）

- 実践例：新聞売り子問題（不確実な需要に対する最適発注量決定問題）

2. **ベイズ意思決定理論**：事前情報を活用した意思決定

- ベイズ更新と事後分布

- ベイズリスク最小化

3. **ゲーム理論**：複数主体間の戦略的意思決定

- ナッシュ均衡とその存在定理

- 囚人のジレンマと繰り返しゲーム

- メカニズムデザイン

### 意思決定の分類

| 分類基準 | 種類 | 主要な手法 |

|---------|------|-----------|

| 結果の確実性 | 決定論的/リスク下/不確実性下 | 最適化/期待効用/ベイズ決定 |

| 評価基準の数 | 単一目的/多目的 | 最適化/パレート最適化 |

| 選択肢の属性 | 単属性/多属性 | MAUT, AHP, TOPSIS |

### 実践的応用

- **在庫管理**：期待効用最大化の具体例（新聞売り子問題など）

- **オークション理論**：VCGメカニズム、第二価格封印オークション

- **契約理論**：Moral Hazard、Adverse Selection

- **強化学習**：MDP、Q学習、Actor-Critic法

### 計算的手法

- **ナッシュ均衡の計算**：Lemke-Howsonアルゴリズム、Support Enumeration法

- **確率制御**：HJB方程式、確率微分方程式

- **数値解法**：有限要素法、モンテカルロ法、深層学習との融合

### 関連トピック

- **在庫管理**：意思決定理論の実践的応用例（新聞売り子問題、EOQモデルなど）

- **最適化理論**：制約付き最適化、ロバスト最適化、分布ロバスト最適化

- **機械学習**：ベイズ最適化、メタ学習、フェデレーテッド学習

### 今後

意思決定理論を深めるためには、以下のトピックも重要である：

- 行動経済学とプロスペクト理論の詳細

- 実験ゲーム理論と実証研究

- 多エージェントシステムと協調学習

- 情報設計とベイジアン説得の応用

意思決定理論の実践的応用例としては、在庫管理（新聞売り子問題、EOQモデル）、オークション理論、契約理論、強化学習などが挙げられる。

Collection

note

Citation

unjuno, “シミレーション工学８,” unjuno'sResearchLibrary, accessed October 8, 2026, https://archive.unjuno.org/items/show/127.

Output Formats

Facebook Twitter Tumblr Email

シミレーション工学８

Dublin Core

Title

Creator

Date Created

Rights

note Item Type Metadata

note

Collection

Citation

Output Formats

コメント