tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

ゲーム理論で警備する:セキュリティゲーム

今年の3月に情報処理学会全国大会というところに行ってきまして、「ゲーム理論やメカニズムデザイン」についての招待講演を聞いてきました。以前からこの分野にはなんとなく関心があったのですが、この話がとても面白かったということもあり、関連する分野を調べたいというモチベーションが湧いてきました。

調べているうちに、人工知能学会の学会誌にちょうど良い解説記事があるのを見つけて、読んでみることにしました。
jsai.ixsq.nii.ac.jp

上の解説記事の中で、特に興味をもったのが セキュリティゲーム という研究です。セキュリティゲームは、ゲーム理論の知見を実際の警備システムに応用するという研究です。勉強がてらブログ記事にまとめてみようと思います。

セキュリティゲームとは?

テロのターゲットになることの多い空港などの公共施設では、十分な警備対策が必要とされています。日本だと比較的安全なのであまり実感がないかもしれませんが、アメリカでは日頃からテロの危機に備えて、強面のお兄さん方が日々警備しているのだそうです。

たとえば、この論文のFigure 1とかをご覧ください。
An Overview of Recent Application Trends at the AAMAS Conference: Security, Sustainability and Safety | AI Magazine


さてここで、空港を守る警備側と、空港の特定の場所(ターゲット)を攻撃する攻撃側の戦略を考えてみましょう。

f:id:tsujimotter:20190418190441p:plain:w360

まず警備側ですが、警備には人手がかかります。365日いつ襲われるかわからない空港において、狙われるすべてのターゲットを24時間警備し続けることができるほど、人員が確保できるとは限りません。そこで、ある程度効率的に警備する方法を考える必要があります。

たとえば、空港で警備すべきターゲットが5箇所あったとしましょう。このとき、配置できる警備員の人数を2名とします(もちろんこんなに人員が少ないわけないので、これはあくまで例として、です)。当然、2名で5箇所を警備することはできないので、大事そうなターゲットを2箇所警備してもらうことにします。

f:id:tsujimotter:20190418190521p:plain:w360

ここで攻撃側の視点に立ちましょう。警備している人の配置を確認すれば(あるいは事前に警備計画を傍受することができれば)、警備員のいないターゲットを探すことは容易にできてしまいます。そして当然、警備員のいないターゲットが攻撃されてしまうでしょう。

f:id:tsujimotter:20190418190546p:plain:w360

警備問題の難しいところは、警備側は攻撃側がどのような戦略をとるかわからないまま警備計画を立てる一方、攻撃側はその警備計画を見た上で最適な攻撃を実行できるという点です。警備側と攻撃側で、情報の非対称性があるわけです。


そこで警備側の戦略として、警備箇所を毎回ランダムで決定するという方法が考えられます。1時間ごとに5箇所の中から2箇所をランダムで決定して、警備員に通知する。攻撃側は、どこに警備員が配置されるか知ることはできません。警備員でさえも直前まで配置を知らされませんので、情報が漏れる心配もありません。こういう発想ができる人は頭がいいですね。

f:id:tsujimotter:20190418190641p:plain:w360

もちろんこの方法も完璧ではなく、もし完全に一様な確率で警備すると仮定した場合、攻撃側は(捕まるリスクがあることを承知で)どこかのターゲットに攻撃を加えます。すると、確率3/5で攻撃が成功してしまうわけです。どうせ同じ確率で捕まるなら、一番お得なターゲットに攻撃を加えたほうがいいわけですから、一番損害の出る箇所が狙われることになります。これでは、警備側は困ってしまいますね。

そこで、攻撃されたときの損害の程度を加味して、警備員を振り分ける確率を設定します。これが警備側の戦略です。攻撃側は、警備側の戦略(すなわち、警備員を振り分ける確率)を知った上で、どのターゲットを攻撃するか決定します。これが攻撃側の戦略です。

攻撃側が警備側の戦略に対して最適に反応すると仮定した上で、警備側の損害の期待値を最小化する警備側の戦略を求める問題が、今回紹介したい セキュリティゲーム というわけです。


