selfish2

Selfish Routing and the Price of Anarchy
第2回
D2 杉原堅也
復習
• 扱っている問題
• ナッシュフローと最適フロー
• ナッシュフローの性質
復習
コスト関数（遅延を表す）
ce ( x)  60
e 0
60
台
s
ナッシュフロー
e
ce (0)  60
t
60
ce ( x)  x
の遅延．
平均遅延: 60×0 + 60×1 = 60
ce (60)  60
の遅延．
復習
コスト関数（遅延を表す）
ce ( x)  60
e 0
60
台
s
ナッシュフロー
e
t
60
ce ( x)  x
ce ( x)  60
e 30
60
台
s
最適フロー
ce (0)  60
e
30
ce ( x)  x
の遅延．
平均遅延: 60×0 + 60×1 = 60
ce (60)  60
の遅延．
ce (30)  60 の遅延．
t
平均遅延: 60×0.5 + 30×0.5 = 45
ce (30)  30
の遅延．
復習
コスト関数（遅延を表す）
ce ( x)  1
e 0
1
s
ナッシュフロー
1
s
最適フロー
e
ce (0)  1
t
1
の遅延．
平均遅延: 1×0 + 1×1 = 1
ce ( x)  x
ce (1)  1
ce ( x)  1
e 0.5
ce (0.5)  1 の遅延．
e
0.5
ce ( x)  x
t
の遅延．
平均遅延: 1×0.5 + 0.5×0.5 = 0.75
ce (0.5)  0.5 の遅延．
復習
フロー f がナッシュフロー
⇔ si から ti へのパス P1 , P2 Pi , f P  0 に対し，cP1 ( f )  cP2 ( f )
1
si から ti へのパス P1 , P2 Pi , f P1 , f P2  0 に対し， cP1 ( f )  cP2 ( f )
x
1 x
0
si
2
0.5
0.5
0.5
ti
2x
全てのパスの遅延時間は2
発表内容
2.4節最適フローの特徴付け
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
発表内容
2.4節最適フローの特徴付け
最適フローの求め方
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
定義 2.4.2
(a) ユークリッド空間上の2点 x, y の凸結合 (convex combination)．
⇔ x, y を結ぶ線分上の点． x  (1   ) y　(0    1)
(b) S ⊆ Rn が凸 (convex)．
⇔ 要素が凸結合で閉じている集合． x, y  S  x  (1   ) y  S
(c) 関数 h: S → R が凸 (convex function)．
⇔ h(x  (1   ) y )  h( x)  (1   )h( y )
（2階微分導関数が0以上）
(d) 関数 c: R+ → R+ が準凸 (semiconvex function)．
⇔ x・c(x) が凸．
c を滑らかで非減少とすると，
c が凸 ⇒ c が準凸
h( x)  (1   )h( y )
h(x  (1   ) y )
x
y
x  (1   ) y
問題の定式化
Min.
h ( f )
e
eE
Subject to:
P f
P
e
P
 ri i  {1, , k}
i
fe 
f

