ロジットモデルと最適化

May 29 (Thu), 2025

ロジット (logit) モデルと摂動付き最適化 (perturbed optimization) との交通分野ではよく知られた関係について簡潔にまとめる．内容は別のメモとほぼ同一である．より包括的・一般的なサーベイは福田・城間 (2023) を参照のこと．

ランダム効用モデルとロジット

意思決定者 (decision maker, DM) が，複数の選択肢からどれか一つを選ぶ状況を考える．選択肢の有限集合を $A$ とする．各選択肢 $a \in A$ を選んだときの効用 $V_a$ は不確実であり，次のような確率変数として表現されるとする：

\[V_a = v_a + \epsilon_a,\]

ここで $v_a$ は既知の確定的な利得，$\epsilon_a$ はランダムな利得成分である． $\epsilon_a$ は選択肢間で独立同分布 (i.i.d.) であると仮定する．

さらに，DM は確率的な意思決定を行う（混合戦略）とし，各選択肢 $a$ をその選択肢が利得最大となる（最適応答である）確率で選ぶものとする．すなわち，

\[\begin{aligned} p_a & = \Pr[V_a \ge V_b \quad \forall b \in A] \\ & = \Pr[v_a + \epsilon_a \ge v_b + \epsilon_b \quad \forall b \in A]. \end{aligned}\]

このような枠組みは，加法的なランダム効用モデル (additive random utility models, ARUM) と呼ばれる．

応用の立場からは，$\{\epsilon_a\}$ は例えば (1) 分析者が観測不能な利得成分，(2) 説明変数・選択の観測の誤差，(3) 分析者が設定した確定効用 $v$ のモデル化誤差，(4) その他の個別的異質性によって生ずると解釈される．個人の効用が実際にランダムに揺らぐというよりは，あくまで分析者の視点からはそうした不完全性により確率的に選択されているかのようにしか捉えられない状況であると解釈される．

さて，全ての $\epsilon_a$ が $E \subseteq \mathbb{R}$ に値をとる微分可能な同一の累積分布関数 (c.d.f.) $F$ に独立に従っているとき，定義より選択確率 $p_a$ は以下のように表される：