このような警備計画は実際にアメリカの空港で使われているそうです。ARMOR(2008年)というシステムは、ロサンゼルス国際空港(LAX)で連邦航空保安局の警備計画に用いられています。IRIS(2009年)というシステムは国際貨物輸送において、PROTECT(2011年)はアメリカ沿岸警備隊における警備計画の策定に用いられているそうです。アメリカ国土安全保障省の運輸保安庁などのさまざまな警備主体が使えるようにするために設計されたGUARDS(2011年)というシステムもあるそうです。

セキュリティゲームの論文は、マルチエージェントシステムに関する分野でトップカンファレンスと称される国際会議 AAMAS にて2012年の最優秀論文賞(Baconらの論文)になり、その後たくさんの関連研究が投稿されるようになるなど、非常に注目を集めた研究とのことです。

この分野の研究者の感覚としては、AAMASに通るだけでもすごいなという印象です。その中で、最優秀論文賞ということは、相当すごいなという感じです(ふわっとした感想)。というわけで、俄然興味が湧いてきます。

シュタッケルベルクゲーム

セキュリティゲームは、実はゲーム理論において古くから研究されてきた「シュタッケルベルクゲーム」にそっくりな問題です。実際、セキュリティゲームはシュタッケルベルクセキュリティゲームと呼ばれることもあります。古くから考えられてきたゲーム理論の問題設定が、実際のセキュリティの研究に応用できたということもあって、セキュリティゲームが注目を集めたとも言われています。

そこで、まず シュタッケルベルクゲームについて紹介しましょう。 シュタッケルベルクゲームは経済学における基本的な問題ですが、(私を含め)経済学にあまり関心がない読者を想定して、その手の説明は簡単に済ませたいと思います。

シュタッケルベルクゲームにおいて、プレーヤーは2人。一人がリーダー、もう一人はフォロワーです*1。この2人は、どちらも同じ市場において似たような商品を販売している(少なくとも消費者目線では同じに見える)ライバル企業です。イメージとしては、リーダーは既に市場に参入している企業で、フォロワーは後追いでその市場に参入する企業といったところでしょうか。

どちらのプレーヤーも、商品の生産量という戦略を決定します。戦略の集合をそれぞれ  X_1, X_2 としましょう。商品の価格は、市場の原理により  x_1 \in X_1, x_2 \in X_2 から決定されます。すると、それに合わせて各プレーヤーの利得が決定されます  u_1(x_1, x_2), \; u_2(x_1, x_2) *2

さて、ここで情報の非対称性を導入します。リーダーの方は自分の情報だけで  x_1 を決めますが、フォロワーの方はリーダーの戦略を見つつ自分の戦略を決定することができます。つまり、フォロワーはリーダーの戦略  x_1 が与えられた状況で  u_2(x_1, x_2) を最大化する戦略を決めます。

 \newcommand{\argmax}{\mathop{\rm arg~max}\limits} R(x_1) = \argmax_{x_2\in X_2} u_2(x_1, x_2)

このような戦略  R(x_1) x_1 に対する最適反応戦略といいます。リーダーとフォロワーという名前の意味がわかりますね。

リーダーは、フォロワーが最適反応戦略を出すという前提のもとで、自己の利益を最大化させる戦略を決定します。つまり、こういうことです。

 x_1^* = \argmax_{x_1 \in X_1} u_1(x_1, R(x_1))

このときの戦略の組  (x_1^*, \; R(x_1^*) ) に対応する利得の組

 (u_1(x_1^*, \; R(x_1^*) ), \; u_2(x_1^*, \; R(x_1^*) ) )

強シュタッケルベルク均衡 といいます。


セキュリティゲームは、警備側をリーダー、攻撃側をフォロワーとするシュタッケルベルクゲームとなっています。

セキュリティゲームの定式化

それでは、セキュリティゲームを具体的に定式化していきましょう。今回は、IRISで使用されているERASERアルゴリズム(2009年)と同じ設定で説明したいと思います。

まず、ターゲットが攻撃を受けたときの警備側・攻撃側の利得を定めましょう。

攻撃を受けたときに、もし該当のターゲットが警備されていたとします。そのときは、攻撃者を逮捕できるので警備側の利得は  5、攻撃側の利得は  -20 とします。該当のターゲットが警備されていなかった場合、攻撃者は無条件で攻撃できてしまうので、警備側の利得は  -20、攻撃側の利得は  30 とします。まとめると以下のようになります。