P
P :eP
P
e  E
f P  0　P P
he ( f e )  ce ( f e ) f e
とする．
ce が準凸 (he が凸) ⇒ 凸計画問題
(NLP)
最適フローの求め方
1
0.5
s
t
x
0.5
コスト関数に x をかけて微分
( x 1)  1 0.5
s
t
( x  x)  2 x
0.5
このネットワークでのナッシュフローは
元のネットワークの最適フローとなっている．
ナッシュフロー
最適フローの特徴付け
( x 1)  1
定義 2.4.5
c を微分可能なコスト関数としたとき，
c 
*
d
dx
( x  c( x))
s
t
( x  x)  2 x
を限界コスト関数 (marginal cost function) と定義する．
系 2.4.6
(G, r, c) を滑らかで準凸なコスト関数を持つインスタンスとする．
フロー f が最適 ⇔ f は(G, r, c*)のナッシュフロー．
証明：次の命題の(a)と(b)から．
命題 2.4.4
f*: NLPの実行可能解
he= c(x)・x: 滑らか，凸． he ( x) 
d
dx
he ( x)  c * ( x), hP ( f )   he ( f e )
eP
(a)～(d)は同値．
(a) f* が最適フロー
(b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し，
hP1 ( f * )  hP2 ( f * )
(c) 全ての実行可能なフロー f に対し，
*
*

h
(
f
)
f
 P
P 
PP
(d) 全ての実行可能なフロー f に対し，
*

h
(
f
 P ) fP
PP
 he ( f e ) f e   he ( f e ) f e
*
eE
*
*
eE
命題 2.4.4 の証明
(c)
(c) ⇔ (d)
*
*

h
(
f
)
f
 P
P 
PP
(d)
*
*
*
*



h
(
f
)
f

h
(
f
)
f

h
(
f
 P
 e e e  e e ) fe
P
PP
eE
eE
Σの順番をいれかえ．
(b) ⇔ (c)
(b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し，
hP1 ( f * )  hP2 ( f * )
H( f ) 
*

h
(
f
 P ) fP
cP1 ( x)  hP1 ( f * )
を定義
P1
PP
f* を固定すると，定数コストのネットワークにおける
f の平均遅延を表す式となる．
(b) は元のネットワークで f*P > 0 のパスは，固定後にコスト最小のパスとなると言っている．
(c) の左辺は，f* を流したときの平均遅延，右辺はその他のフロー平均遅延．
命題 2.4.4 の証明
(a) ⇒ (b)
(a) f* が最適フロー
(b) 全ての i ∈ {1, ..., k} と， f*P1 > 0 となる P1, P2 ∈ Pi に対し，
hP1 ( f * )  hP2 ( f * )
f* のうち，f*P1 > 0 となるパス P1 のフローの微小量 λを
P2 に流れるフローに加えると，
目的関数値は，

*
* 
he ( f e )     he ( f e )   he ( f e )

eE
eP1
eP2

*
に変化する．f* の最適性から [・] 内は 0 以上．
P1
P2
命題 2.4.4 の証明
(d) ⇒ (a)
(d)
 he ( f e ) f e   he ( f e ) f e
*
*
eE
*
eE
(a) f* は最適フロー
f を任意の実行可能フローとする．

 he ( f e )   he ( f e )  he ( f e )( f e  f e )
eE
eE
*
*
*

he は凸
y
y  he ( f )
  he ( f e )   he ( f e )( f e  f e )
*
eE
*
*
eE
  he ( f e )
*
eE
(d) から 0 以上．
f
f
y  he ( f  )( f  f  )  he ( f  )
その他の事実
事実 2.4.9
コスト関数c が準凸のとき，最適フローは，任意に小さい誤りで，
入力サイズと要求された正確さ(precision)のビット数の多項式時間で計算できる．
・入力サイズについては正確に議論しない (remark 2.4.10)．
・誤りを含むのは，最適フローが無理数だとしても
既存の凸計画問題のアルゴリズムは有理数を出力するため (remark 2.4.11)．
事実 2.4.12
コスト関数 c が任意のとき，入力サイズと近似の正確さのビット数の
多項式時間で近似解を計算するアルゴリズムは存在しない if P≠NP．
・下界: ω(n1-ε)．
発表内容
2.4節最適フローの特徴付け
2.5節例
いくつかの例を紹介
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
例 2.5.3 (強パレート suboptimality)
枝追加後の Braess’s paradox のナッシュフローは最適フローに強パレート支配される．
しかし，枝の削除 (追加する前) によってナッシュフローは改善され，
最適フローの強パレート支配ではなくなる．
x
0.5
ナッシュフロー
1
1
t
s
1
0.5
1
x
0
s
x
t
1
x
x
1
枝の追加
x
0.5
1
t
s
1
0.5
x
0.5
最適フロー
t
0
s
1
0.5
x
例 2.5.3 (強パレート suboptimality)
ナッシュフローが最適フローに強パレート支配され，
かつどの枝を削除しても強パレート支配される例を示す．
1
1
s
t
x
x
1
ナッシュフロー
コスト（遅延）は2
例 2.5.3 (強パレート suboptimality)
ナッシュフローが最適フローに強パレート支配され，
かつどの枝を削除しても強パレート支配される例を示す．
1
1
s
t
x
x
1
0.5
コスト（遅延）は2
1
1
s
t
x
0.5
ナッシュフロー
x
最適フロー
それぞれのパスの
コスト（遅延）は1.5
例 2.5.4 (非線形な Pigou の例)
Pigou の例，Bｒaess’s paradox，例 2.5.3の price of anarchy は 3/4．
これは偶然ではなく，コスト関数が線形のときは高々3/4 となる (3章)．
しかし，線形ではないときには price of anarchy が任意に大きくなる場合がある．
1
s
t
xp
1
(G, r, c)
ナッシュフローは下のリンクに1．
平均遅延は1．
例 2.5.4 (非線形な Pigou の例)
Pigou の例，Bｒaess’s paradox，例 2.5.3の price of anarchy は 4/3．
偶然ではなく，コスト関数が線形のときは高々4/3 となる (3章)．
しかし，線形ではないときには price of anarchy が任意に大きくなる場合がある．
1 1  ( p  1)
s
 1p
t
xp
( p  1)
1 1  ( p  1)
s
t
( p  1) x
 1p
(G, r, c)
 1p
p
( p  1)
 1p
(G, r, c*)
ナッシュフローは下のリンクに1．
平均遅延は1．
 1p
 1p
1  ( p  1) 下のリンクに ( p  1)
 1p
 1p
 pp
 pp1
平均遅延は {1  ( p  1) } 1  ( p  1)  ( p  1)
 1  p( p  1)
最適フローは，上のリンクに
例 2.5.5 (最適フローの不公正性)
今までの例では，
全てのトラフィックにおいて最適フローの各々のパスの遅延は
ナッシュフローよりコストが優るか同等だった．
一部のトラフィックを犠牲にしてコストを最小とする最適フローの例を示す．
2－ε
s
t
x
1
(G, r, c)
ナッシュフローは下のリンクに1．遅延は1．
例 2.5.5 (最適フローの不公正性)
今までの例では，
全てのトラフィックにおいて最適フローの各々のパスの遅延は
ナッシュフローよりコストが優るか同等だった．
一部のトラフィックを犠牲にしてコストを最小とする最適フローの例を示す．
2－ε
 /2
s
2－ε
t
x
 /2
s
t
1  / 2
2x
(G, r, c)
1  / 2
(G, r, c*)
ナッシュフローは下のリンクに1．遅延は1．
2－εの遅延
 /2
1   / 2 の遅延
1  / 2
2
平均遅延は (2   )   / 2  (1   / 2)  (1   / 2)  1   / 4
最適フローは，上のリンクに
下のリンクに
例 2.5.6 (多品種の Braess’s paradox)
Bｒaess’s paradox の多品種版(品種が2つ)
（コスト 0 の枝を加えたらナッシュフローの平均遅延が増大）
xp
s2
0
1
3
t2
2
3
x
s1
1
ナッシュフロー：
品種1 のコストは
0
p
v
1
2 3
3
w
1 
1
t1
xp
.
2 p
3
品種2 のコストは
.
2 p
3
p → ∞ で 1 と 0 になる．
例 2.5.6 (多品種の Braess’s paradox)
Bｒaess’s paradox の多品種版(品種が2つ)
（コスト 0 の枝を加えたらナッシュフローの平均遅延が増大）
t2
xp
1
s2
0
0
x
v
p
1
s1
1
1
t1
0
w
xp
枝を加えた後のナッシュフロー：
品種1 のコストは 2，品種2 のコストも 1．
従って，枝 (v,w) を加える前後において，p を大きくするとコストの差は大きくなる．
元のネットワークのナッシュフロー：
p
品種1 のコストは 1  2 . 品種2 のコストは
3 
.
2 p
3
p → ∞ で 1 と 0 になる．
発表内容
2.4節最適フローの特徴付け
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
2.6節ナッシュフローの存在性と一意性
(G, r, c) の最適フロー
(G, r, c) のナッシュフロー
⇔
(G, r, c*) のナッシュフロー
⇔
(G, r,
c* 
d
dx
( x  c( x))
ĉ) の最適フロー
x
1
cˆ  x  c(t )dt
0
命題 2.6.1
Min.
h ( f )
e
eE
Subject to:
P f
P
e
P
 ri i  {1, , k}
i
fe 
f

P
P :eP
P
e  E
(CP)
f P  0　P P
x
he ( x)   ce (t )dt とする．
0
・ CP の最適フローは NLP のナッシュフロー．
・ CPは凸計画問題（ce(x) は非減少関数だから，he の2階微分は非負で he は凸）．
・実行可能領域は有界閉集合で目的関数は連続 → 最適解(ナッシュフロー)が存在．
ナッシュフローの一意性
1
s
t
1
上のネットワークでは全ての実行可能フローがナッシュフローとなる．
ナッシュフローは厳密に一意となるわけではない．
ナッシュフローの一意性
系 2.6.2
~
~
f と f がナッシュフローのとき，全てのe ∈ E で ce ( f e )  ce ( f e ).
証明
~
~
f と f の凸結合を考える． f  (1   ) f
CPは凸計画問題なので実行可能解．
h(x) をCPの目的関数とすると，凸関数なので，
~
~
~
h( f ), h( f ) はCPの最適解
h(f  (1   ) f )  h( f )  (1   )h( f )
~
 h( f )
 h( f )  h( f )
~
 (1   ) f も最適解で，上式の等号が成立．
~
従って， f  (1   ) f (0    1) において
つまり， f
h は線形関数で，h は c の積分だから，c は定数関数となる．
ナッシュフローの一意性
系 2.6.2
~
~
f と f がナッシュフローのとき，全てのe ∈ E で ce ( f e )  ce ( f e ).
系 2.6.3
~
~
実行可能なフロー f があるナッシュフロー f と各枝 e で f e  f e
~
を満たすとき，f はナッシュフローである．
系 2.6.4
~
~
f と f がナッシュフローのとき，ce が狭義増加関数なら f e  f e
ナッシュフローの一意性
系 2.6.6
f がナッシュフロー
⇔ あらゆる実行可能なフロー f* に対し，
 ce ( f e ) f e   ce ( f e ) f e .
*
eE
略証：命題 2.4.4 から，
eE
 h ( f ) f   h ( f ) f
eE
e
e
e
eE
e
e
*
e
系 2.6.7
ナッシュフローは，任意に小さい誤りで，
入力サイズと要求された正確さ(precision)のビット数の多項式時間で計算できる．
発表内容
2.4節最適フローの特徴付け
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
2.7.1 Classical Network Flow Theory
フローに関する古典的な結果と，導かれる本問題のフローの性質．
2.7.2 Monotone Orderings
命題 2.7.1
(G, r, c) を単品種のインスタンスとする．
(a) f が(G, r, c) の実行可能フローのとき，下の線形システムの実行可能解となる．
x
e  ( s )
e

e

x
e

e  ( v )
r
x
 r
x
 0　v  V \ {s, t}
e  ( s )
x
e  ( t )
x
e  ( t )
e  ( v )
e
e
e
s
x  0　e  E
δ+ (v) はvを始点とする枝の集合， δ- (v) はvを終点とする枝の集合．
(b) f を上の線形システムの実行可能解とするとき，
~
~
全ての e で f e  f e となる(G, r, c) の実行可能フロー { f e }eE が存在する．
命題 2.7.2
f が(G, r, c) の実行可能フロー，S が G の s-t カットのとき，
f
e
(
の合計) － (
e  ( S )
S
s

f
e  ( S )
e
fe
 r.
の合計) = r
t
G
命題 2.7.3
f が(G, r, c) の実行可能フローのとき，
~
有向閉路のない実行可能フロー { f e }eE で，
全ての枝 e に対し ~f e  f e であるものが存在する．
フローの有向閉路
⇔ fe >0 の e からなる
有向閉路．
証明
2
3
4
1
2
6
6
3
5
3
0
1
5
5
5
0
閉路内の枝でフローが最も小さいものを選び，
その値を閉路内のフローからひく
この操作で新たに構成したフロー fˆ は命題2.7.1の線形システムを満たす．~
また，命題2.7.1 (b) から ~
f  fˆ  f となる (G, r, c) の実行可能フロー f が存在．
e
e
この操作を閉路がなくなるまで繰り返す．
発表内容
2.4節最適フローの特徴付け
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
2.7.1 Classical Network Flow Theory
2.7.2 Monotone Orderings
単品種のネットワークにおけるナッシュフローの性質
命題 2.7.4
単品種ネットワークのインスタンスは有向閉路のないナッシュフローを持つ．
略証
・ナッシュフローの存在性は命題 2.2.5による．
・命題 2.6.1 から，ナッシュフロー ⇔ 凸計画問題CPの最適解．
・命題 2.7.3 から，あるナッシュフロー f について，
~
~
全ての枝 e で f e  f e となる有向閉路のない実行可能フロー f が存在．
~
・ f はCPの最適解だから f も最適解であり，ナッシュフローである．
定義 2.7.5
f をナッシュフローとする．
d(v) ⇔ 枝の長さを ce(fe) としたときの s から v への最短経路の長さ．
x
1 x
0
s
0.5
0.5
0.5
d(v) = 2
v
2
2x
1
1
t
節点の順序付けが f-monotone ⇔ 次の (P1) ~ (P3) を満たす．
(P1) ソース s が一番目．
(P2) フローはこの順序に逆らわずに節点を辿る．
(P3) d(v) の値がこの順序で非減少．
1
s
x
2
x
0
2
4
3
0.5
2x
f に有向閉路がある場合，
f-monotone ordering は存在しない．
5
1
6
t
命題 2.7.7
f: 実行可能フロー
・全ての枝 e = (v, w) に対し， d ( w)  d (v)  ce ( f e ).
・ f がナッシュフロー ⇔ 全ての fe > 0 で上の不等式の等号成立
証明
d (v)
d(・) は最短経路の長さなので3角不等式が成立．
d ( w)  d (v)  ce ( f e )
 d ( w)  d (v)  ce ( f e )
v
ce ( f e ).
s
w
d (w)
命題 2.7.7
f: 実行可能フロー
・全ての枝 e = (v, w) に対し， d ( w)  d (v)  ce ( f e ).
・ f がナッシュフロー ⇔ 全ての fe > 0 で上の不等式の等号成立
証明
cP ( f )   ce ( f e )
eP

{d (w)  d (v)}
e  ( v , w )P
s
・・・
v
w
 d (t )  d ( s)  d (t )
G
fP > 0 とする．
f がナッシュフロー ⇔
cP ( f )  d (t )
t
・・・
(命題2.2.2) ⇔ 上式の等号成立．
命題 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) は存在しない．
w
(存在すると，d(w)－d(v) = ce(fe) (命題2.7.7))．
0
1.5
つまり，v, w を入れ替えても (P2) は満たされる． s
0.5
u
1
1
節点の順序付けが f-monotone ⇔ 次の (P1) ~ (P3) を満たす．
v
(P1) ソース s が一番目．
トポロジカルソート v, w, u
(P2) フローはこの順序に逆らわずに節点を辿る．
d(・) = 1, 0.5, 2
(P3) d(v) の値がこの順序で非減少．
まとめ
2.4節最適フローの特徴付け
最適フローの求め方
2.5節例
2.6節ナッシュフローの存在性と一意性
2.7節単品種ネットワークのナッシュフロー
2.7.1 Classical Network Flow Theory
フローに関する古典的な結果と，導かれる本問題のフローの性質．
2.7.2 Monotone Orderings
単品種のネットワークにおけるナッシュフローの性質

Download Report