計算量理論
（11月１０日）
情報学研究科
社会情報学専攻 M1
満永 拓邦
復習
• ナッシュフロー
– 各ユニットが自由に行動する時に均衡となるフロー
• 最適フロー
– 全体としての総コストが最小になるフロー
• 無秩序の代償
– ナッシュフローと最適フローの比
具体例
C(x) =1 （広い道）
S
図２．２
T
C(x) =X （狭い道・裏道）
S町からT町に至る2つの道がある
・上の道は交通量によらず一定の広い道
・下の道は交通量に比例して時間がかかる狭い道
S町からT町まで一定の数の車が移動するとき（上記例では
１の量の車）、それぞれの車はどちらの道を選ぶか。
ナッシュフロー
• 各車が自分の時間を最小になるように行動
（全ての道のコストが等しくなるフロー）
前回の[Proposition 2.2.2]
– この場合は全て車が下の道を選ぶ
• その時の道のコストは１になる。
– よってその時の総コストは
１
×
１
（下のパスを通る量）
（パスのコスト）
＝
１ となる
（総コスト）
最適フロー
• 交通規制され、全体の総コスト最も少なくする時
のフロー
– 限界コスト関数によって求める C* = {ｘ・C(x)} / dx
– 上下それぞれの道に半分ずつ
• 上の道のコスト１ 下の道のコスト １／２
– 総コスト
•
•
１
１／２
（下のパスを通る量）
• 計
３／４
×
×
１／２ ＝
１／２ ＝
（パスのコスト）
１／２ （上のパス）
１／４ （下のパス）
（各道のコスト）
ナッシュフローと最適フロー
●ナッシュフローでは各
車の最適のみを考えるので
道のコストを基準に考える
●最適フローでは全体の
最適を考えるので
道のコスト×交通量（面積）
を基準に考える
無秩序の代償
• ナッシュフロー・・各々が自らの最適を目指した場合
総コスト
• 最適フロー
１
・・全体にとって最適を目指した場合
総コスト
３／４
• 無秩序の代償
•
ナッシュフロー／最適フロー ＝ ４／３ ≒ １．３３
Breass’s Paradox
x
上下のパスともコストは
１＋X なので
半分ずつのフローが流れる
v
s
１
t
０
１
w
x
コストは、上下それぞれ
１／２ × （１ ＋ １／２） ＝ ３／４
（フロー）
（コスト）
より、総コストは ３／２
⇒新たなパスを作ると
全てのフローが
s - v - w - t の順で流れて
１
×
２
＝
２
より、総コストは ２となる
パレート支配
C(x) =1
C(x) =1
S
T
C(x) =X
ナッシュフロー ２
最適フロー
１．５
C(x) =X
今までの例では、各ユニットごとに考えると、最適フローの時のコストは
常に最悪でもナッシュ均衡と同じか低くなる。
これを経済学の用語で、「ナッシュフローは最適フローにパレート支配される」
と表現する。
⇒ただし、これは常に成立するわけではない。
パレート支配的でない例
●ナッシュフロー
全てが下の道に１流れる
各ユニットのコストは１、総コストは１
C(x) =２－ε
ε ／２
S
T
１－ε ／２
●最適フロー
２－ε ＝ ２X より
上の道に ε／２
下の道に１－ ε ／２流れる
C(x) =X
(具体例)
上に流れたε／２のフローの
コストは、２－εとなり上昇する
総コストは、１－ε^2/4
C(x) =１．９
０．０５
S
T
０．９５
C(x) =X
具体的には、ε = 0.1の時は、
上の道に0.05のフローが流れ
１．９のコストがかかる
ナッシュフロー
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のエッジの並び順は、次の３つを満たすとき
f-monotoneである
– P1) sの順序が1番目
– P2) すべてのフローが、順番に流れる
– P3) エッジ間のdの値は、非減少である
Breass’s Paradox
x
v
s
１
t
０
１
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
ナッシュフローの定義２
• 同様に、すべてのエッジw ,v に対して、
d(w) - d (v) = Ce(fe) for e = (w,v)
が成立すれば、feはナッシュフローである。
この定義は、５．２において活用する。
© Copyright 2024 ExpyDoc