警備されている警備されていない
警備側の利得 5 -20
攻撃側の利得 -20 30


ターゲットの集合を  T とし、警備側がターゲット  t \in T を警備する確率を  c_t とします。この確率の組  C = (c_t)_{t\in T} を警備ベクトルといい、警備側の戦略とします。ここで、すべての  t \in T に対して  c_t

 0 \leq c_t \leq 1 \;\; \;\; \forall t \in T \tag{1}

を満たすとします。ここで注意したいのは、 c_t は「 t を警備するかどうかを表す確率」だということです。それぞれの  t \in T ごとに確率  c_t のサイコロにしたがって警備するかどうか決めるというわけです。そのため、 c_t をすべての  t \in T で足して1になる必要はありません。

ここで、警備側の人員のリソースを考慮しましょう。 m を警備側の割けるリソースの量とします。 m = 3 だったら警備員3人みたいなイメージですね。ただし、1単位のリソースを必ずしも1人に設定する必要はありません。警備員が2人で1組で行動するのであれば、2人で1単位としてもいいのです。このようなリソースを考慮するためには、以下の式が成り立っていればよいでしょう:

 \displaystyle \sum_{t\in T} c_t \leq m \tag{2}

確率  c_t を考慮して、全体で  m 以下のリソースがターゲット全体に割り当てられるという条件になっています。


次に、攻撃側を考えましょう。攻撃側は、どのターゲットを攻撃するか1つ選択するというのが戦略です。ターゲット  t \in T を攻撃するとき  a_t = 1、攻撃しないとき  a_t = 0 とします。すなわち、次が成り立つ必要があります:

 a_t \in \{0, 1\} \;\;\;\; \forall t \in T  \tag{3}

この  a_t を並べたベクトル  A = (a_t)_{t\in T} を攻撃ベクトルといいます。これが攻撃側の戦略です。

今は、攻撃側は1組しかおらず、1箇所しか攻撃できないと仮定します。すると、以下の式が成り立つ必要があります:

 \displaystyle \sum_{t\in T} a_t = 1 \tag{4}


次に警備側と攻撃側の期待利得を定義します。

警備側が戦略  C = (c_t)_{t\in T} で警備しているとき、攻撃側がターゲット  t を攻撃したときの、警備側の期待利得を  U_D(C, t)、攻撃側の期待利得を  U_A(C, t) とします。これは、上に書いた利得表を元に次のように計算されます:

 \begin{align} U_D(C, t) &= 5 c_t - 20 (1-c_t) \\ U_A(C, t) &= -20 c_t + 30 (1-c_t) \end{align} \tag{5}


さらに、攻撃ベクトル  A = (a_t)_{t\in T} が与えられたときの警備側の期待利得を  d(C, A)、攻撃側の期待利得を  k(C, A) とします。するとこれらは次で計算できるでしょう:

 \begin{align} d(C, A) &= \sum_{t\in T} a_t U_D(C, t) \\ k(C, A) &= \sum_{t\in T} a_t U_A(C, t) \end{align} \tag{6}


さて、ここでシュタッケルベルクゲームに話を乗せるための準備は整いました。警備側(リーダー)は警備ベクトル  C を決定します。これに対して、攻撃側(フォロワー)は  C に対する最適応答戦略となるような攻撃ベクトル  A(C) を決定します。つまり、 k(C, A) を最大化させる戦略  A = A(C) を決定するということです。

攻撃側が  C に対する最適応答戦略  A(C) を選択するという前提のもとで、警備側は自己の期待利得  d(C, A(C)) を最大化させる戦略  C = C^* を求めるというのは、まさにシュタッケルベルクゲームの問題設定でした。 (C^*, A(C^*) ) の組が均衡点です。


ここでセキュリティゲームの説明を終えてもいいのですが、このままでは均衡点を計算する具体的なアルゴリズムが与えられていません。ERASERでは、上記の問題を混合整数線形計画問題に帰着させることで、具体的な計算手段を得ることに成功しています。もう少しだけ考えを進めてみましょう。

