2014 BinN 理論談話会#13

Congestion pricing andlearning in traffic network games
Melo,Emerson.
journal of Public Economic Theory,
Vol. 13(3), pp. 351-367, 2011.
2014.06.28(Fri)

M1

芝原 貴史

もくじ
1. Introduction
2. Congestion Pricing and Payoﬀ-Based AdaptiveDynamics
3. Global Convergence of the Learning Process
1. Rest Points and Nash Equilibrium
2. The Symmetric Case
4. Comments and Final Remarks2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games

2

1.Introduction• 交通混雑は典型的な外部不経済の問題– 経済学的な解法はPigou（1920）– Merginal Cost Pricing (Beckmann, McGuire, andWinstein (1956))– すべての経路に外部不経済に応じた課金＝走行すること自体が他者に影響を与えることが– ユーザーは経路の遅延によるコストと，料金によるコストの2つを考慮しなければならない．

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games

3

1.Introduction•

この施策は，プランナーがユーザーの情報を得ていることを前提にしている．
• 均衡状態にどのように到達するかがわからない．
•

均衡状態への到達を動的に示した論文は，Sandholm (2005,2007)がある．
– Sandholm(2005)では進化ゲーム理論を集計人口レベルで用いる．
– Sandholm(2007)では個人のプレイヤーを想定した．
– これらの論文は，計画者がmerginal costを導入することでゲームがナッシュ均衡へ収束することを示す．古典的にはRosenthal(1973)で示された．
– Monderer and Shapley(1996) and Sandholm(2001)で一般化されて示された．

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games

4

1.Introduction••

本論文では，学習過程の適用を提案．
Pay-oﬀ based な過程（Cominetti, Melo, and Sorin(2010)）で交通ゲームの文脈で効率的な均衡状態に至る収束過程を証明する．

•

ルールは，
– プレイヤーは前もって各選択肢の利得を推定可．
– 効用最大化理論に基づき，ロジットモデルを用いて選択確率を表現．
– プレイヤーは以前通った経路の利得のみ知覚できるが，これは他のプレイヤー全員の選択から決定される混雑度合いに依存．
– プランナーはプレイヤーの利得を平準化．このときの経済原理で効率的な均衡状態に到達．
– その利得がその選択肢の次回以降の利得として更新＝学習過程– これを繰り返し行う

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games

5

1.Introduction• 論文の特徴は以下2つ• Reinforcemet model に似た学習過程を使用．
– 確率的選択と緩やかな適用？の性質を持つ• Merginal cost pricing という単純な施策がプランナーの有効な分散手法であることを理論的に示した．
– 多くのプレイヤーのいる交通戦略において最小の情報を集めれば良いということ– リアプノフ関数を用いてCominetti, Melo, andSorin(2010)とは異なる結果を得た．

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games6

2.Congestion Pricing and PayoffBased Adaptive Dynamics
N ：プレイヤーの総数
i ∈ P：選択したプレイヤーir ∈ R：選択したルート
cur ： u 人のユーザーが通るときの経路 r の平均旅行時間
Si = R：ユーザー i の純粋戦略の集合

Δ=∏

i∈P

Δi

gni = G i (rn ) = −cur
利得：stage n におけるユーザー i が経路 r を選択したとき

コストxni ∈ ( xnir )in：純粋戦略Siの元での混合戦略の集合

i：経路rについて個人iが認知している旅行時間r∈Rinπ = σ (x ) ∈ Δ
2014 BinN理論談話会 #13

i：期待利得σ ir (x i ) =exp ( βi x ir )∑ exp (β x )
ia

（1）

ia∈R

Congestion pricing and learning in traffic network games7

2.Congestion Pricing and PayoffBased Adaptive Dynamics
iri

σ (x ) =exp ( βi x ir )∑ exp (β x )
ia（1）

ia∈R

••
•

プレイヤーの利己的な戦略は他者の利得を見越したものではない
ナッシュ均衡は非効率的な均衡状態といえる．
この選択はプランナーの目的に反する→個々の選択を考慮した，効用の総和の最大化＝ネットワークの総コスト最小化問題と等価．

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games8

2.Congestion Pricing and PayoffBased Adaptive Dynamics• 定式化

