20240805_raota_hori_r1

連続最適化におけるナッシュ均衡問題 堀 篤史（成蹊大学 理工学部） 令和 6 年 8 月 5 日 日本 OR 学会研究部会：最適化の理論とアルゴリズム（RAOTA） @ 国立情報学研究所 1 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 2 / 96

大まかな構成 本講演の構成： ▶ 前半： 1. 数学的準備（前半） 2. マルチリーダー・フォロワーゲームに対する解法（前半） ▶ 後半： 1. 2 段階分布的ロバストナッシュ均衡問題（後半） 2. まとめ・今後の展望（後半） 3 / 96

紹介論文 A. Hori, D. Tsuyuguchi, and E.H. Fukuda, A method for multi-leader–multi-follower games by smoothing the followers’ response function, J. Optim. Theory Appl., 2024 (doi: 10.1007/s10957-024-02506-2) URL: https://link.springer.com/article/10.1007/s10957-024-02506-2 A. Hori and N. Yamashita, Two-stage distributionally robust noncooperative games: Existence of Nash equilibrium and its application to Cournot–Nash competition, J. Ind. Manag. Optim., 19, 6430–6450, 2023. URL: https://www.aimsciences.org/article/doi/10.3934/jimo.2022221 （一部）A. Hori and M. Fukushima, Gauss–Seidel method for multi-leader–follower games, J. Optim. Theory Appl., 180, 651–670, 2019. URL: https://link.springer.com/article/10.1007/s10957-018-1391-5 4 / 96

• https://link.springer.com/article/10.1007/s10957-024-02506-2
• https://www.aimsciences.org/article/doi/10.3934/jimo.2022221
• https://link.springer.com/article/10.1007/s10957-018-1391-5

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 ナッシュ均衡問題 変分不等式問題 ナッシュ均衡の存在性・一意性 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 5 / 96

ゲーム理論の簡単な歴史 現代のゲーム理論は，1920 年代に J. von Neumann によって提案されたゼロサム ゲームに始まり，その後，彼と O. Morgenstern によってゼロサムゲームと協力ゲー ムに関する著書を出版した [Neumann & Morgenstern (1944)]1 1950 年代に J. F. Nash [J.F. Nash (1950), J.F. Nash (1951)]23 は非協力ゲームにお ける均衡解（のちにナッシュ均衡と呼ばれる）の存在性を証明し，ゲーム理論を新し い方向に発展させた 1 J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944 2 J. Nash, Equilibrium points in 𝑛 -person games, Proc. Natl. Acad. Sci. USA, 36, 48–49, 1950. 3 J. Nash, Non-cooperative games, Ann. Math., 54, 286–295, 1951. 6 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 ナッシュ均衡問題 変分不等式問題 ナッシュ均衡の存在性・一意性 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 7 / 96

ナッシュ均衡問題（NEP） 定義：ナッシュ均衡問題（Nash Equilibrium Problem: NEP） 非協力ゲームにおけるナッシュ均衡（後述）を求める問題 非協力ゲームにおける重要な概念 プレイヤー：合理的な意思決定主体 戦略（空間）：各プレイヤーが実行可能な手段（の集合） コスト（=−1× 利得）関数： 各プレイヤーのコスト（利得）を表し，戦略空間から実数への関数 8 / 96

ナッシュ均衡：基本的な問題設定 問題設定 プレイヤー数： 𝑁 𝜈 ∈ {1, . . . , 𝑁 }：プレイヤーを区別するラベル プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } に対して， ▶ 戦略空間：𝑋 𝜈 ⊂ R𝑛𝜈 （𝑛 𝜈 ：プレイヤー 𝜈 の戦略ベクトルの次元） ▶ 戦略：𝑥 𝜈 ∈ 𝑋 𝜈 ．プレイヤー 𝜈 以外の戦略の組を 𝑥 −𝜈 と表す．すなわち， 𝑥 −𝜈 := (𝑥 1 , . . . , 𝑥 𝜈−1 , 𝑥 𝜈+1 , . . . , 𝑥 𝑁 ) ▶ コスト関数：𝜃 𝜈 : R𝑛 → R とする（ここで，𝑛 := Í𝑁 𝜈=1 = 𝑛1 + · · · + 𝑛 𝑁 とする） 9 / 96

ナッシュ均衡 I 問題設定（つづき） 各プレイヤーは相手の戦略を推測しながら，自身の戦略空間（制約条件）上で自身の コスト関数（目的関数）を最小化する以下の最適化問題を解く： P𝜈 (𝑥 −𝜈 ) : min 𝜈 𝑛 𝑥 ∈R 𝜈 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) s.t. 𝑥𝜈 ∈ 𝑋 𝜈 定義：ナッシュ均衡（Nash Equilibrium: NE） 戦略組 𝑥 ∗ := (𝑥 ∗,1 , . . . , 𝑥 ∗,𝑁 ) ∈ 𝑋 := 𝑋 1 × · · · × 𝑋 𝑁 が（前述の）非協力ゲームの ナッシュ均衡である def ⇐⇒ ∀𝜈 ∈ {1, . . . , 𝑁 }, 𝜃 𝜈 (𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 ) ≤ 𝜃 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 ) ∀𝑥 𝜈 ∈ 𝑋 𝜈 10 / 96

ナッシュ均衡 II 上の条件式は， 𝑥 ∗,𝜈 が 𝑥 ∗,−𝜈 を固定したときの各プレイヤーの最適化問題について， 大域的最適解（最適反応戦略）となっており，それがすべてのプレイヤーについて， 同時に成り立つことを意味する すなわち，ナッシュ均衡の条件は以下のようにも定義できる： 𝑥 ∗ ∈ 𝑋 がナッシュ均衡 ⇐⇒ 𝑥 ∗,𝜈 ∈ argmin 𝜃 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 ) ∀𝜈 ∈ {1, . . . , 𝑁 } 𝑥 𝜈 ∈𝑋 𝜈 11 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 ナッシュ均衡問題 変分不等式問題 ナッシュ均衡の存在性・一意性 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 12 / 96

変分不等式問題 I 定義：変分不等式問題（Variational Inequality Problem: VIP） 集合 𝑆 ⊂ R𝑛 を閉凸集合，ベクトル値関数 𝐹 : R𝑛 → R𝑛 とする．以下の式を満たす 𝑥 ∗ ∈ 𝑆 を見つける問題を変分不等式問題といい，VI(𝑆, 𝐹) と記す： 0 ∈ 𝐹(𝑥 ∗ ) + 𝒩𝑆 (𝑥 ∗ ) 𝒩𝑆 (𝑥)：点 𝑥 ∈ 𝑆 における閉凸集合 𝑆 の法線錐 𝒩𝑆 (𝑥) := {𝑦 ∈ R𝑛 | ⟨𝑦, 𝑧 − 𝑥⟩ ≤ 0 ∀𝑧 ∈ 𝑆} ただし， ⟨·, ·⟩ は内積を表す． 13 / 96

変分不等式問題 II 法線錐 𝒩𝑆 (𝑥) の定義より，変分不等式は以下のようにも書ける： ⟨𝐹(𝑥 ∗ ), 𝑥 − 𝑥 ∗ ⟩ ≥ 0 ∀𝑥 ∈ 𝑆 𝑆 = R+𝑛 := {𝑥 ∈ R𝑛 | 𝑥 ≥ 0} のとき，以下の相補性問題となる： 𝑥 ≥ 0, 𝐹(𝑥) ≥ 0, ⟨𝑥, 𝐹(𝑥)⟩ = 0 ⇐⇒ 𝑥 𝑖 ≥ 0, 𝐹𝑖 (𝑥) ≥ 0, 𝑥 𝑖 𝐹𝑖 (𝑥) = 0 (𝑖 = 1, . . . , 𝑛) 相補性問題は以下のようにも表現することがある： 0 ≤ 𝑥 ⊥ 𝐹(𝑥) ≥ 0 ここで， 𝑥 ⊥ 𝐹(𝑥) ⇐⇒ ⟨𝑥, 𝐹(𝑥)⟩ = 0 𝑆 = R𝑛 のとき，非線形方程式 𝐹(𝑥) = 0 となる 14 / 96

変分不等式問題のイメージ 図 1: VI(𝑆, 𝐹) の解 𝑥 ∗ ∈ 𝑆 ˆ の解でない 𝑥 ∗ ∈ 𝑆 図 2: VI(𝑆, 𝐹) 15 / 96

最適化問題と変分不等式の関係 閉凸集合 𝑆 ∈ R𝑛 ，関数 𝑓 : R𝑛 → R とする．以下の最適化問題を考える： P: min 𝑥∈R𝑛 𝑓 (𝑥) s.t. 𝑥∈𝑆 関数 𝑓 が微分可能であるとき， 𝑥 ∗ ∈ 𝑆 が最適化問題 P の最適解 =⇒ VI(𝑆, ∇ 𝑓 ) の解 さらに，関数 𝑓 が凸であれば，必要十分となる { 変分不等式は最適化問題に対する一次の最適性条件 16 / 96

ナッシュ均衡問題と変分不等式の関係 （再掲）プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } が以下の最適化問題を解く： P𝜈 (𝑥 −𝜈 ) : 𝑥 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) min 𝜈 𝑛 ∈R 𝜈 s.t. 𝑥𝜈 ∈ 𝑋 𝜈 命題：ナッシュ均衡と変分不等式の解 すべての 𝜈 に対して，𝑋 𝜈 が閉凸集合であり，𝜃 𝜈 (·, 𝑥 −𝜈 ) が連続的微分可能，かつ凸と する．このとき， 𝑥 ∗ ∈ 𝑋 がナッシュ均衡であることの必要十分条件は変分不等式 VI(𝑋 , 𝐹) の解であることである．ただし， 𝑋 := 𝑋 1 × · · · × 𝑋 𝑁 ,  ∇𝑥 1 𝜃1 (𝑥 1 , 𝑥 −1 )      . .. 𝐹(𝑥) :=      ∇𝑥 𝑁 𝜃 𝑁 (𝑥 𝑁 , 𝑥 −𝑁 )    17 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 ナッシュ均衡問題 変分不等式問題 ナッシュ均衡の存在性・一意性 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 18 / 96

ナッシュ均衡の存在性 （再掲）プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } の解く最適化問題： P𝜈 (𝑥 −𝜈 ) : 𝑥 min 𝜈 𝑛 ∈R 𝜈 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) s.t. 𝑥𝜈 ∈ 𝑋 𝜈 命題：ナッシュ均衡の存在性 [Aubin (1979)]4 以下の仮定が成り立つとする： 1. 𝜃 𝜈 : R𝑛 → R：連続 2. 𝜃 𝜈 (·, 𝑥 −𝜈 )：凸関数 3. 𝑋 𝜈 ⊂ R𝑛𝜈 ：非空・コンパクト・凸集合 このとき，各プレイヤーが P𝜈 (𝑥 −𝜈 ) を解くような非協力ゲームにおいてナッシュ均衡が 存在する． 4 J.P. Aubin, Mathematical Methods of Game and Economic Theory, North-Holland, 1979 19 / 96

ナッシュ均衡の一意性 命題：ナッシュ均衡の一意性 ナッシュ均衡の存在性の仮定（前頁）に加えて，以下のように定義されるベクトル値 関数 𝐹 : R𝑛 → R𝑛 が狭義単調と仮定する： ただし， ⟨𝐹(𝑥) − 𝐹(𝑥 ′), 𝑥 − 𝑥 ′⟩ > 0 ∀𝑥, 𝑥 ′ ∈ 𝑋 (𝑥 ≠ 𝑥 ′)  ∇𝑥 1 𝜃1 (𝑥 1 , 𝑥 −1 )      . .. 𝐹(𝑥) :=  ,    ∇𝑥 𝑁 𝜃 𝑁 (𝑥 𝑁 , 𝑥 −𝑁 )    𝑋 := 𝑋 1 × · · · × 𝑋 𝑁 このとき，各プレイヤーが P𝜈 (𝑥 −𝜈 ) を解くような非協力ゲームにおいて，ナッシュ均衡 が一意に存在する． 20 / 96

