西村　亮一 　 Nash 均衡問題と解の一意性 N 人非協力ゲームに対するロバスト

特別研究報告書

N

ロバスト

Nash

指導教員 福嶋雅夫 教授      林 俊介 助手     

京都大学工学部情報学科 数理工学コース

平成１５年４月入学 平成１９年３月卒業

西村 亮一

平成１９年１月３１日提出

N

ロバスト

Nash

西村 亮一 摘要

非協力ゲームとは，各プレイヤーが他のプレイヤーとは独立に意思決定する状況をモデル化した ものであり，その重要な均衡概念として知られるのがNash^{均衡である．}Nash^{均衡は，各プレイ} ヤーがゲームのルールについて完全な知識，すなわち，ゲームのすべてのパラメータや各プレイ ヤーのコスト関数などの情報を持ち，それ自体がプレイヤーの共通認識であるという前提の下で意 味をもつ．しかし，現実の問題においては，その前提が満たされるとは限らない．そこで，ゲーム のルールについてプレイヤーが不確実な情報しかもたない情報不完備ゲームをモデル化することが 重要になってくる．これまで情報不完備ゲームに対して多くの研究がなされてきたが，本報告書で は，その中でも特に各プレイヤーが不確実な情報の下で，ロバスト最適化と呼ばれる概念に基づい て自分の戦略を決定することを仮定したモデルを考える．このモデルにおいて起こり得る均衡状態 をロバストNash均衡といい，その均衡点を求める問題をロバストNash^{均衡問題という．}

本報告書では，まず，既存のロバストNash均衡の概念をより一般化し，プレイヤーの数がN^人 で，各プレイヤーのコスト関数（利得関数）が自分の戦略に関して非線形な場合に対して，ロバス トNash均衡を定義する．さらに，コスト関数や戦略集合に対する凸性とコンパクト性の仮定のも とで，ロバストNash均衡解の存在性を示す．さらに，ロバストNash均衡問題を等価な一般化変 分不等式問題に変換することにより，ロバストNash均衡解が一意に存在するための十分条件を与 える．特に，各プレイヤーのコスト関数が二次の項を含み，不確実性を表す集合が二次のノルムを 用いて表されるロバストNash均衡問題を二次錐相補性問題として再定式化できることを示す．二 次錐相補性問題に対するアルゴリズムを用いた数値実験を行い，ロバストNash^{均衡解の性質を調} べる．

目次

1 序論 1

2 ^定式化 2

3 ^ロバストNash^{均衡解の存在} 3

4 ^ロバストNash^{均衡解の一意性} 5

5 ロバストNash均衡問題の二次錐相補性問題への定式化 8 5.1 相手の戦略の評価に不確実性がある場合 . . . 9 5.2 コスト関数に不確実性がある場合 . . . 12

6 数値実験 15

6.1 ロバストNash均衡解とコスト関数値の関係 . . . 16 6.2 不確実性集合の大きさとロバストNash均衡解の関係 . . . 18

7 ^結論 23

1

私たちは，個人，または企業などの組織において，様々な意思決定を行っている．私たちの意思決定は，他の 人々の意思決定に影響を及ぼし，同様に他の人々の意思決定は，私たちの意思決定に影響を及ぼす．ゲーム理 論は，経済や社会における様々な意思決定を数理的な方法論を用いて分析する理論である[18]．Nash [16, 17]

は非協力ゲームを最初に定義し，それに対して均衡解（Nash均衡解）の概念を提示した．Nash均衡解は，各 プレイヤーはゲームのルールについて完全な知識，すなわち，ゲームのすべてのパラメータや各プレイヤーの コスト関数などの情報を持ち，またそれ自体がプレイヤーの共通認識であるという前提の下で意味をもつ．こ の前提を情報完備という．しかし，現実の問題において，情報完備の前提が満たされるとは限らない．そこ で，ゲームのルールについてプレイヤーが不完全な知識しか持っていない情報不完備ゲームが多くの研究者に よって研究されている．

Harsanyi [13, 14, 15]は，情報不完備ゲームを定式化した．その定式化では，不確実な情報の下での意思決

