§3.1-3.3, How Bad Is Selfish Routing? 永井智映@知能情報学専攻 2008年12月1日

はじめに：なにをやるか 無秩序の代償の上限 線型コスト関数の場合 (§ 3.2) 一般の場合 (§ 3.3)

§3.2

例2.5.1(Pigou’s Example)-(a) c上(x)=1 traffic rate r = 1 フロー: f s t cost関数 c下(x)=x 1 このフロー f は(G,r,c)に対してナッシュ均衡． c上パス(f)=Σe∈上パスce(fe)=c上(0)=1 c下パス(f)=Σe∈下パスce(fe)=c下(1)=1 C(f)=ΣP∈PcP(f)fP=c上パス(f)f上パス+c下パス(f)f下パス =1・0 + 1・1 =1.

例2.5.1(Pigou’s Example)-(b) c*上(x)=1 traffic rate = 1 1/2 フロー: f* s t 1/2 marginal cost関数 c*下(x)=2x フロー f* は(G,r,c*)に対してナッシュフロー． ⇒フロー f* は(G,r,c)に対して最適フロー． c上パス(f*)=Σe∈上パスce(f*e)=c上(1/2)=1 c下パス(f*)=Σe∈下パスce(f*e)=c下(1/2)=1/2 C(f*)=ΣP∈PcP(f*)f*P=c上パス(f*)f*上パス+c下パス(f*)f*下パス =1・1/2 + 1/2・1/2 =3/4. C(f)/C(f*)=1/(3/4)=4/3.

線形コスト関数の場合 インスタンス(G,r,c)に対し， どのエッジのコスト関数も線型であるとする ce(x)=aex+be とあらわせる c*e(x)=d/dx[x(aex+be)]=2aex+be

ナッシュ均衡の定義

系3.2.2 インスタンス(G,r,c)が各エッジeに対しコスト関数ce(x)=aexをもつとする 実現可能流f が(G,r,c)に対しナッシュ均衡 ⇒ fは(G,r,c)に対し最適フロー 各エッジのコスト関数のbe=0として，(3.2)が成り立つときのみ(3.1)がなりたつ

系3.2.2の例 1/2 フロー: f 1/2 フロー f は(G,r,c)に対してナッシュフロー． P1 c1(x)=x s t traffic rate = 1 1/2 フロー: f s t 1/2 cost関数 c2(x)=x P2 cP1(f)=Σe∈P1ce(fe)=cP1(1/2)=1/2 cP2(f)=Σe∈P2ce(fe)=cP2(1/2)=1/2 フロー f は(G,r,c)に対してナッシュフロー．

系3.2.2の例 (con’d) 1/2 フロー: f 1/2 フロー f は(G,r,c*)に対してナッシュフロー． P1 c1(x)=2x traffic rate = 1 1/2 フロー: f s t 1/2 cost関数 c2(x)=2x P2 cP1(f*)=Σe∈P1ce(f*e)=cP1(1/2)=1 cP2(f*)=Σe∈P2ce(f*e)=cP2(1/2)=1 フロー f は(G,r,c*)に対してナッシュフロー． ⇒フロー f は(G,r,c)に対して最適フロー．

補題3.2.3 インスタンス(G,r,c)が各エッジeに対し線型コスト関数ceをもつとする． fは(G,r,c)に対してナッシュフローとする． ∀eに対して c*e(fe/2)=ce(fe)． (G,r,c)に対してフロー f/2は最適．

補題3.2.3の例 P1 traffic rate r = 1 c1(x)=x+b 1/2 フロー: f (ア) s t 1/2 cost関数 c2(x)=x+b P2 traffic rate r = 1/2 P1 marginal cost関数 c*1(x)=2x+b 1/4 (イ) フロー: f/2 s t 1/4 c*2(x)=2x+b P2 c1(f1)=c1(1/2)=(1/2)x+b=c*1(1/4)=c*1(f1/2) 下も同様

補題3.2.3の例 (con’d) 1/2 フロー: f 1/2 1/4 フロー: f/2 1/4 P1 traffic rate = 1 c1(x)=x+b 1/2 フロー: f (a) s t 1/2 cost関数 c2(x)=x+b P2 traffic rate = 1/2 P1 marginal cost関数 c*1(x)=2x+b 1/4 (b) フロー: f/2 s t 1/4 c*2(x)=2x+b P2 f/2は(G,r/2,c*)に対してナッシュフロー ⇒ f/2は(G,r/2,c)に対して最適フロー