cur ： u 人のユーザーが経路 r を選択したときのコスト$'r r
H (π ) = −E &∑U cUr )%r∈R(Ur = ∑i∈P

X ir

P ( X ir = 1) = π ir

H :[0,1]P×R → R

X ir ：ベルヌーイ分布の確率変数

π ni = σ i (xni) ∈ Δ i ：期待利得
xni ∈ ( xnir )•：経路rについて個人iが認知している旅行時間r∈R(2)を最大化するように，プランナーはmerginal costる．

2014 BinN理論談話会 #13(2)r
Ur を考えcCongestion pricing and learning in traffic network games9

2.Congestion Pricing and PayoffBased Adaptive Dynamicsru• (2)を最大化するためにプランナーは各経路に税 pす.
ru

r
u

ru−1

p = (u −1)(c − c )∀r ∈ Rを課(3)

ru ：経路rをu人のユーザーが通っているときの税p• この定式化は古典的な merginal cost pricing を動的に発展させたもの

2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games 10

2.Congestion Pricing and PayoffBased Adaptive Dynamics• Stage n において割引された利得とコストは，!gin = G! i ( rn ) = G i ( rn ) − pur = −c!ur∀r ∈ Rc!ur = cur + pur•

c!urが凸で増加関数なら，2014 BinN理論談話会 #13!c1r ≤ c!2r " ≤ c!NrCongestion pricing and learning in traffic network games 11

2.Congestion Pricing and PayoffBased Adaptive Dynamics• 学習過程のフローと定式化
x irn ：n期，個人iの経路rについて認知している利得	  ↓π irn ：n期に個人iが経路rを選択する確率	  ↓r in ：n期に個人iに選択された経路	  ↓"iiri!
r1−γx+γg$if()n =rnnn nir
x n+1 = #xnir$%otherwise

γ n ∈ ( 0,1)

Averaging	  factor

urn ：n期，経路rの混雑	  ↓∑ γ =∞ ∑ γg! in ：混雑度による課税を考慮した利得	  ↓γn =n n1n2n n<∞普通は←と書くx irn+1 ：n+1期，個人iの経路rについて認知している情報（更新）	  2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games 12

2.Congestion Pricing and PayoffBased Adaptive Dynamics"iri!
1−γx+γg$()nnn
x irn+1 = #xnir$%• 学習過程の定式化

xirn+1irn− x = γ n [ wn − xn ]" !i$ gnir
w n = # ir$% x nifr in = rotherwise(4)

ifr in = r(5)otherwise• (4)の式は確率的アルゴリズムを含み，wn は個人のロジット型選択確率（以前の認知 xn に基づき決定）から決まる
2014 BinN理論談話会 #13

Congestion pricing and learning in traffic network games 13

2.Congestion Pricing and PayoffBased Adaptive Dynamics• (4)式の１階微分は以下のように書ける．(appendix参照)

dx= E (w | x) − xdt• この式を，すと，？

(6)

π ir = P ( X ir = 1)

irの条件の元で書き下rir
rr
"
$"
$!
F (π ) = E #−cU r | X = 1% = E #− cU r +1 + pU r +1 %ii(U =∑ Xrik≠i2014 BinN理論談話会 #13kr)(7)

Fは他者がπで選択することを前提としたときの，	  ユーザーiによって観測される平均コストを表す．	  
Congestion pricing and learning in traffic network games 14

2.Congestion Pricing and PayoffBased Adaptive Dynamics
Ω=∏RR• 認知旅行時間の空間をと定義
i∈P• 写像 C : Ω → Ωによって利得ベクトルは以下のように書ける．
irir

C ( x ) = F ( Σ ( x ))(８)

• ロジット型選択確率は写像 Σ : Ω → Δとで組み入れることができる．

(

Σ( x) = σ ( x )2014 BinN理論談話会 #13ii)

i∈Pで表現するこ(９)Congestion pricing and learning in traffic network games 15

2.Congestion Pricing and PayoffBased Adaptive Dynamics• 補助命題１– U ijr = ∑irk≠i, jX kr(とするとき，)(F (π ) = E −cUr r +1 + ∑σ jr ( x j ) E −ΔcUr r +2ij≠iij)

ir
F (π ) = E "#−c!Ur r | X ir = 1$% = E "#− cUr r +1 + pUr r +1 $%((()) (i) (iE − cUr r +1 + pUr r +1 = E −cUr r +1 + E − pUr r +1(ii) ( (iE − pUr r +1 = E −U ir cUr r +1 − cUr ri(ii2014 BinN理論談話会 #13r
pur = (u −1)(cur − c u−1))より))= E −∑ X jr ΔcUr r +1j≠ii)i)(= ∑σ jr ( x j )E −ΔcUr r +2j≠iij)

Congestion pricing and learning in traffic network games 16

2.Congestion Pricing and PayoffBased Adaptive Dynamics• 提案１：(6)は下のように書けるのではないか．

dx= E (w | x) − x
dt

(6)

ir

dx
ir
i " ir= σ ( x )$C ( x ) − x ir %'#&dtirir(Σ( x) = σ ( x )C ( x ) = F ( Σ ( x ))ir()ii(10))

i∈P

π ni = σ i (xni) ∈ Δ i(C ( x ) = E −cUr r +1 + ∑σ jr ( x j ) E −ΔcUr r +2
2014 BinN理論談話会 #13

ij≠iijより)Congestion pricing and learning in traffic network games 17

3. Global Convergence of theLearning Process• (7)の形で表される利得の写像は，ポテンシャル関数の勾配としても表せる．(Monderer and Shapley (1996))• 今回提案する関数形は，Sandholm(2001)に近い．ポテ(7)ンシャル関数をHで表せることが興味深い．
irr
irrr""$!
F (π ) = E #−cU r | X = 1% = E #− cU r +1 + pU r +1 $%ii(P×RH :[0,1]
2014 BinN理論談話会 #13$'r r
H (π ) = −E &∑U cUr )%r∈R()(2)

Congestion pricing and learning in traffic network games 18

3. Global Convergence of theLearning Process• 提案2

F (π ) = ∇H (π )for	  allπ ∈ΔirF (π ) = E "#−c!Ur r | X ir = 1$% = E "#− cUr r +1 + pUr r +1 $%(• 証明ii)(7)

r $H (π ) = −∑ E "#U r cUr%r∈Rr $H (π ) = −∑ "#π ir E (U ir +1) cUr r+1 + (1− π ir ) E (U r cUr)%(r∈Ri)∂Hr
π = −E (U ir +1) cUr r+1 + E (U r cUr)
ir ( )i∂π()ir= E "#− cUr r +1 + pUr r +1 $% = F (π )(i2014 BinN理論談話会 #13i)

Congestion pricing and learning in traffic network games 19

3. Global Convergence of theLearning Process• 補助命題22∂ H#c r − c r % ∈ −2δ, 0 ,π=2E[]
jrir ( )U ijr +1U ijr +2 &$∂π ∂πwith j ≠ i, where U ijr = ∑ X krk≠i, j• 補助命題3∇πir(x ) = β π ∑ δ − πiir

12014 BinN理論談話会 #13iara∈Ria

1= 2 βi π (1− π ) ≤ βi2irir

Congestion pricing and learning in traffic network games 20