まとめ：連続最適化とナッシュ均衡問題 連続最適化の観点から NEP を紹介 { 各プレイヤーがパラメータ付きの連続最適化問題を解く状況を考えており，（一定の 仮定の下で）変分不等式問題へと帰着できる 実際，NEP は変分不等式問題に再定式化して解くこともしばしばある （[Facchinei & Pang (2003)]5 ） 研究課題（本講演で紹介する研究の動機） より複雑な非協力ゲームにおいても，「うまく」取り扱えるか？   連続最適化の理論を用いたナッシュ均衡の存在性の証明や 堅固な理論に基づく解法の開発   5 F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, 2003. 21 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム マルチリーダー・フォロワーゲームとは・問題設定 研究背景・研究課題 停留均衡解・提案手法 電力卸売市場への応用・数値実験結果 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 22 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム マルチリーダー・フォロワーゲームとは・問題設定 研究背景・研究課題 停留均衡解・提案手法 電力卸売市場への応用・数値実験結果 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 23 / 96

導入：マルチリーダー・マルチフォロワーゲーム（MLMFG） 複数の先手（リーダー）と後手（フォロワー）による非協力ゲーム { 2 レベル最適化は MLMFG の特殊な場合（1 リーダー・1 フォロワー） MLMFG がみられる実社会の例：電力卸売市場，エッジコンピューティング   図 3: エッジコンピューティングの例  最適な計算資源配分を MLMFG としてモデル化して解く研究が近年みられる 6  6 Y. Chen, Z. Li, B. Yang, K. Nai, and K. Li (2020), A Stackelberg game approach to multiple resources allocation and pricing in mobile edge computing, Future Gener. Comput. Syst., 108, 273–287. 24 / 96

問題設定：リーダーの最適化問題 𝑁 人のリーダーと 𝑀 人のフォロワーによる MLMFG を考える リーダー 𝜈 ∈ {1, . . . , 𝑁 } の最適化問題 𝑥 min 𝜈 𝑛 ∈R 𝜈 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝑦) s.t. 𝑥𝜈 ∈ 𝑋 𝜈 𝑥 𝜈 ：リーダー 𝜈 の戦略（決定変数） 𝑥 −𝜈 := (𝑥 1 , . . . , 𝑥 𝜈−1 , 𝑥 𝜈+1 , . . . , 𝑥 𝑁 )：リーダー 𝜈 以外のすべてのリーダーの戦略組 𝑦 := (𝑦 1 , . . . , 𝑦 𝑀 )：すべてのフォロワーの戦略組 仮定 L コスト関数 𝜃 𝜈 : R𝑛+𝑚 → R：滑らか 戦略集合 𝑋 𝜈 ⊂ R𝑛𝜈 ：凸集合 25 / 96

問題設定：フォロワーの最適化問題 フォロワー 𝜔 ∈ {1, . . . , 𝑀} の最適化問題 min𝑚 𝜔 𝑦 ∈R 𝜔 𝛾 𝜔 (𝑥, 𝑦 𝜔 , 𝑦 −𝜔 ) s.t. 𝑦 𝜔 ∈ 𝑌 𝜔 (𝑥) := {𝑦 𝜔 ∈ R𝑚𝜔 | 𝑔 𝜔 (𝑥, 𝑦 𝜔 ) ≤ 0} すべてのリーダーの戦略組 𝑥 := (𝑥 1 , . . . , 𝑥 𝑁 ) は所与 𝑦 𝜔 ：フォロワー 𝜔 の戦略（決定変数） 𝑦 −𝜔 := (𝑦 1 , . . . , 𝑦 𝜔−1 , 𝑦 𝜔+1 , . . . , 𝑦 𝑀 )：フォロワー 𝜔 以外の戦略組 仮定 F すべての 𝜔 ∈ {1, . . . , 𝑀} と 𝑥 ∈ 𝑋 に対して，以下の条件が成り立つ： 𝛾 𝜔 : R𝑛+𝑚 → R：滑らか．𝛾 𝜔 (𝑥, ·, 𝑦 −𝜔 ) は凸関数 𝑌 𝜔 (𝑥)：コンパクト凸集合 不等式制約 𝑔 𝜔 (𝑦 𝜔 , 𝑥) ≤ 0 について，一次独立制約想定（LICQ）が成り立つ 26 / 96

フォロワーのナッシュ均衡 定義：フォロワー間のゲームのナッシュ均衡 点 𝑦 ∗ := (𝑦 ∗,1 , . . . , 𝑦 ∗,𝑀 ) ∈ 𝑌(𝑥) := 𝑌 1 (𝑥) × · · · × 𝑌 𝑀 (𝑥) において，以下の条件が 成り立つとき， 𝑦 ∗ をナッシュ均衡という： 𝑦 ∗,𝜔 ∈ arg min 𝛾 𝜔 (𝑥, 𝑦 𝜔 , 𝑦 ∗,−𝜔 ) 𝑦 𝜔 ∈𝑌 𝜔 (𝑥) ∀𝜔 ∈ {1, . . . , 𝑀}   フォロワーの中で自身の戦略を一方的に変更する動機を誰一人もたない状態   𝒮(𝑥)：フォロワー間のゲームのナッシュ均衡 𝑦 ∗ を要素とする集合 27 / 96

リーダー・フォロワーナッシュ均衡（悲観的・楽観的） 定義：悲観的・楽観的リーダー・フォロワー（LF）ナッシュ均衡 点 (𝑥 ∗ , 𝑦 ∗ ) ∈ 𝑋 × 𝒮(𝑥 ∗ ) が MLMFG の悲観的 LF ナッシュ均衡： 𝑥 ∗,𝜈 ∈ arg min 𝜈 𝜈 𝑥 ∈𝑋 max 𝑦∈𝒮(𝑥 𝜈 ,𝑥 ∗,−𝜈 ) 𝜃𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 , 𝑦) ∀𝜈 ∈ {1, . . . , 𝑁 } 点 (𝑥 ∗ , 𝑦 ∗ ) ∈ 𝑋 × 𝒮(𝑥 ∗ ) が MLMFG の楽観的 LF ナッシュ均衡： 𝑥 ∗,𝜈 ∈ arg min 𝜈 𝜈 𝑥 ∈𝑋 min 𝑦∈𝒮(𝑥 𝜈 ,𝑥 ∗,−𝜈 ) 𝜃𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 , 𝑦) ∀𝜈 ∈ {1, . . . , 𝑁 } 𝒮(𝑥) が単集合のとき，これらは一致し，単にLF ナッシュ均衡と呼ぶ 28 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム マルチリーダー・フォロワーゲームとは・問題設定 研究背景・研究課題 停留均衡解・提案手法 電力卸売市場への応用・数値実験結果 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 29 / 96

研究背景：MLMFG に対する解法 I 1. MLMFG に対する主流な解法としては，EPEC（均衡制約付き均衡問題）へ再定式化 して MPEC ソルバー（例：NLPEC [Ferris et al. (2005)]7 ）などで解く手法 （[Leyffer & Munson (2010)]8 [Hori & Fukushima (2019)]9 など） 2. フォロワーの最適応答戦略をリーダーの戦略を変数とする陰関数として見なし，リー ダー間の非協力ゲームに帰着させて解く手法（[Hu & Fukushima (2011)]10 ， [Herty et al. (2022)]11 ]） 7 M.C. Ferris, P. Dirkse, and A. Meeraus: Mathematical programs with equilibrium constraints: automatic reformulation and solution via constrained optimization. In: T.J. Kehoe, T.N. Srinivasan, and J. Whalley, (eds.) Frontiers in Applied General Equilibrium Modeling, 67–93. Cambridge University Press, Cambridge, 2005 8 S. Leyffer and T. Munson, Solving multi-leader–common-follower games, Optim. Method Softw. 25, 601–623, 2010. 9 A. Hori and M. Fukushima, Gauss–Seidel method for multi-leader–follower games, J. Optim. Theory Appl., 180, 651–670, 2019. 10 M. Hu and M. Fukushima, Variational inequality formulation of a class of multi-leader-follower games, J. Optim. Theory Appl. 151, 455-473, 2011 11 M. Herty, S. Steffensen, and A. Thünen (2022), Solving quadratic multi-leader-follower games by smoothing the follower’s best response, Optim. Method Softw. 37, 772–799, 2022 30 / 96

1. 均衡制約付き均衡問題（EPEC）への再定式化 フォロワーの問題の最適性条件を各リーダーの問題の制約条件に取り込むことで， MLMFG におけるリーダー 𝜈 の最適化問題は以下のように帰着される： min 𝜈 𝜃𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝑦) s.t. 𝑥 𝜈 ∈ 𝑋 𝜈 , 𝑦 ∈ 𝒮(𝑥) 𝑥 ,𝑦 ただし， 𝒮(𝑥) := {𝑦 ∈ R𝑚 | ⟨𝐺(𝑥, 𝑦), 𝑦 ′ − 𝑦⟩ ≥ 0 ∀𝑦 ′ ∈ 𝑌(𝑥)} 𝑀 とし，𝐺(𝑥, 𝑦) := [∇ 𝑦 𝜔 𝛾𝜔 (𝑥, 𝑦 𝜔 , 𝑦 −𝜔 )]𝜔=1 ，𝑌(𝑥) := 𝑌 1 (𝑥) × · · · × 𝑌 𝑀 (𝑥) とする．   フォロワーの戦略を各々のリーダーがそれぞれ別々に「自身の都合の良いように」 変更できてしまうため，フォロワーの戦略の解釈が煩雑になる   31 / 96

2. 応答関数を用いた解法 I 𝒮(𝑥) を単集合とする．すなわち，各 𝑥 ∈ 𝑋 に対して，フォロワーのナッシュ均衡が 一意に定まるとする { 𝑦 ∗ を 𝑥 の関数として， 𝑦(𝑥) と表し，これを応答関数と呼ぶ 各リーダーの最適化問題に表れる 𝑦 を 𝑦(𝑥) に置き換える { 𝑦 が陽に現れなくなる 𝜈 P̂ (𝑥 −𝜈 ) : 𝑥 min Θ 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) := 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝑦(𝑥 𝜈 , 𝑥 −𝜈 )) 𝜈 𝑛 ∈R 𝜈 s.t. 𝑥𝜈 ∈ 𝑋 𝜈 𝜈 𝑁 各リーダーが P̂ (𝑥 −𝜈 ) を解くようなナッシュ均衡問題を NEP(𝑋 , {Θ 𝜈 } 𝜈=1 ) と表す 32 / 96

2. 応答関数を用いた解法 II 𝑁 命題：NEP(𝑋 , {Θ 𝜈 } 𝜈= 1 ) と LF ナッシュ均衡との関係 𝑁 点 𝑥 ∗ ∈ 𝑋 が NEP(𝑋 , {Θ 𝜈 } 𝜈=1 ) のナッシュ均衡，すなわち， 𝜈 𝜈 ∗,−𝜈 𝑥 ∗,𝜈 ∈ arg min Θ (𝑥 , 𝑥 ) 𝜈 𝜈 𝑥 ∈𝑋 ∀𝜈 ∈ {1, . . . , 𝑁 } ならば，(𝑥 ∗ , 𝑦(𝑥 ∗ )) は LF ナッシュ均衡である    Θ 𝜈 の非凸性から，LF ナッシュ均衡の存在性は一般に保証されない  33 / 96