定に対して，それらの真の値を確率分布の形で予想し，各プレイヤーはその確率分布のもとでの期待値を最適 化するというベイジアン仮説を採用した．さらに，確率分布に対するある仮定の下で，情報不完備ゲームを変 換してベイジアンゲームを定義した．ベイジアンゲームは，情報不完備ゲームから定義されるゲームである が，ベイジアンゲームの構成要素に関しては完全な知識をもつ情報完備ゲームである．情報不完備ゲームとベ イジアンゲームは，プレイヤーにとって戦略上の観点からは同値であると見なせる．

Aghassi and Bertsimas [1]やHayashi, Yamashita, and Fukushima [11]は，情報不完備ゲームに対して，ベイ ジアンゲームの仮定を緩和して確率分布を用いないモデルを提案した．彼らのモデルでは，各プレイヤーがロ バスト最適化[4, 5, 6]を行うことにより自分の戦略を決定することが仮定されている．ここで，ロバスト最 適化とは，不確実なパラメータを含むが，そのパラメータが少なくともある範囲内（不確実性集合）に入っ ていることが期待できる最適化問題に対して，その範囲内で起こり得る最悪のケースを想定して最適化を行 うものである．各プレイヤーがロバスト最適化を行った結果起こり得る均衡状態をロバストNash均衡とい う．また，そのような均衡点を求める問題をロバストNash均衡問題という．Aghassiら[1]は，N人のプレ イヤーがそれぞれ線形計画問題（Linear Programming : LP）を解くようなゲームを考え，それに対してロバス トNash均衡^*1を定義した．さらに，不確実性集合が凸多面体である問題に対して，ロバストNash均衡解を 求める方法を提案した．Hayashiら[11]は，Aghassiら[1]とは独立に，双行列ゲームに対してロバストNash 均衡の概念を定義した．彼らは，不確実性集合がユークリッドノルムやフロベニウスノルムを用いて表される という仮定の下で，各プレイヤーの解くべき最適化問題を二次錐計画問題（Second-Order Cone Programming : SOCP）[2]として再定式化し，その結果，ロバストNash均衡問題が二次錐相補性問題（Second-Order Cone Complementarity Problem : SOCCP）に帰着されることを示した．なお，Aghassiら[1]のモデルでは，各プレ イヤーが解くべき最適化問題に含まれる行列やベクトルのみに不確実性が仮定されているのに対し，Hayashi ら [11]は，他のプレイヤーの戦略にも不確実性が存在する場合も取り扱っている．

本報告書では，Hayashi [11]らの取り扱った問題を拡張して，N 人非協力ゲームに対するロバストNash均 衡の概念を定義する．特に，解の存在性を示すにあたって，Aghassiら[1]やHayashiら [11]は，各プレイ ヤーのコスト関数（利得関数）が自分の戦略に対して線形な場合のみを考えたが，本報告書ではコスト関数が 自分の戦略に関して凸な関数を考える．そして，適当な仮定の下で，ロバストNash均衡解が一意に存在する

*1Aghassiらの論文ではロバスト最適化均衡と書かれているが，実質的に同じものである．

ことを示す．また，Hayashiら[11]が提案した手法を用いて，各プレイヤーのコスト関数が自分の戦略に関し て2次の項を含むようなロバストNash均衡問題をSOCCPに再定式化する．

本報告書の構成は，次の通りである．第2節では本報告書で扱うゲームを定式化し，ロバストNash均衡の 概念を定義する．第3節でロバストNash均衡解の存在条件を示す．第4節では適当な仮定の下で，ロバスト Nash均衡解が一意に存在することを示す．第5節では，いくつかのケースに対して，ロバストNash均衡問

題をSOCCPに再定式化する．第6節で，それらの問題に対する数値実験を行ってロバストNash均衡解の性

質を調べる．

本報告書を通じて，以下の表記法を用いる．集合X に対して，X のすべての部分集合の集合をP(X)^と 表す．ℜⁿ₊は各成分が非負であるようなn次元実ベクトルの集合を表す．すなわち，ℜⁿ₊ := {x ∈ ℜⁿ | xi ≥ 0(i =1, . . . ,n)}^{である．ベクトル}x ∈ ℜ^{n に対して，}∥x∥ :=√

x^Tx はユークリッドノルムを表す．行列 M ∈ ℜ^{n×m に対して，}∥M∥F :=(∑_n

i=1

∑_m

j=1(M_{i j})²)^1/2はフロベニウスノルムを表す．

2

