Selfish routing 川原　純.

Presentation on theme: "Selfish routing 川原　純."— Presentation transcript:

1 selfish routing 川原　純

2 かかります。全体の平均遅延を最小にするために、
1.1 selfish routing とは （利己的ルーティング） 車でA町まで向かう途中… A町に行くには2つの道があります。 左の道は 30分 右の道は 50分 かかります。全体の平均遅延を最小にするために、 あなたは右へ行ってください。 どちらへ行きますか？ おせっかいなカーナビ

3 } 1.1 selfish routing とは 重要な事実 人は皆、自分にかかるコストを最小にするように動く selfish この差を
（利己的ルーティング） 重要な事実 人は皆、自分にかかるコストを最小にするように動く selfish この差を 社会的繁栄の損失 とよぶ 神様が交通整理したときの平均遅延時間 人が利己的に動いたときの平均遅延時間 } selfish routing による社会的繁栄の損失を評価し、 なるべく損失を抑えるネットワークの設計が目標 交通網、コンピュータ ネットワークなど

4 1.2 研究の動機付けとなる2つの例題 ピゴーの例題　[Pigou, 1920] ブライスのパラドックス 　[Braess, 1968]

5 1.2.1 ピゴーの例題 A町からB町まで行く道が2つある 広くて遠い道 一律に60分かかる A B 車の台数に比例した 時間がかかる
1台→1分 狭くて近い道

6 1.2.1 ピゴーの例題 広くて遠い道 一律に60分かかる 60台 A B 車の台数に比例した 時間がかかる 1台→1分 狭くて近い道

7 1.2.1 ピゴーの例題 広くて遠い道 一律に60分かかる 60台 A B 車の台数に比例した 時間がかかる 1台→1分 狭くて近い道
明らかに、全員が下の道を選ぶ 平均遅延時間＝60分

8 1.2.1 ピゴーの例題 神様が交通整理をするなら selfish な振る舞いは社会的に最適であるとは限らない 広くて遠い道
一律に60分かかる 60台 30台 A B 30台 車の台数に比例した 時間がかかる 1台→1分 狭くて近い道 平均遅延時間＝60 × 0.5 ＋ 30 × 0.5 ＝ 45 分

9 1.2.2 ブライスのパラドックス 以降、交通の総量は 1 と仮定 枝のコスト関数を c(x) で表す c(x) = x v
s t c(x) = 1 w c(x) = x

10 1.2.2 ブライスのパラドックス selfish な場合 c(x) = x v c(x) = 1 0.5 s t 0.5 c(x) = 1
w c(x) = x 上の道: = 1.5 下の道: = 1.5

11 1.2.2 ブライスのパラドックス selfish な場合 社会的に最適な場合 c(x) = x v c(x) = 1 c(x) = x v
0.5 0.5 s t s t 0.5 0.5 c(x) = 1 w c(x) = x c(x) = 1 w c(x) = x 上の道: = 1.5 下の道: = 1.5 上の道: = 1.5 下の道: = 1.5

12 1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v
0.5 s t c(x) = 0 0.5 c(x) = 1 w c(x) = x 上の道: = 1.5 下の道: = 1.5

13 1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v
0.5 s c(x) = 0 t 0.5 c(x) = 1 w c(x) = x 上の道: = 1.5 下の道: = 1.5 の道: = 1

14 1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v
0.4 s 0.2 c(x) = 0 t 0.4 c(x) = 1 w c(x) = x 0.6 1.6 上の道: = 1.5 下の道: = 1.5 0.6 1.6 の道: = 1 0.6 0.6 1.2

15 1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v
0.3 s 0.4 c(x) = 0 t 0.3 c(x) = 1 w c(x) = x 0.7 1.7 上の道: = 1.5 下の道: = 1.5 0.7 1.7 の道: = 1 0.7 0.7 1.4

16 1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v
s 1 c(x) = 0 t c(x) = 1 w c(x) = x 1 2 上の道: = 1.5 下の道: = 1.5 1 2 の道: = 1 1 1 2

