selfish1

selfish routing
川原純
1.1 selfish routing とは
（利己的ルーティング）
車でA町まで向かう途中…
どちらへ行きますか？
A町に行くには2つの道があります。
左の道は 30分
右の道は 50分
かかります。全体の平均遅延を最小にするために、
あなたは右へ行ってください。
おせっかいなカーナビ
1.1 selfish routing とは
（利己的ルーティング）
重要な事実
人は皆、自分にかかるコストを最小にするように動く
selfish
この差を
社会的繁栄の損失
とよぶ
selfish routing による社会的繁栄の損失を評価し、
なるべく損失を抑えるネットワークの設計が目標
神様が交通整理したときの平均遅延時間
人が利己的に動いたときの平均遅延時間
}
交通網、コンピュータ
ネットワークなど
1.2 研究の動機付けとなる2つの例題
ピゴーの例題 [Pigou, 1920]
ブライスのパラドックス [Braess, 1968]
1.2.1 ピゴーの例題
• A町からB町まで行く道が2つある
広くて遠い道
A
一律に60分かかる
B
狭くて近い道
車の台数に比例した
時間がかかる
1台→1分
1.2.1 ピゴーの例題
広くて遠い道
一律に60分かかる
60
台
A
B
狭くて近い道
車の台数に比例した
時間がかかる
1台→1分
1.2.1 ピゴーの例題
広くて遠い道
一律に60分かかる
60
台
A
B
狭くて近い道
明らかに、全員が下の道を選ぶ
平均遅延時間＝60分
車の台数に比例した
時間がかかる
1台→1分
1.2.1 ピゴーの例題
• 神様が交通整理をするなら
selfish な振る舞いは社会的に最適であるとは限らない
広くて遠い道
一律に60分かかる
60
台
30台
A
30台
狭くて近い道
B
車の台数に比例した
時間がかかる
1台→1分
平均遅延時間＝60 × 0.5 ＋ 30 × 0.5 ＝ 45 分
1.2.2 ブライスのパラドックス
以降、交通の総量は 1 と仮定
枝のコスト関数を c(x) で表す
c(x) = x
v
c(x) = 1
s
t
c(x) = 1
w
c(x) = x
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
c(x) = 1
0.5
s
t
0.5
c(x) = 1
w
c(x) = x
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
社会的に最適な場合
c(x) = 1
c(x) = x
0.5
c(x) = 1
0.5
s
t
s
t
0.5
c(x) = 1
v
0.5
w
c(x) = x
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
c(x) = 1
w
c(x) = x
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
渋滞を緩和するため、
道路を追加することを考える
v
c(x) = 1
0.5
s
0.5
c(x) = 1
c(x) = 0
w
c(x) = x
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
t
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
渋滞を緩和するため、
道路を追加することを考える
c(x) = 1
0.5
s
c(x) = 0
0.5
c(x) = 1
w
c(x) = x
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
の道: 0.5 + 0 + 0.5 = 1
t
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
渋滞を緩和するため、
道路を追加することを考える
c(x) = 1
0.4
s
0.2 c(x) = 0
t
0.4
c(x) = x
c(x) = 1
w
0.6
1.6
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
0.6 1.6
の道: 0.5 + 0 + 0.5 = 1
0.6
0.6 1.2
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
渋滞を緩和するため、
道路を追加することを考える
c(x) = 1
0.3
s
0.4 c(x) = 0
t
0.3
c(x) = x
c(x) = 1
w
0.7
1.7
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
0.7 1.7
の道: 0.5 + 0 + 0.5 = 1
0.7
0.7 1.4
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
渋滞を緩和するため、
道路を追加することを考える
c(x) = 1
0
s
1 c(x) = 0
0
c(x) = 1
w
c(x) = x
1
2
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
1
2
の道: 0.5 + 0 + 0.5 = 1
1
1
2
t
1.2.2 ブライスのパラドックス
selfish な場合
c(x) = x
v
社会的に最適な場合
c(x) = 1
c(x) = x
0
s
v
c(x) = 1
0.5
1 c(x) = 0
0
t
s
0.5
c(x) = 0
c(x) = x
c(x) = x
c(x) = 1
w
selfish routing では、見せかけの改良により、
効率が悪くなることがある
1
2
上の道: 0.5 + 1 = 1.5
上の道: 0.5 + 1 = 1.5
下の道: 1 + 0.5 = 1.5
下の道: 1 + 0.5 = 1.5
1
2
の道: 0.5 + 0 + 0.5 = 1
1
1
2
c(x) = 1
w
t
2.1 モデル
交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、
E は有向辺集合、多重辺をもつ
2.1 モデル
交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、
E は有向辺集合、多重辺をもつ
交通の発生源
source
s1
s2
2.1 モデル
交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、
E は有向辺集合、多重辺をもつ
交通の発生源
source
s1
t1
交通の吸収
sink
t2
s2
single-commodity
multicommodity
source-sink のペア {si, ti } → commodity i
2.1 モデル
: commodity i のパスの集合
s1
t1
t2
s2
2.1 モデル
: commodity i のパスの集合
v
s1
t1
w
1
s1 → v → t1,
= s1 → v → w → t1,
s1 → w → t1
2.1 モデル
: パスP を選んだ人の数
: フロー
v
（十分大きいとする）
十分大きくない場合の
考察は4.4節
0.5
s1
0
t1
0.5
w
1
s1 → v → t1,
= P1
= s1 → v → w → t1, = P2
s1 → w → t1
= P3
1
= 0.5
2
=0
3
= 0.5
2.1 モデル
: 枝に流れるフローの集合
e1
0.3
0.7 e2
s1
e3
1
2
3
v
w
= 0.3 + 0.7 = 1
= 0.7
=0
t1
2.1 モデル
: commodity i に流れるフローの総量
e1
0.3
0.7 e2
s1
e3
r1 = 1
v
w
t1
2.1 モデル
: コスト関数
: 枝 e のコスト関数
パス P のコスト
ce1(x) = x
v
ce2(x) = 1
0
s
0
ce4(x) = 1
1 ce3(x) = 0
w
t
ce5(x) = x
全パスのコストの総和
2.2 ナッシュフロー
• 定義2.2.1
def
がナッシュ均衡（ナッシュフロー）である
すべての commodity i について、
すべての
なるパス
について、
すべての
について
が成り立つ
=
－
if
＋
if
otherwise
2.2 ナッシュフロー
ピゴーの例題
f=0
A
f=1
c(x) = 1
B
c(x) = x
c下 = 1
f = 0 + 0.1 c(x) = 1
A
f = 1 – 0.1
c上 = 1
B
c(x) = x
c下 ≦ c 上なので
ナッシュフローの
条件に合う
2.2 ナッシュフロー
c(x) = x
v
ブライスのパラドックス
（枝を加えた直後）
c(x) = 1
0.5
s
0 c(x) = 0
t
0.5
c上 = 1.5
c(x) = 1
w
c(x) = x
c(x) = x
v
c(x) = 1
0.5 – 0.1
s
0 + 0.1 c(x) = 0
t
0.5
c(x) = x
c(x) = 1
w
c中 = 1.1
c上 ≦ c 中なので
ナッシュフローの
条件に合わない
2.2 ナッシュフロー
c(x) = x
v
ブライスのパラドックス
（安定した後）
c(x) = 1
0
1 c(x) = 0
s
t
0
c(x) = 1
w
c(x) = x
c(x) = x
v
c(x) = 1
0 + 0.1
s
1 - 0.1 c(x) = 0
t
0
c(x) = x
c(x) = 1
w
c中 = 2
c上 = 2
c中 ≦ c 上なので
ナッシュフローの
条件に合う
2.2 ナッシュフロー
• 定理2.2.2
すべての commodity i について、
すべての
なるパス
について、
2.2 ナッシュフロー
• 系2.2.3
各 commodity i について、
すべての
,
なるパス
について、
すなわち、commodity i にのみ依存する
コスト ci(f) をもつ

Download Report