本報告書では，N 人のプレイヤーが，それぞれ自らのコスト関数を最小化しようとする非協力ゲームを考え る．各プレイヤーi∈ {1, . . . ,N}^{に対して，}xⁱ ∈ ℜ^{mi をプレイヤー}iの戦略，集合S_i ⊆ ℜ^{mi を許容戦略集合，}

f_i :ℜ^m1× · · · × ℜ^mN → ℜをコスト関数とする．また，表記を簡単にするために，以下の記号を導入する．

x :=(x^j)^N_j=1 x⁻ⁱ :=(x^j)^N_j=1,j̸=i

m :=

∑N i=1

m_i m₋i :=m−mi

S_−i :=

∏N j=1,j̸=i

S_j

情報完備の前提が満たされるならば，各プレイヤーi は他のN −1人のプレイヤーの戦略x⁻ⁱ を固定した 次の最小化問題を解くことによって，自らの戦略を決定する．

minimize

xⁱ

f_i(xⁱ,x⁻ⁱ) subject to xⁱ ∈S_i

(1)

各プレイヤーi ∈ {1, . . . ,N}^{に対して，}xⁱ ∈argmin_xi∈Si f_i(xⁱ,x⁻ⁱ)^{が成り立つとき，点}(x¹,x², . . . ,x^N)^を Nash均衡解と呼ぶ．すなわち，各プレイヤーがそれぞれ戦略x¹,x², . . . ,x^N をとるとき，どのプレイヤーも 戦略を変える動機を持たないことを意味する．Nash均衡解の概念が意味をもつためには，各プレイヤーが自 分以外のN−1人の相手の戦略，あるいは，自分のコスト関数を正確に評価できなければならない．しかし，

実際の問題においては，時間による変化や推定誤差などのため，情報に不確実性が存在する．そこで本報告書 では，不確実な情報をもったゲームを考える．

以下では，不確実な情報をもつN 人非協力ゲームに対して，ロバストNash均衡解を定義する．各プレイ

ヤーi ∈ {1, . . . ,N}がとる行動に対して次の3つの前提条件が成り立っているものとする．

1. プレイヤーiのコスト関数は，パラメータuⁱ ∈ ℜ^{νi に依存して，}f_i^ui :ℜ^mi × ℜ^m−i → ℜ^{と表される．}

しかし，プレイヤーiはそのパラメータuⁱを厳密には推定できず，空でない集合U_i ⊆ ℜ^{νi に含まれて} いると予想する．

2. プレイヤーi は他のN−1人のプレイヤーの戦略x⁻ⁱ を正確に知っているが，実際にコスト関数の値 が計算されるときには，他者の戦略はx⁻ⁱ+δx⁻ⁱ のようにδx⁻ⁱ だけの「ずれ」を含んだ形で評価され る．しかし，プレイヤーiはδx⁻ⁱ の値を事前に知ることはできず，xˆ⁻ⁱ :=x⁻ⁱ+δx⁻ⁱ が，空でない集 合X_−i(x⁻ⁱ)に含まれていると予想する．

3. プレイヤーiは条件1,2の下で起こり得る最悪のケースを想定し，そのコストを最小化しようとする．

このとき，プレイヤーiが想定する最悪のコストを表す関数 f˜i :ℜ^mi × ℜ^m−i →(−∞,+∞]は次のように定 義できる．

f˜_i(xⁱ,x⁻ⁱ):=sup{f_i^uˆi(xⁱ,xˆ⁻ⁱ)| ˆu_i ∈U_i,xˆ⁻ⁱ ∈ X_−i(x⁻ⁱ)} (i =1, . . .N) (2) さらに，各プレイヤーi∈ {1, . . . ,N}が解くべき最小化問題は以下で表される．

minimize

xⁱ

f˜_i(xⁱ,x⁻ⁱ) subject to xⁱ ∈S_i

(3)

以上の準備の下で，ロバストNash均衡解を定義する．

定義2.1. 関数 f˜_i が(2)で定義されているとする．さらに，ある戦略の組(x¹, . . . ,x^N)∈ S₁× · · · ×S_N が，

xⁱ ∈argmin_xi∈S_i f˜_i(xⁱ,x⁻ⁱ) (i =1, . . . ,N)を満たしている，すなわち，ゲーム(3)のNash均衡解になってい るとする．このとき，戦略の組(x¹, . . . ,x^N)^をゲーム(1)のロバストNash均衡解という．

3

Nash