\[\begin{aligned} p_a = \int_{\epsilon_a \in E} F'(\epsilon_a) \prod_{b \ne a} F(v_a - v_b + \epsilon_a)\ \mathrm{d}\epsilon_a. \end{aligned}\]

各 $\epsilon_a$ がスケールパラメータ $\eta > 0$，ロケーションパラメータ $\mu = - \eta\gamma$ の ガンベル (Gumbel) 分布に従うと仮定する．ただし $\gamma \approx 0.5772$ はオイラー定数．このとき c.d.f. は

\[F(\epsilon) = \exp\left( - \exp\left(- \eta^{-1} (\epsilon + \eta\gamma)\right) \right), \quad \epsilon \in (-\infty,\infty)\]

で与えられる．期待値は　$\mathbb{E}[\epsilon] = \mu + \eta\gamma = 0$，分散は $\operatorname{Var}[\epsilon] = \eta^2 \pi^2 / 6$ で与えられる．したがって，$\eta$ は不確実性の大きさを表すパラメータであり，$\eta$ が大きいほど DM の選択における確定利得 $v$ の影響は小さく，$\eta$ が小さいほど影響は大きくなる．

全ての $\{\epsilon_a\}$ が独立に同一のガンベル分布に従うという仮定のもとでは，選択確率は次のような ロジット選択則 (logit choice rule) になる：

\[p_a = \frac{\exp(\eta^{-1} v_a)}{\sum_{b \in A} \exp(\eta^{-1} v_b)}.\]

このときの最大化された効用の期待値，すなわち 期待最大効用 (expected maximum utility, EMU) は

\[\lambda \equiv \mathbb{E}[\max_{a\in A} \{V_a\}] = \eta \log \sum_{a \in A} \exp\left(\eta^{-1} v_a\right)\]

である．選択確率 $p_a$ はこの EMU の $v_a$ に関する偏微分に一致することがわかる：

\[\frac{\partial \lambda}{\partial v_a} = p_a.\]

すなわち，選択確率ベクトルは期待最大効用の確定利得ベクトルに関する勾配になっている．この結果はロジットモデルに限らず，緩やかな条件のもとで一般の ARUM に拡張される（Williams–Daly–Zachary の定理，詳細は Fosgerau et al. (2020) などを参照）．

選択確率 $p_a$ の計算

仮定した分布のもとで以下の関係が成立することに注意する： $$ \begin{aligned} & F'(\epsilon) = \rho(\epsilon) F(\epsilon)\quad \text{with}\quad \rho(\epsilon) \equiv \eta^{-1} \exp \left(- \eta^{-1}\epsilon\right)\qquad\quad \text{(= p.d.f.)},\\ & F(v + \epsilon) = F(\epsilon)^{\exp(-\eta^{-1}v)},\\ & \{F(\epsilon)^t\}' = t F(\epsilon)^{t - 1} F'(\epsilon) = t \rho(\epsilon) F(\epsilon)^{t}. \end{aligned} $$ この関係を使えば， $$ \begin{aligned} p_a & = \int_{-\infty}^\infty F'(\epsilon_a) \prod_{b \ne a} F(v_a - v_b + \epsilon_a) \mathrm{d}\epsilon_a \\ & = \int_{-\infty}^\infty \rho(\epsilon_a) F(\epsilon_a) \prod_{b \ne a} F(\epsilon_a)^{\exp(\eta^{-1}(v_b - v_a))} \mathrm{d}\epsilon_a \\ & = \int_{-\infty}^\infty \rho(\epsilon_a) F(\epsilon_a)^{1 + \sum_{b \ne a}\exp(\eta^{-1}(v_b - v_a))} \mathrm{d}\epsilon_a \\ & = \frac{1}{1 + \sum_{b \ne a}\exp(\eta^{-1}(v_b - v_a))} \left[ F(\epsilon_a)^{1 + \sum_{b \ne a}\exp(\eta^{-1}(v_b - v_a))} \right]_{-\infty}^{\infty} \\ & = \frac{\exp(\eta^{-1}v_a)}{\sum_{b \in A}\exp(\eta^{-1}v_b)}. \end{aligned} $$ 期待最大効用 $\lambda$ については，$\hat{V} \equiv \max_{a \in A} V_a$ とすると， $$ \begin{aligned} \Pr[\hat{V} \le x] & = \Pr[\epsilon_a \le x - v_a\ \forall a\in A] = \prod_{a \in A}F(x - v_a) \\ & = F(x)^{\sum_{a \in A} \exp(\eta^{-1} v_a)} = F(x)^{\exp(\eta^{-1} \lambda_0)} \\ & = F(x - \lambda_0), \end{aligned} $$ ただし $\lambda_0 \equiv \eta \log \sum_{a \in A} \exp(\eta^{-1} v_a)$．すなわち，$\hat{V}$ の確率分布はロケーションパラメータ $- \eta\gamma + \lambda_0$ のガンベル分布に他ならない．よって $\lambda = \mathbb{E}[\hat{V}] = - \eta \gamma + \lambda_0 + \eta\gamma = \lambda_0$．

混合最適応答

ここで，改めて決定論的なアプローチを考えてみよう．引き続き，選択肢 $a \in A$ と対応する利得 $v = (v_a)_{a\in A}$ が与えられているとする．意思決定者の問題は，以下の線形最適化問題を解くことによって利得を最大化する混合戦略を決定することだとしよう：

\[\max_{y \in \Delta} \quad \langle v, y \rangle\]

ここで，$\Delta \equiv \{ y \ge \mathbf{0} \mid \sum_{a \in A} y_a = 1 \}$ は確率単体 (probability simplex) を表し，$\langle v, y \rangle = \sum v_a y_a $ は $v$ と $y$ の内積を意味する．

この問題の解 $y^\star$ は，次の条件を満たさなければならない：

\[y_a^\star > 0 \Rightarrow a \in \operatorname{br}(v),\]

ここで，

\[\operatorname{br}(v) \equiv \arg\max_{b \in A} \\{v_b\\}\]

は，利得ベクトル $v$ が与えられたとき利得を最大化する選択肢の集合である．

このような $y^\star$ は凸集合を形成するが，$\operatorname{br}(v)$ の要素は複数の選択肢が利得を最大化する場合は唯一ではない．このため，$y^\star$ の一意性は常に保証されるわけではない（cf. 線形最適化問題の解の一意性）．

上述の最適化問題に対応する双対 (dual) 問題は，次のように与えられる：

\[\min_{\lambda} \quad \lambda \qquad \text{s.t.} \quad \lambda \ge v_a \quad \forall a \in A．\]

この問題は，DM が達成可能な利得に対する最良の上界（=最小の上界）を得ることを目的としている．明らかに，この問題の解および最適値は $\lambda^\star = \max_{a \in A} v_a$ であり，これは当初の最適化問題の最適値と一致する（=線形最適化における 強双対性 (strong duality)）．

最適応答の双対問題の導出

まず，$\lambda$を制約 $\sum_{a\in A} y_a = 1$ に対する Lagrange 乗数としよう．Lagrange 関数は $$ \begin{aligned} L(y, \lambda) \equiv \langle v, y \rangle - \lambda \left(\langle \boldsymbol 1, y \rangle - 1\right) = - \langle \lambda\boldsymbol 1 - v, y \rangle +\lambda \end{aligned} $$ ただし $y \ge\boldsymbol 0$． Lagrange 双対問題は以下の目的関数を最小化する問題であるから，上述の双対問題を得る： \begin{align} \omega(\lambda) = \sup_{y\ge 0} L(y,\lambda) = \sup_{y\ge 0} \lambda -\langle\lambda\boldsymbol 1 - v, y \rangle = \begin{cases} \lambda & \text{if } \lambda \ge v_a \quad \forall a \in A,\\ \infty & \text{otherwise}. \end{cases} \end{align}

摂動付き最適化問題

先に見たように，決定論的アプローチでは，DMの選択に関して一意的な予測が得られない．最適化理論の観点から見ると，これは最適応答が線形最適化問題であることに起因している．こうした場合には，解の一意性を保証するために 正則化項 (regularization term) を加えてみるのが自然な発想の一つとなる．

DM の最適応答の問題が次のように変更されたと仮定する：

\[\max_{y \in \Delta} \ \langle v, y \rangle - H(y)\]

関数 $H:\text{int}(\Delta) \to \mathbb{R}$ は，狭義凸 (strictly convex) であり，$y$ が $\Delta$ の境界に近づくにつれて勾配が際限なく急になる（発散する）と仮定する．このとき，目的関数は狭義凹であり，かつ実行可能領域 $\Delta$ が凸かつ有界で閉（= 有限次元なのでコンパクト性と等価）であるため，この修正された問題は一意な解を持つ．

代表的ケースとして，$H$ が 負のエントロピー (negative entropy) であると仮定した場合を考えよう

\[H(y) = \eta \sum_{a \in A} y_a \log y_a，\]

ただし，$0 \log 0 \equiv 0$ と定義する．明らかに，$\eta \to 0$ のとき最初の問題に収束する．

最適解 $y^\star$ は，ロジット選択則と一致する：

\[y_a^\star = p_a = \frac{\exp(\eta^{-1} v_a)}{\sum_{b\in A} \exp(\eta^{-1} v_b)}．\]

また，正則化された問題の最適値は次のように表される：

\[\lambda(v) \equiv \langle v, y^\star \rangle - \eta \langle y^\star, \log y^\star \rangle = \eta \log \sum_{a \in A} \exp(\eta^{-1} v_a)．\]

この最適値は，ロジットモデルにおける期待最大効用と一致する．更に，

\[\frac{\partial \lambda(v)}{\partial v_a} = \frac{\exp(\eta^{-1} v_a)}{\sum_{b\in A} \exp(\eta^{-1} v_b)} = p_a．\]

すなわち，関数 $\lambda(v)$ は利得ベクトル $v$ に関する滑らかな関数であり，その勾配はロジット確率に一致する．最適値関数 $\lambda(v)$ は，定義より関数 $H$ の凸共役 (convex conjugate) あるいは Legendre変換に他ならず，この事実が $p_a$ の $\lambda(v)$ の勾配としての表現にもつながっている．実際，この関係は凸最適化において一般的に現れるものであり，ロジットモデル以外のモデルでも最適値関数の勾配が選択確率として表現されることがある．

正則化付き問題の ラグランジュ双対問題 は次のように表される：

\[\min_{\lambda} \ \lambda \quad \text{s.t.} \quad \lambda = \eta \log \sum_{a \in A} \exp(\eta^{-1} v_a)\]

この双対問題の解が主問題の最適値と一致するのは明らかである（凸最適化における強双対性）．また，

\[\lim_{\eta \to 0} \lambda(v) = \max_{a \in A} v_a.\]

となり，非正則化ケースの線形問題における双対問題とも対応する．

摂動問題の最適解と双対問題の導出

Lagrange 関数は $L(y, \lambda) \equiv - \langle v, y \rangle + \lambda \left(\langle\boldsymbol 1, y \rangle - 1\right) + H(y)$. 最適性条件は $$ \begin{aligned} & y_a \dfrac{\partial L(y,\lambda)}{\partial y_a} = 0, y_a \ge 0, \dfrac{\partial L(y,\lambda)}{\partial y_a} = - v_a + \lambda + \eta \log y_a + \eta\ge0, \label{eq:PBR-opt}\\ & \dfrac{\partial L(y,\lambda)}{\partial \lambda} = \sum_a y_a - 1 = 0. \end{aligned} $$ ここで $y_a \to 0$ のとき $\frac{\partial L(y,\lambda)}{\partial y_a} \to -\infty$ であるから, $y_a = 0$ は解として不適．従って $y_a > 0$．$\frac{\partial L(y,\lambda)}{\partial y_a} = 0$，すなわち $y_a = \exp\left(\eta^{-1} \left(v_a - \lambda \right) - 1\right)$. 更に，制約 $\sum_a y_a = 1$ より， $$ \begin{aligned} & \lambda^\star = \eta \log \sum_{a\in A} \exp(\eta^{-1} v_a) - \eta. \end{aligned} $$ であり，これを用いると既にみたロジット選択則を得る．また，$\sup_{y \ge 0} L(y,\lambda) = \lambda^\star + \eta$ であり，実際には既に $\lambda$ について解けた形で双対問題が得られる．Lagrange 乗数 $\lambda^\star$ が定数分だけ確率的選択の文脈の MEU とずれるのが気になる場合は $H(y)$ の定義を微修正すればよいが，選択確率と最適値には影響しない．

さて，$\eta \to 0$ のとき，$y_a > 0$ となるのは $a \in \operatorname{br}(v)$ の場合に限られ，$a \notin \operatorname{br}(v)$ のときは $y_a \to 0$ となる．これは正則化なしのケースと整合的である．実際，

\[\begin{aligned} y_a & = \frac{1}{\sum_{b\in A} \exp(\eta^{-1} (v_b - v_a ))}\\ & = \frac{1}{|\operatorname{br}(v)| + \sum_{b\notin \operatorname{br}(v)} \exp(\eta^{-1} (v_b - v_a ))}． \end{aligned}\]

であるから，もし $a \notin \operatorname{br}(v)$ であれば，ある $b \in A$ に対して $v_b > v_a$ となる．このとき，$\eta \to 0$ で分母が無限大に発散するから，$y_a \to 0$ である．ただし，$a \in \operatorname{br}(v)$ の場合 $y_a \to 1 / |\operatorname{br}(v)|$ となる．これは正則化なしのケースとは異なっている．通常の混合最適応答は一意でない可能性を許すためである．

異なる凸関数 $H$ を用いることで，異なる選択ルールが導かれる．実際に使用されている多くの ARUM は，このような 摂動最適化問題 によって表現されるが，すべての摂動最適化問題の解に対応する ARUM が存在するとは限らない (Fosgerau et al., 2020)．

参考文献

Anderson, S. P., de Palma, A., and Thisse, J. F. (1992). Discrete Choice Theory of Product Differentiation. MIT Press.
Fosgerau, M., Melo, E., de Palma, A., and Shum, M. (2020). “Discrete choice and rational inattention: A general equivalence result.” International Economic Review, 61(4), 1569–1589.
Fudenberg, D., Iijima, R., and Strzalecki, T. (2015). “Stochastic choice and revealed perturbed utility.” Econometrica, 83(6), 2371–2409.
Hofbauer, J. and Sandholm, W. H. (2002). “On the global convergence of stochastic fictitious play.” Econometrica, 70(6), 2265–2294.
Hofbauer, J. and Sandholm, W. H. (2007). “Evolution in games with randomly disturbed payoffs.” Journal of Economic Theory, 132(1), 47–69.
土木学会 (1998). 『交通ネットワークの均衡分析：最新の理論と解法』. 土木学会出版．（残念ながら絶版）
福田・城間 (2023). 離散選択モデル研究の最近の展開––異質性と摂動性の観点から––. 土木学会論文集 D3 (土木計画学), 78(5), I1-I20.