2. 先行研究の詳細と研究課題 フォロワーの最適化問題の特徴 [Hu & Fukushima (2011)]12 ：フォロワーの最適化問題が線形等式制約のみの凸二次 計画 [Herty et al. (2022)]13 ：フォロワー間のゲームが凸二次ポテンシャルゲーム { フォロワーの応答 𝑦(𝑥) を陽に書き下せるような問題設定のみ 研究課題 𝑦(𝑥) が陽に書き下せない場合でも同様の手法を確立できるか 12 M. Hu and M. Fukushima (2011), Variational inequality formulation of a class of multi-leader-follower games, J. Optim. Theory Appl. 151, 455-473. 13 M. Herty, S. Steffensen, and A. Thünen (2022), Solving quadratic multi-leader-follower games by smoothing the follower’s best response, Optim. Method Softw. 37, 772–799. 34 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム マルチリーダー・フォロワーゲームとは・問題設定 研究背景・研究課題 停留均衡解・提案手法 電力卸売市場への応用・数値実験結果 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 35 / 96

停留均衡解：Clarke 停留均衡 LF ナッシュ均衡解より弱い停留均衡解を考える 定義：Clarke 停留均衡解 点 𝑥 ∗ := (𝑥 ∗,1 , . . . , 𝑥 ∗,𝑁 ) ∈ 𝑋 が MLMFG の Clarke 停留均衡解であるとは，以下の条 件を満たすことである： 0 ∈ 𝜕𝑥 𝜈 Θ 𝜈 (𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 ) + 𝒩𝑋 𝜈 (𝑥 ∗,𝜈 ) ∀𝜈 ∈ {1, . . . , 𝑁 } 𝒩𝑋 𝜈 (𝑥 𝜈 ) := {𝑑 𝜈 ∈ R𝑛𝜈 | ⟨𝑑 𝜈 , 𝑤 𝜈 − 𝑥 𝜈 ⟩ ≤ 0 ∀𝑤 𝜈 ∈ 𝑋 𝜈 }：法線錐   応答関数 𝑦(𝑥) は平滑でないため，停留均衡点の計算が難しい   36 / 96

ナッシュ均衡の条件と等価な KKT 条件 フォロワー 𝜔 ∈ {1, . . . , 𝑀} の最適化問題 min 𝑦 𝜔 ∈ R𝑚 𝜔 𝛾 𝜔 (𝑥, 𝑦 𝜔 , 𝑦 −𝜔 ) s.t. 𝑦 𝜔 ∈ 𝑌 𝜔 (𝑥) = {𝑦 𝜔 | 𝑔 𝜔 (𝑥, 𝑦 𝜔 ) ≤ 0} ⇕ （ ∵ 凸性） フォロワー 𝜔 ∈ {1, . . . , 𝑀} の最適化問題に対する KKT 条件 Í𝜔 𝜔 ∇ 𝑦 𝜔 𝛾 𝜔 (𝑥, 𝑦 𝜔 , 𝑦 −𝜔 ) + 𝑙𝑖=1 𝜆 𝑖 ∇ 𝑦 𝜔 𝑔𝑖𝜔 (𝑥, 𝑦 𝜔 ) = 0 （𝜆 𝜔 ：Lagrange 乗数） 𝑖 𝑔𝑖𝜔 (𝑥, 𝑦) + 𝑧 𝑖𝜔 = 0 (𝑖 = 1, . . . , 𝑙 𝜔 ) （ 𝑧 𝑖𝜔 ：スラック変数） 𝜔 𝜔 𝑧 𝑖𝜔 ≥ 0, 𝜆 𝜔 𝑖 ≥ 0, 𝑧 𝑖 𝜆 𝑖 = 0 (𝑖 = 1, . . . , 𝑙 𝜔 )   すべてのフォロワーの KKT 条件を満たす 𝑦, 𝑧, 𝜆 を求める { 𝑦 はナッシュ均衡   37 / 96

KKT 条件を滑らかに近似した非線形方程式 相補性条件 𝑧 𝑖𝜔 ≥ 0，𝜆 𝜔 ≥ 0， 𝑧 𝑖𝜔 𝜆 𝜔 = 0 (𝑖 = 1, . . . , 𝑙 𝜔 ) と等価な等式制約： 𝑖 𝑖 𝜙0 (𝑧 𝑖𝜔 , 𝜆 𝜔 𝑖 ) := q (𝑧 𝑖𝜔 )2 + (𝜆 𝜔 )2 − (𝑧 𝑖𝜔 + 𝜆 𝜔 𝑖 ) = 0, 𝑖 = 1, . . . , 𝑙 𝜔 𝑖 { 𝑧 𝑖𝜔 = 𝜆 𝜔𝑖 = 0 にて，微分不可能 𝜙0 を平滑化近似した関数 𝜙 𝜀 : R2 → R： q 𝜙 𝜀 (𝑧 𝑖𝜔 , 𝜆 𝜔 𝑖 ) := 𝑧 2𝑖 + 𝜆2𝑖 + 2𝜀2 − (𝑧 𝑖 + 𝜆 𝑖 ) (𝜀 > 0) { すべての点で十分滑らか（𝜙 𝜀 (𝑧 𝑖𝜔 , 𝜆 𝜔𝑖 ) = 0 ⇐⇒ 𝑧 𝑖𝜔 > 0, 𝜆 𝜔𝑖 > 0, 𝑧 𝑖𝜔 𝜆 𝜔𝑖 = 𝜀2 ） KKT 条件を近似した滑らかな方程式  ∇ 𝑦 𝜔 𝛾 𝜔 (𝑥, 𝑦 𝜔 , 𝑦 −𝜔 ) + Í𝑙𝜔 𝜆 𝜔 ∇ 𝑦 𝜔 𝑔 𝜔 (𝑥, 𝑦 𝜔 )  𝑀   𝑖=1 𝑖 𝑖 𝜔 𝜔 𝜔   𝑔 (𝑥, 𝑦 ) + 𝑧 𝐻𝜀 (𝑥, 𝑦, 𝑧, 𝜆) :=  =0  𝑙 𝜔   [𝜙 𝜀𝜔 (𝑧 𝑖𝜔 , 𝜆 𝜔 )]𝑖=1  𝜔=1  𝑖 38 / 96

応答関数の平滑化 命題（𝐻0 と 𝐻𝜀 に対する陰関数定理） ¯ を方程式 𝐻𝜀 (𝑥, 𝑦, 𝑧, 𝜆) = 0 の解と ¯ 𝑧¯ , 𝜆) 与えられた 𝜀 ≥ 0 と 𝑥 ∈ 𝑋 に対して，点 ( 𝑦, する．このとき，点 (𝜀, 𝑥) のある近傍 𝑈 × Ω ⊂ R1+𝑛 と，局所 Lipschitz 連続な関数 (𝑦, 𝑧, 𝜆) : R1+𝑛 → R𝑚+𝑙+𝑙 が存在して， 𝐻𝜀 (𝑥, 𝑦 𝜀 (𝑥), 𝑧 𝜀 (𝑥), 𝜆 𝜀 (𝑥)) = 0 を満たす．特に，固定した 𝜀 ∈ 𝑈 \ {0} に対して，(𝑦 𝜀 (·), 𝑧 𝜀 (·), 𝜆 𝜀 (·)) : Ω → R𝑚+𝑙+𝑙 は 連続的微分可能である．    𝐻𝜀 (𝑥, 𝑦 𝜀 (𝑥), 𝑧 𝜀 (𝑥), 𝜆 𝜀 (𝑥)) = 0 の両辺を 𝑥 について微分し， 式変形することで，∇𝑥 𝑦 𝜀 (𝑥) が得られる  39 / 96

応答関数の劣微分の特徴付け 応答関数 𝑦(𝑥) と 𝑦 𝜀 (𝑥) の（劣）微分に関する以下の命題を導いた 命題：劣微分 𝜕𝑦(𝑥) との関係式 以下の包含関係を満たす 0 に収束する正数列 {𝜀𝑘 } 𝑘 が存在する 14 ．   lim ∇𝑦 𝜀𝑘 (𝑥 𝑘 ) ⊂ 𝜕𝑦(𝑥 ∗ ) 𝑘→∞ ここで， 𝑥 𝑘 → 𝑥 ∗ （ 𝑘 → ∞）とする． 14 𝑋 のコンパクト性が特に重要！ 40 / 96

滑らかなリーダーの非協力ゲーム 応答関数 𝑦(𝑥) を 𝑦 𝜖 (𝑥) に置き換えた以下のリーダーの最適化問題は微分可能： 𝜈 P̂𝜀 (𝑥 −𝜈 ) : 𝑥 min Θ𝜀𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) := 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝑦 𝜀 (𝑥 𝜈 , 𝑥 −𝜈 )) 𝜈 𝑛 ∈R 𝜈 s.t. 𝑥𝜈 ∈ 𝑋 𝜈 𝜈 𝑁 各リーダーが P̂𝜀 (𝑥 −𝜈 ) を解くような非協力ゲームを NEP(𝑋 , {Θ𝜀𝜈 } 𝜈=1 ) と表す 𝑁 NEP(𝑋 , {Θ𝜀𝜈 } 𝜈=1 ) の停留均衡解は以下の変分不等式問題を解くことで得られる： Find 𝑥 ∗𝜀 ∈ 𝑋 such that 0 ∈ 𝐹ℓ𝜀 (𝑥 ∗𝜀 ) + 𝒩𝑋 (𝑥 ∗𝜀 )  ∇𝑥 1 Θ1 (𝑥 1 , 𝑥 −1 )  𝜀     . .. ただし，𝐹ℓ𝜀 (𝑥) :=   , 𝑋 := 𝑋 1 × · · · × 𝑋 𝑁    ∇𝑥 1 Θ𝜀𝑁 (𝑥 𝑁 , 𝑥 −𝑁 )    41 / 96

収束性 定理（MLMFG の停留均衡解への収束） 仮定 L，F が成り立ち，任意の 𝑥 ∈ 𝑋 に対して，フォロワーのナッシュ均衡が一意に 𝑁 定まるとする． 𝜀𝑘 → 0 (𝑘 → ∞) とし，点列 {𝑥 𝑘 } は NEP(𝑋 , {Θ𝜀𝜈𝑘 } 𝜈=1 ) の停留均衡解， すなわち，以下の式を満たすと仮定する． 0 ∈ 𝐹ℓ𝜀 (𝑥 𝑘 ) + 𝒩𝑋 (𝑥 𝑘 ) さらに，すべての 𝜈 ∈ {1, . . . , 𝑁 } について，   lim ∇𝑥 𝜈 𝑦 𝜀𝑘 (𝑥 𝑘,𝜈 , 𝑥 𝑘,−𝜈 ) ⊂ 𝜕𝑥 𝜈 𝑦(𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 ) 𝑘→∞ を満たすとき，{𝑥 𝑘 } の集積点 𝑥 ∗ ∈ 𝑋 は MLMFG の停留均衡解である．すなわち， 0 ∈ 𝜕𝑥 𝜈 Θ 𝜈 (𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 ) + 𝒩𝑋 𝜈 (𝑥 ∗,𝜈 ) ∀𝜈 ∈ {1, . . . , 𝑁 } 42 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム マルチリーダー・フォロワーゲームとは・問題設定 研究背景・研究課題 停留均衡解・提案手法 電力卸売市場への応用・数値実験結果 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 43 / 96

電力卸売市場 [Pang & Fukushima (2005)]15 [Hu & Fukushima (2011)]16 1990 年代より欧米を中心に電力市場の自由化がなされた 過剰な自由市場は独占や違法な取引につながるような様々な問題を引き起こす { 健全な市場であるためのマーケットデザインが欠かせない 電力卸売市場の問題設定（マルチリーダー・シングルフォロワーゲーム） リーダー：電力会社（戦略：各ノード（地域）への売電量を決める） フォロワー：独立系統運用機関（ISO） （戦略：各電力会社からいくら電気を買うか） 15 J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2, 21–56, 2005. 16 M. Hu and M. Fukushima, Variational inequality formulation of a class of multi-leader-follower games, J. Optim. Theory Appl., 151, 455–473, 2011. 44 / 96

電力卸売市場のイメージ 図 4: 電力卸売市場のイメージ 45 / 96

リーダー（電力会社）のモデル 電力会社（リーダー）の最適化問題 簡単のため，リーダーの数を 2 とする 𝑇 ：ノード（地域）の数 リーダー（電力会社）の最適化問題： max 𝑥 𝜈 ∈R𝑇 𝑏 𝜈 (𝑥 𝜈 , 𝑦) − 𝑤 𝜈 (𝑥 𝜈 ) s.t. 0 ≤ 𝑥 𝜈 ≤ 𝜌𝜈 𝑥 𝑖𝜈 （ 𝑖 = 1, . . . , 𝑇 ）：電力会社 𝜈 のノード 𝑖 への送電量（売電量） 𝑦 := (𝑦 1 , . . . , 𝑦 𝑁 )： 𝑦 𝑖𝜈 は電力会社 𝜈 の地域 𝑖 へ送る電気の量（ISO の買電量） 𝑏 𝜈 (·, ·)：入札価格関数（ISO への売電量に対する利益） 𝑤 𝜈 (·)：取引コスト関数（『限界費用逓増の法則』が成り立つ { 凸関数） 46 / 96

フォロワー（ISO）のモデル ISO（フォロワー）の最適化問題 max 𝑦∈R2𝑇 ! 2 𝑇  2 1 2 Õ Õ   𝑦 𝑦 𝜁 𝑖 𝑖 𝑖  𝑞 𝑖 (𝑦 1 , 𝑦 2 ) − − 𝑏 𝜈 (𝑥 𝜈 , 𝑦) − 𝑖 𝑖   2 𝑎1 𝑎2  𝑖=1    𝜈=1 𝑇 Õ s.t. 𝑖=1 𝑦 𝑖𝜈 ≤ 𝑎 𝜈 (𝜈 = 1, 2), 𝑦≥0 𝑞 𝑖 (𝑦 𝑖1 , 𝑦 𝑖2 )：ノード 𝑖 に 𝑦 𝑖1 + 𝑦 𝑖2 送電した時に得られる利益 Í𝑇 𝜈 𝑖=1 𝑦 𝑖 ≤ 𝑎 𝜈 ：電力会社 𝜈 の送電量は 𝑎 𝜈 以下 𝜁 𝑖 > 0：（政府による）市場介入パラメータ { 市場の均衡を保つために導入される 47 / 96

価格関数と利益 ノード 𝑖 に対する逆需要関数（価格）を 𝑝 𝑖 (𝑌𝑖 ) := 𝛼 𝑖 − 𝛽 𝑖 𝑌𝑖 (𝛼 𝑖 , 𝛽 𝑖 > 0) とし，𝑌𝑖 = 𝑦 𝑖1 + 𝑦 𝑖2 とすると，ISO がノード 𝑖 に 𝑌𝑖 送電した時に得られる利益 𝑞 𝑖 (𝑦 𝑖1 , 𝑦 𝑖2 ) は以下のようになる 図 5: 利益関数 𝑞 𝑖 (𝑦 𝑖1 , 𝑦 𝑖2 ) 48 / 96

数値実験：問題設定（リーダー） 先述の電力卸売市場を例に数値実験を行う 数値例は [Hu & Fukushima (2011)] を参考にした 電力会社 𝜈 ∈ {1, 2} の最適化問題 𝑇 Õ max 𝑥 𝜈 ∈R𝑇 𝑖=1 1 𝑥 𝑖𝜈 𝑦 𝑖𝜈 − 2 𝑏 𝜈 (𝑥 𝜈 ,𝑦) 𝑇 Õ 𝑖=1 𝜏𝑖𝜈 (𝑥 𝑖𝜈 )2 s.t. 0 ≤ 𝑥 𝜈 ≤ 𝜌𝜈 𝑤 𝜈 (𝑥 𝜈 ) 数値例： ▶ 取引コスト：𝜏11 = 1.2, 𝜏21 = 1, 𝜏12 = 1.3, 𝜏22 = 1.5 ▶ 売電量の上限：𝜌1 = 𝜌2 = 1 49 / 96

数値実験：問題設定（フォロワー） ISO の最適化問題 " 𝑇  Õ max 𝑦∈R2𝑇 𝑖=1 𝑇 Õ s.t. 𝑖=1 𝛽𝑖 𝛼 𝑖 (𝑦 𝑖1 + 𝑦 𝑖2 ) − (𝑦 𝑖1 + 𝑦 𝑖2 )2 2 𝑞 𝑖 (𝑦 𝑖1 ,𝑦 𝑖2 ) 𝑦 𝑖𝜈 ≤ 𝑎 𝜈 (𝜈 = 1, 2),  𝜁𝑖 − 2 𝑦 𝑖1 𝑎1 − 𝑦 𝑖2 !2# 𝑎2 市場介入ペナルティ − 2 Õ 𝑇 Õ 𝜈=1 𝑖=1 𝑥 𝑖𝜈 𝑦 𝑖𝜈 𝑏 𝜈 (𝑥 𝜈 ,𝑦) 𝑦≥0 数値例： ▶ 逆需要関数の定数：𝛼1 = 1.5, 𝛼2 = 1.8, 𝛽1 = 0.6, 𝛽2 = 0.7 ▶ ペナルティパラメータ：𝜁1 = 𝜁2 = 0.05 ▶ 買電量（送電量）の上限： 𝑎1 = 1.2, 𝑎2 = 1.8 50 / 96

数値実験概要 概要 リーダー数 𝑁 ：2 ノード数 𝑇 ：2 平滑化パラメータ 𝜀𝑘 = 0.75 𝑘 (𝑘 = 0, 1, . . . , 35） （ 𝜀0 = 1， 𝜀35 ≈ 5 × 10−5 ） 各 𝑘 （ 𝑘 = 1, . . . , 35）について均衡解を求める 初期点： 𝑥 0 := (1, 1, 1, 1)（ 𝑦 0 は 𝑥 0 に依存して一意に決まるので不要） Semismooth Newton 法 [Qi and Sun (1993)]17 を用いて解いた 17 L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Program 58, 353–367, 1993. 51 / 96

実験結果：リーダーの戦略 Leader 1's strategy Leader 2's strategy x11 x21 0.5 x12 0.4 0.5 x 2 value x 1 value x22 0.6 0.3 0.2 0.4 0.3 0.1 10−4 10−3 10−2 ε 10−1 100 図 6: 電力会社（リーダー）1 の戦略 𝑥 1𝜀𝑘 10−4 10−3 10−2 ε 10−1 100 図 7: 電力会社（リーダー）2 の戦略 𝑥 2𝜀𝑘 52 / 96

実験結果：フォロワーの戦略 ISO's strategy (sum) ISO's strategy 1.8 1.0 1.6 1.4 y value y value 0.8 0.6 1.2 1.0 0.8 0.4 y y y 0.2 y 0.6 1 1 y +y y +y 1 2 0.4 2 1 1 2 2 2 1 2 2 2 10 10 1 1 −4 10 −3 10 −2 10 −1 10 ε 図 8: ISO の送電量 𝑦11,𝜀𝑘 (𝑥 𝑘 )， 𝑦21,𝜀𝑘 (𝑥 𝑘 ), 𝑦12,𝜀𝑘 (𝑥 𝑘 )， 𝑦22,𝜀𝑘 (𝑥 𝑘 ) 0 −4 10 −3 10 −2 10 −1 10 0 ε 図 9: ISO による各電力会社の送電量 𝑦11,𝜀𝑘 (𝑥 𝑘 ) + 𝑦21,𝜀𝑘 (𝑥 𝑘 )（実線）， 𝑦12,𝜀𝑘 (𝑥 𝑘 ) + 𝑦22,𝜀𝑘 (𝑥 𝑘 )（破線） 53 / 96

市場介入パラメータによる均衡解の変化 市場介入ペナルティ  1 𝑦2  2 𝜁 𝑖 𝑦𝑖 ISO の目的関数にある市場介入ペナルティ項 2 𝑎1 − 𝑎2𝑖 について， 𝜁 の変化に よって各ノードへの送電量の比 𝑦 𝑖1 : 𝑦 𝑖2 を見ていく 送電量の制約 𝑦1𝜈 + 𝑦2𝜈 ≤ 𝑎 𝜈 については前頁と同様， 𝑎 1 = 1.2， 𝑎 2 = 1.8 表 1: 送電量の比（ 𝑦 𝑖1 = 1 としたとき） 𝜁 𝑦11 : 𝑦12 𝑦21 : 𝑦22 (0.01, 0.01) 1 : 1.3641 1 : 1.6298 (0.05, 0.05) 1 : 1.3660 1 : 1.6286 実際， 𝑎 1 : 𝑎 2 = 1 : 1.5 となり，政府による市場介入によって， 各ノードへの送電量は各電力会社の規模 へと近づくことがわかる 54 / 96

まとめ・課題 まとめ 応答が陽に書けない場合でも MLMFG の（停留）均衡点を得る手法を提案 数値実験によって，手法の有効性を検証 課題 ∇𝑦 𝜖 (𝑥)，および ∇𝑥 𝜈 Θ𝜖𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) の評価コストを抑えるアルゴリズムへの改良 フォロワーのナッシュ均衡の一意性を仮定しないときの悲観的・楽観的リーダー・ フォロワーナッシュ均衡の計算方法を確立 55 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 準備：確率ナッシュ均衡問題 ２段階分布的ロバスト確率ナッシュ均衡問題・ナッシュ均衡の存在性 2 段階分布的ロバスト変分不等式への再定式化 クールノー・ナッシュ均衡問題への応用・数値実験結果 5 まとめ・今後の展望 56 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 準備：確率ナッシュ均衡問題 ２段階分布的ロバスト確率ナッシュ均衡問題・ナッシュ均衡の存在性 2 段階分布的ロバスト変分不等式への再定式化 クールノー・ナッシュ均衡問題への応用・数値実験結果 5 まとめ・今後の展望 57 / 96

導入：確率ナッシュ均衡問題 定義：確率ナッシュ均衡問題 𝑁 人のプレイヤーによる非協力ゲームを考える．写像 𝜉 : Ω → Ξ を確率変数とする． プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } の最適化問題が以下のように確率変数を含むようなナッシュ 均衡問題を確率ナッシュ均衡問題と呼ぶ： E[𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝜉)] min 𝜈 𝑛 𝑥 ∈R 𝜈 s.t. 𝑥𝜈 ∈ 𝑋 𝜈 戦略空間に確率変数を含むものも考えられるが，本発表では 目的関数のみ確率変数を含むものを考える 各プレイヤーの目的関数に以下のようなものも確率ナッシュ均衡問題と呼ばれる： 𝜈 𝜈 −𝜈 min 𝜃 (𝑥 , 𝑥 , 𝜉) 𝜈 𝑛 𝑥 ∈R 𝜈 s.t. 𝑥𝜈 ∈ 𝑋 𝜈 58 / 96

2 段階確率ナッシュ均衡問題 時系列に応じて演じる非協力ゲームを考える 2 段階確率ナッシュ均衡問題：各プレイヤーが 2 段階の意思決定を行う非協力ゲーム VWVWDJH EHIRUHREVHUYLQJ DUHDOL]DWLRQ QGVWDJH HJWRPRUURZ )LUP 3UREDELOLW\ )LUP  3UREDELOLW\ 6WUDWHJ\ 6XSSO\ )LUP  6FHQDULRXQGHUSULFH 6WUDWHJ\ 3URGXFWLRQ )LUP  )LUP  )LUP  6FHQDULRXQGHUSULFH 図 10: 2 段階確率ナッシュ均衡問題のイメージ 59 / 96