本節では，ロバストNash均衡解が存在するための十分条件を与える．そのために，まず，点-集合写像の連 続性を定義する[9, P.89]．なお，前節の前提条件2の中で与えられているX₋i(·)^は，点-集合写像とみなせる ことに注意する．

定義3.1.  

1. 点-集合写像 A : U → P(X)^が点u ∈ U のまわりで一様有界であり，さらにu^k → u,x^k → x かつ x^k ∈ A(u^k)(k=1,2, . . . )であるような任意の点列{u^k} ⊆U ,{x^k} ⊆X に対してx∈ A(u)^{が成立する} とき，点uにおいて上半連続であるという．

2. 点-集合写像A : U →P(X)^がu^k →u ∈U となる任意の点列{u^k} ⊆Uとx∈ A(u)^{を満たす任意の} 点x ∈ Xに対して，x^k → xかつx^k ∈ A(u^k)(k≥k₀)^{であるような整数}k₀>0と点列{x^k} ⊆ Xが存 在するとき，点uにおいて下半連続であるという．

3. 点-集合写像 A : U →P(X)^がu ∈U において上半連続かつ下半連続であるとき，点uにおいて連続 であるという．

以下では，前節の条件1,2で与えられているX₋i(·)^とUi および関数 f^ui，集合Si (i =1, . . . ,N)^{に対して，}

次の仮定が満たされているとする．

仮定1.  

(a) G_i(xⁱ,x⁻ⁱ,uⁱ):= f_i^ui(xⁱ,x⁻ⁱ)^{で定義される関数}G_i :ℜ^mi × ℜ^m−i × ℜ^νi → ℜ^{は，任意の点}(xⁱ,x⁻ⁱ,uⁱ) で連続である．

(b) 任意のx⁻ⁱ ∈ ℜ^{m−i において，点}-集合写像X_−i :ℜ^m−i →P(ℜ^m−i)^{は連続であり，}X_−i(x⁻ⁱ)^{は空でない} コンパクト集合である．

(c) Ui ⊆ ℜ^νi は，空でないコンパクト集合である．

(d) Si は空でないコンパクト凸集合である．また，x⁻ⁱ,uⁱ を任意に固定したとき，関数 f_i^ui(·,x⁻ⁱ):ℜ^mi → ℜ はSi上で凸である．

この仮定1(a)–(c)より，f˜_i はすべての(xⁱ,x⁻ⁱ)∈ ℜ^mi × ℜ^m−i において有限値をとり，連続となる．また，

すべてのi ∈ {1, . . . ,N}に対して次の補題が成り立つ．

補題3.1. 仮定1が成り立つとする．このとき，任意に固定したx⁻ⁱ ∈S_−iに対して，関数 f˜_i(·,x⁻ⁱ):ℜ^mi → ℜ はS_i 上で凸である．

証明. プレイヤーi ∈ {1, . . . ,N}を任意に選び，他者の戦略x⁻ⁱ ∈S_−i を任意に固定する．さらに，表記の簡 単のため，変数，集合，関数を以下のように書き直す．

y :=xⁱ, wˆ :=(ˆuⁱ,xˆ⁻ⁱ)^T, g_wˆ(y):= f_i^uˆi(xⁱ,xˆ⁻ⁱ), W :=U_i ×X_−i(x⁻ⁱ)

ここで，x⁻ⁱ は定数，xˆ⁻ⁱ はパラメータとみなしていることに注意する．このとき，以下で定義される関数

˜

g :ℜ^mi → ℜが凸であることを示せばよい．

˜

g(y):=sup{g_wˆ(y)| ˆw∈W} (4) 仮定1より，任意のwˆ ∈Wに対して，g_wˆ はS_i 上で凸である．さらに，(4)より，任意のy∈S_iおよびwˆ ∈W に対して，g_wˆ(y)≤ ˜g(y)^{が成り立つ．よって，}g_wˆ(y)^のwˆ ∈W に対する連続性（仮定1(a)）と，W のコンパ クト性（仮定1(b)(c)）から，任意のy∈S_i に対して，

w(y)∈arg max{g_wˆ(y)| ˆw∈W}

が存在する．ここで，任意のy¹,y²∈ S_i とα∈[0,1]に対して，y³:=(1−α)y¹+αy²∈S_i とおくと，

˜

g(y³)=g_w(y3)(y³)

≤(1−α)g_w(y3)(y¹)+αg_w(y3)(y²)

