Selfish Routing and the Price of Anarchy 4.3 2008年12月22日 岩間研究室 M1 木下直紀

4.3 枝容量の導入 各枝に流せるフローの上限 ue を設定したときの無秩序の代償など 容量付きインスタンス (G,r,c,u) 結論から言うと、前章までの結果は、全てのナッシュフローについては成り立たない。ただし、同様の結果が成り立つナッシュフローが少なくともひとつは存在する。

定義4.3.1 ナッシュ均衡 実現可能フロー f が容量付きインスタンス (G,r,c,u) について次の条件を満たすとき、ナッシュ均衡にあるという。 ただし、 もしくは　　は実現可能ではない

命題2.2.2の拡張 命題4.3.2 容量付きインスタンス (G,r,c,u) について、フロー f は次の条件を満たすとき、かつそのときのみナッシュ均衡にある。

例4.3.3 [1/2] 容量付きネットワークにおいて、ナッシュフロー f のコストは最適フロー f * よりいくらでも多くかかる場合がある v u s t 0,1/2 0,∞ コスト,容量 = 1,∞ 容量付きネットワークにおいて、ナッシュフロー f のコストは最適フロー f * よりいくらでも多くかかる場合がある

例4.3.3 [2/2] v u s t 0,1/2 0,∞ コスト,容量 = 1,∞ v u s t 0,1/2 0,∞ 容量付きネットワークにおいて、ナッシュフロー f のコストは最適フロー f * よりいくらでも多くかかる場合がある v u s t 0,1/2 0,∞ コスト,容量 = 1,∞ v u s t 0,1/2 0,∞ コスト,容量 = 1,∞ 1/2 1/2 f : (G,1,c,u) C( f ) = 1/2 f * : (G,1,c,u) C( f *) = 0

定理3.3.7の拡張 定理4.3.4 Anarchy value a(C) を持つ集合 C のコスト関数を持つ容量付きインスタンス (G,r,c,u) について、 f がナッシュフローであり、f * が実現可能な最適フローであるとき、

系2.6.6の拡張 補題4.3.6 容量付きインスタンス (G,r,c,u) に関する任意の実現可能フロー f * について、次の条件を満たす実現可能ナッシュフロー f が存在する。

補題4.3.6の証明 [1/4] 補題2.6.1の凸計画問題 (CP) を拡張 容量付きインスタンス (G,r,c,u) に対する任意の実現可能フロー f * について、次を満たす実現可能なナッシュフロー f が存在 補題2.6.1の凸計画問題 (CP) を拡張

補題4.3.6の証明 [2/4] 容量付きインスタンス (G,r,c,u) に対する任意の実現可能フロー f * について、次を満たす実現可能なナッシュフロー f が存在 f が (CAP) の最適解ならば、f は (G,r,c,u) のナッシュフローであり（命題2.4.4の証明と同じ）、さらに式 (4.2) を満たす（以下）。 対偶を示す。f が (G,r,c,u) の実現可能フローであり、次の条件を満たす f * が存在したとする。このとき f は最適解ではないことを示す。

補題4.3.6の証明 [3/4] 目的関数 は f において各枝 e について連続微分可能、偏導関数 = ce( fe) 容量付きインスタンス (G,r,c,u) に対する任意の実現可能フロー f * について、次を満たす実現可能なナッシュフロー f が存在 目的関数　　　　　　　　は f において各枝 e について連続微分可能、偏導関数 = ce( fe) ある小さい l について、f ' = (1–l) f +l f * を考える。目的関数を f において1次項までテーラー展開すると、f ' における値は、 ※ R( f ' ) は l↓0 で無視できる誤差項

補題4.3.6の証明 [4/4] 容量付きインスタンス (G,r,c,u) に対する任意の実現可能フロー f * について、次を満たす実現可能なナッシュフロー f が存在 を仮定すると、f ' = (1–l) f +l f * における目的関数の値 は f における値より小さくなる。従って f は (CAP) の最適解ではない。 ■

定理4.3.4の証明 補題3.3.6より x = fe*, r = fe を代入すると ■ C 上の容量付きインスタンス (G,r,c,u) に対するナッシュフロー f が存在し、最適フロー f * について、 補題3.3.6より x = fe*, r = fe を代入すると ■

例4.3.7 [1/2] s 0,2/3 0,∞ コスト,容量 = 1,∞ t v w u x 容量付きネットワークにおいては、ナッシュフロー f よりいくらでも多くのトラフィックを、いくらでも少ないコストで流す最適フロー f * が存在するようなインスタンスが存在する。

例4.3.7 [2/2] s 0,2/3 0,∞ コスト,容量 = 1,∞ t v w u x s 0,2/3 0,∞ 容量付きネットワークにおいては、ナッシュフロー f よりいくらでも多くのトラフィックを、いくらでも少ないコストで流す最適フロー f * が存在するようなインスタンスが存在する。 s 0,2/3 0,∞ コスト,容量 = 1,∞ t v w u x s 0,2/3 0,∞ コスト,容量 = 1,∞ t v w u x 1/3 2/3 2/3 f : (G,1,c,u) C( f ) = 1/3 f * : (G,2,c,u) C( f *) = 0

定理3.6.2の拡張 定理4.3.8 容量付きインスタンス (G,2r,c,u) に関する任意の実現可能フロー f * について、次の条件を満たす (G,r,c,u) に関する実現可能ナッシュフロー f が存在する。

定理4.3.8の証明 [1/4] 次の新しいコスト関数を定義 ce( fe) fe ce(x) x ce( fe) fe ce(x) x (G,2r,c,u) で実現可能な任意のフロー f * について (G,r,c,u) のナッシュフロー f が存在し、C( f )≦C( f *) 次の新しいコスト関数を定義 ce( fe) fe ce(x) x ce( fe) fe ce(x) x

定理4.3.8の証明 [2/4] f */2 は (G,r,c,u) で実現可 定理3.6.2途中結果より ■ (G,2r,c,u) で実現可能な任意のフロー f * について (G,r,c,u) のナッシュフロー f が存在し、C( f )≦C( f *) ce( fe) fe ce(x) x f */2 は (G,r,c,u) で実現可 定理3.6.2途中結果より ■

定理4.3.8の拡張 定理4.3.9 容量付きインスタンス (G,2r,c,2u) に関する任意の実現可能フロー f * について、次の条件を満たす (G,r,c,u) に関する実現可能ナッシュフロー f が存在する。 証明は定理4.3.8と同じ 定理4.3.8の場合、(G,2r,c,u) について実現可能フローが存在しない場合がある