まず、次の条件  (7) を考えます。

 0 \leq k(C, A) - U_A(C, t) \leq (1-a_t)\cdot Z \;\;\;\; \forall t \in T \tag{7}

ここで  Z は警備側および攻撃側のそれぞれの利得の最大値と比べて十分大きな値とします。 \forall t \in T としていますので、 T の個数分だけ式があると思ってください。

この式の意味するところを考えていきましょう。 k(C, A) は現在の戦略の組  (C, A) に対する攻撃側の利得で、 U_A(C, t) t を攻撃したときの攻撃側の利得です。

まず左側の不等式

 0 \leq k(C, A) - U_A(C, t)

を考えましょう。これは、 k(C, A) \geq U_A(C, t) ですから「現在選んでいる  A の方が、 t 単体を攻撃する以上の利得を得られますよ」という条件を表しています。イコールがついているので、等しい場合もあります。

次に右側の不等式

 k(C, A) - U_A(C, t) \leq (1-a_t)\cdot Z

を考えます。これはややこしいので場合分けして考えます。

 \begin{cases} k(C, A) - U_A(C, t) \leq Z & (a_t = 0) \\ 
k(C, A) - U_A(C, t) \leq 0 & (a_t = 1) \end{cases}

2番目の条件は  \leq 0 となっていますが、左側の不等式も  0\leq だったので、 = 0 ということです。すなわち、 k(C, A) = U_A(C, t) です。つまり、 a_t = 1 であれば( t を攻撃するのであれば)攻撃側の利得は  U_A(C, t) と等しい。つまり、これは「攻撃側は  t を単体で攻撃する」という条件になっているでしょう。1番目の条件は  Z を十分大きくとっているので、不等式は常に満たされます。*3

以上から、式  (7) は「攻撃側が単体を攻撃するという条件のもとで最適な  A を選んでいる」ことを表す条件といえますね。面白いのは「 \max k(C, A) となる  A を選ぶ」という条件を、不等式で言い換えることができるという点です。


同様に、今度は警備側の利得に関する条件  (8) を考えましょう:

 d(C, A) - U_D(C, t) \leq (1-a_t)\cdot Z \;\;\;\; \forall t \in T \tag{8}

この式も  \forall t \in T とあることから、 T の個数分だけ式があると思ってください。

これも  a_t の値によって場合分けすると

 \begin{cases} d(C, A) - U_D(C, t) \leq Z & (a_t = 0) \\ 
d(C, A) - U_D(C, t) \leq 0 & (a_t = 1) \end{cases}

となります。二つ目の式は、 d(C, A) \leq U_D(C, t) ということですが、 a_t = 1 のときは「 t を単体で攻撃したときより、現在の攻撃ベクトル  A で攻撃した方が、警備側の利得が下がる」といっています。あぁ、これは攻撃側が警備側の利得を最小化させるという制約条件を述べているんですね。


というわけで、以上で制約条件の説明は終わりです。 (1) から  (8) を満たすべき制約条件として  d(C, A) を最大化する  (C, A) を求めよというのが、セキュリティゲームにおいて解くべき最適化問題となります。まとめると

 \begin{array} \mbox{maximize} & d(C, A) & \\
\mbox{subject to} &  C = (c_t)_{t\in T},\; A = (a_t)_{t\in T}, & \\
& 0 \leq c_t \leq 1 & \forall t \in T, \\
&  a_t \in \{0, 1\} & \forall t \in T, \\
&  \sum_{t\in T} c_t \leq m, & \\
&  \sum_{t\in T} a_t = 1, & \\
&  0 \leq k(C, A) - U_A(C, t) \leq (1-a_t)\cdot Z & \forall t \in T, \\
&  d(C, A) - U_D(C, t) \leq (1-a_t)\cdot Z & \forall t \in T. \end{array}

ということです。この最適化問題を解いて得られた解が、セキュリティゲームにおける均衡点になっているということですね。