定理3.2.6 (G,r,c)は線型コスト関数つきインスタンスで，

定理3.2.6の証明アプローチ (G,r,c)に対するナッシュフローfから，(G,r/2,c)に対する最適フローf/2を求める． この二つのステップの下限をべつべつにもとめる．

補題3.2.4:ひとつめの下限

補題3.2.5:ふたつめの下限 (G,r,c)は線型コスト関数つきインスタンス，f*はこれに対する最適フローとする ∀δに対して(G,(1+δ)r,c)は少なくともC(f*)+δΣe∈Ec*e(f*e)f*e 以上のコストをもつ fを(G,(1+δ)r,c)上の実現可能なフローとする

補題3.2.5 証明の方針 c(fe)fe≧(fe=f*eでの接線) C(f)=Σe∈Ece(fe)fe において，feは実現可能な流れのいろんな値(変数) c*e(fe)=d/dfe[ce(fe)fe] y=ce(fe)fe y=c*e(f*e)(fe-f*e)+ce(f*e)f*e y fe O f*e

定理3.2.6 (G,r,c)は線型コスト関数つきインスタンス

定理3.2.6の証明 フローfを(G,r,c)に対するナッシュフローとする 補題3.2.5にδ=1を入れて， C(f*)≧C(f/2)+Σe∈Ec*e(fe/2)fe/2 を得る．(f/2は最適フロー) f*は（G,r,c)に対して実現可能なので， C(f*)≧1/4C(f)+1/2Σe∈Ece(fe)fe =3/4C(f) C(f)

§3.3 永井智映@知能情報学専攻 2008年12月8日

例(2-link 2-node, 線型Pigou’s Example) 1-(1-b)/a c上(x)=1 traffic rate r := 1 flow : f s t cost関数: c上, c下 (a≠0) c下(x)=ax+b (1-b)/a このフロー f は(G,r,c)に対してナッシュ均衡． c上パス(f)=Σe∈上パスce(fe)=c上(1-(1-b)/a)=1 c下パス(f)=Σe∈下パスce(fe)=c下((1-b)/a)=1 C(f)=ΣP∈PcP(f)fP=c上パス(f)f上パス+c下パス(f)f下パス =1・{1-(1-b)/a} + 1・(1-b)/a =1-(1-b)/a + (1-b)/a =1.

例(con’d) 1-(1-b)/(2a) (1-b)/(2a) c*上(x)=1 traffic rate r := 1 flow : f* s t marginal cost関数: c*上, c*下(a≠0) c*下(x)=2ax+b (1-b)/(2a) フロー f* は(G,r,c*)に対してナッシュフロー． ⇒フロー f* は(G,r,c)に対して最適フロー． c*上パス(f*)=Σe∈上パスc*e(f*e)=c*上(1-(1-b)/(2a))=1, c*下パス(f*)=Σe∈下パスc*e(f*e)=c*下((1-b)/(2a))=1. c上パス(f*)=Σe∈上パスce(f*e)=c*上(1-(1-b)/(2a))=1, c下パス(f*)=Σe∈下パスce(f*e)=c*下((1-b)/(2a))=1/2.

例(con’d) c上パス(f*)=Σe∈上パスce(f*e)=c上(1-(1-b)/(2a))=1, c下パス(f*)=Σe∈下パスce(f*e)=c下((1-b)/(2a))=1/2. C(f*)=ΣP∈PcP(f*)f*P=c上(f*)f*上+c下(f*)f*下 =1・{1-(1-b)/(2a)} + 1/2・{(1-b)/(2a)} =1-(1-b)/(4a). ∴ρ(G,r,c) =C(f)/C(f*) =1-(1-b)/(4・a) =(4a)/(4a+b-1)

復習 Selfish Routingにおける §3.2の結果: 線型コスト関数つき(G,r,c) 一般の(関数の)場合での上限はどうなるか？ ⇒例2.5.4を見て予想をたてよう．

例2.5.4 (非線型Pigou’s Example) c上(x)=1 traffic rate r := 1 フロー: f s t cost関数: c上, c下 c下(x)=xp 1 このフロー f は(G,r,c)に対してナッシュ均衡． cP上(f)=Σe∈P上ce(fe)=c上(0)=1 cP下(f)=Σe∈P下ce(fe)=c下(1)=1 C(f)=ΣP∈PcP(f)fP=cP上(f)fP上+cP下(f)fP下 =1・0 + 1・1 =1.

