P(n)と新しく出た選択確率p(n+1)を比較し，誤差が十分小さけ。
れぼそこで処理を終了する.
すなわち，関値をεと置いた時，上式が成り立てば十分収束したとみなし，処理を終了する．一方誤差が関値より大きい場合には，p(n+1)を新しい選択確率とし，ステップ1～ステップ4を繰り返す. [1]今村晋,有村俊秀,片山東:労働政策の評価：「構造推定アプローチ」と「実験的アプローチ」,日本労働研究雑誌, Vol.43, pp.14-21, 2001. [2] Rust, J., Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher, Econometrica, Vol.55,pp.999-1033, 1987. [3] Hotz, V. J., and R. A. Miller, Conditional Choice Probabilities and the Esti- mation of Dynamic Models, Review of Economic Studies, Vol.60, pp.497-529, 1993 [4] V,Aguirregabiria., P,Mira., Swapping the Nested Fixed Point Algorithm: A Class of Estimators for Discrete Markov Decision Models利用者均衡配分の基礎概念(a)効率的な道路政策を進めるために道路投資の効果をいかに評価するかということが重要になってきている.そのためには道路整備前と後で交通量や、その旅行時間を推計することが必要となってくる.また従前は交通量の再現や予測にその焦点が当てられていたが、近年はマルチモーダル、TDM、ITS施策といったソフト施策の評価が重要となってきている.そこで利用者均衡配分による交通量推計が行われるようになった.利用者均衡配分とは以下に示すWardropの第一原則を仮定したモデルである. - Wardropの第一原則(等時間原則)一それぞれのドライバーは自分にとって最も旅行時間の短い経路を選択する.その結果として、起終点間に存在する経路のうち、利用される経路の旅行時間は皆等しく、利用されない経路の旅行時間よりも小さいか、せいぜい等しいという状態となる.ここでは利用者均衡配分のモデルについて扱う.まずモデルを構築するにあたっての前提条件を二つ仮定する. 1.起終点の旅行時間は、その通貨経路を構成するリンクの旅行時間の和で表わされる. 2.各リンクのリンク旅行時間はそのリンクの容量と交通量のみによって決まり、他のリンク(対向車線や交差する道路等)の交通状況には影響を受けない.利用者均衡配分問題は、すべてのOD間のフロー数が与えられたときにWardrropの第一原則を満たすリンクフローを求める問題である.まず定式化に際し用いる変数の定義を表3.4行う.
先の二つの前提条件を仮定したときWardropの第一原則が成り立っている状態を数式で表現すると式(3.65)のようになる.
ここでursはODベアrs間の最小旅行時間である.次に利用者均衡条件を満たす、つまり式(3.65)を満たすような等価な数学的問題に置き換える．これはすべてのOD間のフロ一数qrsが与えられたときに、利用者均衡条件を満たすべてのリンクフロー麦。を求める問題である.このとき式(3.66)のように定式化できる.
ここでxはすべてのリンクを表わすべクトルで、x = (…, x a ….)である．制約条件は式(3.70)、式(3.71)のようになる.
また当然満たされるべき関係として式(3.72)、式(3.73)がある.
式(3.72)はODペアrs間の経路kの旅行時間は経路k上にあるすべてのリンク旅行時間の総和であることを、式(3.73)はリンクaの総フロ一数はリンクaを通るすべての経路k上のフロー数の総和であることを意味している.参考文献(c)等価性の証明式(3.66)に式(3.70)を用いたラグラジアンで表わすと式(3.73)のようになる.
ただしfはすべての経路上のフロー数を表わすべクトルでf = (…,frå,…)である.またursは各ODベアのフロー数制約に与えられる双対係数で、 u = (..., u rs, ...)である.このときフロー数の非負制約条件式(3.71)が満たされていなければいけない.ここでラグラジアン(3.73)の停留点では式(3.272)が満たされていなければいけない.
また双対係数については式(3.273)が満たされていなければいけない.
この式(3.273)は式(3.70)と同じで、フロー数制約が満たされなければいけないことを意味しているパスフロー fresに関するラグラジアンの偏微分は式(3.274)となる.
ここで式(3.274)第一項は式(3.275)のようになる.
式(3.275)の右辺を分解して考える.まず右辺左側については式(3.276)のようになる.
170
また式(refue5)に注意すると式(3.275)右辺の右側は式(3.277)のようになる。式(3.276)、式(3.277)を式(3.275)に代入し、式(3.73)を利用すると式(3.278)が導かれる.これはあるODペアmn間のパスしの旅行時間を表わしている.次に式(3.274)の第二項について.まず式(3.279)が成立する. qrs、ursはfinnについて定数なので、式(3.274)の第二項は式(3.280)のようになる.この式(3.281)を式(3.272)に代入し、また式(3.273)と非負制約条件式(3.71)をまとめると式(3.282)のようになる.式(3.282)は利用者均衡条件に他ならないので、式(3.66)を制約条件式(3.70)、 (3.71)のもとで解くことで利用者均衡配分問題を解くことができることが示された. 3.3.2 システム最適化配分(a)システム最適化配分の基礎概念前節まではW ardropの第一原則が満たされるような交通量配分を考え定式化を行った.一方で以下に示すW ardropの第二原則を満たすような交通量配分をシステム最適化配分という. – Wardropの第二原則—道路ネットワーク上の総旅行時間が最小となる. W ardropの第一原則と第二原則は同時に満たされる場合もあるが、一般には異なった配分結果をもたらす.システム最適配分は道路網全体としての効率化を目指した配分であり、道路事業者が車の流れを管理してドライバー全体の総走行時間を最小化しようとする場合に相当する.したがってシステム最適化配分を行ったとき各ドライバーは最小旅行時間を移動しているとは限らない．利用者均衡配分のときと同様に式(3.283)～式(3.285)の等価な数学的問題に置き換えることでシステム最適化配分問題も解くことができる.
(b) ブラエスのパラドクスシステム最適化と利用者均衡の違いを理解していないと次のような問題が起こる．システム最適化の観点で道路ネットワーク上の総旅行時間を小さくするために新しい道路(バイパス)をつくった結果、以前よりも総旅行時間が大きくなってしまうことがある.これをプラエスのパラドクスという.例えば図3.65の上図のような道路ネットワークがあり、出発地から到着地まで6台の自動車が移動するとする.つまりq = 6である.このとき各パスの旅行時間は式(3.286)だとする. t1 [x1] = 50 + x1 t2 [x2] = 50 + x2 t3 [x3] = 10x3 ts [xs] = 10xs
このとき利用者均衡条件を満たすようなフローは図3.65の下図のようになる.このとき各パスの旅行時間はO →リンク1 →リンク4 → D、O →リンク3 →リンク2 → Dのどちらも50 + 3 + 10 × 3 = 83であり、道路ネットワーク上の総旅行時間は498となる.今道路ネットワーク上の総旅行時間改善のために図3.66の上図のようにリンク5をひとつ新たに設ける.リンク5の旅行時間は式(3.287)である.このとき利用者均衡条件を満たすようなフローは図3.66の下図ようになる.このとき各パスの旅行時間はO →リンク1 →リンク4 → D、O →リンク3 →リンク2 → D、O →リンク3 →リンク5 →リンク4 → Dのどれも92であり、道路ネットワーク上の総旅行時間は552であり、リンク5を設けた場合のほうが総旅行時間が大きくなっていることがわかる.この結果は利用者均衡配分の枠組みではドライバーは自分の旅行時間のみを最小とするように経路を選択し、自分の経路選択の結果ネットワーク全体の旅行時間に与える影響を考慮していないことが原因で発生する. (a) 確率的利用者均衡配分の基礎概念前節まで扱っていた利用者均衡配分では各道路利用者が各経路の旅行時間を完全に知っている状態で、最短経路を選ぶという強い仮定を置いていた.したがって最短経路以外には交通路湯が全く配分されなかった.この条件を緩和し、道路利用者が知っている各経路の旅行時間は不正確であり、旅行時間以外の要因も考慮して経路を選択しているとしたのが確率的利用者均衡配分である.この確率的均衡配分のほうがより現実的であり、すなわち道路利用者が図3.65 プラエスのバラドクス:初期状態図3.66 プラエスのバラドクス:新リンク追加後認識している各経路の旅行時間は確率的に変動する誤差を含んでいるとしたモデルである.均衡状態ではW ardropの考え方に対応させると以下のような状態が成り立つ.それぞれのドライバーは自分にとって最も旅行時間の短いと思われる経路を選択する.その結果として、起終点間に存在する経路のうち、利用される経路の旅行時間は皆等しいと信じられ、利用されない経路の旅行時間よりも小さいか、せいぜい等しいと信じている状態となる.確率的利用者均衡配分において道路利用者が認識している旅行時間が誤差を含んでいるという考えかたはランダム効用理論に基づく、離散選択モデル(非集計モデル)と同等である.つまり、道路利用者が経路を選択する際に従うルールに非集計モデルを適用したのが確率的利用者均衡配分だといえる.ODペアrs間の経路kの効用関数の確定項Vr*を、旅行時間のみの関数とすると式(3.288)のようになる.
効用関数の誤差項が正規分布に従うとした場合プロビット型など様々なっモデルが考えられるが、ここでは誤差項をガンベル分布を仮定したロジットキ
デルで話を進める.このときODベアrs間の経路選択肢集合K,sから経路kが選択される確率Pr*は式(3.289)のようになる.
ここでθは分散パラメータを表わす.このθの値によって認知旅行時間の誤差が変化する.つまり、θが大きいほど認知旅行時間のずれは小さくなり、確定的な利用者均衡配分に近づき、θが小さいほど認知旅行時間のずれは大きくなり、実際の旅行時間の大小にかかわらず、どの経路も同じように選択されるようになる.今選択確率が決定したとするとODベアrs間の経路にのフロー数ƒ蒙は式(3.291)で表わされる.
確率的利用者均衡配分を満たす解を求めるための数理的最適化問題は式(3.291)であり、制約式は式(3.292)のようになる.
ここでΩはすべてのODべアの集合を表わす.また確定的利用者均衡配分のときと同様に当然満たされるべき条件として式(3.293)がある.
前節まに様々な配分問題の定式化を行った.ここではその問題を解くアルゴリズムについて説明を行う.まず利用者均衡配分の解法の一つ線形計画法であるFrank — Wolfe法を説明する. (a)   Frank – Wolfe法Frank — Wolfe法は計算手順が比較的簡単でプログラムを作成しやすいという長所がある一方で、均衡解に近づくに従い収束が緩慢になる．具体的なアルゴリズムを以下に示す.またupsはn回目の試行を行ったときのOD間最小旅行時間を表わす.すべてのリンクの交通量x 2 ＝ 0としリンク旅行時間t 2を計算する.この旅行時間に基づきall — or — nothing配分(交通量0のときのリンク旅行時間を用いた最適経路配分)により初期実行可能解(リンク交通量の初期値) x 1を設定する.このとき繰り返し計算の試行回数n = 1とする.リンク交通量28に対するリンク旅行時間t2を計算する.このときODペアごとの最小旅行時間u nを計算する.リンク旅行時間tsの状態ですべてのOD間の交通量を最短経路に配分し、そのときの交通量をy nとする.d n = y n − x nによって降下方向ベクトルdgを計算する.式(3.294)のようなx +1に対して式(3.66)で表わされる目的関数の値が最も小さくなるようなα nを探索する.すなわち式(3.295)を解くことでα nを探索すればよい.得られたα nによってx n +1を計算す
る.新たなリンク交通量から旅行時間th+1を計算し、ODペアごとの最小旅行時間ure 1を計算する.
式(3.296)の収束条件(この収束判定基準は唯一のものではない)が満たされていれば、n = n + 1としステップ1へ戻る.収束条件が満たされていれば、計算を終了しリンク交通量æ t 1を解として出力する.ただし式(3.296)中のκはあらかじめ決定された定数とする.
確率的利用者均衡配分の解法アルゴリズムには確定的な利用者均衡配分で用いたFrank – Wolfe法は実用上は計算が複雑になるため用いられることはない.ここでは確率的利用者均衡配分の解法アルゴリズムとして逐次平均法( MSA ; Methodof Successive Averages )、部分線形化法、 SimplicialDecomposition法を紹介する. (a)  逐次平均法逐次平均法は計算手順がシンプルであり、記憶容量も少ない方法であるが、計算の収束に必要な繰り返し計算回数が多くなる.この逐次平均法ではあらかじめ降下ステップサイズを決定しておくことで目的関数を計算することを回避している.また最短経路にすべての配分を行った確定的利用者均衡配分のときと異なり、リンク旅行時間を固定したときの確率的配分( Dial配分法など)を用いる.以下に具体的なアルゴリズムを示す. 177ステップ0: 初期実行可能解の設定すべてのリンクの交通量æ ＝ 0としリンク旅行時間toを計算する.この旅行時間に基づき確率的配分により初期実行可能解(リンク交通量の初期値)☞を設定する.このとき繰り返し計算の試行回数n = 1とする.リンク交通量式をに対するリンク旅行時間tsを計算する.リンク旅行時間t͡ɕの状態ですべてのOD間の交通量をネットワーク上に確率的配分し、そのときの交通量をy nとする.d n = y n − x nによって降下方向ベクトルd賞を計算する.降下ステップサイズをα nとし式(3.297)により新しいリンク交通量を計算する.
n + 1
式(3.294)によりæ +¹を計算する.新たなリンク交通量から旅行時間tn+1を計算する.式(3.298)の収束条件(この収束判定基準は唯一のものではない)が満たされていれば、n = n + 1としステップ1へ戻る.収束条件が満たされていれば、計算を終了しリンク交通量æ n +1を解として出力する.ただし式(3.298)中のκはあらかじめ決定された定数とする. (3.298)ただし定をは式(3.299)で表わされるとする。
(3.299) ī
ステップ4の収束判定で、逐次平均法では降下ステップサイズがあらかじめ決定された定数列でnが大きくなると小さくなっていくのでn回目のリンク交通量x ''とn + 1回目のリンク交通量x ''+'の差は当然小さくなる.そこで、式(3.299)のように直近m回分の移動平均をとることで収束判定を行っている. (b) 部分線形化法部分線形化法ではエントロピー分解定理を用いることで起点別リンク交通量(＝各リンク交通量がどの出発地からどれだけ発生したものか表わす)から目的閲数の計算を行いステップサイズを計算しており、ステップサイズをあらかじめ決定している逐次平均法よりも効率的に解を収束させることができる.まずエントロピー分解定理について説明する.式(3.291)の第２項(エントロピー項)は式(3.300)のように分解することができる.
ただしますは起点別リンク交通量(リンクaの交通量のうちノードすを出発地とするもの)、Rは出発地ノードの集合、Nはノードの集合、I 1はノードjに流入するリンクの集合を表わす.この式(3.300)を用いることでパス交通量を用いることなく目的関数の計算が可能で降下ステップサイズ探索や収束判定に目的関数の値を利用することができる．以下に具体的なアルゴリズムを示す.すべてのリンクの交通量x 2 ＝ 0としリンク旅行時間t 2を計算する.この旅行時間に基づき全OD交通量を出発地別　に確率的配分し、得られた初期実行可能解(起点別リンク交通量の初期値) ☞を設定する.このとき繰り返し計算の試行回数n = 1とする.ステップ1: リンク旅行時間の更新リンク交通量x n = ∑ステップ2: 降下方向ベクトルの探索リンク旅行時間trの状態ですべてのOD間の交通量を出発地別にネットワーク上に確率的配分し、そのときの交通量をy ;"とする.d";" = y α n — x α nによって降下方向ベクトルd α nを計算する.ステップ3: 降下ステップサイズの探索降下ステップサイズをα nとし、式(3.302)により新しい起点別交通量を計算する.
得られたx ",n+1を目的関数に代入した値が最も小さくなるようなαを探索する.すなわち式(3.303)を解くことでαを探索すればよい.
(3.302)式(3.296)の収束条件(この収束判定基準は唯一のものではない)が満たされていれば、n = n + 1としステップ1へ戻る.収束条件が満たされていれば、計算を終了しリンク交通量æ t ¹を解として出力する. SimplicialDecomposition法は逐次平均法や部分線形化法とは異なり、経路を明示的に列挙していることが特徴である.経路選択肢どのように生成するかによって得られる解が異なる．以下に具体的なアルゴリズムを示す．ステップ0: 初期実行可能解の設定ODペア別経路集合をÅ, 。とし、初期状態を空集合とする．す
のリンクの交通量xg ＝ 0としリンク旅行時間tgを計算する.この旅行時間に基づき最短経路を探索し、 Á r sに加える.また最短経路へ、 all — or — nothingによってfrs,1、リンク交通量x,を計算する.このとき繰り返し計算の試行回数n = 1とする.ステップ1: 端点の生成リンク交通量麦雲に対するリンク旅行時間ts を計算する.リンク旅行時間の下で最短経路を探索し、得られた経路をK rsに加える.ステップ2: 限定親問題を解く経路交通量ベクトルfn+1 = (frs,n+1)について式(3.303)を解く.
制約条件として式(3.304)が与えられる.
この問題の解法として部分線形化法が利用できる.ステップ2-0: 初期設定限定親問題の解の初期値をgrs,¹ = frs,¹、y 1 = x 2とする.限定親問題を解くループの繰り返し計算回数のカウントをm = 1とする.ステップ2-1: 降下方向ベクトルの探索式(3.305)によりリンクコストtwを更新する.
(3.305リンクコストパターンt m の下での経路選択確率に従って全OD交通量を各経路に配分し、得られた経路交通量hrs,k、リンク交通量zmをそれぞれ式(3.306)、(3.307)によって計算する.
また降下方向ベクトルers,mとdmを式(3.308)、(3.309)により計算する.
ステップ2-2: 降下ステップサイズの算出と解の更新降下ステップサイズη を用いて交通量を式(3.310)、(3.311)により更新する.
このg r s,m+1、y m+1を目的関数に代入した値が最も小さくなるようなりを探索する.すなわち式(3.312)を解くことで探索を行う.
182限定親問題の解が収束すれば、すなわちgm 当hmならば、frs,n+1 , grs,m+1、xn+1 = ym+1としてステップ3へ進む.そうでなければm = m + 1としてステップ2-1に戻る.収束条件が満たされていなければn = n + 1としてステップ1に戻る.収束条件式が満たされていれば、計算を終了しリンク交通量xn+1と経路交通量ƒҡ ,ɳ+¹として解を出力する.遺伝的アルゴリズム(以下GAとする)は，データの集合を遺伝子DNAの進化プロセスになぞらえて，最適解を計算する最適化アルゴリズムの１つである．ここまで述べた他の最適化アルゴリズムは目的関数の微分可能性や変数の探索空間の構造(実数値)を前提においていた．また，ネットワークの規模が大きくなるほど計算に膨大な時間がかかり，現実的な時間内に計算が終了しない場合がある．GAは整数問題など広範な問題に対応でき，また必ずしも厳密解が得られるわけではないものの，ある程度それに近い解を比較的短時間で得ることができるヒューリスティックなアルゴリズムである.以下の図3.67に遺伝的アルゴリズムによる計算プロセスを示す．個体群(この場合は解の候補の集合)が適応度(目的関数の値)が高くなるように自ら「進化」していくことがGAの大きな特徴である.各プロセスにおける操作は以下の3つのステップに分けられる.初めに解の候補の初期値を与える．この時，解の表現の仕方を工夫する必要があり，例えば合計10台の車が3つの経路に流れるフロ一数を考える時，遺伝子型を(2, 3, 5)のように直接経路の台数で表現することもできるが，図3.68のように車両10台と仕切り2枚を並べたときの仕切りの位置と考えて，(3,7)のように表すこともできる．実は，後者の方がSTEP2の遺伝的操作を行う際に適した形である(理由は後述する).このように直接的な表現型から，遺伝子型と呼ばれる遺伝的操参考文献園3.67   GAの計算プロセス3.3ネットワークモデル作に適した形に変換することをエンコードと呼ぶ。逆に遺伝子型から表現型に戻す操作をデコードと呼ぶ.経路1:2台
図3.68 エンコーまた，個体の個数の設定も重要である．個体数が少ないと収束までに時間がかかり，逆に個体数が多いと1世代あたりの計算時間が長くなる．一般的に，遺伝子の長さが長いほど個体数を多くとる必要がある．現在(む期とする)の個体群に含まれる全ての個体の適応度を評価する.適応度は最大化問題の場合は目的関数をそのまま用いる．一方で最小化問題の場合は目的関数を－1倍する，逆数をとるなどの工夫が必要となる。遺伝的操作は，選択・交叉・突然変異の３つの操作からなる.選択選択では次の交叉で親となる遺伝子を選出する．適応度の高いものを優先的に選び，優れた個体ほど子孫を残しやすくする．選択の方法としては，各個体の選択確率を適応度に応じた比例配分によって求めるルーレット選択，予め順位ごとに選ばれる確率を設定するランキング選択，ランダムに一定数個体を取り出しその中で適応度が最大な個体を選ぶ操作を繰り返すトーナメント選択などが存在する．また，上位の個体をそのまま次の世代に残し(エリート選択という)，残りの個体から選択を行うことで，より適応度の高い集団にする方法も存在する. 185選択で選んだ2つの個体(親)のデータを交叉し，新しい2つの個体をつくる.交叉の方法には，1箇所を選んでその前後のデータを入れ替える1点交叉，2箇所を選んでその間のデータを入れ替える2点交叉，入れ替える場所をランダムに選んだ一様交叉などが用いられる．一般的には一様交叉が用いられることが多い．図3.69に一様交叉の例を示す。一様交叉では，はじめに１と０からなるランダムなビット列を作成し，その値が１の地点を入れ替えることで新しい個体を作る.ここで遺伝子の表現方法の議論が重要になる。先程の例でいえば,各経路のフロー数を遺伝子型とした場合，交叉によって生じる個体の要素の合計が総車両数を超えてしまう、あるいは総車両数に達さないといった，制約条件を満たさない個体ができてしまう恐れがある．このように制約条件を満たさない個体の遺伝子を致死遺伝子と呼び，なるべく交叉によって致死遺伝子が発生しないようなエンコードが求められる.交叉で生成した新しい個体は，親の個体の性質を引き継いでいるため，初期収束のように個体の特性が偏る恐れがある．突然変異は交叉によって生じた個体を一定確率で変化させることによって個体の多様性を保つ操作である．一般的な突然変異では，要素の一部を乱数で置き換えることによって突然変異を行う．他にもランダムに選んだ2点の遺伝子を入れ替える転座や，2点間の遺伝子の順序を逆にする逆位といった手法がとられることもある.遺伝子操作によって第ｔ期の遺伝子群から新しい第ｔ＋１期の遺伝子群ができる.ここで終了条件の判定を行う．終了条件としては，一定回数だけ計算する，関値を超える適応度の個体が現れる，世代の平均値が関値を超える，前の世代からの平均値の増加率が関値以下になる状態が一定期間続く，など様々である．計算環境や問題の性質に応じて使い分ける必要がある.以上の操作を行うことによって，GAは比較的短時間でおおよそ最適な解を導くことができる．しかし，実際にアルゴリズムを実行する際，以下のような問題が起こりうることに注意が必要である．比較的初期の世代の集団の中で，適応度が他の個体に比べ著しく高い個体が存在する時，交叉によってその個体の遺伝子が集団に急速に広がり，局所最適解に収束してしまう恐れがある．一般的には初期収束を避けるために突然変異の頻度を調節したり，個体の集中度合いによって適応度に重みづけするなどの対策がとられる.最適解にきわめて近い2つの個体を交叉させても，最適解を得られないことがある．この場合，遺伝子長が長いほど最適解が得られる確率は極端に低くなっていく．一般的に，この問題は一様交叉によって簡単に回避することが可能である. GAに基づいて解を探索している．しかし，その仮説が成立しないような問題も存在する．このような問題に対してGAを適用した場合，局所最適解に陥りやすく最適解を発見することが難しくなる．この問題を回避するためには，これまで述べたような単純な形のGAの枠を超えた拡張が必要となる.参考文献(e)計算例ここでは利用者均衡配分を図3.70のネットワークを使って実際に計算を行う．ただし各パスごとの旅行時間は式(3.313)とする．
Frank — Wolfe法の計算例を図3.71〜図3.73にに示す.最終的に計算を繰り返していくとx 1 = 3.58、x 2 = 4.62、x 3 = 1.81を得る.ただし収束判定のための定数κ = 0.001とした. (f)ゲーム理論を適用したリスク回避利用者均衡配分Bell and Cassir(2002)[5]では，経路コストに不確実性が伴う状況，すなわち脆弱性を伴うネットワーク上での利用者の確率的な経路選択を定式化するため，ゲーム理論を導入した．はじめに，ネットワーク利用者がn人であるとき，交通量配分はナッシュ均衡状態のn人参加混合戦略非協力ゲームと等価であることを示す.決定論的利用者均衡と確率論的利用者均衡の等価性の証明188 3.3ネットワークモデル189 n = 1 u ' = 20園3.72   Frank — Wolfe法: ステップ図3.73   Frank — Wolfe法: ステップ1、ステップ2 3,ステップ4前提として，1つのODペア，複数の経路選択肢が存在するネットワークを，一様なn人が利用する状況を想定する． (i)決定論的交通量均衡配分の必要十分条件Wardropの第一原則は，以下のように定式化される. (3.314) (3.315)ここで，hは経路交通量ベクトル，gは経路旅行時間ベクトルである．nが十分大きいと仮定すると，大数の法則により，h j = p jnあるいはh j = 0のときpj = 0が成り立つ.ただしpjは経路jがどの利用者にも選択される確率である．それ故，もしg j (h*)が最小ODコストgod(h)より大きいとき，均衡点h*，p j = 0となる. (ii) n人非協力混合戦略ゲームが混合戦略ナッシュ均衡であるための必要十分条件どの利用者αも複数の経路選択肢があり，経路選択は他の全ての利用者に対するゲームであると仮定し，経路選択混合戦略である状況を想定する．利用者αに対する混合戦略saは，経路選択純戦略πaiの凸結合である．経路選択純戦略παjは，利用者αが経路jを選択する場合に用いられる．故に，参考文献
ここで，Pajは利用者aが経路」を選択する確率である．利用者aの経路は，全ての利用者による混合戦略のn次元ベクトルsによって次のように定義される.
ここでca(s-a, παj)は利用者αが経路jを選択し，他の利用者がn-1次元ベクトルs-aで表される混合戦略に従った場合のコストである．利用者は一様とする仮定から，コストは全ての利用者間で同一である．全ての利用者が同じ選択肢(同じ経路)を持ち，全員がコストを最小化するため，プレーヤーは入れ替え可能である。それ故どの経路」に対しても，以下の等式が成り立つ.
hはおよそpnと等しいため，利用者aにとっての経路jのコストはおよそhに基づく経路」のコストと同等である.
大数の法則により，利用者aにとっての経路jのコストはnの増加に従い，hに基づく経路jのコストに近づく．nが十分大きい場合，以下の式より，決定論的利用者均衡配分はナッシュ均衡と同等であるといえる.
混合戦略ナッシュ均衡(Nash, 1951)であるための必要十分条件はそれ故，nが十分大きいときの決定論的利用者均衡の必要十分条件と同等であることが示された. 190
Network demonを導入したn+1人ゲームの定式化次に，新たなゲームのプレーヤーとなるdemonの存在を導入する．demonは１つのリンクにダメージを与えることで，ネットワーク利用者のコストを最大化する．純粋ナッシュ均衡でない限り，demonはネットワーク内のリンクの数と同数の純粋戦略を実行しなくてはならない．n+1人ゲームG 1は以下のように定式化される. Ca (s,q) = , Paj _ , qkcn+1,k(sa) for the demon player n + 1 Cn+1(s,q) =ここで，qはリンクダメージシナリオルの発生確率ベクトル，cak (s-a, πaj)は利用者aがシナリオルにおいて経路すを選択し，経路戦略n-1次元ベクトルs_aが適用されるときのコスト,  cn+1,k(s)はdemonがシナリオkを選択し，n次元ベクトルである利用者戦略sを適用するときの効用を表す．このプレーヤーの狙いは全プレーヤーのコストを増加させることである．シナリオムにおけるネットワーク利用者の期待コストの合計cn+1,k(s)は,以下のように定式化される.
ここで，少なくともひとつの混合戦略均衡解が存在する(Nash(1951)). しかし，特にnが大きいとき，均衡点を見つけるのは困難である．そこで，以下では二段階最適化問題によって均衡解を求めることで，ゲームのマクロ的な解法とおよそ同等の解を得る.二段階最適化問題B1の定式化参考文献
ここでgjk(h)はシナリオk,交通量ベクトルh下での経路jのコスト, tuk(vu)はシナリオkにおけるリンクuの交通量に依存するコスト, aujは経路」にリンクuが含まれるとき1，そうでない場合は0となる指示関数である．以下に，nが十分大きいとき，二段階最適化問題B1はG1のマクロ的な解を与えることを示す. B1の上位問題はdemonの視点からゲームを解いており，ネットワーク利用者に撰される期待コストの和を最大化させる．下位問題は，期待コストに基づく標準的な決定論的利用者均衡配分問題である．相互に一定の点(ナッシュ均衡であり，シュタッケルベルグ均衡ではない)において，以下の条件が適用される.
大数の法則により，集団レベルでの合計期待ネットワークコストは，nが大きくなるにつれて個々の期待コストの和に近づく.
192
この差はnが大きくなるにつれて小さくなる．従って，ミクロ的なレベルの上式は，以下の様に示される.
nが大きいとき，任意の経路」と大数nに対し,
また，h j = p j n = p aj nであるために，上式はミクロレベルにおいて， (3.334)
(3.335) nが大きいとき，これらの条件は非協力混合戦略n+1人ナッシュ均衡問題における必要十分条件である(Nash, 1951)[6]. 従って，nの増加に伴って， B1を解くことでこれまでに定義したn+1人ゲームであるG1に関するマクロ的な近似解を得ることが示された. [1]土木計画学研究委員会交通需要予測技術検討小委員会:道路交通需要予測の理論と適