Prologとゲーム理論 - Simulating Theoretical Models of

2015/10/1
1
Prologとゲーム理論
関東学園大学経済学部
犬童健良
電気学会情報システム部門大会セッション「論理プログラミングの実績と展望」配布資料 2004/9/2 宇都宮大学
内容
目的と動機
今回したこと
代表的なゲーム理論モデル
• 予稿集第２～４節
ゲームの解を計算するアルゴリズム
• 予稿集第５～６節
補遺：ゲームモデリングの認知科学的問題
まとめ
2
お断り
 報告者自身はゲーム理論や数理計画いずれの専
門家ではないことを、まず言っておくべきかと思いま
す。
 本報告は上記分野に言及します。ゲーム理論モデ
リングの論理構造を理解し、応用システムの開発を
将来の目的として、報告者自身が現時点で理解で
きたと思う範囲でお話しいたします。
 内容は時間をかけて検討しておりますが、理解の不
十分、プログラムミス等は報告者の責任です。その
場合、申し訳ございませんが何卒ご寛容の上、ご指
摘、ご教示のほどお願いいたします。
3
研究のねらい
 ゲーム理論的モデリングには選好順序や多面体の幾何な
ど離散的構造が多く用いられる。Ｐｒｏｌｏｇには向いている。
 またゲーム理論はネットワーク理論と並び、初期の組合せ
最適化アルゴリズムが成功を収めた領域でもある。
 そこで古典的なゲーム理論のアルゴリズムをPrologによっ
て実装してみた。
 また掃出し法を手がかりに、ゲーム理論のアルゴリズムと
導出との関連に焦点を当ててみたい。
4
主な目的・動機
意思決定者のモデリング
アルゴリズム理解
理論学習の支援
より詳しく目的と動機を述べると…
5
目的と動機（１）：意思決定者のモデリング．
 意思決定の規範理論
 経済学やオペレーションズリサーチ（OR)分野で開発された。
 連続的領域での（または離散的領域での組合せ）最適化。
 意思決定支援システム（DSS)の基礎でもある。
 整数計画法は論理的推論を含む。
 Prologの潜在的有用性
 手続き型言語と比べて比較的素直に数学的条件を書ける場合がある。
 上の場合、コーディング手間や宣言的理解の面でまさる。
 意外に、表計算では扱いにくいものが多い。
 ゲーム理論への応用
 とくにゲーム理論は、上記をコンポーネントとする統合的モデリング。
 社会文脈におかれた意思決定者の知的推論モデルとかかわる。
 Prologによる実装事例はあまり知られていない。
 エージェントシステムでも初期の研究を除くと、主流ではない。
補足：とはいえ、将来的にはＰｒｏｌｏｇが重要な役割を果たすことになる可能性はある。例えば、ミシガン大のＡＩグループが始めた
International Trading Agent Competition (TAC) では通信系サーバーはＪａｖａだが、マーケットや取引ゲームのサーバープログラムはＰｒｏｌ
6
ｏｇで組まれているそうである。また合理的な決定手続きや、法律などの制度的メカニズムを工学的に扱うための基礎に向くだろう。
目的と動機（2）：アルゴリズム理解．
 ゲーム理論のアルゴリズム
 Gale＆Shapley(1962)の安定結婚アルゴリズムやナッシュ均衡を
計算するLemke＆Howson(1964)による相補掃出しが古典的。
 以降、さまざまなアルゴリズムが開発された。二次計画法(Lemke,
1965) 、ホモトピー法(Wilson, 1992)、代数幾何（Blume and
Zame, 1994)などが基礎になる。
 近年の均衡アルゴリズム（たとえばGovindan&Wilson(2003)）
ではホモトピー法と大域ニュートン法が融合。
 論理プログラミングと最適化の融合
 論理プログラミングと線形計画法を関係付けるJeroslow and
Wang(1989)の定理。
 Benders 分解のような古典的最適化技法とその推論双対性
に基づく、制約プログラミングの改良 (Hooker, 2000)。
 ゲーム理論との接点をPrologによる実装を足がかりに学ぼう。
7
目的と動機（3）：理論学習の支援
 意思決定の理論を動くモデルで学びたい
 ゲーム理論やOR分野は、一定の数学的センスがないと、数式と手
計算だけでハードルを越えるのはむずかしい。
 また、ソルバー（ソフトウェア）の暗箱的利用は、必ずしも、実用や教
育に供さない。認知的に侵入できなくさせる。
 規範理論を使うには納得や信頼が必要
 例えばゲーム理論では、エージェントがなぜ・どのようにその戦略を
予測・決定するのかが重要。
 それゆえ、ただモデリングして後はソルバー（ソフトウェア）を暗箱的