具体例：原油市場における 2 段階確率ナッシュ均衡問題 [Jiang et al. (2019)]18 プレイヤーを原油産出国（例：ロシア，中国，サウジアラビア）とする 第一段階の戦略：原油の算出 第二段階の戦略：原油の市場への供給（輸出） 第１段階 （需要を観測する前） 第２段階（例：翌月） 産油国A 確率 確率 産油国A 価格 કྲྀʁ‫ݬ‬་͹ਫ਼ࢊྖ 産油国B કྲྀʁࢤ৖΃͹‫ྖڇڛ‬ 産油国B のシナリオ 産油国A 価格 産油国B のシナリオ 図 11: 例：原油市場における 2 段階確率ナッシュ均衡問題 18 J. Jiang, Y. Shi, X. Wang, and X. Chen, Regularized two-stage stochastic variational inequalities for Cournot–Nash equilibrium under uncertainty, J. Comput. Math., 37, 813–842, 2019. 60 / 96

2 段階確率非協力ゲーム：第２段階 第２段階：実現値 ξ ∈ Ξ におけるプレイヤー 𝜈 ∈ {1, . . . , 𝑁 } の最適化問題 𝑄 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , ξ) B min 𝑦 𝜈 (ξ) s.t. 𝜃2𝜈 (𝑦 𝜈 (ξ), 𝑦 −𝜈 (ξ), 𝑥 𝜈 , 𝑥 −𝜈 , ξ) 𝑦 𝜈 (ξ) ∈ 𝑌 𝜈 (𝑥 𝜈 , ξ) ⊂ R𝑚𝜈 プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } に対して， ▶ 𝜃2𝜈 ：第２段階のコスト関数 ▶ 𝑦 𝜈 (ξ)：第２段階における戦略ベクトル（決定変数） ▶ 𝑌 𝜈 (𝑥 𝜈 , ξ)：戦略集合 ▶ 𝑦 −𝜈 (ξ)：第２段階におけるプレイヤー 𝜈 以外のプレイヤーの戦略組 ▶ 𝑥 𝜈 ：第１段階における戦略ベクトル ▶ 𝑥 −𝜈 ：第１段階におけるプレイヤー 𝜈 以外のプレイヤーの戦略組 𝑄 𝜈 (·, ·, ξ)：リコース関数とも呼ばれる 61 / 96

