修士論文 要旨

多重集合を戦略としてもつコンジェスチョンゲーム
数理情報学専攻 48-176210
指導教員

城山 健吾
平井 広志 准教授が定義できて,1 はじめに利害が必ずしも一致しない状況において複数の人間

Φ(X−i , Q) − Φ(X) = πi (X−i , Q) − πi (X)の行動の最適戦略を分析する数学の理論をゲーム理論が成立し, Φ を局所的に最小化する戦略の組 X においという. コンジェスチョンゲーム (Rosenthal [11]) とてはどのプレイヤーも自分だけ戦略を変更しても自身は, 使う人数が多くなるほどコストが大きくなる限られのコストを小さくできないからである. また, 利己的なた資源を複数のプレイヤーがどう分け合えばよいかをプレイヤー達が自身のコストを小さくするように戦略考えるゲームのモデルであり, 応用例としては, 渋滞のを変更していくとポテンシャル関数も減少していくた解消やプロセッサースケジューリングなどがある. コンめ, 必ずナッシュ均衡に到達することもわかる.

ジェスチョンゲームは,しかし, ナッシュ均衡に到達するのは一般には指数時

Γ = (N, A, (Xi )i∈N , (ca )a∈A )(1)

間かかってしまうことがわかっている. そこで, プレイヤーがそれぞれ戦略を変更するとき, どんなクラスの組で表される. N はプレイヤーの集合 (|N | = n),のコンジェスチョンゲームでは多項式時間でナッシュ

A は有限な資源の集合 (|A| = m), Xi は A の部分集均衡に到達するかが研究されている. Ackermannら [1]合の集合族である (Xi ⊆ 2A ). 全てのプレイヤーはそは, マトロイドコンジェスチョンゲームというクラスでれぞれ戦略として, A の要素のうちいくつかを使用すは, 各プレイヤーが自身のコストを最小化するように戦る. プレイヤー i は自分の戦略として Xi の要素のう略を変える最適応答列によって多項式時間でナッシュ

ち 1 つをとれる. つまり, Xi はプレイヤー i がとれる均衡に到達することを示した. ここでマトロイドコン戦略の集合である. ca は資源 a を使う人 1 人当たりのジェスチョンゲームとは, 任意のプレイヤー i の戦略コストを表す. ca は a を使う人数に対する関数であり

Xi ⊆ 2A が資源集合 A 上のマトロイド Mi の基族と(ca : Z≥0 → R≥0 ), 単調非減少である. これは, 1 つのなっているコンジェスチョンゲームである.

資源を使う人数が多いほど 1 人当たりのコストは大きくなることを表している. ca (0) = 0 とする.
このときプレイヤー i のコストは

πi (X) =∑ca (σa (X))

2 多重集合のコンジェスチョンゲーム
これまでのコンジェスチョンゲームでは 1 人のプレイヤーは 1 つの資源を高々 1 回までしか使えないものa∈Xiだった. ここで 1 つの資源を同一のプレイヤーが複数回と表せる. ここで, X = (X1 , . . . , Xi , . . . , Xn ) はプレイ使ってもよい多重集合コンジェスチョンゲームを導入

ヤーが実際にとる戦略の組である. σa (X) は戦略の組する. これも, (1) 式の組で表される. N はプレイヤーのX のもとで資源 a を使う人数を表す. それぞれのプレ集合 (|N | = n), A は資源の集合 (|A| = m), Xi ⊆ ZA
≥0

イヤーは自身のコストをなるべく小さくしようとする

はプレイヤー i ∈ N がとれる戦略の集合であり, Xi のゲームにおける解としてはさまざまなものが提案さ

戦略 Xi ∈ ZA
≥0 を (Xi,a )a ∈ A で表し, Xi,a はプレイれているが, その 1 つにナッシュ均衡がある. ナッシュ

ヤー i が a を何回使うかを表すものとする. ca (a ∈ A)

均衡とは, どのプレイヤーも他のプレイヤーが戦略を変

は資源 a を使うプレイヤーの合計回数に対するコストえない限り自分の戦略をどう変えても利得を大きくでの関数である.

きない戦略の組み合わせのことである.
コンジェスチョンゲームではナッシュ均衡が必ず存在することが知られている [11]. これは, コンジェス
チョンゲームではポテンシャル関数

Φ(X) =a (X)∑ σ∑a∈A l=0

ここで, プレイヤーが 1 つの資源を使う回数に応じて, その資源を使うコストが増加するように定義するのが自然であるが, その方法は 1 通りではない.
プレイヤーの戦略 X

σa (X) =ca (l)∑= (X1 , . . . , Xn ) の 下 でj∈N Xj,a を a が使われる合計回数とす多重集合を戦略としてもつコンジェスチョンゲーム (城山 健吾)

ると, Harksら [6] は i が a を使うコスト ca,i (X) をca,i (X) = Xi,a ca (σa (X))