に利用すると考えるのは、納得いく意思決定モデルとはいえない。
 限界合理性の処方箋として
 Prologの活用を試みたい。
 限界合理性についての詳細な検討は、本論の目的を越える。
 時間が許せば、若干補足したい。（ディスカッション）
8
望ましいモデリング技術の条件
望ましいモデリング技術は、たんに最適化
（均衡計算）を実行したり、道具的に何らかの
応用に役に立つことを主張するのでなく、ア
ルゴリズムに内在する論理的思考、あるいは
その有用性に照らした関心を、いわば意思決
定者の認知的必然性として導くよう支援すべ
きだろう。
9
ナッシュ戦略を記述したプログラム
標準形ゲーム＊の例
行（b）：－列（l）．
（同時手番）２の純粋戦略
プレイヤー１（行）
の利得行列
l
A=
プレイヤー２（列）
の利得行列
B=
行（t）：－列（r）．
r
0
2
3
l
列（r）：－行（m）．
6T
5M
3B
r
1
0
4
＊）2人のときは双行列ゲーム(bimatrix
１
の
純
粋
戦
略
0T
2M
3B
10
game)ともいう。
列（l）：－行（t）; 行（b）．
純
粋
戦
略
で
の
両
者
の
最
適
反
応
列がｌを選ぶなら、
行はBが最適だが、
列がｒを選ぶなら、
行はTが最適。
行が M を選ぶなら、
列はｒが最適だが、
行が TまたはB を
選ぶなら、列はｌが
最適。
そ
の
交
わ
り
が
ナ
ッ
シ
ュ
均
衡
ナッシュ均衡の論理構造を論理プログラミン
グで論理的に…
 ナッシュ均衡は最適応答の組。混合戦略（ランダム化を許す
場合）、均衡の存在を連続写像の不動点として証明できる（Ｎ
ａｓｈ,1951)。
 例題では（b、ｌ）が条件を満たし、それ以外の組は整合しない
ことは簡単に確認できる。
 しかし前頁のプログラムは標準のPrologではループする。こ
の種の自己言及の不動点を扱うＰｒｏｌｏｇの拡張には触れない。
 後出のシグナリングゲームのモデリングでは、均衡の整合を
生成＆テストする手続きをプログラムした。
11
均衡アルゴリズムとProlog
 以降の部分ではゲームの均衡を求めるアルゴリズムに触れ
るが、この分野は、誕生から数理計画法と共に歩んだ歴史
がある。またAIの研究者も一部かかわっている。
 パソコンで使えるパッケージソフトウェア（たとえばGAMBIT）
も知られているが、手続き型言語で実装されている。
 Koller＆Pfeffer(1997)のGALAシステムではPrologが初期
実装に用いられた。またGAMBITやGAMSを外部ソルバーと
して用いていた。
 ここでまず均衡アルゴリズムの基礎でもある線形計画法・凸
２次計画法の掃出し法（ピボット演算）と、Prologの推論（導
出原理）の関係をおさらいしておこう。
12
簡単なPrologプログラムの線形計画問題へ
の読み替え
ただしこのままでは実行
Horn
clauses:
 図参照