≤(1−α)g_w(y1)(y¹)+αg_w(y2)(y²)

=(1−α)g˜(y¹)+αg˜(y²)

を得る．これは，g˜がS_i 上で凸であることを示している．

次の補題は，N人の非協力ゲームに対するよく知られた結果である．

補題 3.2. [3, Theorem 9.1.1] N 人の非協力ゲームにおいて，各プレイヤーi ∈ {1, . . . ,N}^{のコスト関数} θi :ℜ^mi × ℜ^m−i → ℜ^{が任意の点}(xⁱ,x⁻ⁱ)∈S_i ×S_−i において連続であり，さらにx⁻ⁱ ∈ S_−i を任意に固定 したとき，関数θi(·,x⁻ⁱ)^がS_i 上で凸であるとする．また，戦略集合S_i は，空でないコンパクト凸集合であ るとする．そのとき，このゲームは少なくとも一つのNash均衡解をもつ．

この2つの補題から，ゲーム(1)におけるロバストNash均衡解の存在定理が得られる．

定理3.1. 仮定1が成り立つとする．このとき，ゲーム(1)は少なくとも一つのロバストNash均衡解をもつ．

証明. 補題3.1より，f˜_i(·,x⁻ⁱ)^はS_i上で凸である．また，f˜_i は連続関数である．よって，補題3.2から，ゲー ム(3)はNash均衡解をもつ．これは，定義2.1から，ゲーム(1)が少なくとも一つのロバストNash均衡解を もつことを示している．

4

Nash

前節では，ロバストNash均衡解が存在するための十分条件を考えた．しかし，情報完備ゲームにおける Nash均衡解と同様，ロバストNash均衡解は一般に複数存在し，そのすべてを知るのは困難である．ところ が，情報完備ゲームにおけるNash均衡解は，ある条件の下で一意に存在することが知られている．実際，

Rosen [19]は各プレイヤーの利得関数が連続的微分可能な情報完備ゲームに対して，解が一意に存在するため

の条件を与えた．そこで示されている条件は，ゲームを等価な変分不等式問題（Variational Inequality Problem

: VIP）に変換したときに，そのVIPに含まれる写像が狭義単調性をもつことにほかならない．そこで，本節

では，ロバストNash均衡解が一意に存在するための十分条件について考える．具体的には，Nash均衡問題，

及びロバストNash均衡問題とそれぞれ等価な変分不等式問題を導く．次に，VIPに対する結果を用いて，ロ バストNash均衡解の一意性を考える．なお，本節では簡単のため，各プレイヤーのコスト関数 f_i^ui は連続的 微分可能であると仮定する．

変分不等式問題VIP(F,S)^{とは，ベクトル値写像} Fと空でない閉凸集合Sが与えられたとき，次の条件を 満たすベクトルx∈Sを求める問題である[7]．

⟨F(x),y−x⟩ ≥0 ∀y∈S (5) 変分不等式問題は，ベクトル方程式や相補性問題，最適化問題などを含む幅広いクラスの問題である．実際，

S= ℜ^{nとすると}VIP(5)はベクトル方程式F(x)=0と等価であるし，S = ℜⁿ₊^とするとVIP(5)は非線形相 補性問題x ≥0,F(x)≥0,x^TF(x)=0と等価である．VIP(F,S)については，写像F が以下で定義される狭 義単調性をもつとき，解は存在すれば一意であることが知られている．

定義4.1.  ベクトル値写像F :ℜⁿ→ ℜ^{nと空でない凸集合}S⊆ ℜⁿが与えられているとする．このとき，任 意のx,y∈S(x̸=y)^に対して

⟨x−y,F(x)−F(y)⟩ ≥(>)0

が成り立つならば，写像FはSにおいて単調（狭義単調）であるという．

定理4.1. [9,定理5.4]ベクトル値写像Fを連続写像，Sを空でない閉凸集合とする．そのとき，FがSにお

いて狭義単調であれば，変分不等式問題(5)の解は存在すれば一意である．

さらに，Fが微分可能であれば，その導関数を調べることにより，Fの狭義単調性をチェックできる．

定理4.2. [9,定理2.67] F :ℜⁿ → ℜⁿを連続的微分可能なベクトル値関数とする．このときF が狭義単調で

あるための十分条件は，∇F(x)^が任意のxに対して正定値になることである．

