Selfish Routing ４章前半 岡本　和也.

Presentation on theme: "Selfish Routing ４章前半 岡本　和也."— Presentation transcript:

1 Selfish Routing ４章前半 岡本　和也

2 ４章の構成 traffic routing model の一般化 traffic routing model に対する評価基準
4.1 ネットワークモデルではない一般化されたモデル Nonatomic Congestion Games (NCGs) 4.2 近似的なナッシュ均衡 4.3 枝が最大容量を持つ場合 4.4 ネットワークのユーザが全体のトラフィックの一部を弄れる場合 traffic routing model に対する評価基準 4.5 optimal を必要としない（大体の） price of anarchy 4.6 平均的な price of anarchy 4.7 公平さ 僕はここまで

3 4.1 Nonatomic Congestion Games (NCGs)
要素集合 E={e1, e2, …, em} 各要素 e が cost function ce を持つ。（非負、連続、非減少。） player types 1, 2, …, k 各 player type i の人数 ni 各 player type i の選択可能な戦略集合 Si 各戦略は E の部分集合 消費割合 aS,e 各 player type i の戦略 S による e (∈ S) に対する混雑貢献度 正数 枝 品種 流量 パス 1 e5 e2 t1 s1 e4 e7 e1 e3 e6 s2 t2

4 4.1 Nonatomic Congestion Games (NCGs)
要素集合 E={e1, e2, …, em} 各要素 e が cost function ce を持つ。（非負、連続、非減少。） player types 1, 2, …, k 各 player type i の人数 ni 各 player type i の選択可能な戦略集合 Si 各戦略は E の部分集合 消費割合 aS,e 各 player type i の戦略 S による e (∈ S) に対する混雑貢献度 正数 パラメータ 各 player type i のうち戦略 S を取る人数 xs 要素 e の混雑度 要素 e のコスト 戦略 S のコスト 全体のコスト 要素 e1, e2, e3 player type 1, 2 n1 = 2, n2 = 3 戦略集合 S1 = {{e1, e2}1, {e1, e3}1} S2 = {{e2, e3}2, {e1, e2, e3}2} 消費割合 a{e1, e2}1,e1 = 1, a{e1, e2}1,e2 = 2, … 最小化問題

5 Definition 4.1.1 以下の条件を満たすとき、NCG のパラメータ x が均衡である という。
∀i (player type), ∀S1, S2 ∈ Si （戦略集合）（但し、xS1 ＞ 0）, ∀δ ∈ (0, xS1].

6 NCGs における Price of Anarchy
３章の結果を全て持ってこれる。 コストの定義が変わっていない。 流量に基づくコスト関数×流量 目的関数も同じ全体のコストである。 Price of Anarchy の定義も同じ。 均衡となる割り当てのコスト／最適な割り当てのコスト ３章の証明で NCGs に対する trafic routing model の特殊性を 　　利用していない。 消費割合が１である。 ネットワークに基づきパスが制約を受ける。

7 NCGs における Price of Anarchy
コスト関数集合 C に対して anarchy value α(C) を同様に 定義すると、コスト関数集合が C である NCG の price of anarchy は最大でα(C) 以下となる。 (Extension of Theorem 3.3.7) コスト関数集合 C に定数関数を含む場合、２つの要素、 １つの player type、各要素を１つずつ含む戦略、１の消費割合で price of anarchy が α(C)－εとなる例題を作成できる。 (Extension of Theorem 3.4.2)

8 NCGs における Price of Anarchy
コスト関数集合 C が inhomogeneous な関数集合の場合、 １つの player type、互いに素となる戦略、１の消費割合で price of anarchy が α(C)－εとなる例題を作成できる。 (Extension of Theorem 3.4.9) 任意の NCG において均衡となる割り当てのコストは 各 player type の数を２倍にした NCG における 最適な割り当てのコスト以下となる。 (Extension of Theorem 3.6.2)

9 4.2 近似的なナッシュ均衡 (Definition 4.2.1)
以下の条件を満たすとき、trafic routing model (G, r, c) に対して、適切なフロー f がε近似ナッシュ均衡であるという。 ∀i ∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）, ∀δ ∈ (0, fP1].

