多重集合を戦略としてもつコンジェスチョンゲームについて

全文

(1)

多重集合を戦略としてもつコンジェスチョンゲームについて

01507724 東京大学 平井広志 HIRAI Hiroshi

東京大学 *城山健吾 SHIROYAMA Kengo

1.

はじめに

利害が必ずしも一致しない状況において複数 の人間の行動の最適戦略を分析する数学の理論 をゲーム理論という. コンジェスチョンゲーム (Rosenthal[3])とは,使う人数が多くなるほどコス トが大きくなる限られた資源を複数のプレイヤー がどう分け合えばよいかを考えるゲームのモデル であり, 応用例としては, 渋滞の解消やプロセッ サースケジューリングなどがある. コンジェスチョ ンゲームは,

Γ = (N, A,(Xi)i∈N,(ca)a∈A) (1) の組で表される. Nはプレイヤーの集合(|N|=n), Aは有限な資源の集合(|A|=m),XiAの部分 集合の集合族である(Xi 2A). 全てのプレイヤー はそれぞれ戦略として, Aの要素のうちいくつか を使用する. プレイヤーiは自分の戦略としてXi

の要素のうち1つをとれる. つまり, Xiはプレイ ヤーiがとれる戦略の集合である. caは資源aを 使う人1人当たりのコストを表す. caaを使う 人数に対する関数であり(ca :Z0 R0), 単調 非減少である. これは, 1つの資源を使う人数が多 いほど1人当たりのコストは大きくなることを表 している. ca(0) = 0とする.

このときプレイヤーiのコストは πi(X) = ∑

aXi

caa(X))

と表せる. ここで,X = (X1, . . . , Xi, . . . , Xn)はプ レイヤーが実際にとる戦略の組である. σa(X)は 戦略の組Xのもとで資源aを使う人数を表す. そ れぞれのプレイヤーは自身のコストをなるべく小 さくしようとする

ゲームにおける解としてはさまざまなものが提 案されているが,その1つにナッシュ均衡がある. ナッシュ均衡とは, どのプレイヤーも他のプレイ ヤーが戦略を変えない限り自分の戦略をどう変え

ても利得を大きくできない戦略の組み合わせのこ とである.

コンジェスチョンゲームではナッシュ均衡が必 ず存在することが知られている[3]. これは, コン ジェスチョンゲームではポテンシャル関数

Φ(X) =∑

a∈A σa(X)

l=0

ca(l)

が定義できて,

Φ(Xi, Q)−Φ(X) =πi(Xi, Q)−πi(X) が成立し, Φを局所的に最小化する戦略の組Xに おいてはどのプレイヤーも自分だけ戦略を変更し ても自身のコストを小さくできないからである. た, 利己的なプレイヤー達が自身のコストを小さ くするように戦略を変更していくとポテンシャル 関数も減少していくため,必ずナッシュ均衡に到達 することもわかる.

しかし, ナッシュ均衡に到達するのは一般には 指数時間かかってしまうことがわかっている. そ こで,プレイヤーがそれぞれ戦略を変更するとき, どんなクラスのコンジェスチョンゲームでは多項 式時間でナッシュ均衡に到達するかが研究されて いる. Ackermannら[1]は,マトロイドコンジェス チョンゲームというクラスでは, 各プレイヤーが 自身のコストを最小化するように戦略を変える最 適応答列によって多項式時間でナッシュ均衡に到 達することを示した. ここでマトロイドコンジェ スチョンゲームとは, 任意のプレイヤーiの戦略 Xi 2Aが資源集合A上のマトロイドMiの基族 となっているコンジェスチョンゲームである. 2.

多重集合のコンジェスチョンゲーム

これまでのコンジェスチョンゲームでは1人のプ レイヤーは1つの資源を高々1回までしか使えない ものだった. ここで1つの資源を同一のプレイヤー が複数回使ってもよいマルチセットコンジェスチョ ンゲームを導入する. これも, (1)式の組で表され

1-E-2