さて，ゲーム(1)において，x⁻ⁱ ∈ S_−i を任意に固定した関数 f_i(·,x⁻ⁱ)が連続的微分可能とし，S_i は空で ない閉凸集合であるとしよう．このとき，F とSを次のように定めると，ゲーム(1)に対するNash均衡問題 はVIP(5)と等価になる．

x :=(xⁱ)i=1,...,N

F(x):=(

∇i f_i(xⁱ,x⁻ⁱ))

i=1,...,N (6)

S :=S₁× · · · ×S_N

ここで，∇i f_i は，プレイヤーiの戦略xⁱのみを変数と見たときの関数 f_i の勾配∇_xⁱ f_i を意味している．従っ て，定理4.1より，(6)で定められるFがSにおいて狭義単調ならば，ゲーム(1)のNash均衡解は存在すれ ば一意である．さらに，補題3.2の仮定が成り立てば，Nash均衡解の存在も保証される．

もし，(2)で定義される f˜_iが微分可能であれば，ロバストNash均衡問題も上と同様に等価なVIPへと再定 式化できる．しかし，たとえ f_i^ui が微分可能であっても，f˜_i は微分可能であるとは限らない．そこで，微分 不可能な凸関数に対して，劣微分写像と呼ばれる点-集合写像を定義し，ロバストNash均衡問題を，ベクト ル値写像の代わりに点-集合写像を用いた一般化変分不等式問題(Generalized Variational Inequality Problem :

GVIP)に再定式化することを考える．

一般化変分不等式問題GVIP(F,S)^とは，点-集合写像F^{と空でない閉凸集合}Sに対して，次のように定義 される問題である．

Find x∈S

such that ξ ∈F(x)

⟨ξ,y−x⟩ ≥0, ∀y∈ S

(7)

GVIPについてもVIPと同様，点-集合写像が以下で定義される狭義単調性をもつとき，解は存在すれば一 意であることが知られている[8]．

定義4.2.  点-集合写像A :ℜⁿ→P(ℜⁿ)^{と空でない凸集合}S ⊆ ℜⁿが与えられているとする．このとき，任 意のx,y∈S(x̸=y)^とξ ∈ A(x), η∈ A(y)^{に対して，}

⟨x−y, ξ−η⟩ ≥(>)0

が成り立つならば，点-集合写像 AはSにおいて単調（狭義単調）であるという．

定理4.3. 点-集合写像F :ℜⁿ →P(ℜⁿ)^がSにおいて狭義単調であれば，GVIP(7)の解は，存在すれば一意 である．

ロバストNash均衡問題をGVIPに再定式化する．まず，凸関数に対して劣微分写像を定義する．

定義4.3. 凸関数 f :ℜⁿ→ ℜに対して，以下のように定義される集合∂f(x)⊆ ℜ^nを f の点xにおける劣微 分という．

∂f(x)= {ξ ∈ ℜⁿ| f(y)− f(x)≥ ⟨ξ,y−x⟩(∀y∈ ℜⁿ)}

劣微分写像とは，任意の点x∈ ℜ^nに関数 f の劣微分∂f(x)^{を対応させる点}-集合写像である．

点-集合写像F :ℜ^m → P(ℜ^m)^と集合S を次のように定義すると，ロバストNash均衡問題はGVIP(7)と 等価になる．

F(x):=(

∂if˜_i(xⁱ,x⁻ⁱ))

i=1,...,N (8)

S :=S1× · · · ×SN

ここで，∂if˜i は，プレイヤーiの戦略xⁱ のみを変数と見たときの関数 f˜i の劣微分∂xⁱ f˜iを意味している．

仮定1が成り立つとき，定理3.1よりロバストNash均衡解が存在するので，それと等価なGVIP(7)にも 解が存在する．したがって，定理4.3より，(8)で定義される点-集合写像F が狭義単調であれば，ロバスト Nash均衡解は一意に存在することがわかる．

次に，Fが狭義単調となるための条件を与える．仮定1に加えて，次の仮定を満たす場合を考える．

仮定2.  

(a) 集合U_i は唯一の要素からなる．

(b) コンパクト集合Y₋i ⊆ ℜ^{m−i が存在して，}X₋i(x⁻ⁱ)=x⁻ⁱ+Y₋i と書ける．