2 段階確率非協力ゲーム：第１段階 実現値ξ を知る前に演じられるゲーム（第２段階の利得を期待値で評価） 第１段階：プレイヤー 𝜈 の最適化問題 min 𝜈 𝑛 𝑥 ∈R 𝜈 𝜃1𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) + E[𝑄 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝜉)] s.t. 𝑥𝜈 ∈ 𝑋 𝜈 𝜉 : Ω → Ξ：確率変数 𝑋 𝜈 ：戦略集合（実行可能集合） 𝜃1𝜈 ：第１段階のコスト関数（目的関数）   多段階確率変分不等式 [Rockafellar & Wets (2017)]19 の発展により， 近年連続最適化の分野でも注目されるようになる   19 R.T. Rockafellar and R.J.B. Wets, Stochastic variational inequalities: single-stage to multistage, Math. Program., 165, 331–360, 2017 62 / 96

先行研究 [Haurie et al. (1990)]20 ：寡占市場において，各プレイヤーが 2 段階確率計画問題を 解くような非協力ゲームを考えた（我々の知る限り）初めての論文 [Jiang et al. (2019)]21 ：（今回主として取り扱う）Cournot–Nash ゲーム [Zhou & Sun (2020)]22：[Jiang et al. (2019)] をリスク回避型（CVaR）に拡張した２ 段階ゲームと 2 段階確率変分不等式への再定式化 20 A. Haurie et al., Stochastic equilibrium programming for dynamic oligopolistic markets, J. Optim. Theory Appl., 66, 243–253, 1990 21 J. Jiang et al., Regularized two-stage stochastic variational inequalities for Cournot–Nash equilibrium under uncertainty, J. Comput. Math., 37, 813–842, 2019 22 B. Zhou and H. Sun, Two-stage stochastic variational inequalities for Cournot–Nash equilibrium with risk-averse players under uncertainty, Numer. Algebra, Control. Optim., 10, 521–535, 2020 63 / 96

多段階確率非協力ゲームの応用 I [Genc et al. (2007)]23 ：寡占市場における動的な非協力ゲームを多段階確率計画問題 として定式化．オンタリオ州（カナダ）の電力卸売市場を分析 [Philpott et al. (2016)]24：水力発電における電力配分問題を多段階確率非協力ゲーム として定式化して分析 [Jiang et al. (2019)]25 ：石油市場におけるシェアの推移を予測 23 T.S. Genc, S.S. Reynolds, and S. Sen, Dynamic oligopolistic games under uncertainty: A stochastic programming approach, J. Econ. Dyn. Control., 31, 55–80, 2007. 24 A. Philpott, M.C. Ferris, and R.J.B. Wets, Equilibrium, uncertainty and risk in hydro-thermal electricity systems, Math. Program, 157, 483–513, 2016. 25 J. Jiang et al., Regularized two-stage stochastic variational inequalities for Cournot–Nash equilibrium under uncertainty, J. Comput. Math., 37, 813–842, 2019. 64 / 96

研究動機 確率変数の分布を特定するためには十分なデータがなければならない 一般には，各数年分なかったりある年のデータがなかったりと，十分でない   その中で各プレイヤーが非協力ゲームを演じるようなゲームを考えてみたらどうか   65 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 準備：確率ナッシュ均衡問題 ２段階分布的ロバスト確率ナッシュ均衡問題・ナッシュ均衡の存在性 2 段階分布的ロバスト変分不等式への再定式化 クールノー・ナッシュ均衡問題への応用・数値実験結果 5 まとめ・今後の展望 66 / 96

2 段階分布的ロバスト確率非協力ゲーム プレイヤー 𝜈 ∈ {1, . . . , 𝑁 } の最適化問題 第１段階（ワーストケース確率分布における期待利得を最大化）： min 𝜈 𝜈 𝑥 ∈𝑋 Θ 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) B {𝜃1𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) + sup E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝜉)]} 𝑃∈P 𝜈 P 𝜈 ：分布不確実性集合（例：P 𝜈 B {𝑃 : D(𝑃0 , 𝑃) ≤ 𝛿}） 第２段階は同じ最適化問題 データ不足やノイズなどが原因で 𝜉 の確率分布が正確に予測できないでも， リターンを考慮しながらリスクを抑える均衡解を得ることを目的 （cf. ロバストナッシュ均衡問題） 67 / 96

2 段階分布的ロバストナッシュ均衡（TSDRNE） 定義：2 段階分布的ロバストナッシュ均衡（TSDRNE） 点 (𝑥 ∗ , 𝑦 ∗ (·)) B (𝑥 ∗,1 , . . . , 𝑥 ∗,𝑁 , 𝑦 ∗,1 (·), . . . , 𝑦 ∗,𝑁 (·)) が 2 段階分布的ロバストナッシュ 均衡（Two-Stage Distributionally Robust Nash Equilibrium: TSDRNE）であるとは， すべての 𝜈 ∈ {1, . . . , 𝑁 } に対して，      𝑥 ∗,𝜈 ∈ argmin 𝑥 𝜈 ∈𝑋 𝜈 Θ 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 ) 𝑦 ∗,𝜈 (ξ) ∈ argmin 𝜃2𝜈 (𝑦 𝜈 (ξ), 𝑦 ∗,−𝜈 (ξ), 𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 , ξ) ∀ξ ∈ Ξ    𝑦 𝜈 (ξ)∈𝑌 𝜈 (𝑥 ∗,𝜈 ,ξ)  68 / 96

ナッシュ均衡の存在性 定理：均衡解の存在条件 以下の仮定の下で，２段階分布的ロバスト非協力ゲームは均衡解をもつ． すべての 𝜈 ∈ {1, . . . , 𝑁 } について， 1. 𝜃1𝜈 , 𝜃2𝜈 ：連続 2. 𝜃1𝜈 (·, 𝑥 −𝜈 )：任意に固定した 𝑥 −𝜈 に対して凸 3. 𝜃2𝜈 (·, 𝑦 −𝜈 (ξ), ·, 𝑥 −𝜈 , ξ)：任意に固定した (𝑦 −𝜈 (ξ), 𝑥 −𝜈 , ξ) に対して結合凸 𝜈 4. 𝑋 𝜈 ⊂ R𝑛 ：凸 & コンパクト 5. 𝑌 𝜈 (·, ·)：連続 & 𝑌(𝑥 𝜈 , ξ) における任意の 𝑥 𝜈 ∈ 𝑋 𝜈 と ξ ∈ Ξ に対してコンパクト凸 6. P 𝜈 ：弱コンパクト 26 . ′ 26 P が弱コンパクト def ⇔ 任意の列 {𝑃 𝑖 } ⊂ P は P 上の点に弱収束する部分列 {𝑃 𝑖 } をもつ 69 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 準備：確率ナッシュ均衡問題 ２段階分布的ロバスト確率ナッシュ均衡問題・ナッシュ均衡の存在性 2 段階分布的ロバスト変分不等式への再定式化 クールノー・ナッシュ均衡問題への応用・数値実験結果 5 まとめ・今後の展望 70 / 96

離散型確率変数 以下では，確率分布は離散型（連続型を離散近似させたもの）として進める シナリオが 𝐾 個存在し，シナリオの集合を Ξ𝐾 := {ξ1 , . . . , ξ𝐾 } とする．シナリオ ξ 𝑘 ∈ Ξ の確率を 𝑝 𝑘 ≥ 0 とする 𝐾 取りうる分布のすべてを Δ ⊂ R+ とする： Δ := {𝑃 ∈ R+𝐾 | 𝑃1 + · · · + 𝑃𝐾 = 1} 以後，P 𝜈 ⊂ Δ を離散型の分布不確実性集合とし，プレイヤー 𝜈 の確率ベクトルを 𝑃 𝜈 := (𝑃1𝜈 , . . . , 𝑃𝐾𝜈 ) ∈ Δ とする 71 / 96

2 段階分布的ロバスト変分不等式への再定式化 定理：2 段階分布的ロバスト変分不等式 [Hori & Yamashita (2023)] への再定式化 以下の仮定が成り立つとする： 1. 𝜃1𝜈 , 𝜃2𝜈 ：連続的微分可能 2. 𝜃1𝜈 (·, 𝑥 −𝜈 )：任意に固定した 𝑥 −𝜈 に対して凸 3. 𝜃2𝜈 (𝑦 𝜈 (𝜉), 𝑦 −𝜈 (𝜉), 𝑥 𝜈 , 𝑥 −𝜈 , 𝜉)：任意に固定した (𝑦 −𝜈 (𝜉), 𝑥 −𝜈 , 𝜉) に対して，(𝑦 𝜈 (𝜉), 𝑥 𝜈 ) について結合凸 𝜈 4. 𝑋 𝜈 ⊂ R𝑛 ：コンパクト凸 5. 𝑌 𝜈 (·, ·)：連続 & 𝑌(𝑥 𝜈 , ξ) における任意の 𝑥 𝜈 ∈ 𝑋 𝜈 と ξ ∈ Ξ に対してコンパクト凸 6. P 𝜈 ：閉凸集合 72 / 96

2 段階分布的ロバスト変分不等式への再定式化（続き） （続き） このとき，戦略の組 (𝑥 ∗ , 𝑦 ∗ (·)) が TSDRNE であるための必要十分条件は，ある 𝑃 ∗,𝜈 （𝜈 = 1, . . . , 𝑁 ）が存在して，(𝑥 ∗ , 𝑦 ∗ (·)) が以下の条件を満たすことである： 0 ∈ 𝐹(𝑥 ∗ ) + E𝑃 ∗ [𝑣(𝑥 ∗ , 𝜉)] + 𝒩𝑋 (𝑥 ∗ ) 0 ∈ 𝐺(𝑥 ∗ , 𝑦 ∗ (ξ 𝑘 ), ξ 𝑘 ) + 𝒩𝑌(𝑥 ∗ ,ξ𝑘 ) (𝑦 ∗ (ξ 𝑘 )) ∀𝑘 𝑃 ∗,𝜈 ∈ argmax E𝑃 [𝑄 𝜈 (𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 , 𝜉)], 𝑃∈P 𝜈 ただし， 𝜈 = 1, . . . , 𝑁 𝑁 𝐹(𝑥) := [∇𝑥 𝜈 𝜃1𝜈 (𝑥 𝜈 , 𝑥 −𝜈 )]𝜈=1 𝑣(𝑥, 𝜉) ∈ 𝜕𝑥 1 𝑄 1 (𝑥 1 , 𝑥 −1 , 𝜉) × · · · × 𝜕𝑥 𝑁 𝑄 𝑁 (𝑥 𝑁 , 𝑥 −𝑁 , 𝜉) 𝑁 𝐺(𝑥, 𝑦(ξ), ξ) := [∇ 𝑦 𝜈 (ξ) 𝜃2𝜈 (𝑦 𝜈 (ξ), 𝑦 −𝜈 (ξ), 𝑥 𝜈 , 𝑥 −𝜈 , ξ)]𝜈=1 73 / 96

Progressive Hedging Algorithm の適用 離散確率変数の多段階確率変分不等式に対する解法（Progressive Hedging Algorithm: PHA）は [Rockafellar & Sun (2019)]27 によって提案された その後，連続確率変数の離散化近似手法 [Chen et al. (2019)]28 [Jiang & Sun (2023)]29 や擬単調への拡張 [Cui et al. (2023)]30 がなされた もともと PHA は多段階確率計画問題に対して提案されたもの [Rockafellar & Wets (1991)]31 を多段階確率変分不等式問題に拡張した 27 R.T. Rockafellar and J. Sun, Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging, Math. Program, 174, 453–471, 2019. 28 X. Chen, H. Sun, and H. Xu, Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems, Math. Program., 177, 255-289, 2019. 29 J. Jiang and H. Sun, Monotonicity and complexity of multistage stochastic variational inequalities, J. Optim. Theory Appl., 196, 433–460, 2023. 30 X. Cui, J. Sun, and L. Zhang, On multistage pseudomonotone stochastic variational inequalities, J. Optim. Theory Appl., 2023. 31 R.T. Rockafellar and R.J.B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16, 119–147, 1991 74 / 96

