ch3-4-7

計算量理論
第3章 4節
社会情報学専攻
ナレッジクラスタ講座M1
岩木 祐輔
前回までの話 その1
• ナッシュフロー
– みんなが利己的にふるまったとき(ナッシュ均衡)
のフロー
• 最適フローを求めるには?
–
を求めて
– そのナッシュフローを計算
• 無秩序の代償
前回までの話 その2
• 無秩序の代償はどのくらいか?
– 上は?
rは総トラフィック
・・・定数
無秩序の度合い
直感的には
「利己的な振る舞い(ナッシュフロー)が
いかに迷惑になるか」の度合い
今回の話
• いろんなネットワークを考えて
上の関係の等号が成り立つのか?
• 考える事例
– Cが定数関数を含むとき(これまでの話)
– Cがdiverseのとき
– Cがinhomogeneousのとき
(定義は後ほど…)
今回の話(結論から)
• 2-Link,2-Nodeの時に最悪なことが起こるのは
– Cが定数関数を含むとき(これまでの話)
• m-Link,2-Nodeの時に
〃
– Cがdiverseのとき
• パスの結合なグラフの時に
– Cがinhomogeneousのとき
〃
・
・
・
注 「必ず起こる」かどうかについては言及されていない
まずは関数の形に注目
(準備)コスト関数の図形的理解
「最善の関数」
• 無秩序の度合い(anarchy value)
– ルーティングの話は抜きに
関数の式の形だけで見ると…
– コスト関数が定数なら
20
• つねに1
– 〃
15
単調増加なら
10
• 最小値は1
→定数が「最善の関数」
5
1
1
2
3
4
5
6
「最悪の関数」
• 無秩序の度合い(anarchy value)
20
15
10
この部分が
大きいほど悪い
5
1
2
3
4
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
1
0.2
0.4
0.6
0.8
1.0
0
1
2
3
4
5
5
6
(本題) Cの性質を考慮して
無秩序の代償を 分析する
今回の話
• 2-Link,2-Nodeの時に最悪なことが起こるのは
– Cが定数関数を含むとき(これまでの話)
• m-Link,2-Nodeの時に
〃
– Cがdiverseのとき
• パスの結合なグラフの時に
〃
– Cがinhomogeneousのとき
・
・
・
Cがdiverse(多様)
• 関数集合Cが多様である
を満たすような
が存在する。
例
Cがdiverseのとき
• 命題
・
・
・
2-node,m-edge ならば以下が成立する
証明(1/4)
となるような
Cは多様なので
右図のように
が取れる
ここで、下のようなグラフ
(もっとも最悪なケース)の
最適フローを考える
・
・
・
最適フロー
を選ぶ
証明(2/4)
・
・
・
δ
最適フロー
どんなδに対してもmが十分に大きくとれば
が成り立つ。(コスト関数は連続なので)
証明(3/4)
・
・
・
・
・
・
ナッシュフロー
最適フロー
証明(3/4)
・
・
・
・
・
・
ナッシュフロー
最適フロー
証明(3/4)
・
・
・
・
・
・
ナッシュフロー
最適フロー
証明(4/4)
δ→0とすると
・・・
なので、
εは任意に小さく取れるので、
の定義そのもの
今回の話
• 2-Link,2-Nodeの時に最悪なことが起こるのは
– Cが定数関数を含むとき(これまでの話)
• m-Link,2-Nodeの時に
〃
– Cがdiverseのとき
• パスの結合なグラフの時に
– Cがinhomogeneousのとき
〃
Cがhomogeneous(一様)
• 関数集合Cが一様である
Cが一様ではない
Cが多様
一様でない
一様でも多様でもない例
多様
Cが一様でないとき
• 命題
・
・
・
union of path(パスの結合) ならば以下が成立する
Cが一様でないとき
• 証明の方針
変換
Cは一様でない
・
・
・
Cは多様
・
・
・
証明(1/4)
まず、Cを以下のように拡張して考える
Cは一様ではないので、
となるcが必ず存在するので、
20
は多様である
15
また、β倍しても無秩序の度合いは等しいので
10
5
1
1
2
3
4
5
6
証明(2/4)
フローは途中でなくなったりしないので
上のような直列のパスの全体のコスト関数をcとすると
等価
証明(3/4)
・
・
・
・
・
・
以下の条件を満たすように
各枝をそれぞれ(うまく)スカラー倍
m-link, 2-nodeの場合に帰着
・
・
・
証明(4/4)
は多様であるから、
・
・
・
より、
・
・
・
m-link, 2-nodeの場合に帰着
εは任意に小さく取れるので、
ここまでのまとめ
• 2-Link,2-Nodeの時に最悪なことが起こるのは
– Cが定数関数を含むとき
• m-Link,2-Nodeの時に
〃
– Cがdiverseのとき
• パスの結合なグラフの時に
– Cがinhomogeneousのとき
〃
さらに一般化すると・・・
グラフ集合Gの性質を考慮する
グラフ集合Gがtrivial
• グラフ集合Gがtrivialであるとは
すべてが「一本道の集合」であること
このとき、
これは自明。
• Gがnon-trivialならば
計算量理論
第3章 5節
これまで
• いろいろな形のネットワークで
「最悪の場合」を見つけて、
無秩序の代償の上限を求めた
・
・
・
・
・
・
今回の話
1. コスト関数が「多項式だけ」であるとすれ
ば?
2. コスト関数がM/M/1(待ち行列)関数なら?
• 結論から言うと、
– 「無秩序の代償は変化率の大きい関数でない
限り、小さい」
(1より)
– 「無秩序の代償は、トラフィックがに余裕が
あれば、小さい」 (2より)
コスト関数が多項式のとき
• 命題
以下が成り立つ
コスト関数が多項式のとき
• 証明の方針
変換
・
・
・
・
・
・
・・・一様でない
・・・多様
証明(1/4)
直列につないだ場合の無秩序の代償
を
に内分する点
証明(2/4)
直列につないだ場合の無秩序の値
証明(2/4)
直列につないだ場合の無秩序の値
証明(2/4)
直列につないだ場合の無秩序の値
20
15
10
5
1
1
2
3
4
5
6
証明(3/4)
ナッシュフロー
r
最適フロー
証明(4/4)
ここまで示された
証明(4/4)
(ロピタルの定理を2回使う、詳細は略)
コスト関数が多項式のとき
「無秩序の代償は変化率の大きい関数でない限り、小さい」
コスト関数がM/M/1関数のとき
(引用: http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/?ST=start2)
コスト関数がM/M/1関数のとき
ナッシュフロー
r
最適フロー
コスト関数がM/M/1関数のとき
↑
「トラフィックに余裕があれば、利己的ルーティングでもよい」
計算量理論
第3章 6節
今回の話
• 結論だけ先に言うと
最適化を頑張ることより
道路改良を行うほうがよい
トラフィックが増えると・・・
r=1のとき
トラフィックが増えると・・・
r=1のとき
r=2のとき
トラフィックが増えると・・・
r=1のとき
r=2のとき
トラフィックが増えると・・・
ナッシュフローの
コストは1
r=1のとき
最適フローの
コストは7/4
r=2のとき
トラフィックの増加
• 命題
のナッシュフロー
の最適フロー
とすると、
が成り立つ。
トラフィックの増加
• 命題(
)のとき
のナッシュフロー
の最適フロー
とすると、
が成り立つ。
証明(1/4)
• コスト関数を変換
証明(2/4)
のナッシュフロー
の最適フロー
証明(2/4)
のナッシュフロー
最適フロー
の最適フロー
について、
の代わりに
コストの増加分はせいぜい
を用いた際の
程度。
証明(3/4)
単位フローあたりのコスト
証明(3/4)
単位フローあたりのコスト
ナッシュフローなので、定数
証明(3/4)
単位フローあたりのコスト
証明(3/4)
単位フローあたりのコスト
証明(4/4)
以上の2式
より、
が成り立つ。
逆の発想
先の命題の仮定
のナッシュフロー
の最適フロー
2倍のフローを流したとき
単位フロー当たりのコストが半分
=
2倍のフローを流したとき
総コストが等しい
とすると、
逆の発想
先の命題の仮定
のナッシュフロー
の最適フロー
とすると、
のナッシュフロー
の最適フロー
とすると、
まとめ
のナッシュフロー
の最適フロー
・・・
2倍のトラフィックがあっても
単位フロー当たりのコストがもとの半分
とすると、
最適化を頑張ることより
道路改良を行うほうがよい
※道路改良・・・それぞれのルートのキャパシティを2倍にする
今回の話
• コスト関数の制約をもっと緩めても
上の関係は成り立つ
• 制約をどう緩めていくか
– Cが定数関数を含むとき(これまでの話)
– Cがdiverseのとき
– Cがinhomogeneousのとき
(定義は後ほど…)
Cがdiverseのとき
• 証明のアプローチ
・・・証明済み
ナッシュ均衡
• 「単位フローあたりのコストが等しい」は
どこに現れるか
ナッシュ均衡
• 「単位フローあたりのコストが等しい」は
どこに現れるか
ナッシュ均衡
• 「単位フローあたりのコストが等しい」は
どこに現れるか
最適フロー
• 「総コストが最小」はどこに現れるか
最適フロー
• ナッシュフローとの比較
コスト関数に定数を含むとき
• 定数=「最善の関数」
コスト関数を定数でなくすと
• 「最善」より少し悪い関数だと・・・
単位フローあたりのコストが
等しい定数関数と比べて
無秩序の代償が小さい
無秩序の代償
• 定義式を見てみると・・・
を
のいずれと取り替えて
2経路を作っても
その無秩序の代償は(*)を
より大きくなることはない。
何でいまさら?
• まず、もっとも単純な例
– (今まで扱ってきた例)
上の定義を少し変形して
Cが定数関数を含む場合
• 条件を少し変えてみる・・・
総流量1
総流量r
は減少
Cが定数関数を含む場合
• つなげてみる
を
に内分する点
Cがdiverseのとき
• 定数を含んでいたら
等号が成り立つことは前回示された
(定数関数と「最悪の関数」の2ルート場合など)
• 含まないときも上限は
なのか?
復習
• まず、もっとも単純な例
– (今まで扱ってきた例)
上の定義を少し変形して
何でいまさら?
• これまで
数々の不等号が出てきたが
等号の成り立つ時については
議論してこなかった
本当はもっと小さい数でおさえられることがあるかも?
定数関数を含むとき
両辺の和をとると
がナッシュフローなので、
前回の話にあった
を用いて、
ナッシュ
フロー
最適フロー
上リンク
0
1/2
下リンク
1
1/2
総コスト
1
3/4
ナッシュ
フロー
最適フロー
上リンク
1
3/2
下リンク
1
1/2
総コスト
2
7/4