(c) 任意に xⁱ を固定した関数 f_i^ui(xⁱ,·) : ℜ^m−i → ℜはアフィンである．すなわち，ある関数gi :ℜ^mi → ℜ, hi : ℜ^mi → ℜ^{m−i が存在して，}f_i^ui(xⁱ,y⁻ⁱ) := gi(xⁱ)+hi(xⁱ)^Ty⁻ⁱ と書ける．さらに，任意の y⁻ⁱ ∈Y_−i に対して，θi(xⁱ):=h(xⁱ)^Ty⁻ⁱ で定義される関数θiはS_i 上で凸である．

仮定2(a)より，本節では，関数 f_i^ui (i =1, . . . ,N)^を単に f_i と書くことにする．また，仮定2(b)(c)より，

f˜i(xⁱ,x⁻ⁱ)= max

ˆ

x⁻ⁱ∈X_−i(x⁻ⁱ) fi(xⁱ,xˆ⁻ⁱ)

= max

δx⁻ⁱ∈Y_−i

f_i(xⁱ,x⁻ⁱ+δx⁻ⁱ)

= f_i(xⁱ,x⁻ⁱ)+ max

δx⁻ⁱ∈Y₋i

h_i(xⁱ)^Tδx⁻ⁱ (9)

と書くことができる．

補題4.1. 仮定2が成り立っているとする．このとき，F が狭義単調であれば，(8)で定義される点-集合写像 F^{も狭義単調である．}

証明. ψi(xⁱ):=max_δx−i∈Y₋i hi(xⁱ)^Tδx⁻ⁱ とおく．このとき，(9)より，f˜iのxⁱ についての劣微分は以下で表 される．

∂if˜_i(xⁱ,x⁻ⁱ)= ∇if_i(xⁱ,x⁻ⁱ)+∂ψi(xⁱ)

また，F(x)^{は以下で表される．}

F(x)=F(x)+∂ψ1(x¹)× · · · ×∂ψN(x^N)

関数ψiは，仮定2(c)より凸であるから，その劣微分写像∂ψi はS_i 上で単調である[9,定理2.68]．すなわち，

任意のxⁱ,yⁱ ∈ S_iとξ˜ⁱ ∈∂ψi(xⁱ),η˜ⁱ ∈∂ψi(yⁱ)^{に対して，}

⟨xⁱ−yⁱ,ξ˜ⁱ− ˜ηⁱ⟩ ≥0

が成り立つ．よって，任意のx,y∈Sとξ ∈F(x), η∈F(y)^{に対して，}

⟨x−y, ξ−η⟩ = ⟨x−y,F(x)−F(y)⟩ +

∑N i=1

⟨xⁱ −yⁱ,ξ˜ⁱ − ˜ηⁱ⟩>0

が成り立つ．したがって，F^{は狭義単調である．}

以上の補題より，ロバストNash均衡解の一意性に関する次の定理を得る．

定理4.4. 仮定1および仮定2が成り立つとする．このとき，(6)で定義されるF が狭義単調であれば，ロバ ストNash均衡解は一意に存在する．

証明. 仮定1と定理3.1より，ロバストNash均衡解は存在する．さらに，補題4.3，補題4.1により，ロバス トNash均衡解は一意である．

5

Nash

本節では，各プレイヤーが混合戦略をとり，各々のコスト関数が自分の戦略に関する凸2次関数で表される ゲームを考える．特に，コスト関数のパラメータや相手の戦略の評価値に対する不確実性集合がユークリッド ノルムやフロベニウスノルムを用いて表せるようなある種のゲームに対して，ロバストNash均衡問題が二次 錐相補性問題（SOCCP）として定式化できることを示し，その解の存在性や一意性を議論する．

一般に，SOCCPとは次の条件を満たすベクトル(ξ, η, ζ)∈ ℜ^l× ℜ^l× ℜ^{νを求める問題である．}

K∋ξ ⊥η∈K, G(ξ, η, ζ)=0 (10)

ただし，G :ℜ^l× ℜ^l× ℜ^ν → ℜ^l× ℜ^ν は与えられた関数であり，ξ ⊥η^は，ξ^Tη=0を意味する．また，K^は，

K^lj = {(ζ1, ζ2)∈ ℜ×ℜ^lj−1| ∥ζ2∥ ≤ζ1}^{で定義される}l_j 次元の二次錐K^{lj を用いて}K=K^l1×K^l2×· · ·×K^lm で定義される閉凸錐である．SOCCPに対しては，平滑化法や再定式化法などのアルゴリズムが提案されてい る[10]．本報告書では，特に次の二次錐相補性条件を満たすベクトルζ を求める問題を考える．