この問題は、すべての制約条件が  c_1, \ldots, c_{\# T}, a_1, \ldots, a_{\# T} に対する1次不等式となっています。変数は 0 以上 1 以下の連続変数  c_t と、0, 1 いずれかの変数  a_t の混在しています。したがって「混合整数計画問題」といえるでしょう。

整数計画問題は、線形計画問題と異なり一般にNP困難な問題に該当するため、多項式時間で解くことができるアルゴリズムが存在しません。一方で、いろいろなところで便利なソルバーは公開されていますので、規模が小さければ十分解ける場合もあります。

最適化などの手法を援用して、計算機を用いてゲーム理論における解概念(ナッシュ均衡など)を計算する手法を研究する分野のことを「計算論的ゲーム理論」というそうです。セキュリティゲームを始めとして、この分野も近年特に注目を集めているようです。面白そうですね。

実際に解いてみよう

さて、せっかくセキュリティゲームを定式化したので、試しにサイズの小さな問題で解を見つけてみましょう。

ターゲットの箇所は  5 箇所とし、 T = \{ 1, 2, 3, 4, 5\} とします。警備員の人数を  2 人とし、攻撃側は1箇所のみを攻撃するとします。

最適化のソルバーを使うのが面倒だったので、今回は  c_t の候補を  \{0.0, 0.2, \ldots, 1.0\} と 0.2 毎に限定して、 (C, A) の組を全探索させることにします。

そのような計算を行うRubyのプログラムは、以下のようになります。

# security_game.rb

# 警備箇所のサイズ
T_SIZE = 5

# 警備員の人数
M = 2

# 攻撃者の攻撃箇所の個数
A = 1

# 攻撃側・警備側の利得より十分大きな整数値
Z = 1000

# 制約を満たさないときに返す値
FALSE_VALUE = -10000



# 警備側の利得
def u_table_defense(c)
	if c == 1
		return 5
	else 
		return -20
	end
end

# 攻撃側の利得
def u_table_attack(c)
	if c == 1
		return -10
	else 
		return 30
	end
end



# U_A
def util_defense(c_vec, t)
	return (c_vec[t] * u_table_defense(1) +  (1 - c_vec[t]) * u_table_defense(0))
end

# U_D
def util_attack(c_vec, t)
	return (c_vec[t] * u_table_attack(1) +  (1 - c_vec[t]) * u_table_attack(0))
end




def d_func(c_vec, a_vec)
	sum = 0
	T_SIZE.times do |t|
		sum += a_vec[t] * util_defense(c_vec, t)
	end
	return sum
end


def k_func(c_vec, a_vec)
	sum = 0
	T_SIZE.times do |t|
		sum += a_vec[t] * util_attack(c_vec, t)
	end
	return sum
end



def main(c_vec, a_vec)
	flag = true

	d = d_func(c_vec, a_vec)
	k = k_func(c_vec, a_vec)

	#puts "m = #{M}"
	#puts "(1) d: #{d}"
	#puts "(   k: #{k} )"
	#puts "(2) c: #{c_vec}"

	c_sum = c_vec.inject(:+)
	#puts "(3) sum of c: #{c_sum} <= #{M}"
	if !(c_sum <= M)
		return FALSE_VALUE
	end

	#puts "(4) a: #{a_vec}"

	a_sum = a_vec.inject(:+)
	#puts "(5) sum of a: #{a_sum} == #{A}"
	if !(a_sum == A)
		return FALSE_VALUE
	end

	#puts "(6):"
	T_SIZE.times do |t|
		#puts "\##{t}: #{d - util_defense(c_vec, t)} <= #{(1 - a_vec[t])*Z}"
		dd = d - util_defense(c_vec, t)
		zz = (1 - a_vec[t])*Z
		if !(dd <= zz)
			return FALSE_VALUE
		end

	end

	#puts "(7):"
	T_SIZE.times do |t|
		#puts "\##{t}: #{0} <= #{k - util_attack(c_vec, t)} <= #{(1 - a_vec[t])*Z}"
		kk = k - util_attack(c_vec, t)
		zz = (1 - a_vec[t])*Z
		if !(0 <= kk && kk <= zz)
			return FALSE_VALUE
		end
	end

	return d
end



#c = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
c = [0.0, 0.2, 0.4, 0.6, 0.8, 1.0]
a = [0, 1]

d_max = FALSE_VALUE

c.product(c, c, c, c).each do |c_vec|
	a.product(a, a, a, a).each do |a_vec|
		d = main(c_vec, a_vec)
		if d_max <= d
			if d_max < d
				# 更新した場合、改行する
				puts ""
			end
			puts "#{c_vec}, #{a_vec}, #{d}"

			d_max = d
		end
	end
end


結果は次の通りでした。

$ ruby security_game.rb
[0.4, 0.4, 0.4, 0.4, 0.4], [0, 0, 0, 0, 1], -10.0
[0.4, 0.4, 0.4, 0.4, 0.4], [0, 0, 0, 1, 0], -10.0
[0.4, 0.4, 0.4, 0.4, 0.4], [0, 0, 1, 0, 0], -10.0
[0.4, 0.4, 0.4, 0.4, 0.4], [0, 1, 0, 0, 0], -10.0
[0.4, 0.4, 0.4, 0.4, 0.4], [1, 0, 0, 0, 0], -10.0

つまり、 C = (0.4, 0.4, 0.4, 0.4, 0.4), \;\;  A =(1, 0, 0, 0, 0), (0, 1, 0, 0, 0), \ldots, (0, 0, 0, 0, 1)  の組が強シュタッケルベルク均衡解ということですね。

図で表すとこんな状況です。

f:id:tsujimotter:20190418191321p:plain:w360

攻撃側はどこか1箇所を攻撃し、警備側はそれに対してすべての箇所を確率  0.4 で警備するという結果です。警備員は  2 人で警備箇所は  5 箇所なので、均等に割り当てると最大  0.4 になりますから、たしかに妥当な結果ですね。

というか、当たり前の結果 ですね。

仮に2箇所を100%で守ったとして、攻撃側には守っていないところを突かれてしまいます。一般に、均等に守っていない場合は、その守っていない箇所が攻撃側の最適応答戦略になりますから、そこを突かれると利得が下がってしまいます。となると、警備側は均等に守るほかないわけです。


というわけで、一生懸命がんばって定式化したのですが、このままの問題設定だと自明な結果しか得られないことがわかりました。

もう少し面白い問題設定にするためには、たとえば警備箇所の利得をターゲット毎に変える方法があるでしょう。そうすれば、警備の割合は自明ではなくなります。

もう一つの面白い設定としては、攻撃者のタイプを複数考えるという方法です。異なるタイプを持ったテロリストがいて、それぞれが異なる利得を持っており、一定の割合でテロリストのタイプが選ばれます。警備側は、潜在的にどのようなタイプのテロリストが、どのような確率で選ばれるかを事前知識として持っていることを仮定します。それらの仮定を元に、最適な警備ベクトルを決定する問題が、ベイジアンシュタッケルベルクゲームです。テロリストのタイプを条件とする条件付き確率によって定式化されます。

というわけで、今後はより拡張された問題設定で考えてみたいですね。

おわりに

今回は「セキュリティゲーム」と呼ばれる計算論的ゲーム理論の一問題について紹介しました。ゲーム理論の応用的な手法が、実際に警備のシステムとして運用されているというのは面白いですね。

普段と異なり整数論ではない話題でしたが、たまにはこういう私の研究分野に近い話もブログに書いていこうかと思います。

それでは今日はこの辺で。

参考ページ

セキュリティゲーム分野において中心的な研究者であるMilind Tambe教授らのグループによるページです。

"publication"のセクションでは、関連する論文のリストが大量にならんでいます。興味を持った人は読んでみてはいかがでしょうか。
teamcore.usc.edu

まだちゃんと見てないですが、Tambe先生の講演動画などもついていて、なかなか楽しそうなページになっています。

*1:Twitterみたいですね

*2:実際、ゲーム理論の教科書で「シュタッケルベルクゲーム」について扱われているときは、この  u_1, u_2 という関数は具体的な関数として定義されることが多いでしょう。しかしながら、今回の記事においては、そのディテールはまったくもって不要なので、あえて抽象化して定義しています。

*3:右側の不等式は「 A は1箇所だけを攻撃する」という程度の条件にしかなっていない気がします。式  (4) で1箇所しか攻撃しない条件はついているので、左側の条件だけでも十分な気もしますが、右側の不等式は何のために必要なんでしょうか。