Selfish Routing and the Price of Anarchy

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

1 Selfish Routing and the Price of Anarchy
川原　純

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 ピゴーの例題 10台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台：1分

7 1.2.1 ピゴーの例題 10台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台：1分
全車が下の道を選ぶ 簡単のため、この場合は全車が10分かかるとする

8 1.2.1 ピゴーの例題 60台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台：1分

9 1.2.1 ピゴーの例題 60台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台：1分
全車が下の道を選ぶ 平均時間は 60 分

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

11 ナッシュフロー 30台 90台 広いが、長い道 広いが、長い道 一律に60分かかる A B 60台 狭いが、短い道 車の台数に比例した
時間がかかる 1台：1分 どちらを通っても60分かかる。 このようなバランスされた状態をナッシュ均衡と呼ぶ このフローをナッシュフローと呼ぶ 詳しい定義は2章で

12 無秩序さの代償 60台 広いが、長い道 一律に60分かかる A B 60台 狭いが、短い道 車の台数に比例した 時間がかかる 1台：1分
神様が交通整理すると45分のところ、60分かかる場合、 この比　60/45 = を無秩序さの代償 （price of anarchy） と呼ぶ 詳しい定義は2章で

13 1.2.1 ピゴーの例題 以降、交通の総量は 1 と仮定 枝のコスト関数を c(x) で表す c(x) = 1 A B c(x) = x

14 1.2.2 ブライスのパラドックス 次のようなネットワークを考える c(x) = x v c(x) = 1 s t c(x) = 1 w

15 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

16 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

17 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

18 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

19 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

20 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

21 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

22 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

23 1.3 応用 1.3.1 交通ネットワーク 1.3.2 コンピュータネットワーク 1.3.3 物理、工学
交通ネットワーク 昔から研究されている。数百の論文がある コンピュータネットワーク 当然、幅広く研究されている 物理、工学

24 物理への応用 理想バネ バネの長さは重りの重さに比例する

25 物理への応用

26 物理への応用

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

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

29 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 } → 品種 i (commodity)

30 パスとパスの集合 v パス P1 P2 s1 t1 P3 w P5 s2 P4 t2 P1 : P2 : P3 : s1 → v → t1,
s1 → v → w → t1, s1 → w → t1 P4 : P5 : s2 → w → t2, s2 → v → w → t2, : commodity i のパスの集合 = { P1, P2, P3 } = { P4, P5 } 1 2

31 フロー : フロー : パスP の流量 車の台数など（エージェント） P2 v P1 0.3 0.7 s1 t1 P3 w = 0.3
エージェントの数は十分大きいとする 0.3 0.7 s1 十分大きくない場合の 考察は4.4節 t1 P3 w = 0.3 1 P1 : P2 : P3 : s1 → v → t1, s1 → v → w → t1, s1 → w → t1 = 0.7 2 = 0 3 = { P1, P2, P3 } 1

32 枝ごとに見たフロー : 枝を流れるフロー e1 v 0.3 s1 0.7 e2 t1 e3 w = 0.3 + 0.7 = 1 = 0.7

33 フローの総量 ri : commodity i に流れるフローの総量(traffic rate) + + = 0.3 + 0.7 + 0
v 0.3 s1 0.7 e2 t1 が成り立つ時、 f を実現可能流と呼ぶ (feasible) e3 w P1 : P2 : P3 : s1 → v → t1, s1 → v → w → t1, s1 → w → t1 1 2 3 = = 1 = r1 = { P1, P2, P3 } なので f は実現可能流 1

34 コストとコスト関数 （車などの）エージェントが枝を流れるときにはコストがかかる ce1(x) = 1 e1 e2 ce2(x) = x
枝に流れる流量によってコストが決まる → コスト関数 c(x) : 枝 e のコスト関数 ce1(x) = 1 e1 e2 ce2(x) = x

35 コストとコスト関数 ce1(x) = 1 e1 e2 ce2(x) = x ce2(0.4) = 0.4 0.4 × 0.4 = 0.16
0.6 0.4 e2 ce2(x) = x 下の枝の（単位フロー当りの）コスト ce2(0.4) = 0.4 エージェントのそれぞれに0.4のコストがかかる 下の枝の全体コストは 0.4 × 0.4 = 0.16 上の枝の全体コストは Ce1(0.6) × 0.6 = 1 × 0.6 = 0.6

36 複数のフローとコスト ce3(x) = 3x ce1(x) = 1 ce2(x) = 1
：パス P の（単位フロー当りの）コスト P1 0.6 ce3(x) = 3x ce1(x) = 1 ce2(x) = 1 0.4 P1の総コストは c P1(f) = ce1(fe1) + ce3(fe3) 4 ×0.6 = 2.4 = ce1(0.6) + ce3(1) = 1 + 3×1 = 4

37 コスト関数の計算例 c P2 (f) = ce1(fe1) + ce3 (fe3) + ce5(fe5) ce1(x) = x v
0.3 P2 s ce3(x) = 0 t 0.7 P3 ce4(x) = 1 w ce5(x) = x ：パス P の（単位フロー当りの）コスト c P2 (f) = ce1(fe1) + ce3 (fe3) + ce5(fe5) 1 0.7 0.7 = = 1.7 同様に cP1(f) = 2, cP3(f) = 1.7

38 パスPの総コスト C(f) = cP1(f) fP1+ cP2 (f) fP2 + cP3(f) fP3 ce1(x) = x v
: コスト関数 P1 0.3 P2 : 枝 e のコスト関数 s ce3(x) = 0 t 0.7 P3 ：パス P のコスト ce4(x) = 1 w ce5(x) = x ：全パスのコストの総和 0.3 0.7 C(f) = cP1(f) fP1+ cP2 (f) fP2 + cP3(f) fP3 2 1.7 1.7 = 2 × × × 0 = 1.79

39

40 発表時の注意 （紙の）資料は必ず作ること スライドは（式よりも）図を使う。 具体例、計算例を必ず出す（教科書にはないので自分で作る）
（本スライド35ページ中、32ページに図があります） 具体例、計算例を必ず出す（教科書にはないので自分で作る） 記号が多いので、見せ方を工夫する たとえば、いきなり と書かれて 何だったか思い出せますか？

41

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

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

44 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

45 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

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

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