計算量理論 (11月10日) 情報学研究科 社会情報学専攻 M1 満永 拓邦 復習 • ナッシュフロー – 各ユニットが自由に行動する時に均衡となるフロー • 最適フロー – 全体としての総コストが最小になるフロー • 無秩序の代償 – ナッシュフローと最適フローの比 具体例 C(x) =1 (広い道) S 図2.2 T C(x) =X (狭い道・裏道) S町からT町に至る2つの道がある ・上の道は交通量によらず一定の広い道 ・下の道は交通量に比例して時間がかかる狭い道 S町からT町まで一定の数の車が移動するとき(上記例では 1の量の車)、それぞれの車はどちらの道を選ぶか。 ナッシュフロー • 各車が自分の時間を最小になるように行動 (全ての道のコストが等しくなるフロー) 前回の[Proposition 2.2.2] – この場合は全て車が下の道を選ぶ • その時の道のコストは1になる。 – よってその時の総コストは 1 × 1 (下のパスを通る量) (パスのコスト) = 1 となる (総コスト) 最適フロー • 交通規制され、全体の総コスト最も少なくする時 のフロー – 限界コスト関数によって求める C* = {x・C(x)} / dx – 上下それぞれの道に半分ずつ • 上の道のコスト1 下の道のコスト 1/2 – 総コスト • • 1 1/2 (下のパスを通る量) • 計 3/4 × × 1/2 = 1/2 = (パスのコスト) 1/2 (上のパス) 1/4 (下のパス) (各道のコスト) ナッシュフローと最適フロー ●ナッシュフローでは各 車の最適のみを考えるので 道のコストを基準に考える ●最適フローでは全体の 最適を考えるので 道のコスト×交通量(面積) を基準に考える 無秩序の代償 • ナッシュフロー・・各々が自らの最適を目指した場合 総コスト • 最適フロー 1 ・・全体にとって最適を目指した場合 総コスト 3/4 • 無秩序の代償 • ナッシュフロー/最適フロー = 4/3 ≒ 1.33 Breass’s Paradox x 上下のパスともコストは 1+X なので 半分ずつのフローが流れる v s 1 t 0 1 w x コストは、上下それぞれ 1/2 × (1 + 1/2) = 3/4 (フロー) (コスト) より、総コストは 3/2 ⇒新たなパスを作ると 全てのフローが s - v - w - t の順で流れて 1 × 2 = 2 より、総コストは 2となる パレート支配 C(x) =1 C(x) =1 S T C(x) =X ナッシュフロー 2 最適フロー 1.5 C(x) =X 今までの例では、各ユニットごとに考えると、最適フローの時のコストは 常に最悪でもナッシュ均衡と同じか低くなる。 これを経済学の用語で、「ナッシュフローは最適フローにパレート支配される」 と表現する。 ⇒ただし、これは常に成立するわけではない。 パレート支配的でない例 ●ナッシュフロー 全てが下の道に1流れる 各ユニットのコストは1、総コストは1 C(x) =2-ε ε /2 S T 1-ε /2 ●最適フロー 2-ε = 2X より 上の道に ε/2 下の道に1- ε /2流れる C(x) =X (具体例) 上に流れたε/2のフローの コストは、2-εとなり上昇する 総コストは、1-ε^2/4 C(x) =1.9 0.05 S T 0.95 C(x) =X 具体的には、ε = 0.1の時は、 上の道に0.05のフローが流れ 1.9のコストがかかる ナッシュフロー v s1 t1 w z t2 s2 x ①赤と黒のフローを別々に足すと、それぞれの全体のフローになる ②重なる部分(緑色)の部分のフローは赤と黒の和となる ③フローは非負 ナッシュフロー 定義から、heの導関数Ceは連続、非減少よりheは凸関数 ⇒(CP)は解を持つconvex programであり、解がナッシュフロー また、前回Proposition2.2.2より、各パスのコストが最適(最小) の時に、ナッシュフローとなり最適なものなので一意的に解をもつ 古典的なネットワークでの定義 古典的なネットワークでの定義 (sから出るフロー) s (sに入るフロー) v t 非ループのフロー w s v w Proposition 2.7.3 ある実現可能なフローfe が存在するとき、 全てのeに対して、f ‘e ≦ fe となる、非ループのフローが存在する。 t f-monotone • ナッシュフローf に対して、d(v)を、コストの点でs-t間の 最少のパスとする • Gのエッジの並び順は、次の3つを満たすとき f-monotoneである – P1) sの順序が1番目 – P2) すべてのフローが、順番に流れる – P3) エッジ間のdの値は、非減少である Breass’s Paradox x v s 1 t 0 1 w x ナッシュフローにおいて d(s) = 0 d(v) = 1 d(w) = 1 d(t) = 2 であり、このグラフは f-monotoneを満たす。 P1) sの順序が1番目 P2) すべてのフローが、順番に流れる P3) エッジ間のdの値は、非減少である 非ループのフロー C(x) = 0.6 s w v C(x) = 0.6 w C(x) = 1 d(w) - d(v) ≦ Ce(fe) [v - w 間のコスト] が成立 等号が成立するのは、 v -w間で、最小のコストのパスを選んだ時 t ナッシュフローの定義2 • 同様に、すべてのエッジw ,v に対して、 d(w) - d (v) = Ce(fe) for e = (w,v) が成立すれば、feはナッシュフローである。 この定義は、5.2において活用する。
© Copyright 2024 ExpyDoc