提案手法

c オペレーションズ・リサーチ

■学生論文賞受賞論文 要約■

Gauss–Seidel method for multi-leader-follower games

堀 篤史

南山大学大学院理工学研究科システム数理専攻（現：三菱電機株式会社）

指導教員：福島雅夫 南山大学 教授

1.

序論

マルチリーダー・フォロワー(multi-L/F)ゲームは，

一部の複数プレイヤー（リーダー）にイニシアチブが あり，残りのプレイヤー（フォロワー）が彼らを追従 するように戦略を決定するような階層型非協力ゲーム である．その応用に，規制緩和された電力市場や通信 市場などがある．

本研究では，multi-L/Fゲームを均衡制約をもつ均

衡問題(EPEC)と呼ばれる問題に再定式化することに

より，元の問題がもつ数値的取り扱いにくさを解消す るGauss–Seidel法を基盤とした2段階アルゴリズム を提案する．また，提案したアルゴリズムにおいて，強 停留均衡点と呼ばれる解への収束性を証明し，数値実 験によって有効性を確認した．

2. Multi-L/F

ゲームと

EPEC

本節では，本研究で扱うmutli-L/Fゲームの問題設 定とEPECへの再定式化を述べ，停留均衡の概念を述 べる．

N 人のリーダーと1人のフォロワーによるmulti- L/F ゲ ー ム を 考 え る ．リ ー ダ ー の ラ ベ ル を ν(=

1, . . . , N)とし，リーダーνの戦略をx^ν∈ ^nνとする．

また，それぞれのリーダーは費用関数θ^ν:^n+m→ と制約関数g^ν:^nν → ^rν,h^ν:^nν → ^sν が与え られているものとし，どれもC²級とする．フォロワー はy∈ ^mと戦略とし，費用関数γ:^n+m → と 制約関数u:^n+m→ ^pが与えられているものとし，

どれもC³ 級とする．ここで，n := n1+· · ·+nN

とする．リーダー ν は与えられた戦略の組x^−ν :=

(x¹, . . . , x^ν−1, x^ν+1, . . . , x^N)∈ ^n−nν とy∈ ^mに 対して，次の最適化問題を解く．

x^νmin∈^nν θ^ν(x^ν, x^−ν, y)

s.t. g^ν(x^ν)≤0, h^ν(x^ν) = 0

(1)

一 方 ，フ ォ ロ ワ ー は 与 え ら れ た 戦 略 の 組 x :=

(x¹, . . . , x^N)∈ ⁿに対して，次の最適化問題を解く．

y∈min^mγ(x, y) s.t.u(x, y)≤0 (2) ここで，フォロワーの問題(2)は任意に与えられた x∈ ⁿに対して，凸最適化問題と仮定すると，KKT 条件は問題(2)に対する必要十分条件となり，以下の 混合相補性問題として等価に扱うことができる．

ψ(x, y, z, λ) : =

⎡

⎣ ∇yγ(x, y) +∇yu(x, y)λ u(x, y) +z

⎤

⎦

= 0 (3)

0≤z⊥λ≥0 (4)

ただし，λ∈ ^pをLagrange乗数とし，z∈ ^pを不等

式制約u(x, y)≤0に対するスラック変数とする．方

程式系(3), (4)を問題(1)の制約条件に取り込むこと で，リーダーνの問題は以下のようなx^−νをパラメー タとする相補性制約をもつ数理計画問題(PMPCC)と して再定式化される．

PMPCC^ν(x^−ν) : min

x^ν,y,z,λ θ^ν(x^ν, x^−ν, y)

s.t. g^ν(x^ν)≤0, h^ν(x^ν) = 0 ψ(x^ν, x^−ν, y, z, λ) = 0 0≤z⊥λ≥0

問題の組(PMPCC^ν(x^−ν))^N_ν=1の均衡解を見つける 問題は均衡制約をもつ均衡問題(EPEC)と呼ばれる．

変数(y, z, λ)はすべてのリーダーが共通にもつ決定変 数のため，共有変数と呼ぶことにする．

一般に，EPECは均衡解が存在する保証がないうえ，

均衡解かどうかを確かめることは困難なため，本研究 では均衡解の拡張概念である停留均衡解の求解を目標 とする．なかでも，強い性質をもつ強停留均衡解を以 下に定義する．

定義. 戦略の組(x^∗, y^∗, z^∗, λ^∗)がEPEC（もしくは multi-L/Fゲームの）強停留均衡点であるとは，それぞ れのリーダーνに対して，解(x^ν,∗, y^∗, z^∗, λ^∗)が問題 PMPCC^ν(x^−ν,∗)の強停留点[1]となることである．

722（60）^Copyrightcby ORSJ. Unauthorized reproduction of this article is prohibited. オペレーションズ・リサーチ

3.

提案手法

本節では，EPECを解くためのアルゴリズムを提案 し，multi-L/Fの停留均衡を求める手法を二段階に分 けて紹介する．

3.1 Phase I: Gauss–Seidel型ペナルティ法 準備として，問題の変換を行う．まず，相補性条件 0 ≤ z ⊥ λ ≥ 0 はFischer–Burmeister (FB)関 数φ(a, b) := a+b−√

