Selfish Routing 4章前半

Selfish Routing ４章前半
岡本和也
４章の構成

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 公平さ
4.1 Nonatomic Congestion Games
(NCGs)

要素集合 E={e1, e2, …, em} 枝




品種
player types 1, 2, …, k
各 player type i の人数 ni 流量
各 player type i の選択可能な戦略集合 Si パス


各要素 e が cost function ce を持つ。（非負、連続、非減少。）
各戦略は E の部分集合
消費割合 aS,e 1


各 player type i の戦略 S による e (∈ S) に対する混雑貢献度
正数
e5
e2
s1
e1
s2
t1
e4
e3
e7
e6
t2
4.1 Nonatomic Congestion Games
(NCGs)

要素集合 E={e1, e2, …, em}





消費割合 aS,e 消費割合 a{e1, e2}1,e1 = 1, a{e1, e2}1,e2 = 2, …




各 player type i の戦略 S による e (∈ S) に対する混雑貢献度
正数
パラメータ


各要素 e が cost function ce を持つ。（非負、連続、非減少。）
player types 1, 2, …, k player type 1, 2
各 player type i の人数 ni n1 = 2, n2 = 3
各 player type i の選択可能な戦略集合 Si 戦略集合 S1 = {{e1, e2}1, {e1, e3}1}
S2 = {{e2, e3}2, {e1, e2, e3}2}

各戦略は E の部分集合


要素 e1, e2, e3
各 player type i のうち戦略 S を取る人数 xs
要素 e の混雑度
要素 e のコスト
戦略 S のコスト
全体のコスト
最小化問題
Definition 4.1.1

以下の条件を満たすとき、NCG のパラメータ x が均衡である
という。

(player type), ∀S1, S2 ∈ Si （戦略集合）（但し、xS1 ＞ 0）,
∀δ ∈ (0, x ].
S1
∀i
NCGs における Price of Anarchy

３章の結果を全て持ってこれる。

コストの定義が変わっていない。



目的関数も同じ全体のコストである。
Price of Anarchy の定義も同じ。


流量に基づくコスト関数×流量
均衡となる割り当てのコスト／最適な割り当てのコスト
３章の証明で NCGs に対する trafic routing model の特殊性を
利用していない。


消費割合が１である。
ネットワークに基づきパスが制約を受ける。
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)
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)
4.2 近似的なナッシュ均衡 (Definition 4.2.1)

以下の条件を満たすとき、trafic routing model (G, r, c) に
対して、適切なフロー f がε近似ナッシュ均衡であるという。

∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）, ∀δ ∈
(0, fP1].
∀i
Proposition 4.2.2

フロー f がε近似ナッシュ均衡であるとき、以下が成り立つ。

∀i
∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）.
cP1(f) ≦ (1+ε) cP2(f)
cP2(f)（最小コスト）
si
cP3(f) ≦ (1+ε) cP2(f)
cP4(f) ≦ (1+ε) cP2(f)
cP5(f) ≦ (1+ε) cP2(f)
ti
Theorem 4.2.3 (Theorem 3.6.2)

ε∈ [0, 1) で、f が (G, r, c) に対するε近似ナッシュ均衡、f* が
(G, 2r, c) に対する適切なフローであった場合、以下が成り
立つ。
Proof of Theorem 4.2.3

品種 i のフローが通るパスの中で最小コストのパスのコスト
を ci(f) とすると以下が成り立つ。

以下のような変形したコスト関数を考える。
ce(x)
ce(fe)
ナッシュフローの
各枝のフロー
fe
x
ce(x)
ce(fe)
fe
x
Proof of Theorem 4.2.3


cP(f0) ≧ ci(f) （f0は流量が全て０のフロー。）
cP(f*) ≧ ci(f) （非減少関数なので。）
各枝ごとに考える。 f*e ≧ f の場合
ce(x)
ce(x)
ce(f*e)
ce(f*e)
ce(fe)
≧
ce(fe)
fe f*e
x
fe f*e
f*e ＜ f の場合
ce(x)
ce(x)
ce(f*e)
ce(fe)
≧ ce(fe) （マイナス）
ce(f*e)
－
x
x
f*e fe
f*e fe
x
Example 4.2.4
Theorem 4.2.3 の等式が等しくなる例

ε近似ナッシュ均衡（流量１）
2
2
g(x)
1-ε
0
s
1-ε
g(x)
1+ε
0
1-δ 1
t
g(x)
1+ε
1
1-ε
1-ε
2 + 2ε
0
1+ε
最適フロー（流量２）
2
2δ
1-ε
0
2×２δ+ (1-ε)×(1-δ)×2
1-δ 0
= 2 – 2ε+ 2δ+εδ
1-δ
→ 2 – 2ε （δ→ 0）
0
1-ε
Theorem 4.2.5 (Theorem 3.2.6)

ε∈ [0, 3) で、f が線形コスト関数を持つ (G, r, c) に対するε
近似ナッシュ均衡、f* が (G, r, c) に対する適切なフローで
あった場合、以下が成り立つ。
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)
ce(fe/2)
a
b
a
b×b≧a×a +(b-a)×2a
a
(b - a)2 ≧ 0
b
fe/2 f*e
x
fe
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)
4.3 枝が最大容量を持つ場合
(Definition 4.3.1)

以下の条件を満たすとき、枝が最大容量を持つ trafic routing
model (G, r, c, u) に対して、適切なフロー f がナッシュ均衡
であるという。

∈ {1, …, k} （品種） ∀P1, P2 ∈ Pi （パス集合）（但し、fP1 ＞ 0）, ∀δ ∈ (0,
fP1].
∀i
～
あるいは、f が適切なフローでない。
Example 4.3.3
1:∞
定数関数のみでも・・・
1:∞
0:1/2
1/2
0:1/2
s
1/2
0:∞
0:∞
s
0:∞
0:∞
0:∞
0:∞
0:1/2
s
1/2
t
0
0:1/2
1:∞
コスト:最大容量
0
1/2
t
0:1/2
∞
t
1/2
1/2
0:∞
0:∞
0:∞
0:1/2
Theorem 4.3.4 (Theorem 3.3.7)

コスト関数集合 C に対して anarchy value α(C) を同様に
定義する。ここで、コスト関数集合が C である (G, r, c, u) の
最適フローを f* としたとき、以下の式が成り立つようなナッ
シュフロー f が存在する。
Theorem 4.3.8, 4.3.9 (Theorem 3.6.2)

(G, r, c, u) に対して、以下の条件を満たすような
ナッシュフロー f が存在する。


(G, 2r, c, u) に対する全ての適切なフロー f*
(G, 2r, c, 2u) に対する全ての適切なフロー f*

Download Report