例2.5.4 (con’d) 1-(p+1)^{-1/p} フロー: f* (p+1)^{-1/p} c*上(x)=1 traffic rate r := 1 フロー: f* s t c*下(x)=(p+1)xp marginal cost関数: c*上, c*下 (pは十分大きい) (p+1)^{-1/p} フロー f* は(G,r,c*)に対してナッシュフロー． ⇒フロー f* は(G,r,c)に対して最適フロー． c*P上(f*)=Σe∈P上c*e(f*e)=c*上(1-(p+1)^{-1/p})=1 c*P下(f*)=Σe∈P下c*e(f*e)=c*下((p+1)^{-1/p})=1 C(f*)=ΣP∈PcP(f*)fP=cP上(f*)f*P上+cP下(f*)f*P下 =p-(p+1)^{-1/p}. p→∞ のとき，C(f*)→0，ρ(G,r,c)→∞ となる．

観察結果 given: 許される(なんでも)コスト関数の集合 C 無秩序の代償の値はこの集合Cにとっても依存している ⇒この集合Cをパラメータとする上限が欲しい α(C)となづける Cにおけるコスト関数の急峻さ，急勾配っぷりを量化するイメージ

motivating 例 r cost関数 c1, c2 traffic rate r フローf c1(x)=1 cost関数 c1, c2 traffic rate r フローf c2(x) c2は以下の条件を満たす: c2(0)<1 かつ c2(x)>1, c2(r)=1となる. r フロー f は(G,r,c)に対してナッシュ均衡． cP上(f)=Σe∈P上ce(fe)=c1(0)=1 cP下(f)=Σe∈P下ce(fe)=c2(r)=1 y y=c2(x) price of anarchy が large な例 例2.5.4の変種 実は，xの動く範囲を，最小値(=C(f*))を変えることなしに 非負とすることができる． 1 C(f)=c1(0)0+c2(r)r C(f*)=minx≦r[c1(r-x)(r-x)+c2(x)x] =minx≦r[c2(r)(r-x)+c2(x)x] (∵c1は定数関数) O r x(十分大きい)

The Anarchy Value α(c) ナッシュフローのコストと最適フローのコストとの最悪な場合のratio Pigou-likeな例の場合のみ: 2-node 2-link α(c):=(ナッシュフローの総コスト)/(最適フローの総コスト) ca(x)=a (a∈R) c(x)

α(c)を簡単にする コスト関数が連続的に微分可能でsemiconvexと仮定する 固定された値r≧0に対して，式(3.5)はPigou-likeな例での cは連続的微分可能で非減少なので， ∀xに対して c*(x)=c(x)+c’(x)x≧c(x). 中間値の定理より， ∃λ∈[0,1]s.t.c*(r)≧c*(λr)≧c(r).

α(c)を簡単にする(con’d) λrを下のリンク，残り(r-λr)を上のリンクに流すと最適フロー C(f)/C(f*) =[c(λr)λr/c(r)r+c(r)r(1-λ)/c(r)r]^-1 =[λμ+(1-λ)]^-1, where μ=c(λr)/c(r).■ α(c)からα(C)へ． C:コスト関数の集合， α(C):=sup0≠c∈Cα(c). (1-λ)r ca(x)=a (a∈R) f* c(x) λr

補題3.3.6 ∀c∈C,x,r≧0に対して c(x)x≧(c(r)r)/α(C)+c(r)(x-r). 定義3.3.1と3.3.3からすぐに. (∵α(C)≧(c(r)r)/(c(x)x+c(r)(r-x)) ⇒c(x)x+c(r)(r-x)≧(c(r)r)/α(C) ⇒c(x)x≧(c(r)r)/α(C)+c(r)(x-r).■)

定理3.3.7 コスト関数の集合C，無秩序の値 α(C)，C中のコスト関数がついたインスタンス(G,r,c)とする． ρ(G,r,c)≦α(C). ∵C(f*)=Σe∈Ece(f*e)f*e ≧1/α(C)Σe∈Ece(fe)fe+Σe∈E(f*e-fe)ce(fe) (∵補題3.3.6，x=f*，r=fe.) ≧C(f)/α(C). (∵系2.6.6.)■