a :- b,c.
b :- d.
c.
d.
The goal:
?- a.
LP:
(0 ≦) Xa +(1–Xb) +(1–Xc) ≦ 1.
(0 ≦)
Xb
+(1-Xd) ≦ 1.
Xc
= 1.
Xd = 1.
Max. z = Xa.
可能単点解でないので、
スラック変数を追加して初
期解を求めてからシンプ
レックス法を使えばよい。
次のスライド
なおこの変形は次の定理
に基づいている。
Jeroslow-Wang-Hookerの定理
命題を非負値変数
に置き換える。形
式的にピボット演
算を実行すると、
係数行列が完全単
模なので解は整数
になる。
係数行列:
Xa Xb Xc Xd Const.
1
–1 –1 0 -1
0
1
0 –1 0
0
0
1 0 1
0
0
0 1 1
–1
0
0 0 0
13
Ax>ａが充足可能なホーン節集合
Hを表現すると仮定する。補助変数
つきの双対問題（本スライドでは主
問題に相当）の最適解は整数であ
り、対応する導出におけるその節
の利用回数を示す。またHが充足
不能のときは、空節の導出に対応
し、最適解は節の出現回数の比を
示す。
シンプレックス法の掃出しの図解
多面体の隣接する辺に沿って移動し、目的の
値を最大（または最小）にする。
線形計画問題を解くシンプレックス法の掃出し演算は、凸２次
計画法における相補掃出しでも活用される。ただし次に基底
に入る変数が、直前に掃出された変数の双対変数に特定され
る。数理計画法については、たとえば今野(1987）を参照。
14
シンプレックス法による導出の模擬
下表は下図のルールベースを線形計画問題（シンプレックス表）として表現したもの。
プログラムlpolp01xyz.plを用いてこれを解いた。
最終表（ステップ４）
tableau(pivot(re0, step(4))
label,
[b, x1, x2, x3, x4, s1, s2, s3, s4]
solved(x4), [1, 0, 0, 0, 1, 0, 0, 0, 1]
solved(x3), [1, 0, 0, 1, 0, 0, 0, 1, 0]
solved(x2), [2, 0, 1, 0, 0, 0, 1, 0, 1]
solved(x1), [4, 1, 0, 0, 0, 1, 1, 1, 1]
solved(obj), [4, 0, 0, 0, 0, 1, 1, 1, 1]
初期表
tableau(pivot(re0, step(0))
label,
[b, x1, x2, x3, x4, s1, s2, s3, s4]
solved(s1), [1, 1, -1, -1, 0, 1, 0, 0, 0]
solved(s2), [1, 0, 1, 0, -1, 0, 1, 0, 0]
solved(s3), [1, 0, 0, 1, 0, 0, 0, 1, 0]
solved(s4), [1, 0, 0, 0, 1, 0, 0, 0, 1]
solved(obj), [0, -1, 0, 0, 0, 0, 0, 0, 0]
rb(re0):
x1:- x2, x3.
x2:- x4.
x3.
x4.
?- x1.
シンプレックス基準（目的関数行に負の係数がな
ければ最適）に基づき掃出し演算（ピボッティング）を
実行した。
最終行のスラック変数の係数は、各節が導出に用
いられた回数である。(Jeroslow & Wang(1989)お
よびHooker(2000 定理６７）を参照。）
なお初期表の列ｂはJeroslow & Wang の例題
4.4の補助変数に対応するベクトルである。
15
途中の表
tableau(pivot(re0, step(1))
solved(x1), [1, 1, -1, -1, 0, 1, 0, 0, 0].
solved(s2), [1, 0, 1, 0, -1, 0, 1, 0, 0]
solved(s3), [1, 0, 0, 1, 0, 0, 0, 1, 0]
solved(s4), [1, 0, 0, 0, 1, 0, 0, 0, 1]
solved(obj), [1, 0, -1, -1, 0, 1, 0, 0, 0]
tableau(pivot(re0, step(2))
solved(x2), [1, 0, 1, 0, -1, 0, 1, 0, 0]
solved(x1), [2, 1, 0, -1, -1, 1, 1, 0, 0]
solved(s3), [1, 0, 0, 1, 0, 0, 0, 1, 0]
solved(s4), [1, 0, 0, 0, 1, 0, 0, 0, 1]
solved(obj), [2, 0, 0, -1, -1, 1, 1, 0, 0]
tableau(pivot(re0, step(3))
solved(x3), [1, 0, 0, 1, 0, 0, 0, 1, 0]
solved(x2), [1, 0, 1, 0, -1, 0, 1, 0, 0]
solved(x1), [3, 1, 0, 0, -1, 1, 1, 1, 0]
solved(s4), [1, 0, 0, 0, 1, 0, 0, 0, 1]
solved(obj), [3, 0, 0, 0, -1, 1, 1, 1, 0]
展開型ゲーム（完全情報と不完全情報）
各ノードはプレイ
ヤーの意思決定
時点表す。
はプレイヤー
の情報集合
を表す。同じ
情報集合内
部のノードは
区別できない。
矢線とラベルは
選択された行為
（純粋戦略）を表
す。
終端の括弧内
は両プレイヤーの
利得。
完全情報の
一ケース
図出典：
次の文献の例題。情報構
造の部分を修正した。B.
Von Stengel. Computing
equilibria for two-person
games. In R.J. Aumann
and S. Hart (eds.),
Handbook of Game
Theory, Vol.3, 2002,
p.1751, Figure 8.
不完全情報
の一ケース
16
不完全想起
いくつかの代表的なゲーム理論モデル
 シグナリングゲーム
プログラム名
完全ベイズ均衡（逐次均衡）
Dempster-Shafer均衡
gbayes0.pl
dse0.pl
 メカニズムデザイン
セカンドプライスオークション
spa.pl
組み合わせオークションの勝者 spa.pl
 ゲームの解の計算
安定結婚アルゴリズム
相補掃出し法
marriage0.pl
lpolp01xy.pl
 ソースコードはホームページからダウンロードできる
hｔｔｐ://www.us.kanto-gakuen.ac.jp/indo/kenkyu.html
17
シグナリングゲーム
または評判・名声
 不確実なメッセージが信頼できるかどうかを戦略的に判断す
る。このため、信用や信頼のモデリングに用いられる。
 シグナリングゲームはHarsanyi型の不完備情報ゲームの代
表的なモデルクラス。特殊な不完全情報ゲームで、ゲームの
最初に自然がプレイヤーのタイプを確率的に選ぶ。
 ショケ期待効用とDempster-Shaferルールを応用し曖昧性回
避を組み込んだ修正モデルもある。離散凸解析があてはまる
ようだが寡聞にして文献を知らない…
 後で述べる相補掃出し法は、シグナリングゲームのような展
開型、つまり手番に順序があり、不完全情報のゲームに適用
されるとき、Prologの推論の自然な拡張を示唆する。
18
シグナリングゲームの例
Kohlberg & Mertens(1986) のFigure 14 を参考に作成。
-3, 0, 1
-1, 0, 1
fight
cooperate
Player 1 of
“weak” type
このゲームの安定均衡：
先手は強弱いずれも送信。
後手は受信したら従順、
受信しなければ５０％以上
の確率で高飛車。
fight
-2, 0, 1
Do
nothing
Send a
signal
10%
cooperate
0, 0, 0
Nature
0, -2, -1
0, 0, 0
fight
cooperate
Send a
signal
fight
90%
Do
nothing
Player 2 of
“strong” type
19
0, -3, -1
0, -1, 0
cooperate
シグナリングゲームのＤＳ均衡
図はプログラムdse0.plの実行画面
20
メカニズムデザイン
 オークションなどの市場取引や、企業組織の分析へ
のゲーム理論の応用。
 情報発信を正直に行わせるための（ナッシュ）遂行理
論と、コミュニケーションの経済学的分析に大別され
る。
 ナッシュ遂行理論は、（VCG税などによって）選好を
摂動させたときの、ナッシュ均衡対応の形の研究。
 組合せオークションは、分散AIの研究者などが注目
している。
21
セカンドプライスオークション
図はプログラムspa.plにおいて、オークションのルールを記述した部分。
配分ルールと支払
ルールがメカニズ
ム設計の中心
22
最高値をつけた勝
者は、第2位の入
札値を支払う。すな
わち勝者はもし次
点が勝者だったら
獲得したであろう価
値を税として支払う。
２つの古典的アルゴリズム
 GaleとShapley（1962)の安定結婚アルゴリズム。
 安定結婚問題は分権化された二部マッチング。Sterling＆Shapiro
「Prologの技芸」の練習問題１４．１(ii)で紹介されている。
 Gale＆Shaplyはそのアルゴリズムにより、安定結婚集合（結婚市場のコ
アに一致）がつねに非空であることを示した。
 男性がプロポーズを繰り返す。女性側で待機リストを用い、先約が覆るこ
とを許す。遅延許諾アルゴリズムともいわれる。
 ちなみにTeXのD. Knuthがこの分野の初期の本を書いた。
 LemkeとHowson(1964)による相補掃出し法
 ２人行列ゲームのナッシュ均衡を線形相補性問題を解いて求める。
 N人の場合や展開型に対して改良されている。完全均衡や固有均衡を求
めるものもある。
 展開型ゲームでは、順序型(sequence form) に変換する方法が、計算効
率化に役立つ。
 ホモトピー法として一般化され、大域ニュートン法との融合も研究されてい
る(例えばGovindan&Wilson(2003)）。
 ともに後のゲーム理論と数理計画法の発展に影響した。
23
ペアE３は
このマッチ
ング案をブ
ロックする。
E
安定結婚問題
1
1
A
B
C
D
男性側はベストの
相手に申し込む。
24
5
2
4
2
3
4
2
5
Gale-Shapleyアルゴリズム
 【第1段階】各男子は一番好きな女子に申し込む。
複数の申し込みをもらった女子は最上位にランクさ
れた者だけ、自分の待機リストに登録し、残りを拒
否する。
 【第２段階】前段で拒否された男子は、次点の女子
に申し込む。女子は新規申し込みと自分の登録リス
トを合わせて、最上位だけ残して後は拒否する。す
べての女子がプロポーズされたら、停止する。それ
以外は段階を進め、この手続きを繰り返す。
25
Prologプログラムmarriage0.pl
 安定な結婚集合は、定義から直接、標準のバックト
ラックを使って求める方法(述語
stable_marriages/1)と、Gale-Shapleyのアルゴリ
ズム(述語matching/0)を両方作成し、例題を用いて
動作を確認した。
 Ｐｒｏｌｏｇプログラム marriage0.plに、上記例題のモ
デルベースを追加し、実装したＧａｌｅ－Ｓｈａｐｌｅｙアル
ゴリズム（コマンドmatching/0)で実験してみると、６
ラウンドで安定結婚集合 [me-w3, mb-w2, ma-w1,
md-w4, mc-w5]に到達した。
26
安定結婚アルゴリズムの数理
 以下はRoth&Sotomayer(1990)、応用数理計画ハンドブック14.2節などを参
照した。
 安定結婚集合とは、同人数の男性と女性に対するマッチング案で、どのペア
からもブロックされない。つまりどんな代替ペアを提案しても、少なくともその
一方は原案から離れたくないと思う。
 ＶａｎｄｅＶａｔｅ(1989)は、次のように安定結婚集合と論理的に等しい条件（0－
1ベクトル空間の安定結婚多面体）に置換えた。
xmw  1 
x
mj
jm w
  xiw m, w A  M W .
i w m
 つまり、安定結婚の条件は、原案で割り当てられていないペアについては、い
ずれかがもっとましと思うパートナーをすでに見つけている。
 GSアルゴリズムではペア解消を許し、ふられた男ともっといい相手を求める
女のブロッキングペアを貪欲に取り入れマッチングを更新することで、上式の
表す凸多面体の端点解として、男性最適安定結婚集合に達する。
27
安定結婚集合の変種とブロック関係、および
より発展した研究
 GSアルゴリズムでは、プロポーズするのは男性だけであり、男性最適の安
定結婚集合が得られる。男女入れ替えて女性最適のそれも得られる。
 安定結婚集合は男性から見た優位性において分配束をなす。同性の最良
（最適）は異性の最悪に対応する。この順序の下で、ｋ－ｔｈ安定結婚集合が、
複数のマッチングの交わりから得られる。
 ブロック関係は協力ゲームのコアの概念と共通する基礎であり、安定結婚問題で
は一致する。
 Danilovはブロック関係を用いて、ナッシュ遂行の条件を導いた。
 GSアルゴリズムをあるマッチング案から開始すると、ループすることがある
（Knuthによる例）。
 しかし全員独身の状態からブロックされるペアをたどる一種の貪欲算法（ランダム
マッチ）によって安定結婚集合を枚挙できる（Roth & Vande Vate, 1990）。
 GSアルゴリズムで求まる（男性最適）安定結婚集合は、虚偽報告に対し脆弱
（ナッシュ遂行不能）。
 Kara& Sönetz(1996)は上記Danilovの結果を応用し、安定結婚ルールは遂行可
能であることを示した。
 近年のゲーム理論では、戦略的ネットワーク形成のモデルに発展している。
補足：GSアルゴリズムをより市場経済に近いモデルに拡張し、Shapley&Shubikの割当ゲームを結びつけた研究として、Crawford&Noer(1981) がある。彼らは貨幣
（給与）のある場合に、従業員と企業のマッチィング問題を解く「給与調整プロセス」がコアに収束することを示した。おおよそGSアルゴリズムで男性がプロポーズする
28
のを、各企業が欲しい従業員候補に対し給与額を（上昇ビット風に）提示することに置き換えたものである。Kelso&Crawford(1982)
Econometrica 50(6):1483-1504
は、「粗代替性」と彼らが呼ぶ条件を用いて給与調整プロセスの収束を一般化した。なお、粗代替性はマトロイド理論の文脈でMナチュラル凹関数の必要十分条件（室
田(2001), 『離散凸解析』, 共立出版定理9.7）であるが、もともと一般均衡モデルで競争均衡の存在などを示すための条件として知られていたものの類似物である。
相補掃出し法と線形相補性問題
 以下はvon Stengel(2002)のレビュー論文などを参照した。
 ２人ゲームのナッシュ均衡は（混合）線形相補性問題と等価である（図参照）。
３人以上は非線形になる。定常点問題、変分不等式問題と等価。
（M,N)を純粋戦略集合の組、（ｘ、ｙ）を混合戦
略組、（A,B）を利得行列の組、ｋやｌを純粋戦
略の番号とする。
ak y ,

 xi  0  ai y  max
kM
NE 
y j  0  b j y  maxbl x.

lN

 Ex  e, E T u  Ay  0, x  0,

T
T
 Fy  f , F v  B x  0, y  0,
(m ixed) LCP 
T
T
x
E
u  Ay  0,


y T F T v  B T x  0.




 Lemke－Howson法（相補掃出し法）は、相補性問題で高々１つの不等式が
違反している多面体の隣接端点解ペアをつないだ準相補的道を作る。
 非退化条件を満たす行列ゲームのナッシュ均衡は、準相補的道の両端にあ
る。
 終点なしの道(ray termination)が一本だけあり、端点は有限個。よって均衡
の個数は奇数。
29
l
A=
相補掃出しの例
 変数のスケール変換によって
LCPは以下のように単純な形に
なる。
Ay' r  1M ,
BT x' s  1N ,
x'T r  0,
y 'T s  0.
 前出の標準形ゲームに対し、相
補掃出しを実行した。
 原点で未利用の最適戦略ｘ2を
最初のピボット列とし、最小比基
準でピボット行ｓ5を掃出す。
 同時に、次のピボット列がその
双対変数ｙ5に決まる。
 以降、同様の操作を繰り返す。
 最初のx2の双対変数ｒ2が0に
落ちたところで停止する。
l
r
0
2
3
6T
5M
3B
B=
r
1
0
4
0T
2M
3B
tableau(m atrix_A B )
step(0)
const x1
x2
x3
y4
y5
r1
r2
r3
s4 s5
solved(r1)
1
0
0
0
0
6
1
0
0
0
0
solved(r2)
1
0
0
0
2
5
0
1
0
0
0
solved(r3)
1
0
0
0
3
3
0
0
1
0
0
solved(s4)
1
1
0
4
0
0
0
0
0
1
0
solved(s5)
1
0
2
3
0
0
0
0
0
0
1
solved(objective) 0
0
0
0
0
0
0
0
0
0
0
step(1) (s5->x2)
solved(x2)
0.5
0
1 1.5
0
0
0
0
0
0 0.5
solved(r1)
1
0
0
0
0
6
1
0
0
0
0
solved(r2)
1
0
0
0
2
5
0
1
0
0
0
solved(r3)
1
0
0
0
3
3
0
0
1
0
0
solved(s4)
1
1
0
4
0
0
0
0
0
1
0
solved(objective) 0
0
0
0
0
0
0
0
0
0
0
step(2) (r1->y5)
solved(y5)
0.167
0
0
0
0
1 0.167
0
0
0
0
solved(x2)
0.5
0
1 1.5
0
0
0
0
0
0 0.5
solved(r2)
0.167
0
0
0
2
0 -0.83
1
0
0
0
solved(r3)
0.5
0
0
0
3
0
-0.5
0
1
0
0
solved(s4)
1
1
0
4
0
0
0
0
0
1
0
solved(objective) 0
0
0
0
0
0
0
0
0
0
0
step(3) (s4->x1)
solved(x1)
1
1
0
4
0
0
0
0
0
1
0
solved(y5)
0.167
0
0
0
0
1 0.167
0
0
0
0
solved(x2)
0.5
0
1 1.5
0
0
0
0
0
0 0.5
solved(r2)
0.167
0
0
0
2
0 -0.83
1
0
0
0
solved(r3)
0.5
0
0
0
3
0
-0.5
0
1
0
0
solved(objective) 0
0
0
0
0
0
0
0
0
0
0
step(4) (r2->y4)
solved(y4)
0.083
0
0
0
1
0 -0.42 0.5
0
0
0
solved(x1)
1
1
0
4
0
0
0
0
0
1
0
solved(y5)
0.167
0
0
0
0
1 0.167
0
0
0
0
solved(x2)
0.5
0
1 1.5
0
0
0
0
0
0 0.5
solved(r3)
0.25
0
0
0
0
0
0.75 -1.5
1
0
0
solved(objective) 0
0
0
0
0
0
0
0
0
0
0
30
lpolp01xyz.plを用いた相補掃出しの結果
構造定理とホモトピー
 有限標準形ゲームのナッシュ均衡対応は、ゲー
ムの利得空間と同型（Kohlberg & Mertens(1986、
定理１)）。
 ホモトピー変数はいわば非最適行動を選択させる
ためのボーナス。（Wilson(1992)による経済学的
解釈）
 相補掃出しなどによって準相補的道をたどると、
それに沿って、ホモトピー変数（補助変数）が０に
落ちていく。
 ただし落ち方は必ずしも単調でない。
31
ホモトピー法のきわめて直観的なイメージ
 ほぼ相補性条件を満たす（未利用
の最適反応の純粋戦略が高々１
つ）という条件を保って、ゲームを連
続的に変形する。
 このときの、ナッシュ均衡集合の軌
跡が、一次元多様体（穴なし、くぼ
みあり）をなす。
 ＡＩでいう「類推」を連続的に行った感
じ。
Ｇ１の
ナッシュ
均衡
Ｇ２の
ナッシュ
均衡
ＧＬの
ナッシュ
均衡
かなり摂動
したゲーム
ＧＬ
Ｇの
ナッシュ
均衡
32
中程度に摂動
したゲーム
Ｇ２
元のゲーム
Ｇ＝Ｇ０
少しだけ摂動
したゲーム
Ｇ１
２ｘ２ゲームでのホモトピー法の適用例
The figure has created by using fixpo04a.xls downloadable from my homepage.
payoff for 1
s21
s11
s12
payoff for 2
s21
s11
s12
Piecew ise linear path of pivot
procedure for a 2-person gam e w ith
the N ash m ap
s22
0
0.1
0.2
0
1
0.75
s22
0.1
0
0
0.4
0.5
0.25
m ixed equilibrium (interior)
0.8
p
0.333333
q
0
0
0.25
0.5
0.75
Reference: A. van den Elzen and D. Talman (1999). An algorithmic approach toward the
tracing procedure for bi-matrix games. Games and Economic Behavior 28: 130-145.
33
1
均衡アルゴリズムはエージェントベースの推
論モデル？
Jeroslow-Wang-Hookerの定理は、ナッシュ
均衡を求める古典的なアルゴリズムである相
補掃出し法との類比、したがって導出のエー
ジェントシステムへの自然な一般化に気づか
せてくれる。
ホモトピー変数の役割に注目しながら、同じく
プログラムlpop01xyz.plを用いて展開型ゲー
ムへの適用例と比較してみよう。
34
payoffs for sequence form
[]
順序型
A=
前出の不完全情報ゲームを順序型に
変換し、混合LCPに当てはめるとこのよ
うになる（von Stengel, 2002 p.1754）。
[]
L
R
E=
1
-1
0
0
1
0
F=
1
-1
0
1
[]
l
LS
0
1
-1
r
[]
0
0
0
[]
0
0
0
3
0
0
0
B=
0
0
1
r
0 []
0 h(1,1)
1 h(1,2)
EとFは制約行列。
ピボット行を選ぶ
ときは無視される。
 Ex  e, E T u  Ay  0, x  0,

T
T
 Fy  f , F v  B x  0, y  0,
m LCP
x T E T u  Ay  0,

T
T
T

y
F
v

B
x  0.



35
l
r
0
0
0
[]
L
4
0
0
L
0
R
0
0
0
R
0
6
LS
0
1
0
LS
2
5
LT
0
0
2
LT
LT
0 []
1 h(2,1)


l
e=
f=
1
0
0
0
1
0
順序型の例に対する掃出しの実行
label
solved(e1)
solved(e2)
solved(e3)
solved(e1)
solved(e2)
solved(e3)
solved(e1)
solved(e2)
solved(e3)
solved(e1)
solved(e2)
solved(e3)
solved(e1)
solved(e2)
solved(e3)
 掃出しの各ステップ
｛slxLS, rLT yl, sr
xLT, rLS yr.｝で、
制約行列の部分に注
目してみよう。
36
c
x0
1
0
0
1
0
1
1
0
1
1
0
1.5
1
0
1.5
xL
-1
1
0
-1
1
0
-1
1
0
-1
1
0
-1
1
0
xR
0
-1
1
0
-1
1
0
-1
1
0
-1
1
0
-1
1
xLS
0
-1
0
0
-1
0
0
-1
0
0
-1
0
0
-1
0
xLT
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
label
c
y0
yl
yr
solved(f4)
1
-1
0
0
solved(f5)
0
1
-1
-1
solved(f4)
1
-1
0
0
solved(f5)
0
1
-1
-1
solved(f4)
1
-1
0
0
solved(f5)
0.5
1
0
1.5
solved(f4)
1
-1
0
0
solved(f5)
0.5
1
0
1.5
solved(f4)
1
-1
0
0
solved(f5) 0.25
1
0
0
0
0
-1
0
0
-1
0
0
-1
0
0
0
0
0
0
相補掃出しとPrologの関係についての観察
 [C1] 命題論理の導出は（シンプレックス法の）ピボッ
ト演算で表現できる。
 [C2] 制約行列にルール節集合が対応する。事実節
集合は、それに対する資源制約の緩和とみなせる。
 [C3] 線形相補性問題を解く手続き（相補掃出し）は、
C1-C2より、導出を表現する。
 [C4] したがってエージェントたちの相互的推論ない
し信念・戦略の調整プロセスに一般化される。
37
補遺：ゲームモデリングの認知科学的問題
ゲームと知性の共変化の解明に向けて
意志とアルゴリズムへの認知的侵入にかん
する推測
38
ゲームと知性の共変化の解明に向けて
 効率的な均衡アルゴリズムの開発は、エージェントの社会と
しての意思決定者モデリングを目指している報告者自身の
専門外のところにあった。ではなぜ今回、重点を置いたか？
 均衡アルゴリズムは、本質的でないと思われるゲームの形
式や利得の摂動に耐える解の安定性・不変性を追求した成
果。組合せ最適化や代数幾何をエレガントに用いて証明され
ている。
 しかし、ゲーム理論の関心は、Kohlberg ＆ Mertensや
Harsanyiが示唆しているように、むしろ均衡の不安定性にあ
る(Kohlberg and Mertens, 1986; Harsanyi, 1991)。すなわ
ちゲームの表象と、ゲームプレイヤーの知性や感情との共
変化に焦点を当てるべきだろう。
39
意志とアルゴリズムへの認知的侵入にかん
する推測
 ゲームと知性の共変化は、人間より強いチェスや囲碁のプロ
グラム製作やゲーム理論を様相体系に翻訳するだけの研究
と比べると、人工知能・認知科学のテーマとしてより自然では
ないか。今回の研究は、その出発点として押えておくべきも
のではあった。
 「意志」のモデル、あるいは「エージェント」のモデルというも
のは本来多重自己的である。思ったとおり最適なことができ、
後悔が不要なら、意志も消える。均衡アルゴリズムでのホモ
トピー変数はそのモデルを示唆する。
 【推測】仕様書のない実装と実験の試行錯誤により、心理的
責任と葛藤が生じた。あえて中国語プログラムの部屋に飛び
込むことにより、理論やアルゴリズムへの認知的侵入が可能
になるのではないか。
40
まとめ
 ４つの古典的なゲーム理論モデリングを、Prologを
用いて実装した。また最近の研究との関連を述べ
た。
 均衡アルゴリズムの実装を通じて、Prologとゲー
ム理論および数理計画法の関連に焦点を当てた。
 掃出し演算と導出の関係を、実装と実験を通じて
理解した。また相補掃出しに基づき、ゲーム理論
的な推論モデルを考察した。
 ゲーム理論モデリングの認知科学的側面に言及
した。
41
参考文献
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
R. Aumann and S. Harｔ(eds): Handbook of Game Theory with Economic Applications, Vol. 3, North-Holland (2002).
L. E. Blume and W. R. Zame: “The algebraic geometry of perfect and sequential equilibrium”. Econometrica 62(4), pp. 783-794 (1994).
D. Gale and L.S. Shapley: “College admissions and stability of marriage”, The American Mathematical Monthly 69, pp. 9-15 (1962).
S. Govindan and R. Wilson: “A global Newton method to compute Nash equilibria”. Journal of Economic Theory 110, pp. 65-86 (2003)
J. C. Harsanyi: “Game solutions and the normal form”. In A. Chikan (ed.), Progress in Decision , Utility and Risk Theory. Kluwer Academic Press, pp.
43-65 (1991).
J. Hooker: Logic-Bsed Methods for Optimization: Combining Optimization and Constraint Satisfaction, John Wiley & Sons. (2000).
R. G. Jeroslow and J. Wang: “Dynamic programming, integral polyhedra and Horn clause knowledge base”. ORSA Journal on Computing 1(1): 7-19
(1989).
T. Kara and T. Sönetz: “Nash implementation of matching rules”. Journal of Economic Theory 68, pp. 425-439 (1996).
D.E. Knuth: Mariages Stables (1976).
E. Kohlberg and J.-F. Mertens : “On the strategic stability of equilibria”. Econometrica 54(5), pp. 1003-1037 (1986).
D. Koller and A. Pfeffer: “Representations and solutions for game-theoretic problems”, Artificial Intelligence 94, pp. 167-215 (1997).
C.E. Lemke: “Bimatrix equilibrium points and mathematical programming”. Management Science 11(7), pp. 681-689 (1965).
C.E. Lemke and J.T. Howson: “Equilibrium points of bimatrix games”. Journal of SIAM 12(2), pp. 413-423 (1964).
J. Nash: ”Non-cooperative games”. Ann. of Math. 54 (1951), pp. 286-295.
A. Pekec and M. H. Rothkopf: “Combinatorial Auction Design”, Management Science 49(11), pp. 1185-1503 (2003).
A. E. Roth and M.A.O. Stomoyor: Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis. Economic Society Monographs, Cambridge
University Press (1990).
A. E. Roth and J.H. Vande Vate: “Random paths to stability in two sided matching.” Econometrica 58, pp.1475-1480.(1992).
M.J. Ryan: “Violations of belief persistence in Dempster-Shafer equilibrium”, Games and Economic Behavior 39 (2002), pp.167-174.
A. van den Elzen and D. Talman: “An algorismic approach toward the tracing procedure for bi-matrix games”. Games and Economic Behavior 28
(1999) , pp. 130-145.
J.H. Vande Vate: “Linear programming brings martial bliss”, Operations Research Letters 8, pp. 147-153 (1989).
B. von Stengel: “Computing equilibria for two-person games”, In Aumann and Hard(2002), chapter 45, pp. 1723-1759.
B. von Stengel, A. van den Elzen, and D. Talman: “Computing normal form perfect equilibria for extensive two-person games”, Econometrica 70(2) ,
pp. 693-715 (2002).
W. Vickrey: “Counterspeculation, auctions, and competitive sealed tenders”. Journal of Finance 16, pp. 8-37 (1961).
R. Wilson: “Computing simply stable equilibria”. Econometrica 60(5) , pp. 1039-1070 (1992).
久保幹雄・田村明久・松井知己（編）: 応用数理計画ハンドブック, 朝倉書店 (2002).
今野浩: 線形計画法, 日科技連 (1987).
42

Download Report