Selfish Routing and the Price of Anarchy 第2回

Presentation on theme: "Selfish Routing and the Price of Anarchy 第2回"— Presentation transcript:

1 Selfish Routing and the Price of Anarchy 第2回

2 復習 扱っている問題 ナッシュフローと最適フロー ナッシュフローの性質

3 復習 コスト関数 （遅延を表す） の遅延． 60台 60 s t 平均遅延: 60×0 + 60×1 = 60 ナッシュフロー

4 復習 s t 60 30 s t 60台 60台 平均遅延: 60×0 + 60×1 = 60 ナッシュフロー
コスト関数 （遅延を表す） の遅延． 60台 s t 平均遅延: 60×0 + 60×1 = 60 60 ナッシュフロー の遅延． 平均遅延: 60× ×0.5 = 45 60台 30 s t 最適フロー

5 復習 s t 1 0.5 s t 1 1 平均遅延: 1×0 + 1×1 = 1 ナッシュフロー
コスト関数 （遅延を表す） の遅延． 1 s t 平均遅延: 1×0 + 1×1 = 1 1 ナッシュフロー の遅延． 1 0.5 s t 平均遅延: 1× ×0.5 = 0.75 最適フロー

6 復習 0.5 1 si ti フロー f がナッシュフロー si から ti へのパス に対し， si から ti へのパス に対し，
⇔ si から ti へのパス　　　　　　　　　　　　　 に対し，　　　　　　　　　　 1 0.5 全てのパスの遅延時間は2 si ti

7 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
2.7節 単品種ネットワークのナッシュフロー

8 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
　　　　　　最適フローの求め方 2.5節 例 2.6節 ナッシュフローの存在性と一意性 2.7節 単品種ネットワークのナッシュフロー

9 定義 2.4.2 ユークリッド空間上の2点 x, y の凸結合 (convex combination)． ⇔ x, y を結ぶ線分上の点．
(b) S ⊆ Rn が凸 (convex)． 　　 ⇔ 要素が凸結合で閉じている集合． (c) 関数 h: S → R が凸 (convex function)． 　　 ⇔ (d) 関数 c: R+ → R+ が準凸 (semiconvex function)． 　　⇔ x・c(x) が凸． （2階微分導関数が0以上） c を滑らかで非減少とすると， c が凸 ⇒ c が準凸

10 問題の定式化 Min. Subject to: (NLP) とする． ce が準凸 (he が凸) ⇒ 凸計画問題

11 最適フローの求め方 0.5 s t s t 0.5 1 ナッシュフロー コスト関数に x をかけて微分 このネットワークでのナッシュフローは
元のネットワークの最適フローとなっている．

12 最適フローの特徴付け s t 定義 2.4.5 系 2.4.6 フロー f が最適 ⇔ f は(G, r, c*)のナッシュフロー．
を限界コスト関数 (marginal cost function) と定義する． 系 2.4.6 (G, r, c) を滑らかで準凸なコスト関数を持つインスタンスとする． フロー f が最適 ⇔ f は(G, r, c*)のナッシュフロー． 証明： 次の命題の(a)と(b)から．