K∋Mζ+q ⊥Nζ+r∈K, Cζ =d (11) ここで，ζ ∈ ℜ^{l+τ は変数で，}M,N ∈ ℜ^l×(l+τ), q,r ∈ ℜ^l,C ∈ ℜ^τ×(l+τ),d ∈ ℜ^τ は定数である．新しい変数 ξ, η∈ ℜ^lを用いて，次のように関数G :ℜ^3l+τ → ℜ^{2l+τを定義すれば，}SOCCP(11)はSOCCP(10)と等価で ある．

G(ξ, η, ζ):=



ξ −Mζ −q η−Nζ −r

Cζ−d





本節では，各プレイヤーi ∈ {1, . . . ,N}^{のコスト関数} fi が行列Ai ∈ ℜ^mi×mi,Bi j ∈ ℜ^{mi×mj，および，ベク} トルcⁱ ∈ ℜ^{mi を用いて，}

fi(xⁱ,x⁻ⁱ)= 1

2(xⁱ)^TAixⁱ+(xⁱ)^T



 ∑^N

j=1,j̸=i

Bi jx^j+cⁱ



 (12)

= 1

2(xⁱ)^TA_ixⁱ+(xⁱ)^T(B_ix⁻ⁱ +cⁱ)

と表される場合を考える．ここで，B_i ∈ ℜ^{mi×m−i は} B_i =[

B_{i 1} · · · B_i(i−1) B_i(i+1) · · · B_{i N}]

を表す．以下では，行列A_i は半正定値であるとし，戦略は混合戦略，すなわち戦略集合S_−i が Si = {xⁱ |xⁱ ≥0, e^T_m

ixⁱ =1} (13)

と表される場合を考える．ただし，em_i =(1,1, . . . ,1)^T ∈ ℜ^{mi である．このとき，}Si は空でないコンパク ト凸集合であることに注意する．また，2節で用いたコスト関数のパラメータuⁱ はvec(Ai),vec(Bi j),j =

1, . . . ,N,j ̸= i およびcⁱ を並べたベクトルと見なすことができる．ここで vec(·)^はm 個の列ベクトル

p₁^c, . . . ,p_m^c からなる行列P ∈ ℜ^{n×m から}nm-次元のベクトル((p^c₁)^T, . . . , (p_m^c)^T)^T を生成するオペレーター である．

5.1

この節では，各プレイヤーがコスト関数の値を計算するときに，その関数に含まれるパラメータは正確に推 定できるが，N −1人の相手プレイヤーの戦略の評価値が不確実性を含む場合を考える．そこで，すべての i ∈ {1, . . . ,N}に対して，次の仮定をおく．

仮定3.  

(a) X_−i(x⁻ⁱ)= {x⁻ⁱ +δx⁻ⁱ | ∥δx^j∥ ≤ρi j, e_m^T

jδx^j =0(j ̸=i)}

(b) U_i = {uⁱ}

仮定3(a) において，条件e_m^T

jδx^j = 0 は，e^T_m

j(x^j +δx^j) = 1かつ e_m^T

jx^j = 1による．また，ρi j(i,j = 1,2, . . . ,N,j ̸=i)は与えられた非負の実数である．

この仮定の下で，次の定理が成り立つ．

定理5.1. 各プレイヤーのコスト関数と戦略集合がそれぞれ(12)と(13)で与えられ，仮定3が成り立つとす る．このとき，ロバストNash均衡解が少なくとも一つ存在する．

証明. コスト関数が(12)で与えられているので，仮定1(a)は成り立つ．また，仮定3が成り立つとき，仮定

1(b)(c)が成り立つことは明らかである．さらに仮定1(d)は，A_i ≽ Oおよび混合戦略であることから成り立

つ．よって，仮定1をすべて満たすので，定理3.1よりロバストNash均衡解が存在する．

さらに，解の一意性に関して，次の定理が成り立つ．

定理5.2. 各プレイヤーのコスト関数と戦略集合がそれぞれ(12)と(13)で与えられ，仮定3が成り立つとす る．そのとき，









A₁ B₁₂ · · · B_1N B₂₁ A₂ ...

... ... ...

B_{N 1} · · · A_N







≻O (14)

が成り立つならばロバストNash均衡解は一意である．