a²+b² によって，等価な 等式制約として表せる．これにより，リーダーνの PMPCC^ν(x^−ν)は次のように書き換えられる．

P^ν(x^−ν) : min

x^ν,y,z,λ θ^ν(x^ν, x^−ν, y)

s.t. g^ν(x^ν)≤0, h^ν(x^ν) = 0 Ψ(x⎡^ν, x^−ν, y, z, λ) :=

⎣ ψ(x^ν, x^−ν, y, z, λ) (φ(z_i, λ_i))^p_i=1

⎤

⎦= 0

しかし，FB関数が微分可能ではないため，P^ν(x^−ν) は数値的に取り扱いにくい．これを避けるために，二 乗FB関数が連続的微分可能である性質を利用する．

問題P^ν(x^−ν)に対する緩和問題を次のように定める．

P^ν_ρ(x^−ν) : min

x^ν,y,z,λ

θ¯^ν_ρ(x^ν, x^−ν, y, z, λ) ただし，

θ¯_ρ^ν(x^ν, x^−ν, y, z, λ) :=θ^ν(x^ν, x^−ν, y)+ρ 2

_rν

i=1

[g^ν_i(x^ν)]²₊ +

sν

i=1

|h^ν_i(x^ν)|² +

m+2p

j=1

|Ψ_j(x^ν, x^−ν, y, z, λ)|²

とし，ρ >0はペナルティパラメータである．また，

[g^ν_i(x^ν)]₊ := max{0, g^ν_i(x^ν)}とする．この問題の目 的関数は微分可能である．

アルゴリズムの概要を説明する．k= 0,1,2, . . .をス テップ数とする．各リーダーは緩和問題P^ν_ρk(x^−ν,(k)) を順に解き，適当な終了条件が満たされればアルゴリ ズムを終了し，そうでなければペナルティパラメータ を更新して再びν= 1からNまで順に解く．このア ルゴリズムに関して以下の結果を得た．

定理. ρ_k→ ∞とする．さらに，各リーダーνとス テップkに対してP^ν_ρk(x^−ν,(k))の解は局所最適解と 仮定する．また，解の点列に極限が存在し，極限にお いてMPCC一次独立制約想定と上位狭義相補性（文 献[1]を参照）が成り立つと仮定する．このとき，極 限はmulti-L/Fゲームの強停留均衡点である．

3.2 Phase II: Refined Gauss–Seidel法

前節のアルゴリズム(phase I)によって得られる解 の精度は必ずしも高くないが，得られた近似解は相補 性制約における有効制約を同定する意味で有用な情報 となる．w¯^ν,∗= (x^ν,∗, y^ν,∗, z^ν,∗, λ^ν,∗)をphase Iで得 られたリーダーνの近似解¹とする．相補性制約に関 して，次のような有効制約集合を定義する．

I¯^ν:={i| |z¯_i^ν,∗|< δ, |λ¯^ν,∗_i | ≥δ} J¯^ν:={i| |¯z_i^ν,∗|< δ, |¯λ^ν,∗_i |< δ} K¯^ν:={i| |¯z_i^ν,∗| ≥δ, |λ¯^ν,∗_i |< δ}

(5)

ただし，δ >0は十分に小さい数とする．簡単のため，

任意のνに対して，I¯:= ¯I^ν,J¯:= ¯J^ν,K¯:= ¯K^νが成 り立つと仮定する．以下は近似解w^ν,∗付近で定義さ れる 相補性制約を含まない 最適化問題である．

P^ν(x^−ν) : min

x^ν,y,z,λ θ^ν(x^ν, x^−ν, y)

s.t. g^ν(x^ν)≤0, h^ν(x^ν) = 0 ψ(x^ν, x^−ν, y, z, λ) = 0 z_i= 0, λ_i≥0 (i∈I)¯ z_i= 0, λ_i= 0 (i∈J¯) z_i≥0, λ_i= 0 (i∈K)¯ Phase IIでは，それぞれのリーダーがP^ν(x^−ν)を順 に解き，適当な終了条件（収束判定）が満たされれば，

アルゴリズムを終了する．最終的に得られた解におい て，P^ν(x^−ν)のKKT条件がすべてのプレイヤーに対 して成り立てば，強停留均衡点が求まったといえる．

Hu and Fukushima [2]の問題例を用いたところ，強 停留均衡点が見つかったほか，[2]で得られた解よりも 精密な解を得ることに成功した．また，解を更新する 際，逐次過緩和法を用いることで，少ない反復回数で 同程度の精度をもつ近似解を得ることに成功した．

参考文献

[1] H. Scheel and S. Scholtes, “Mathematical programs with complementarity constraints: Stationarity, opti- mality, and sensitivity,” Mathematics of Operations Research,25, pp. 1–22, 2000.

[2] M. Hu and M. Fukushima, “Smoothing approach to Nash equilibrium formulations for a class of equi- librium problems with shared complementarity con- straints,” Computational Optimization and Applica- tions,52, pp. 415–437, 2012.

1 共有変数にラベルνを付すのは，一般に値が各リーダーに よって異なるためである．

2018年11月号 ^Copyrightcby ORSJ. Unauthorized reproduction of this article is prohibited.（61）723