13 命題 2.4.4 f*: NLPの実行可能解 he= c(x)・x: 滑らか，凸． (a)～(d)は同値． (a) f* が最適フロー
(b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し， (c) 全ての実行可能なフロー f に対し， (d) 全ての実行可能なフロー f に対し，

14 命題 2.4.4 の証明 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し，
(c) (d) (c) ⇔ (d) Σの順番をいれかえ． (b) ⇔ (c) (b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し， P1 を定義 f* を固定すると，定数コストのネットワークにおける f の平均遅延を表す式となる． (b) は元のネットワークで f*P > 0 のパスは，固定後にコスト最小のパスとなると言っている． (c) の左辺は，f* を流したときの平均遅延，右辺はその他のフロー平均遅延．

15 命題 の証明 (a) ⇒ (b) (a) f* が最適フロー (b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し， f* のうち，f*P1 > 0 となるパス P1 のフローの微小量 λを P2 に流れるフローに加えると， 目的関数値は， に変化する．f* の最適性から [・] 内は 0 以上． P1 P2

16 命題 2.4.4 の証明 he は凸 (d) ⇒ (a) (d) (a) f* は最適フロー f を任意の実行可能フローとする．

17 その他の事実 事実 2.4.9 事実 2.4.12 コスト関数c が準凸のとき，最適フローは，任意に小さい誤りで，
入力サイズと要求された正確さ(precision)のビット数の多項式時間で計算できる． ・ 入力サイズについては正確に議論しない (remark )． ・ 誤りを含むのは，最適フローが無理数だとしても 　既存の凸計画問題のアルゴリズムは有理数を出力するため (remark )． 事実 コスト関数 c が任意のとき，入力サイズと近似の正確さのビット数の 多項式時間で近似解を計算するアルゴリズムは存在しない if P≠NP． ・ 下界: ω(n1-ε)．

18 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
　　　　　 いくつかの例を紹介 2.6節 ナッシュフローの存在性と一意性 2.7節 単品種ネットワークのナッシュフロー

19 例 2.5.3 (強パレート suboptimality)
枝追加後の Braess’s paradox のナッシュフローは最適フローに強パレート支配される． しかし，枝の削除 (追加する前) によってナッシュフローは改善され， 最適フローの強パレート支配ではなくなる． x 1 ナッシュフロー x 1 0.5 1 s t s t 1 0.5 x 1 x 枝の追加 x 1 x 1 0.5 0.5 s t s t 最適フロー 0.5 1 0.5 x 1 x

20 例 2.5.3 (強パレート suboptimality)
ナッシュフローが最適フローに強パレート支配され， かつどの枝を削除しても強パレート支配される例を示す． 1 1 s t 1 ナッシュフロー コスト（遅延）は2 x x

21 例 2.5.3 (強パレート suboptimality)
ナッシュフローが最適フローに強パレート支配され， かつどの枝を削除しても強パレート支配される例を示す． 1 1 s t ナッシュフロー x x 1 コスト（遅延）は2 1 1 0.5 最適フロー それぞれのパスの コスト（遅延）は1.5 s t x x

22 例 (非線形な Pigou の例) Pigou の例，Bｒaess’s paradox，例 2.5.3の price of anarchy は 3/4． これは偶然ではなく，コスト関数が線形のときは高々3/4 となる (3章)． しかし，線形ではないときには price of anarchy が任意に大きくなる場合がある． 1 s t ナッシュフローは下のリンクに1． 平均遅延は1． 1 (G, r, c)

23 例 (非線形な Pigou の例) Pigou の例，Bｒaess’s paradox，例 2.5.3の price of anarchy は 4/3． 偶然ではなく，コスト関数が線形のときは高々4/3 となる (3章)． しかし，線形ではないときには price of anarchy が任意に大きくなる場合がある． 1 1 s t s t (G, r, c) (G, r, c*) ナッシュフローは下のリンクに1． 平均遅延は1． 最適フローは，上のリンクに　　　　　　　　　　　下のリンクに 平均遅延は

24 例 2.5.5 (最適フローの不公正性) s t 2－ε 1 今までの例では， 全てのトラフィックにおいて最適フローの各々のパスの遅延は
ナッシュフローよりコストが優るか同等だった． 一部のトラフィックを犠牲にしてコストを最小とする最適フローの例を示す． 2－ε s t ナッシュフローは下のリンクに1．遅延は1． 1 (G, r, c)

25 例 2.5.5 (最適フローの不公正性) s t s t 2－ε 2－ε 2－εの遅延 の遅延 今までの例では，
全てのトラフィックにおいて最適フローの各々のパスの遅延は ナッシュフローよりコストが優るか同等だった． 一部のトラフィックを犠牲にしてコストを最小とする最適フローの例を示す． 2－ε 2－ε s t s t (G, r, c) (G, r, c*) ナッシュフローは下のリンクに1．遅延は1． 2－εの遅延 の遅延 最適フローは，上のリンクに　　　　　　下のリンクに 平均遅延は

26 例 2.5.6 (多品種の Braess’s paradox)
Bｒaess’s paradox の多品種版(品種が2つ) 　（コスト 0 の 枝を加えたらナッシュフローの平均遅延が増大） t2 s2 v 1 s1 t1 1 w ナッシュフロー： 品種1 のコストは　　　　　　　　　品種2 のコストは p → ∞ で 1 と 0 になる．

27 例 2.5.6 (多品種の Braess’s paradox)
Bｒaess’s paradox の多品種版(品種が2つ) 　（コスト 0 の 枝を加えたらナッシュフローの平均遅延が増大） t2 s2 v 1 s1 t1 1 w 枝を加えた後のナッシュフロー： 品種1 のコストは 2，品種2 のコストも 1． 従って，枝 (v,w)　を加える前後において，p を大きくするとコストの差は大きくなる． 元のネットワークのナッシュフロー： 品種1 のコストは　　　　　　　　　品種2 のコストは p → ∞ で 1 と 0 になる．

28 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
2.7節 単品種ネットワークのナッシュフロー

29 2.6節 ナッシュフローの存在性と一意性 ⇔ ⇔ (G, r, c*) のナッシュフロー (G, r, c) の最適フロー

30 命題 2.6.1 (CP) Min. Subject to: とする． ・ CP の最適フローは NLP のナッシュフロー．
・ CPは凸計画問題 （ce(x) は非減少関数だから，he の2階微分は非負で he は凸）． ・ 実行可能領域は有界閉集合で目的関数は連続 → 最適解(ナッシュフロー)が存在．

31 ナッシュフローの一意性 s t 1 上のネットワークでは全ての実行可能フローがナッシュフローとなる．
ナッシュフローは厳密に一意となるわけではない．

32 ナッシュフローの一意性 系 2.6.2 f と がナッシュフローのとき，全てのe ∈ E で 証明 f と の凸結合を考える．
CPは凸計画問題なので実行可能解． をCPの目的関数とすると，凸関数なので， はCPの最適解 つまり，　　　　　　　　　　 も最適解で，上式の等号が成立． 従って，　　　　　　　　　　　　　　　　　　　　において h は線形関数で，h は c の積分だから，c は定数関数となる．

33 ナッシュフローの一意性 系 2.6.2 系 2.6.3 系 2.6.4 f と がナッシュフローのとき，全てのe ∈ E で
を満たすとき， 　はナッシュフローである． 系 2.6.4 f と がナッシュフローのとき，ce が狭義増加関数なら

34 ナッシュフローの一意性 系 2.6.6 系 2.6.7 f がナッシュフロー ⇔ あらゆる 実行可能なフロー f* に対し，
略証： 命題 から， 系 2.6.7 ナッシュフローは，任意に小さい誤りで， 入力サイズと要求された正確さ(precision)のビット数の多項式時間で計算できる．

35 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
2.7節 単品種ネットワークのナッシュフロー 　　2.7.1 Classical Network Flow Theory 　　　　　 　　　フローに関する古典的な結果と，導かれる本問題のフローの性質． 　　2.7.2 Monotone Orderings

36 命題 2.7.1 s (G, r, c) を単品種のインスタンスとする．
(a) f が(G, r, c) の実行可能フローのとき，下の線形システムの実行可能解となる． s δ+ (v) はvを始点とする枝の集合， δ- (v) はvを終点とする枝の集合． (b) f を上の線形システムの実行可能解とするとき， 　　全ての e で　　　　　　となる(G, r, c) の実行可能フロー　　　　　　が存在する．

37 命題 2.7.2 f が(G, r, c) の実行可能フロー，S が G の s-t カットのとき， ( 　　 の合計) － (　　　 の合計) = r s t S G

38 命題 2.7.3 f が(G, r, c) の実行可能フローのとき， 有向閉路のない実行可能フロー で，
有向閉路のない実行可能フロー　　　　　で，　 全ての枝 e に対し　　　　　であるものが存在する． フローの有向閉路 ⇔ fe >0 の e からなる 　　有向閉路． 証明 2 6 2 5 4 3 3 6 3 5 5 5 1 1 閉路内の枝でフローが最も小さいものを選び， その値を閉路内のフローからひく この操作で新たに構成したフロー は命題2.7.1の線形システムを満たす． また，命題2.7.1 (b) から となる (G, r, c) の実行可能フロー　　が存在． この操作を閉路がなくなるまで繰り返す．

39 発表内容 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性
2.7節 単品種ネットワークのナッシュフロー 　　2.7.1 Classical Network Flow Theory 　　2.7.2 Monotone Orderings 単品種のネットワークにおけるナッシュフローの性質

40 命題 2.7.4 単品種ネットワークのインスタンスは有向閉路のないナッシュフローを持つ． 略証
・ ナッシュフローの存在性は命題 2.2.5による． ・ 命題 から，ナッシュフロー ⇔ 凸計画問題CPの最適解． ・ 命題 から，あるナッシュフロー f について， 　全ての枝 e で　　　　　 となる有向閉路のない実行可能フロー　　 が存在． ・ f はCPの最適解だから　　も最適解であり，ナッシュフローである．

41 定義 2.7.5 f をナッシュフローとする． d(v) ⇔ 枝の長さを ce(fe) としたときの s から v への最短経路の長さ． 0.5 d(v) = 2 1 0.5 1 s v t 節点の順序付けが f-monotone ⇔ 次の (P1) ~ (P3) を満たす． 　 (P1) ソース s が一番目． (P2) フローはこの順序に逆らわずに節点を辿る． (P3) d(v) の値がこの順序で非減少． f に有向閉路がある場合， f-monotone ordering は存在しない． 2 1 5 6 4 s 3 t

42 命題 2.7.7 v s w f: 実行可能フロー ・ 全ての枝 e = (v, w) に対し，
・ f がナッシュフロー ⇔ 全ての fe > 0 で上の不等式の等号成立 証明 v d(・) は最短経路の長さなので3角不等式が成立． s w

43 命題 2.7.7 s t G f: 実行可能フロー ・ 全ての枝 e = (v, w) に対し，
・ f がナッシュフロー ⇔ 全ての fe > 0 で上の不等式の等号成立 証明 s t ・・・ v w ・・・ G fP > 0 とする． f がナッシュフロー ⇔ 　　　　　　　　　　 (命題2.2.2) ⇔ 上式の等号成立．

44 命題 2.7.8 f が有向閉路のないナッシュフローならば f-monotone ordering が存在する． 証明
・ (P1) と (P2) を満たすように，フローが0より大きい枝に対するトポロジカルソート 　(有向枝 u,v が存在する2頂点に関して，uの方がvより小さい番号になる順番付け ) 　を求めることができる．(greedyアルゴリズム) ・ ある x, y (y より x が前) が (P3) を満たさない (d(x)>d(y)) とき， 　ある順序が隣接するペア v, w で (P3) を満たさないものが存在． ・ v と w の順番を入れ替えても (P1) と (P2) は満たされる． 　何故なら，d(s) = 0 で d は非負だから，明らかに (P1) は満たされる． 　 v, w の間に fe > 0 となる枝 e=(v, w) は存在しない． (存在すると，d(w)－d(v) = ce(fe) (命題2.7.7))． 　　　　　　　つまり，v, w を入れ替えても (P2) は満たされる． w 1.5 s 0.5 u 1 節点の順序付けが f-monotone ⇔ 次の (P1) ~ (P3) を満たす． 　 (P1) ソース s が一番目． (P2) フローはこの順序に逆らわずに節点を辿る． (P3) d(v) の値がこの順序で非減少． 1 v トポロジカルソート v, w, u d(・) = 1, 0.5, 2

45 まとめ 2.4節 最適フローの特徴付け 2.5節 例 2.6節 ナッシュフローの存在性と一意性 2.7節 単品種ネットワークのナッシュフロー
　　　　　　最適フローの求め方 2.5節 例 2.6節 ナッシュフローの存在性と一意性 2.7節 単品種ネットワークのナッシュフロー 　　2.7.1 Classical Network Flow Theory 　　　　　 　　　フローに関する古典的な結果と，導かれる本問題のフローの性質． 　　2.7.2 Monotone Orderings 　　　　　単品種のネットワークにおけるナッシュフローの性質