Progressive Hedging Algorithm との交互アルゴリズムの概要 反復回数を ℓ ∈ N ∪ {0} と表す 以下の最大化問題と変分不等式問題を交互に解くことで，TSDRNE を求められる： 1. 点 (𝑥ℓ , 𝑦ℓ (𝜉1 ), . . . , 𝑦ℓ (𝜉𝐾 )) の下で，各プレイヤーにおけるリコースの最悪の期待値 を求める： 𝑃ℓ +1,𝜈 ∈ argmax E𝑃 [𝑄 𝜈 (𝑥ℓ ,𝜈 , 𝑥ℓ ,−𝜈 , 𝜉)], 𝑃∈P 𝜈 𝜈 = 1, . . . , 𝑁 2. PHA を利用して，確率を 𝑃ℓ +1 に固定した以下の２段階確率変分不等式を解く： 0 ∈ 𝐹(𝑥) + E𝑃ℓ +1 [𝑣(𝑥, 𝜉)] + 𝒩𝑋 (𝑥) 0 ∈ 𝐺(𝑥, 𝑦(ξ 𝑘 ), ξ 𝑘 ) + 𝒩𝑌(𝑥,ξ𝑘 ) (𝑦(ξ 𝑘 )) ∀𝑘 （詳細は付録『Appendix: Progressive Hedging Algorithm』を参考） 75 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 準備：確率ナッシュ均衡問題 ２段階分布的ロバスト確率ナッシュ均衡問題・ナッシュ均衡の存在性 2 段階分布的ロバスト変分不等式への再定式化 クールノー・ナッシュ均衡問題への応用・数値実験結果 5 まとめ・今後の展望 76 / 96

2 段階クールノー競争 クールノー競争 [Cournot (1838)]32 ：寡占市場における企業間の競争において， 互いの最適な生産量を決める（不確実性を考慮しない決定論的なモデル） 2 段階確率クールノー競争 [Haurie et al. (1990)]33 ：寡占市場において各企業が生産 （第 1 段階）・市場への供給（第 2 段階）を決める { 将来の需要とライバルの戦略を推測しながら，最適な生産量と供給量を決める 簡単のため，複占市場（ 𝑁 = 2）での 2 段階確率クールノー競争を考える 32 A.-A. Cournot, Recherches sur les Principes Mathématiques de la Théorie des Richesses, 1838 33 A. Haurie, G. Zaccour, and Y. Smeers, Stochastic equilibrium programming for dynamic oligopolistic markets, J. Optim. Theory Appl., 66, 243–253, 1990. 77 / 96

問題設定（第１段階） 複占市場（ 𝑁 = 2）において，各企業はある同質財を生産・供給する意思決定を行う 第一段階（ワーストケース確率分布における期待利益を最大化） 財の生産量を決定する企業 𝜈 ∈ {1, 2} の最適化問題： max 𝜈 min𝜈 E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝜉)] − 𝜃 𝜈 (𝑥 𝜈 ) 𝑥 ∈R 𝑃∈P s.t. 𝑥𝜈 ≥ 0 第二段階の期待利益 生産コスト ※ 戦略集合はコンパクトでない ▶ 𝑥 𝜈 ≥ 0：生産量（設備投資量） ▶ 𝜃 𝜈 : R → R：可変費用関数（『限界費用逓増の法則』が成り立つ { 凸関数） （簡単のため，固定費用は考えない） 78 / 96

問題設定（第２段階） 第２段階（シナリオ ξ ∈ Ξ をとったとき） 第一段階で生産した財の市場への供給量を決める企業 𝜈 ∈ {1, 2} の最適化問題： 𝑄 𝜈 (𝑥 𝜈 , ξ) B max 𝑦 𝜈 (ξ)∈R s.t. 𝑝(𝑞(ξ), ξ)𝑦 𝜈 (ξ) − 𝐻 𝜈 (𝑦 𝜈 (ξ), ξ) 売上 市場への供給コスト 0 ≤ 𝑦 𝜈 (ξ) ≤ 𝑥 𝜈 ▶ 𝑦 𝜈 (ξ) ≥ 0：市場への供給量（ただし， 𝑦 𝜈 (ξ) ≤ 𝑥 𝜈 ） ▶ 𝐻 𝜈 (·, ξ) : R → R：供給コスト（可変費用）関数 （限界費用逓増の法則が成り立つ { 凸関数） ▶ 𝑝(·, ξ) : R2 → R：逆需要関数（𝑝 ′𝑞 (𝑞(ξ), ξ) < 0） ▶ 𝑞(ξ) B 𝑦 1 (ξ) + 𝑦 2 (ξ)：市場に供給される財の総量 79 / 96

均衡解の存在性 定理（クールノー競争における均衡解の存在性） すべての 𝜈 ∈ {1, 2} に対して E𝑃 𝜈 [𝑝(𝑦 𝜈 (𝜉), 𝜉)] < 𝜃 𝜈 ′(𝑥 𝜈 ) (𝑥 𝜈 ≥ 𝑥¯ 𝜈 ) が成り立つとする．このとき，ある生産量の上限 𝑀𝜈 > 0（𝜈 = 1, 2）が存在して， TSDRNE が存在する．ここで， 𝑃 𝜈 ∈ argmin E𝑃 [𝑄 𝜈 (𝑥 𝑗 , 𝜉)] 𝑃∈P 𝜈   限界費用が限界収益の期待値を超えると，企業はそれ以上生産する動機を持たない   80 / 96

問題設定（第１段階）
前節で紹介したクールノー・ナッシュ均衡問題を考える
数値例は [Hori & Yamashita (2023)]34 を参考

第１段階：企業 𝜈 ∈ {1, 2} の最適化問題
𝜈 𝜈
𝜈 𝜈
min
E
[𝑄
(𝑥
,
𝜉)]
−
𝜃
(𝑥 )
max
𝑃
𝜈
𝜈
𝑥 ∈R 𝑃∈P

s.t.

𝑥𝜈 ≥ 0

生産コスト（二次関数）
：

𝜃 𝜈 (𝑥 𝜈 ) :=

1
𝑎 𝜈 (𝑥 𝜈 )2 + 𝑏 𝜈 𝑥 𝜈 + 𝑐 𝜈
2

(𝑎 𝜈 , 𝑏 𝜈 , 𝑐 𝜈 > 0)

34 A. Hori and N. Yamashita, Two-stage distributionally robust noncooperative games: Existence of Nash equilibrium and its application to

Cournot–Nash competition, J. Ind. Manag. Optim., 19, 6430–6450, 2023

81 / 96

問題設定（第１段階）：分布不確実性集合 目的関数 min𝜈 E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝜉)] − 𝜃 𝜈 (𝑥 𝜈 ) 𝑃∈P における分布不確実性集合 P 𝜈 を以下のように定める Kullback–Leibler ダイバージェンス P 𝜈 (𝜈 = 1, 2)：Kullback–Leibler(KL) ダイバージェンスによる分布不確実性集合 ( P 𝜈 = P(𝜌𝜈 ) B 𝑃 ∈ Δ : 𝐾 Õ 𝑘=1  𝑃𝑘 log  𝑃𝑘 ≤ 𝜌𝜈 𝑃0𝑘 ) ただし，𝜌𝜈 > 0 𝑃0𝑘 ：シナリオ 𝑘 の公称確率（少サンプル下で推定したものとみなす） 82 / 96

問題設定（第２段階） 第２段階（シナリオ ξ ∈ Ξ のとき） 𝑄 𝜈 (𝑥 𝜈 , ξ) B max     𝑦 𝜈 (ξ)∈R   𝑝(𝑞(ξ), ξ)𝑦 𝜈 (ξ) − 𝐻 𝜈 (𝑦 𝜈 (ξ), ξ)  売上 0 ≤ 𝑦 𝜈 (ξ) ≤ 𝑥 市場への供給コスト     𝜈    𝑞(ξ) := 𝑦 1 (ξ) + 𝑦 2 (ξ)：市場に供給される財の総量 𝑝(𝑞(ξ), ξ) 逆需要関数： 𝑝(𝑞(ξ), ξ) := 𝛼(ξ) − 𝛽(ξ)𝑞(ξ) (𝛼(ξ) > 𝛽(ξ) > 0) ∀ξ ∈ Ξ 𝐻 𝜈 (𝑦 𝜈 (ξ), ξ) 供給コスト： 1 𝐻 𝜈 (𝑦 𝜈 (ξ), ξ) := 𝜂𝜈 (ξ)(𝑦 𝜈 (ξ))2 +𝜁 𝜈 (ξ)𝑦 𝜈 (ξ)+𝑠 𝜈 (ξ) (𝜂𝜈 (ξ), 𝜁 𝜈 (ξ), 𝑠 𝜈 (ξ) > 0) ∀ξ ∈ Ξ 2 83 / 96

数値実験の目的と概要 数値実験の目的 不確実性集合の変化によって，TSDRNE，つまり各企業の最適反応戦略の変化をみる 数値実験の概要 シナリオ数 𝐾 ：60（Ξ = {ξ1 , . . . , ξ60 }） （実際は連続的な値をとる需要に関するパラメータで，等間隔で離散近似している） 実現値の取りうる値の範囲：ξ 𝑘 ∈ [−1, 1]3 （Ξ ⊂ [−1, 1]3 ） 𝜌1 B 𝜌，𝜌2 B 2 − 𝜌 （0 ≤ 𝜌 ≤ 2）とし，0.1 刻みで 𝜌 を変えながら，それぞれの 場合における TSDRNE を求める 84 / 96