日本オペレーションズ・リサーチ学会

2019年 春季研究発表会

(2)

る. Nはプレイヤーの集合(|N|=n),Aは資源の 集合(|A|=m), Xi ZA0はプレイヤーi∈N が とれる戦略の集合であり, Xi の戦略Xi ZA0 (Xi,a)a∈Aで表し,Xi,aはプレイヤーiaを何 回使うかを表すものとする. ca(a∈A)は資源a 使うプレイヤーの合計回数に対するコストの関数 である.

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

プレイヤーの戦略 X = (X1, . . . , Xn) の下で σa(X) = ∑

jNXj,a aが使われる合計回数と すると, Harksら[2]はiaを使うコストca,i(X) を

ca,i(X) =Xi,acaa(X))

と定義し, 戦略の集合がポリマトロイドのときに ナッシュ均衡が存在することを示した.

それに対し我々はca,i(X)を

ca,i(X) =

Xi,a

k=1

caa(X)−k+ 1)

と定義する(Xi,a= 0のときca,i(X) = 0とする).

iのコストπi(X)は

πi(X) =∑

aA

ca,i(X) となる. このとき,ポテンシャル関数

Φ(X) =∑

aA σa(X)

l=0

ca(l)

が定義できるため,先と同じ議論から,任意の戦略 集合の下でナッシュ均衡が存在することがわかる. 3.

ポリマトロイドコンジェスチョンゲーム

多重集合コンジェスチョンゲームΓに対して,任 意のプレイヤーiMi = (A,Xi)が整ポリマトロ イド(Xiが基)のとき,ポリマトロイドコンジェス チョンゲームという. ここで, MiのランクをXi

の基の成分和とし, rank(Γ) = maxiNrankMiと する.

定理 1. ポリマトロイドコンジェスチョンゲーム ではプレイヤーのO(mn2(rank(Γ))2)回の最適応 答によってナッシュ均衡に到達する.

この結果は,マトロイドコンジェスチョンゲーム に対してのAckermannら[1]のものの拡張となっ ている.

全てのコスト

ca(k) (k= 0,1,2, . . . , nrank(Γ),|A|=m) を非減少の順に並べる. このとき新しくコスト

˜

ca :Z0 R0c˜a(i) = (ca(i)の順位)と定義 する. cの値が等しいとき˜cの値も等しい.

1 ˜ca(k) mnrank(Γ)である. このとき, 次が 成り立つ.

補題 1. X = (X1, . . . , Xi, . . . , Xn)に対するプレ イヤーiの最適戦略をXiとし,ca(i)に対するiの コストπiを厳密に減少させるとする. このとき, X = (X1, . . . , Xi, . . . , Xn)˜ca(i)に対するコスπ˜iも厳密に減少させる.

この補題より,プレイヤーiがコストcの下で最 適応答すると, ˜cの下でもiのコストは減少し, ˜Φ は減少する.

0Φ(X)˜ = ∑

aA σa(X)

i=1

˜ ca(i)

mn2(rank(Γ))2

で あ り Φ˜ は 整 数 値 で あ る こ と か ら, 高々 mn2(rank(Γ))2 回 の プ レ イ ヤ ー の 最 適 応 答 に よってナッシュ均衡に到達する.

謝辞

本 研 究 は JSPS 科 研 費 JP17K00029,

JP26280004の助成を受けたものです.

参考文献

[1] H. Ackermann, H. R¨oglin and B.V¨ocking : On the Impact of Combinatorial Structure on Congestion Games. Journal of the ACM,55 (2008), pp. 25:1–25:22.

[2] T. Harks, M. Klimm, B. Peis : Resource Competition on Integral Polymatroids. Web and Internet Economics, Beijing, China, De- cember 2014, pp. 189–202

[3] R. W. Rosenthal : A Class of Games Possess- ing Pure-Strategy Nash Equilibria. Internat.

J.Games Theory,2 (1973), pp. 65–67.

Updating...

参照

Updating...

関連した話題 :

Scan and read on 1LIB APP