17 1.2.2 ブライスのパラドックス selfish な場合 社会的に最適な場合 c(x) = x v c(x) = 1 c(x) = x v
0.5 s 1 c(x) = 0 t s c(x) = 0 t 0.5 c(x) = 1 w c(x) = x c(x) = 1 w c(x) = x selfish routing では、見せかけの改良により、 効率が悪くなることがある 1 2 上の道: = 1.5 下の道: = 1.5 上の道: = 1.5 下の道: = 1.5 1 2 の道: = 1 1 1 2

18 2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ

19 2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の発生源
2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の発生源 source s1 s2

20 2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の吸収
2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の吸収 sink 交通の発生源 source t1 s1 t2 s2 single-commodity multicommodity source-sink のペア {si, ti } → commodity i

21 2.1 モデル : commodity i のパスの集合 t1 s1 t2 s2

22 2.1 モデル : commodity i のパスの集合 v s1 t1 w s1 → v → t1, s1 → v → w → t1, =
2.1 モデル : commodity i のパスの集合 v s1 t1 w s1 → v → t1, s1 → v → w → t1, s1 → w → t1 = 1

23 2.1 モデル : フロー : パスP を選んだ人の数 （十分大きいとする） v 0.5 s1 t1 0.5 w s1 → v → t1,
2.1 モデル : フロー : パスP を選んだ人の数 （十分大きいとする） v 十分大きくない場合の 考察は4.4節 0.5 s1 t1 0.5 w s1 → v → t1, s1 → v → w → t1, s1 → w → t1 = P1 = 0.5 1 = = P2 1 = 0 2 = P3 = 0.5 3

24 2.1 モデル : 枝に流れるフローの集合 e1 v 0.3 s1 0.7 e2 t1 e3 w = 0.3 + 0.7 = 1 = 0.7
2.1 モデル : 枝に流れるフローの集合 e1 v 0.3 s1 0.7 e2 t1 e3 w = = 1 1 = 0.7 2 = 0 3

25 2.1 モデル : commodity i に流れるフローの総量 r1 = 1 e1 v 0.3 s1 0.7 e2 t1 e3 w

26 2.1 モデル : コスト関数 : 枝 e のコスト関数 パス P のコスト ce1(x) = x v ce2(x) = 1 s 1
2.1 モデル : コスト関数 : 枝 e のコスト関数 パス P のコスト ce1(x) = x v ce2(x) = 1 s 1 ce3(x) = 0 t ce4(x) = 1 w ce5(x) = x 全パスのコストの総和

27 2.2 ナッシュフロー 定義2.2.1 がナッシュ均衡（ナッシュフロー）である def すべての commodity i について、
なるパス について、 すべての について が成り立つ － if = ＋ if otherwise

28 2.2 ナッシュフロー ピゴーの例題 c(x) = 1 f = 0 A B f = 1 c(x) = x c下 = 1 c(x) = 1
ナッシュフローの 条件に合う c(x) = x

29 2.2 ナッシュフロー ブライスのパラドックス （枝を加えた直後） c(x) = x v c(x) = 1 0.5 s c(x) = 0 t
c(x) = 0 t 0.5 c上 = 1.5 c(x) = 1 w c(x) = x c(x) = x v c(x) = 1 c中 = 1.1 0.5 – 0.1 s c(x) = 0 t c上 ≦ c 中なので ナッシュフローの 条件に合わない 0.5 c(x) = 1 w c(x) = x

30 2.2 ナッシュフロー ブライスのパラドックス （安定した後） c(x) = x v c(x) = 1 s 1 c(x) = 0 t
s 1 c(x) = 0 t c中 = 2 c(x) = 1 w c(x) = x c(x) = x v c(x) = 1 c上 = 2 s c(x) = 0 t c中 ≦ c 上なので ナッシュフローの 条件に合う c(x) = 1 w c(x) = x

31 2.2 ナッシュフロー 定理2.2.2 すべての commodity i について、 すべての なるパス について、

32 2.2 ナッシュフロー 系2.2.3 各 commodity i について、 なるパス すべての , について、
コスト ci(f) をもつ