実験結果 I35 ：均衡解における各プレイヤーの利得関数値 横軸：分布不確実性の大きさ 𝜌 大 { プレイヤー 1 の不確実性大 𝜌 小 { プレイヤー 2 の不確実性大   不確実性が大きくなるにつれて 悲観的戦略を取り，利得は減少傾向   公称分布 𝑃0 を過信して 𝜌 を小さく 見積ると，確率分布が極端に異なった時 の損失は大きくなる（次頁） 図 12: 均衡解における各プレイヤーの利得 35 𝜉 のサンプリングによる依存性を減らすために各 𝜌 で 30 回実験し，その平均をプロットしている． 85 / 96

実験結果 II：確率分布の摂動に対する期待利得の変化（感度分析） 確率ベクトルに摂動を与えたときの 期待利得のずれに関して最大値を プロット   𝜌 大 { 確率分布のずれに頑健   図 13: 期待利得の変化（確率ベクトルに関する 方向微分の絶対値の最大） 86 / 96

実験結果 III：均衡解における各プレイヤーの生産・供給量 生産量 𝑥 𝜈 を実線，全シナリオにおける均 衡供給量 𝑦 ∗,𝜈 (ξ1 ), . . . , 𝑦 ∗,𝜈 (ξ𝐾 ) の平均 𝑦¯ ∗,𝜈 1 Õ ∗,𝜈 B 𝑦 (ξ 𝑘 ) 𝐾 𝐾 𝑘=1 を破線でプロット  不確実性が大きいほど，プレイヤーは 生産量の全量を市場に供給する傾向   図 14: 生産量 𝑥 ∗,𝜈 と市場への供給量 𝑦 ∗,𝜈 (ξ1 ), . . . , 𝑦 ∗,𝜈 (ξ60 ) の平均 87 / 96

まとめ・今後の課題 本発表のまとめ 非線形の一般的な 2 段階分布的ロバスト確率非協力ゲームを考え，均衡解の 存在条件を示した クールノー競争を考察し，均衡解の存在条件を経済学的な視点で明らかにした 数値実験を通して，分布的ロバスト性がもたらす意思決定の変化を分析した 今後の課題 大域的収束性が保証された 2 段階分布的ロバスト均衡解を求める数値解法の 確立と高速化 制約条件が他のプレイヤーの戦略に依存するモデルへの拡張 88 / 96

目次 1 本講演の大まかな構成 2 準備：ナッシュ均衡問題と変分不等式 3 研究成果紹介 1：マルチリーダー・フォロワーゲーム 4 研究成果紹介 2：２段階分布的ロバストナッシュ均衡問題 5 まとめ・今後の展望 89 / 96

本講演のまとめ まとめ 準備として，単純なナッシュ均衡問題を通して連続最適化とのつながりを紹介 自身の研究成果を２つ紹介 ▶ MLMFG に対する平滑化近似解法 ▶ TSDRNEP におけるナッシュ均衡の存在性とクールノー競争への応用 90 / 96

研究課題 研究課題 【MLMFG】LF ナッシュ均衡は必ずしも一意とは限らず，一意かどうかを調べること も実際は困難 { 悲観的・楽観的 LF ナッシュ均衡の求解方法の開発 【MLMFG】∇𝑦 𝜀 (𝑥) を求めるためには，フォロワーの最適化問題について高階導関数 の情報が必要であり，計算効率が良いとはいえない 【TSDRNE】戦略空間 𝑋 𝜈 が他のプレイヤーの戦略に依存する（𝑋 𝜈 (𝑥 −𝜈 )）一般化 ナッシュ均衡問題への拡張 【TSDRNE】確率変数 𝜉 や分布不確実性集合 P 𝜈 が戦略に依存するより複雑な設定 下での二段階分布的ロバストナッシュ均衡問題への拡張 91 / 96

参考文献 I [Aubin (1979)] J.P. Aubin, Mathematical Methods of Game and Economic Theory, North-Holland, 1979. [Chen et al. (2019)] X. Chen, H. Sun, and H. Xu, Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems, Math. Program., 177, 255-289, 2019. [Cournot (1838)] A.-A. Cournot, Recherches sur les Principes Mathématiques de la Théorie des Richesses, 1838. [Cui et al. (2023)] X. Cui, J. Sun, and L. Zhang, On multistage pseudomonotone stochastic variational inequalities, J. Optim. Theory Appl., 2023. [Facchinei & Pang (2003)] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, 2003. [Ferris et al. (2005)] M.C. Ferris, P. Dirkse, and A. Meeraus: Mathematical programs with equilibrium constraints: automatic reformulation and solution via constrained optimization. In: T.J. Kehoe, T.N. Srinivasan, and J. Whalley, (eds.) Frontiers in Applied General Equilibrium Modeling, 67–93. Cambridge University Press, Cambridge, 2005. 92 / 96

参考文献 II [Genc et al. (2007)] T.S. Genc, S.S. Reynolds, and S. Sen, Dynamic oligopolistic games under uncertainty: A stochastic programming approach, J. Econ. Dyn. Control., 31, 55–80, 2007. [Haurie et al. (1990)] A. Haurie, G. Zaccour, and Y. Smeers, Stochastic equilibrium programming for dynamic oligopolistic markets, J. Optim. Theory Appl., 66, 243–253, 1990. [Jiang et al. (2019)] J. Jiang, Y. Shi, X. Wang, and X. Chen, Regularized two-stage stochastic variational inequalities for Cournot–Nash equilibrium under uncertainty, J. Comput. Math., 37, 813–842, 2019. [Jiang & Sun (2023)] J. Jiang and H. Sun, Monotonicity and complexity of multistage stochastic variational inequalities, J. Optim. Theory Appl., 196, 433–460, 2023. [Leyffer & Munson (2010)] S. Leyffer and T. Munson, Solving multi-leader–common-follower games, Optim. Method Softw. 25, 601–623, 2010. [J.F. Nash (1950)] J. F. Nash, Equilibrium points in 𝑛-person games, Proc. Natl. Acad. Sci. USA, 36, 48–49, 1950. [J.F. Nash (1951)] J. F. Nash, Non-cooperative games, Ann. Math., 54, 286–295, 1951. 93 / 96

参考文献 III [Neumann & Morgenstern (1944)] J. von Neumann and O. Morgenstern (1944), Theory of Games and Economic Behavior, Princeton University Press. [Herty et al. (2022)] M. Herty, S. Steffensen, and A. Thünen (2022), Solving quadratic multi-leader-follower games by smoothing the follower’s best response, Optim. Method Softw. 37, 772–799, 2022. [Hori & Fukushima (2019)] A. Hori and M. Fukushima, Gauss–Seidel method for multi-leader–follower games, J. Optim. Theory Appl., 180, 651–670, 2019. [Hori & Yamashita (2023)] A. Hori and N. Yamashita, Two-stage distributionally robust noncooperative games: Existence of Nash equilibrium and its application to Cournot–Nash competition, J. Ind. Manag. Optim., 19, 6430–6450, 2023 [Hori et al. (2023)] A. Hori, D. Tsuyuguchi, and E.H. Fukuda, A method for multi-leader-multi-follower games by smoothing the followers’ response function, arXiv: 2311.18601, 2023. [Hu & Fukushima (2011)] M. Hu and M. Fukushima, Variational inequality formulation of a class of multi-leader-follower games, J. Optim. Theory Appl., 151, 455–473, 2011. 94 / 96

参考文献 IV [Pang & Fukushima (2005)] J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2, 21–56, 2005. [Philpott et al. (2016)] A. Philpott, M.C. Ferris, and R.J.B. Wets, Equilibrium, uncertainty and risk in hydro-thermal electricity systems, Math. Program, 157, 483–513, 2016. [Qi and Sun (1993)] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Program 58, 353–367, 1993. [Rockafellar & Sun (2019)] R.T. Rockafellar and J. Sun, Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging, Math. Program, 174, 453–471, 2019. [Rockafellar & Wets (1991)] R.T. Rockafellar and R.J.B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16, 119–147, 1991. [Rockafellar & Wets (2017)] R.T. Rockafellar and R.J.B. Wets, Stochastic variational inequalities: single-stage to multistage, Math. Program, 165, 331–360, 2017. 95 / 96

参考文献 V [Zhou & Sun (2020)] B. Zhou and H. Sun, Two-stage stochastic variational inequalities for Cournot–Nash equilibrium with risk-averse players under uncertainty, Numer. Algebra, Control. Optim., 10, 521–535, 2020. 96 / 96

Appendix：フォロワーのナッシュ均衡の一意性 仮定 F より，以下の変分不等式の解 𝑦 ∗ はフォロワーのナッシュ均衡となる： ⟨𝐺(𝑥, 𝑦 ∗ ), 𝑦 − 𝑦 ∗ ⟩ ≥ 0 ∀𝑦 ∈ 𝑌(𝑥) ただし，  ∇ 𝑦 1 𝛾1 (𝑥, 𝑦 1 , 𝑦 −1 )    𝑌(𝑥) := 𝑌 1 (𝑥) × · · · × 𝑌 𝑀 (𝑥)   . .. 𝐺(𝑥, 𝑦) :=  ,   = {𝑦 ∈ R𝑚 | 𝑔(𝑥, 𝑦) ≤ 0} 𝑀 𝑀 −𝑀  ∇ 𝑦 𝑀 𝛾 (𝑥, 𝑦 , 𝑦 )    仮定 F2 すべての 𝑥 ∈ 𝑋 について，𝐺(𝑥, ·) : R𝑚 → R𝑚 は狭義単調，すなわち ⟨𝐺(𝑥, 𝑦) − 𝐺(𝑥, 𝑦 ′), 𝑦 − 𝑦 ′⟩ > 0 ∀𝑦, 𝑦 ′ ∈ 𝑌(𝑥) (𝑦 ≠ 𝑦 ′)    𝑌(𝑥) のコンパクト凸性と仮定 F2 より，変分不等式の解 𝑦 ∗ は一意 1 / 16

Appendix：LF ナッシュ均衡の存在性 定理：LF ナッシュ均衡の存在性 以下の仮定が成り立つとする： 1. 各 𝑥 ∈ 𝑋 について，応答 𝒮(𝑥) が一意（これを 𝑦(𝑥) と表す） 2. すべての 𝜈 に対して，目的関数 𝜃 𝜈 と応答関数 𝑦 が連続 3. すべての 𝜈 に対して，𝑋 𝜈 ⊂ R𝑛𝜈 が非空コンパクト凸 4. すべての 𝜈 に対して，Θ 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) := 𝜃 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 , 𝑦(𝑥 𝜈 , 𝑥 −𝜈 )) が任意に固定した 𝑥 −𝜈 に対して凸 このとき，MLMFG の LF ナッシュ均衡が存在する．   応答関数 𝑦(𝑥) は陽に書けないため，  Θ 𝜈 (𝑥 𝜈 , 𝑥 −𝜈 ) の凸性を調べることは一般には難しい  2 / 16

Appendix：数値実験：問題設定（リーダー） 3 節で紹介したものよりも複雑な問題でも数値実験した 2 リーダー・2 フォロワーゲーム（ 𝑁 = 𝑀 = 2）を考える モデルは [Hori & Fukushima (2019)]36 を参考にし，数値例は独自で作成 リーダー 𝜈 ∈ {1, 2} の最適化問題 min 𝑥 𝜈 ∈R2 s.t. Õ 1 𝜈 ⊤ 𝜈 𝜈 ⊤ −𝜈 (𝑥 ) 𝐻𝜈 𝑥 + (𝑥 ) 𝐺 𝜈,−𝜈 𝑥 + (𝑥 𝜈 )⊤ 𝐷𝜈,𝜔 𝑦 + (𝑞 𝜈 )⊤ 𝑥 𝜈 2 𝜔=1,2 𝐴𝜈 𝑥 𝜈 ≤ 𝑏 𝜈 , 𝑥 𝜈 ≥ 0 𝐺 𝜈,−𝜈 の例：𝜈 = 1 のとき，𝐺 𝜈,−𝜈 = 𝐺1,2 36 A. Hori and M. Fukushima, Gauss–Seidel method for multi-leader–follower games, J. Optim. Theory Appl., 180, 651–670, 2019. 3 / 16

Appendix：数値実験：問題設定（フォロワー） フォロワー 𝜔 ∈ {1, 2} の最適化問題 min 𝑦 𝜔 ∈R2 s.t. Õ 1 𝜔 ⊤ 𝜔 𝜔 ⊤ −𝜔 (𝑦 ) 𝑀 𝜔 𝑦 + (𝑦 ) 𝑄 𝜔,−𝜔 𝑦 − (𝑥 𝜈 )⊤ 𝐷𝜈,𝜔 𝑦 𝜔 2 (𝑐 𝜔 )⊤ 𝑦 𝜔 + Õ 𝜈=1,2 (𝑑 𝜈 )⊤ 𝑥 𝜈 + 𝑎 𝜔 ≥ 0, 𝑦 𝜔 ≥ 0 𝜈=1,2 ただし， 𝑀 𝜔 ∈ R2×2 （ 𝜔 = 1, 2）は正定値対称行列 仮定：任意の 𝑥 ∈ 𝑋 に対して，フォロワーのナッシュ均衡 𝑦(𝑥) が一意となるために  𝑀1 𝑄 1,2 𝑄2,1 𝑀2  は正定値とする 4 / 16

Appendix：数値実験概要 概要 数値例はプレプリント [Hori et al. (2023)]37 FB 関数の正則化パラメータ 𝜀𝑘 = 0.9 𝑘 (𝑘 = 0, 1, . . . , 75） （ 𝜀0 = 1， 𝜀75 = 0.00037） 各 𝑘 （ 𝑘 = 1, . . . , 75）について停留均衡点を求める 初期点： 𝑥 0 := (1, 1, 1, 1)（ 𝑦 0 は 𝑥 0 に依存して一意に決まるので不要） Semismooth Newton 法 [Qi and Sun (1993)]38 を用いて解いた 37 A. Hori, D. Tsuyuguchi, and E.H. Fukuda, A method for multi-leader-multi-follower games by smoothing the followers’ response function, arXiv:2311.18601. 38 L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Program 58, 353–367, 1993. 5 / 16

Appendix：実験結果：リーダーの戦略 Leader 1's strategy 0.7 Leader 2's strategy 1.0 x11 x21 0.6 0.8 x 2 value x 1 value 0.5 0.4 0.6 x12 x22 0.4 0.3 0.2 0.2 0.0 10−3 10−2 ε 10−1 図 15: リーダー 1 の戦略 𝑥 1𝜀𝑘 100 10−3 10−2 ε 10−1 100 図 16: リーダー 2 の戦略 𝑥 2𝜀𝑘 6 / 16

Appendix：実験結果：フォロワーの戦略 Follwer 1's strategy 0.4 Follwer 2's strategy y11 y21 1.2 1.0 y value y value 0.3 y12 y22 0.2 0.1 0.8 0.6 0.0 10−3 10−2 ε 10−1 100 図 17: フォロワー 1 の戦略 𝑦 𝜀1𝑘 (𝑥 𝑘 ) 10−3 10−2 ε 10−1 100 図 18: フォロワー 1 の戦略 𝑦 𝜀2𝑘 (𝑥 𝑘 ) 7 / 16

Appendix：数値実験のモデルにおける NCP への変形 NEP(𝑋 , {Θ𝜖1 , Θ𝜖2 }) の停留均衡解は以下の相補性問題に帰着できる：  0≤ 𝐻1 𝑥 1 + 𝐺1,2 𝑥 2 + 𝐷1 𝑦 𝜖 (𝑥 1 , 𝑥 2 ) 𝐻2 𝑥 2 + 𝐺2,1 𝑥 1 + 𝐷2 𝑦 𝜖 (𝑥 1 , 𝑥 2 ) 0≤   +  1 𝐴⊤ 1𝜇 2 𝐴⊤ 2𝜇 𝑏 1 − 𝐴1 𝑥 1 𝑏 2 − 𝐴2 𝑥 2   ⊥   ⊥ 𝑥1 𝑥2 𝜇1 𝜇2  ≥0  ≥0 相補性関数（Fischer 関数）を利用して非平滑方程式に帰着できる（詳細は略）： 𝑇(𝑤) = 0, 𝑤 := (𝑥, 𝜇) 各ステップで 𝑇(𝑤 𝑘 ) の Bouligand 劣微分 𝐻 𝑘 ∈ 𝜕𝐵 𝑇(𝑤 𝑘 ) を求め，ニュートン方向を 計算する 8 / 16

Appendix: Ex post ナッシュ均衡と TSDRNE I 参考：Ex post ナッシュ均衡 [Chen et al. (2019)] def. 点 (𝑥 ∗ , 𝑦 ∗ (·)) が ex post ナッシュ均衡 ⇐⇒ ∀𝜈 ∈ {1, . . . , 𝑁 },      𝑥 ∗,𝜈 ∈ argmax 𝑥 𝜈 ∈𝑋 𝜈 𝜃 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 ) + E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 , 𝜉)] ∀𝑃 ∈ P 𝜈 𝑦 ∗,𝜈 (ξ) ∈ argmax 𝛾 𝜈 (𝑦 𝜈 (ξ), 𝑦 ∗,−𝜈 (ξ), 𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 , ξ) ∀ξ ∈ Ξ    𝑦 𝜈 (ξ)∈𝑌 𝜈 (𝑥 ∗,𝜈 ,ξ)  ただし，P B P 1 × · · · × P 𝑁 とする． 9 / 16