この補題より, プレイヤー i がコスト c の下で最適応答すると, c̃ の下でも i のコストは減少し, Φ̃ は減少する.と定義し, 戦略の集合がポリマトロイドのときにナッシュ均衡が存在することを示した.

0 ≤ Φ̃(X) =それに対し我々は ca,i (X) を∑≤ mn (rank(Γ))2ca (σa (X) − k + 1)

k=1と定義する (Xi,a = 0 のとき ca,i (X) = 0 とする). i のコスト πi (X) は

πi (X) =∑ca,i (X)a∈Aとなる. このとき, ポテンシャル関数

Φ(X) =a (X)∑ σ∑ca (l)a∈A l=0が定義できるため, 先と同じ議論から, 任意の戦略集合の下でナッシュ均衡が存在することがわかる.

3 ポリマトロイドコンジェスチョンゲーム
多重集合コンジェスチョンゲーム Γ に対して, 任意のプレイヤー i で Mi = (A, Xi ) が整ポリマトロイド (Xiが基) のとき, ポリマトロイドコンジェスチョンゲームという. ここで, Mi のランクを Xi の元の成分和とし,rank(Γ) = maxi∈N rankMi とする.
定理 1. ポリマトロイドコンジェスチョンゲームではプ
レイヤーの O(mn2 (rank(Γ))2 ) 回の最適応答によってナッシュ均衡に到達する.
この結果は, マトロイドコンジェスチョンゲームに対しての Ackermannら [1] のものの拡張となっている.
全てのコストca (k) (k = 0, 1, 2, . . . , nrank(Γ), |A| = m)を非減少の順に並べる. このとき新しくコストc̃a : Z≥0 → R≥0 を c̃a (i) = (ca (i) の順位) と定義す
る. c の値が等しいとき c̃ の値も等しい. このとき,

1 ≤ c̃a (k) ≤ mnrank(Γ) である. 次が成り立つ.
補題 1. X = (X1 , . . . , Xi , . . . , Xn ) に対するプレイ
ヤー i の最適戦略を Xi∗ とし, ca (i) に対する i のコスト πi を厳密に減少させるとする. このとき, X ∗ =(X1 , . . . , Xi∗ , . . . , Xn ) は c̃a (i) に対するコスト π̃i も厳密に減少させる.

c̃a (i)a∈A i=12

Xi,aca,i (X) =a (X)∑ σ∑

で あ り Φ̃ は 整 数 値 で あ る こ と か ら,
2高々

2mn (rank(Γ)) 回のプレイヤーの最適応答によってナッシュ均衡に到達する.

参考文献[1] H. Ackermann, H. Röglin and B.Vöcking: On theImpact of Combinatorial Structure on Congestion
Games. Journal of the ACM, 55 (2008), pp. 25:1–25:22.
[2] J. Edmonds: Submodular Functions, Matroids andCertain Polyhedra. In Combinatorial Structures andTheir Applications (R. Guy, H. Hanani, N. Sauer andJ. Schönheim, eds.), Gordon and Breach, New York(1970), pp. 69–87.
[3] A. Fabrikant, C. Papadimitriou and K. Talwar: TheComplexity of Pure Nash Equilibria. In Proceedings ofthe 36th ACM Symposium on Theory of Computing,(2004), pp. 604–612.
[4] D. Fotakis: Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy.
Theory of Computing Systems, 47 (2010), pp. 113–136.
[5] S. Fujishige, M. Goemans, T. Harks, B. Peis andR. Zenklusen: Congestion games viewd from Mconvexity. Operations Research Letters, 43 (2015), pp.
329–333.
[6] T. Harks, M. Klimm and B. Peis: Resource Competition on Integral Polymatroids. In Proceedings of the10th Web and Internet Economics, (2014), pp. 189–202.
[7] R. Holzman and N. Law-yone: Network Structure andStrong Equilibrium in Route Selection Games. Mathematical Social Sciences, 46 (2003), pp. 193–205.
[8] S. Ieong, R. McGrew, E. Nudelman, Y. Shoham andQ. Sun: Fast and Compact: A Simple Class of Congestion Games. In Proceedings of the 20th American Association for Artificial Intelligence, (2005), pp.
489–494.
[9] D. S. Johnson and C. H. Papadimitriou: How Easy
Is Local Search? Journal of Computer and System
Sciences, 37 (1988), pp. 79–100.
[10] J. F. Nash: Equilibrium Points in n-Person Games.
National Academy of Sciences, 36 (1950), pp. 48–49.
[11] R. W. Rosenthal: A Class of Games Possessing PureStrategy Nash Equilibria. International Journal ofGame Theory, 2 (1973), pp. 65–67.
[12] H. Whitney: On the Abstract Properties of Linear
Dependence. The American Journal of Mathematics,
57 (1935), pp. 509–533.