計算量理論輪講 4.4-4.7 岩間研究室 照山順一

4.4 Atomic Selfish Routing [有限のエージェントがフローを送る] ２つのモデル： エージェントは複数のパスが使える。 4.4.1　３章の定理が拡張できる エージェントは一つのパスしか使えない。 4.4.2　制限された状態でしか拡張できない

4.4.1 Splittable Flow 定義。

4.4.1 Splittable Flow ナッシュ均衡について

4.4.1 Splittable Flow 定理4.4.3(定理3.6.2の拡張)

定理4.4.3の証明[1/4] 方針：ナッシュフロー f からトラフィックを2倍にしてコストがどのくらい増えるかを評価 　をコスト関数の代わりに導入(定理3.6.2で使用)。 f*は　から　に変わることで高々C(f)だけコストが増える。

定理4.4.3の証明[2/4]

定理4.4.3の証明[3/4] 利益 損失 利益 損失

定理4.4.3の証明[4/4]

4.4.1 Splittable Flow 証明は省略するが以下の定理(定理3.3.7の拡張)も成り立つ 定理4.4.4

4.4.2 Unsplittable Flow Splittable Flowとの違い ネガティブな結果 各ユーザは一つのパスにしか流せない。 ネガティブな結果 3章での定理が拡張が出来ない例が存在

ｓ v w u t x 1 1/ε 2 g(x) 2 1 2 A:コストは少なくとも1/ε B:コストは18より少ない

4.5 A Quick-and-Dirty Bound on the Price of Anarchy 節3.3.1のanarchy value ：price of anarchyを評価するための道具 anarchy valueはちょっと計算が大変 ー＞もう少し簡単に計算できるものへ。 ただ、評価は甘くなる。 例：コスト関数の次数が高々pの時、高々p+1

4.5 A Quick-and-Dirty Bound on the Price of Anarchy 新たに導入するもの 勾配[incline] 定義の動機は非線形計画問題から。 目的関数のゆがみを測る。

定理4.5.3

定理4.5.3の証明 フローの枝分解 勾配の定義から CPでのナッシュフローが 元の問題の最適フロー コスト関数が非減少より

系4.5.4

系4.5.4の証明

4.6 Better Bound for Many Traffic Rate この節では、最悪ケースを除いてprice of anarchyを考える。 任意のネットワーク、任意のコスト関数に対するインスタンスを考える。ただし、traffic rateを選ぶことができるとする。 ゴール：すべてのネットワークにおいて多くのトラフィックは最悪ケースよりだいぶよいことを示す。

例4.6.1(非線形コスト関数のピゴーの例) traffic rateが 1 xp ｓ ｔ 1 xp traffic rateが 1に十分近い：price of anarchyはp次式になる 1より十分小さい： price of anarchyは1 無限大に近づくと、 price of anarchyは1に近づく 少なくともprice of anarchyがρ*であるtraffic rateの幅は、 ρ*を無限大に向かわせると0に向かう。 ほとんどすべてのtraffic rateでprice of anarchyは定数で抑えられる。 簡単のため、この節ではtraffic rateを有限幅でとる。

π-valueを定義する。 定義と定理3.6.2から以下の系が導かれる。 インスタンスのコストは、 トラフィックを半分にしたインスタンスの ナッシュフローのコスト以上

系4.6.4 急激にナッシュフローが減少するときのみ、 price of anarchyが大きい

系4.6.4の証明

補題4.6.5

補題4.6.5の証明 　　　　とする。 　　　　　　　　かつ　　　　　　　　　　　　なるiに対して、系4.6.4を帰納的に適用すると、(G,r,c)のナッシュフローのコストが(G,lr,c)のナッシュフローのコストの少なくとも2i倍ある。

定理4.6.6

4.7 Maximum Cost これまでの最適フロー:“unfair”な状況になりうる パスの最大コストに注目する。

準備

命題4.7.1 証明

系4.7.2 例2.5.2(Breass’s Paradox)から直接来る s t 1 x ナッシュフロー：２ max-最適フロー：3/2

命題4.7.3 [証明] f,f*,fMを(G,r,c)のナッシュ、最適、max-最適フローとする。ナッシュフローはどのパスでもコストが同じことから、C( f )=r・M( f )。

系4.7.4 前の系、命題と、線形関数のインスタンスに関するprice of anarchyの上界から。

例4.7.5 n頂点のグラフに対して、maximum-anarchyがn-1になる例。 1 c1(x) c2(x) c3(x) s t 1 c1(x) c2(x) c3(x) n=4 ナッシュフロー：n-1 max-最適フロー：1

定理4.7.6

定理4.7.6の証明[1/4] [証明] 準備 f ：(G,r,c)のナッシュフロー f* ：(G,r,c)の実行可能フロー d(v)：長さをce( fe )とした時のs-v間の最小距離 M( f )=d(t) G：n頂点のグラフ

定理4.7.6の証明[2/4] f のグラフの頂点に順番付け：列(v1,v2,…,vn) f-monotone：d(v)が非減少な列 tがvjとしてf-monotoneな列に現れるとする。 vi,vi+1： i < j でd(vi+1)-d(vi)が最大になる組

定理4.7.6の証明[3/4] S={v1,v2,…,vi}：f-monotone性からSはs-tカット f *はカットSから少なくともrは 外に出さなくてはいけない カットSからでるある枝e=(u,w)について、ナッシュフローでのフロー量以上。 S V＼S ナッシュフローfにおいて フローは0

定理4.7.6の証明[4/4] 命題2.7.7から、 f-monotoneの列でuはviより前の頂点、wはvi+1より後の頂点であるから、

この定理はマルチコモディティのネットワークには持っていけない。 線形コスト関数：ネットワークサイズに線形 任意のコスト関数：ネットワークサイズの指数