Appendix: Ex post ナッシュ均衡と TSDRNE II 定義（２段階分布的ロバストナッシュ均衡） def. 点 (𝑥 ∗ , 𝑦 ∗ (·)) が２段階分布的ロバストナッシュ均衡 ⇐⇒ ∀𝜈 ∈ {1, . . . , 𝑁 },      𝑥 ∗,𝜈 ∈ argmax 𝑥 𝜈 ∈𝑋 𝜈 𝜃 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 ) + inf 𝜈 E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝑥 ∗,−𝜈 , 𝜉)] 𝑃∈P 𝑦 ∗,𝜈 (ξ) ∈ argmax 𝛾 𝜈 (𝑦 𝜈 (ξ), 𝑦 ∗,−𝜈 (ξ), 𝑥 ∗,𝜈 , 𝑥 ∗,−𝜈 , ξ) ∀ξ ∈ Ξ    𝑦 𝜈 (ξ)∈𝑌 𝜈 (𝑥 ∗,𝜈 ,ξ)  「Ex post ナッシュ均衡 =⇒ 2 段階分布的ロバストナッシュ均衡」は成り立つが， 逆は必ずしも成り立たない    分布不確実性集合 P 𝜈 が大きいとき，ex post 均衡は一般に存在しない  10 / 16

Appendix: 2 段階分布的ロバスト確率変分不等式 クールノー競争の均衡条件（2 段階分布的ロバスト確率変分不等式） 𝑥 ∗ , 𝑦 ∗ (·) が均衡解 ⇐⇒ 以下の 2 段階分布的ロバスト確率変分不等式の解 0 ≤ 𝑥 ∗ ⊥ 𝐴𝑥 ∗ − E𝑃 ∗ [𝜆∗ (𝜉)] + 𝑏 ≥ 0, 0 ≤ 𝑦 ∗ (ξ) ⊥ Π(ξ)𝑦 ∗ (ξ) + 𝜆∗ (ξ) + 𝑟(ξ) ≥ 0 ∀ξ ∈ Ξ, (1) 0 ≤ 𝜆∗ (ξ) ⊥ 𝑥 ∗ − 𝑦 ∗ (ξ) ≥ 0 ∀ξ ∈ Ξ, 𝑃 ∗,𝜈 ∈ argmin E𝑃 [𝑄 𝜈 (𝑥 𝜈 , 𝜉)], 𝑃∈P 𝜈 𝜈 = 1, 2. (2) ただし， 𝐴 B diag(𝑎 1 , 𝑎 2 ), 𝑏 B (𝑏1 , 𝑏 2 )⊤ , Π(ξ) B diag(𝜂1 (ξ), 𝜂2 (ξ)) + 𝛽(ξ)(𝐼 + 11⊤ ) 1 B (1, 1)⊤ ∈ R2 , 𝑟(ξ) B (𝑟1 (ξ), 𝑟2 (ξ)), 𝑟𝜈 (ξ) B 𝜁 𝜈 (ξ) − 𝛼(ξ), 𝜈 = 1, 2. 11 / 16

Appendix: 数値解法 Input: (𝑥 0 , 𝑦 0 (ξ1 ), . . . , 𝑦 0 (ξ𝐾 ), 𝜆0 (ξ1 ), . . . , 𝜆0 (ξ𝐾 )). Output: (𝑥 ∗ , 𝑦 ∗ (ξ1 ), . . . , 𝑦 ∗ (ξ𝐾 ), 𝜆∗ (ξ1 ), . . . , 𝜆∗ (ξ𝐾 )) 1: （初期化）ℓ = 0, 𝑥 ℓ = 𝑥 0 , 𝑦 ℓ (ξ 𝑘 ) = 𝑦 0 (ξ 𝑘 ), 𝜆ℓ (ξ 𝑘 ) = 𝜆0 (ξ 𝑘 ) ∀𝑘 = 1, . . . , 𝐾 2: それぞれの 𝜈 に対して，以下の最小化問題を解き，最悪の分布を求める： 𝑃 𝜈,ℓ +1 ∈ argmin E𝑃 [𝑝(𝑞ℓ (𝜉), 𝜉)𝑦 𝜈,ℓ (𝜉) − 𝐻𝜈 (𝑦 𝜈,ℓ (𝜉), 𝜉)] 𝑃∈P 𝜈 3: 点 (𝑥 𝜈 , 𝑦 𝜈 (ξ1 ), . . . , 𝑦 𝜈 (ξ𝐾 ), 𝜆𝜈 (ξ1 ), . . . , 𝜆𝜈 (ξ𝐾 )) と 𝑃 ℓ +1 が近似的に前頁の (1) と (2) を満たすなら終了． 4: 確率分布を 𝑃 𝜈+1 に固定し， 2 段階確率変分不等式 (1) を PHA [Rockafellar & Sun (2019)] （次頁）で解く． 5: ℓ = ℓ + 1 に更新し，ステップ 2 に戻る． 12 / 16

Appendix: Progressive Hedging Algorithm 所与の確率分布に対して，多段階確率変分不等式を解くための手法 メカニズムは交互方向乗数法（ADMM）に近い ʞʞ ʞʞ ʞʞ 図 19: PHA のイメージ：シナリオの分解と集約を繰り返しながら多段階 SVI を解く 13 / 16

Appendix: Progressive Hedging Algorithm I シナリオ分解：第一段階の均衡条件を 𝐾 シナリオに分解 アルゴリズムの概観 アルゴリズムの反復回数を ℓ とすると，すべての ξ 𝑘 ∈ {ξ1 , . . . , ξ𝐾 } に対して，以下の 変分不等式を解く． 0 ≤ 𝑥(ξ 𝑘 ) ⊥ 𝐴𝑥(ξ 𝑘 ) − 𝜆(ξ 𝑘 ) + 𝑏 + 𝑤ℓ (ξ 𝑘 ) + 𝜎(𝑥(ξ 𝑘 ) − 𝑥ℓ (ξ 𝑘 )) ≥ 0 0 ≤ 𝑦(ξ 𝑘 ) ⊥ Π(ξ 𝑘 )𝑦(ξ 𝑘 ) + 𝜆(ξ 𝑘 ) + 𝑟(ξ 𝑘 ) + 𝜎(𝑦(ξ 𝑘 ) − 𝑦ℓ (ξ 𝑘 )) ≥ 0 0 ≤ 𝜆(ξ 𝑘 ) ⊥ 𝑥(ξ 𝑘 ) − 𝑦(ξ 𝑘 ) + 𝜎(𝜆(ξ 𝑘 ) − 𝜆ℓ (ξ 𝑘 )) ≥ 0 𝑤ℓ (ξ 𝑘 )：制約「 𝑥(ξ 𝑘 ) = 𝑥 ∀ξ 𝑘 ∈ {ξ1 , . . . , ξ𝐾 }」に対する Lagrange 乗数 𝜎(𝑧(𝜉) − 𝑧ℓ (𝜉))：近接項 14 / 16

Appendix: Progressive Hedging Algorithm II シナリオ集約 ▶ 第一段階の変数は固定した確率ベクトルを用いた期待値で更新する 𝑥 𝜈,ℓ +1 := 𝑥¯ 𝜈,ℓ +1 𝐾 Õ = 𝑘=1 𝑃𝑘𝜈,ℓ +1 · 𝑥ˆ 𝜈,ℓ +1 (ξ 𝑘 ) ▶ 「𝑥(ξ 𝑘 ) = 𝑥 ∀ξ 𝑘 ∈ {ξ1 , . . . , ξ𝐾 }」に対する Lagrange 乗数 𝑤ℓ (ξ 𝑘 ) の更新は以下の 通りである： 𝑤ℓ +1 (ξ 𝑘 ) := 𝑤ℓ (ξ 𝑘 ) + 𝜎( 𝑥ˆ 𝜈,ℓ (ξ 𝑘 ) − 𝑥¯ 𝜈,ℓ +1 ) 15 / 16

実験結果 I′：確率分布の摂動に対する期待利得の変化（摂動分析） 均衡解を 𝑥 ∗ , 𝑦 ∗ (ξ 𝑘 ) (𝑘 = 1, . . . , 60) とする プレイヤー 𝜈 について，確率分布 𝑃 ∗,𝜈 の下での期待利得 E𝑃 ∗,𝜈 [𝑄 𝜈 (𝑥 ∗,𝜈 , 𝜉)] = ⟨𝑃 ∗,𝜈 , 𝑄 𝜈 (𝑥 ∗,𝜈 , ·)⟩ を確率ベクトルについて方向微分の絶対値の最大値を求めることで，𝑃 ∗,𝜈 ∈ Δ から わずかに分布を摂動したときの期待利得の最大の増減幅を見ることができる： max |⟨𝛿, 𝑄 𝜈 (𝑥 ∗,𝜈 , ·)⟩| s.t. ∥𝛿∥ = 1 𝛿 1⊤ 𝛿 = 0 ※ 1⊤ 𝛿 = 0：摂動後の分布も 𝑃 ∗,𝜈 + 𝛿 = 1 でなければならない 16 / 16