10 Proposition 4.2.2 フロー f がε近似ナッシュ均衡であるとき、以下が成り立つ。
∀i ∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）. cP1(f) ≦ (1+ε) cP2(f) cP2(f)（最小コスト） cP3(f) ≦ (1+ε) cP2(f) si ti cP4(f) ≦ (1+ε) cP2(f) cP5(f) ≦ (1+ε) cP2(f)

11 Theorem (Theorem 3.6.2) ε∈ [0, 1) で、f が (G, r, c) に対するε近似ナッシュ均衡、f* が (G, 2r, c) に対する適切なフローであった場合、以下が成り立つ。

12 Proof of Theorem 4.2.3 品種 i のフローが通るパスの中で最小コストのパスのコストを ci(f) とすると以下が成り立つ。 以下のような変形したコスト関数を考える。 ce(x) ce(fe) x fe ナッシュフローの 各枝のフロー ce(x) ce(fe) x fe

13 Proof of Theorem 4.2.3 cP(f0) ≧ ci(f) （f0は流量が全て０のフロー。）
各枝ごとに考える。　f*e ≧ f の場合　　　　　　　　　　　　　　　　　f*e ＜ f の場合 ce(x) ce(x) ce(x) ce(x) ce(f*e) ce(f*e) ce(f*e) ce(fe) ce(fe) ce(fe) ≧ ≧ ce(fe) ce(f*e) （マイナス） － x x x x fe f*e fe f*e f*e fe f*e fe

14 Example 4.2.4 Theorem 4.2.3 の等式が等しくなる例 2 ε近似ナッシュ均衡（流量１） 2 g(x) 1-ε 1+ε
2 + 2ε s t 1-ε g(x) 1-ε 1+ε 最適フロー（流量２） g(x) 2 1+ε 2δ 1-ε 2×２δ+ (1-ε)×(1-δ)×2 = 2 – 2ε+ 2δ+εδ → 2 – 2ε　（δ→ 0） 1-δ 1-δ 1-ε 1-δ 1

15 Theorem (Theorem 3.2.6) ε∈ [0, 3) で、f が線形コスト関数を持つ (G, r, c) に対するε近似ナッシュ均衡、f* が (G, r, c) に対する適切なフローであった場合、以下が成り立つ。

16 Proof of Theorem 4.2.5 C(f/2) ≧ C(f)/4 （流量を半分にしてもコストは半分以上のため）
ce(f*e)f*e ≧ ce(fe/2)fe/2 + (f*e-fe/2)ce(fe) ce(x) ce(fe) ce(f*e) a b×b≧a×a +(b-a)×2a (b - a)2 ≧ 0 ce(fe/2) b a a b x fe/2 f*e fe

17 Proof of Theorem 4.2.5 C(f/2) ≧ C(f)/4 （流量を半分にしてもコストは半分以上のため）
ce(f*e)f*e ≧ ce(fe/2)fe/2 + (f*e-fe/2)ce(fe) C(f/2)

18 4.3 枝が最大容量を持つ場合 (Definition 4.3.1)
以下の条件を満たすとき、枝が最大容量を持つ trafic routing model (G, r, c, u) に対して、適切なフロー f がナッシュ均衡 であるという。 ∀i ∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）, ∀δ ∈ (0, fP1]. あるいは、f が適切なフローでない。 ～

19 Example 4.3.3 1/2 1:∞ 定数関数のみでも・・・ 1/2 0:1/2 1:∞ 0:∞ s 1/2 0:∞ t 0:1/2
コスト:最大容量 0:1/2 0:∞ 1/2 s 0:∞ t 1/2 ∞ 0:∞ 0:1/2 1/2

20 Theorem 4.3.4 (Theorem 3.3.7) Theorem 4.3.8, 4.3.9 (Theorem 3.6.2)
コスト関数集合 C に対して anarchy value α(C) を同様に 定義する。ここで、コスト関数集合が C である (G, r, c, u) の最適フローを f* としたとき、以下の式が成り立つようなナッシュフロー f が存在する。 Theorem 4.3.8, (Theorem 3.6.2) (G, r, c, u) に対して、以下の条件を満たすような ナッシュフロー f が存在する。 (G, 2r, c, u) に対する全ての適切なフロー f* (G, 2r, c, 2u) に対する全ての適切なフロー f*