ゲームプレイヤーのモデリング（3G2-01）

1
Prologによるゲームプレイヤーのモデリング
Modeling game players by using Prolog
犬童健良*1
Kenryo Indo
*1 関東学園大学経済学部
Faculty of Economics, Kanto Gakuen University
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
2
１．ゲームプレイヤーのインテリジェンス
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
3
AIにおけるゲーム研究
• アート的ないし工学的アプローチ
– ボードゲームで勝てるプログラムの研究
– エージェントによる交渉・入札など（分散AI。ビジネス産
業への応用）
• 認知科学アプローチ
– チューリングによる思考実験（「模倣ゲーム」を用いた知
性認定）
– 人間を楽しませるプログラム（知性とゲームのインタラク
ション）
– 素朴な疑問：やる気が出る/知性が発揮できるのは、ど
のようなゲームか？
知性とゲームの共変化
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
ゲームプレイヤーのモデル
• ゲーム理論で言うプレイヤーの（個人）合理性とは、その利得＝
期待効用(expected utility)の最大化のことである。
• また均衡点（解概念）を用いて、ゲームの結果を予測する。例え
ば、非協力ゲームにおけるナッシュの均衡点は、最適反応の組
として定義される。
• 一般にゲームの均衡点は一意ではないが、合理性が共通知識
(common knowledge)であると仮定すると、均衡を絞り込むため
の、いくつかの推論モデルが考えられる。（＝均衡リファインメン
トの研究。例えば固有均衡、部分ゲーム完全性、逐次均衡、最
適反応批准可能性など）。
• これらの研究では、共通知識自体は必ずしも明示的にモデリン
グされなかったが、その後、分散人工知能研究との交流もあり、
確率論、論理学、計算論による定式化を通じ、ゲームプレイヤー
の知識がモデリングされるようになった。
• また、合理性や共通知識の仮定を緩和したさまざまな「限界合理
性」の代替理論や心理学的実験（行動的ゲーム理論）およびそ
の応用が研究されている。
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
4
5
なぜゲームプレイヤーをモデル化したいのか
• ゲームモデルと解概念が、ゲームプ
レイヤーの合理性と知識のモデル
から演繹できるか、実験的に確かめ
たい。
• そのためには、プレイヤーの合理性
（ i.e., 最大化行動）や共通知識を明
示的にモデリングする必要がある。
• またそれらの緩和（i.e., 限界合理
性）のモデルの下でのゲーム理論
の限界や拡張を考えたい。
• 従来、確率論や論理学による共通
知識の定式化が用いられていたが、
Prologを使えば、より直接的にゲー
ムプレイヤーの知識処理をシミュ
レーションできるのではないか。
合理性と
共通知識の
論理モデル
選択結果に
ついての
定理
ゲームの
論理モデル
？
旧い
語り口
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
本研究の目的
• 筆者が行ったPrologによるゲーム分析のモデリング
事例のうち、いくつかを紹介したい．
• 以降の内容：
– 第2節
• 標準形ゲーム（利得関数、ナッシュ均衡）、
• 提携形ゲーム（特性関数、コア）
• メカニズムデザイン（遂行理論）
– 第3節
• 展開形ゲーム（完全情報ゲームの木、部分ゲーム完全性）
– 第4節
• 共通知識・取引（不完全情報ゲーム、合理的期待と限界合理性）
– 第5節まとめ
– 参考文献
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
6
ゲームプレイヤーのモデリング用途
• ゲーム理論の基礎の探求と教育目的以外に、以下のような
研究用途が考えられる。
• マルチエージェントシミュレーション
– コンピュータシミュレーションによる限界合理性やメカニズムデザイン
の研究など
• 限界合理性
– 合理性や共通知識の仮定を緩和し、探索的活動やデザイン活動を考
慮したゲーム理論やメカニズムデザイン論の代替理論を研究。
– 計算論による外部基準（計算複雑性）によって合理性の限界を規定・
測定。
– しかし実際の限界（例えば4枚カード問題や連言誤謬）は、低い計算量
で生じる。したがってそれだけでは、なぜ合理性に限界が生じるのか、
またいつエージェントは合理的にふるまおうと意図するのかが分から
ない。
• 合理性の限界の内生的モデル（多重自己メンタルモデル）
– 「心の社会」の解明は認知科学の目的。現実のメンタルモデルは、複
数の構成要素の相互作用の結果である。
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
7
合理性の限界の内生的モデル
（多重自己メンタルモデル）
• 「心の社会」の解明は認知科学の目的。現実のメン
タルモデルは、複数の構成要素の相互作用である。
• 知性は社会環境（ゲーム形式）に対して独立・安定し
ていない。
• 状況や意識する相手によって、同じ思考対象につい
て、「意欲・関心」があったり、なくなったり。
• こうした知性のボラティリティ（ないし知性と社会の共
変化）に影響するゲーム形式ないしメカニズム（＝語
り口）を研究する。
• すなわち、興味・関心という希少資源の配分問題を
解く人工物のデザイン。
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
8
9
2. 行動水準でのゲームモデリング
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
標準形ゲームとナッシュ均衡
• ２人標準形ゲームs1の利得表を図１に示す．
• 各プレイヤーがそれぞれ２つの純粋戦略を持つ同時
手番のゲーム．
• 図１中の＊印は最適応答．
• このゲームのナッシュ均衡は[1,1]と[1,0]の２つ．
• いずれの均衡でも，プレイヤーが単独で自分自身の行
動を変更する動機がない．
Payoff of
Act of player 2
game s1
z
w
---------------------------------------------Act of
x
[1, 1]
[-2, 0]
player
* *
*
1
y
[1, 0]
[-1, -1]
*
*
*
---------------------------------------------図1．標準形ゲームの利得表
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
10
11
2.1 標準形ゲームのPrologモデル
• Prologで上の例題とその純粋ナッシュ戦略均衡をモデリン
グしよう．
• 標準形ゲームｓ１のPrologモデル
game(s1, acts([x,z]), payoffs([1,1]) ).
game(s1, acts([x,w]), payoffs([-2,0]) ).
game(s1, acts([y,z]), payoffs([1,0]) ).
game(s1, acts([y,w]), payoffs([-1,-1]) ).
• また図1の利得表の非対角部分を変更したゲームｓ２では，
[-1,-1]が唯一の均衡となる．（囚人ジレンマゲーム）
• 標準形ゲームｓ２のPrologモデル
game(s2, acts([x,z]), payoffs([1,1]) ).
game(s2, acts([x,w]), payoffs([-2,2]) ).
game(s2, acts([y,z]), payoffs([2,-2]) ).
game(s2, acts([y,w]), payoffs([-1,-1]) ).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
標準形ゲーム
の
12
ナッシュ均衡のPrologモデル
• ナッシュ均衡を求めるプログラム
nash(G,[S1,S2],[P1,P2]):game(G,
acts([S1,S2]),payoffs([P1,P2])
),
\+ (game(G,
acts([_,S2]),payoffs([Px,_])),Px>P1
),
\+ (game(G,
acts([S1,_]),payoffs([_,Py])),Py>P2
).
• 実行例
?- nash(G,Acts,Payoffs).
G = s1
Acts = [x, z]
Payoffs = [1, 1] ;
G = s1
Acts = [y, z]
Payoffs = [1, 0] ;
G = s2
Acts = [y, w]
Payoffs = [-1, -1] ;
No
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
2.2 提携形ゲームのPrologモデル
• 提携形ゲーム，いわゆる協力ゲームは，プレイヤーの可能な
提携(coalition)が生み出す共同利益を特徴関数として定義し
，コア，仁，シャプレー値といった多彩な解概念を用い公平な
分配案を探求する．一般均衡理論や社会選択理論でとくに重
宝された．以下に3人提携形ゲームのモデリング事例を示す．
• 提携形ゲーム（特徴関数）のPrologモデル
game(c1, coalition([ ]),common_value(0) ).
game(c1, coalition([a]), common_value(0) ).
game(c1, coalition([b]), common_value(0) ).
game(c1, coalition([c]), common_value(0) ).
game(c1, coalition([a,b]), common_value(1) ).
game(c1, coalition([b,c]), common_value(1) ).
game(c1, coalition([a,c]), common_value(1) ).
game(c1, coalition([a,b,c]), common_value(1) ).
• ちなみにゲームc1は多数決投票を表す．プレイヤー集合はN
＝{a,b,c}であり，よって可能な提携S⊆Nは8通りある．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
13
配分のPrologモデル
• 配分(imputation)は，
– 全体合理性：ｖ（{1,2,3})＝x1+x2+x3，および
– 個人合理性:x1, x2, x3≧ｖ（{i}）＝０
の2条件を満たす共同利益分配案(x1,x2,x3)の集合である．
• 配分
imputation(game(G),payoff(A)):game(G,form(coalitional),players(N)),
game(G,coalition(N),value(V)),
length(N,LN),
allocation(LN,V,A),
\+ (
nth1(K,N,J),
nth1(K,A,AJ),
game(G,coalition([J]),value(RJ)),
RJ > AJ
).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
14
提携形ゲーム
の
コアのPrologモデル
• コア(core)は，どんな提携Sの下でも互いに支配され
ない配分の集合であり，したがって誰も明らかな不満
(excess)を持たない．
• コア
core(game(G),payoff(A)):game(G,form(coalitional),players(N)),
imputation(game(G),payoff(A)),
\+ (
game(G,coalition(S),value(RY)),
S \= N,
selected_sum(S/N,_B/A,AY),
RY > AY
).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
15
コアの配分の生成
• 3人優加法的提携形ゲームの非空コア存在の必要十分条件は
２・ｖ（{1,2,3})≧ｖ（{1,2})＋ｖ（{2,3})＋ｖ（{1,3})
であることが知られている．ゲームc1は優加法的だから明らかにs1のコア
は空である．また全員提携の値を3/2以上にすればコアが生じる．
• 実行例（全員提携[a,b,c]の値が２のとき* ）
?- core(A,B).
A = game(c1)
B = payoff([1, 1, 0]) ;
A = game(c1)
B = payoff([1, 0, 1]) ;
A = game(c1)
B = payoff([0, 1, 1]) ;
No
（*注）利得スケールを100倍すれば150で初めて[50,50,50]が唯一のコア配分
として出力される．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
16
2.3 社会的選択とメカニズムデザイン
• 選好順序のみに基づく抽象的なゲームモデルもある．
– 社会的選択(social choice)の環境
• 社会の成員の集合
• 社会の成員の可能な選好順序の集合，
• 社会全体で決めるべき代替案の集合，および
• 各選好組に対して定義された望ましい代替案集合（社会選択規則；
SCR）
– 例えば「どの選好状態でもエージェント1とエージェント2の好みは一致し
ないが，３つの代替案のうちcが最悪であることはつねに合意する」と
いった事実や社会選択規則を，以下のように表せる．
• 選好順序
preference(agent(1),state(1),[a,b,c]).
preference(agent(1),state(2),[b,a,c]).
preference(agent(2),state(1),[b,a,c]).
preference(agent(2),state(2),[a,b,c]).
• 社会選択規則
scc(rule(f),state(1),[a]).
scc(rule(f),state(2),[b]).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
17
18
遂行理論のPrologモデル
• こうして定義された社会選択環境に対して，ゲームを通じて
SCRをエージェントたちに分権的に遂行させる問題は，メカ
ニズムデザインないし遂行理論(implementation theory)と
呼ばれる．
• 入札や投票へのより具体的な応用も知られるが，より一般
的には，SCRを遂行するというのは均衡集合とSCRを一致
させることである．その必要十分条件や遂行用のメカニズム
の一般形、および任意のSCRを遂行できる精密なメカニズ
ム（仮想遂行の厳密化）などが研究された．
• なお上記のfは明らかに独裁的SCRだが，fは上の選好に対
し，それ以外にMaskin単調性，制限的拒否権なし，弱パ
レート最適性などを満たすことが分かる．またfはMooreRepulloの条件μ2を満し，ゆえにナッシュ遂行するゲームを
実際に作成できる．
• 筆者の開発したプログラム(impl12.pl) [Indo 02]でこのSCR
に対して、 Moore-Repulloのメカニズムを用い、正直遂行
（正直報告での遂行）を確かめることができる（次のスライド）.
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
遂行理論の
正直遂行のシミュレーション例
test_impl(gMR2, ai, [1, 2], truthful(0), _G445)
start ---------------------[date(2003/5/4), time(16:51:22)]
Testing Nash implementability via prolog simulation
**** the model specification ******
game form: gMR2
members of society: [1, 2]
Scc:
ai(s1) = [a] ai(s2) = [b]
is Maskin-monotone.
is Essentially-monotone.
does not have Moore-Repullo property (defined by Danilov).
is not individually-rational.
preferene domain:
[agent, state, preference, difference]
[1, s1, [a, b, c], [w, w, end]]
[2, s1, [b, a, c], [w, w, end]]
[1, s2, [b, a, c], [w, w, end]]
[2, s2, [a, b, c], [w, w, end]]
other tests for this model
[mm, em, -, -, -, -, rvp, unan, po, -, dict, neli, mlib, -, mju1, mju2, mju3,
mju4]
checking the on-SCC patterns:
[s1, a][s2, b]
For state s1,outcome=a [in, ai], rule=1
message profile is
[[a, b, c], [b, a, c]], a, a, 0, 0
[[a, b, c], [b, a, c]], a, a, 0, 0
This action profile is a Nash equilibrium.
For state s2,outcome=b [in, ai], rule=1
message profile is
[[b, a, c], [a, b, c]], b, a, 0, 0
[[b, a, c], [a, b, c]], b, a, 0, 0
agent=1,Pzs=[1, 2, 3],Czs=[a, b, c],Lcc=[a, b, c] <is_best_response>
agent=2,Pzs=[1, 2, 4],Czs=[b, c],Lcc=[b, c] <is_best_response>
Br_Members=[1, 2]
This action profile is a Nash equilibrium.
checking the off-SCC patterns:
[s1, b][s1, c][s2, a][s2, c]
end <-----------------------[date(2003/5/4), time(16:51:46)]
Summary Result
[s1, a, nash_yes, scc_in]
[s1, b, nash_no, scc_out]
[s1, c, nash_no, scc_out]
[s2, a, nash_no, scc_out]
[s2, b, nash_yes, scc_in]
[s2, c, nash_no, scc_out]
Statistics
cputime= [21.8214, increased from, 1.01145]
inferences= [21724757, increased from, 768134]
atoms= [0, increased from, 3276]
functors= [0, increased from, 1931]
predicates= [0, increased from, 1844]
modules= [0, increased from, 26]
codes= [628, increased from, 68159]
agent=1,Pzs=[1, 2, 3],Czs=[a, b, c],Lcc=[a, b, c] <is_best_response>
agent=2,Pzs=[1, 2, 4],Czs=[a, c],Lcc=[a, c] <is_best_response>
Br_Members=[1, 2]
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
19
20
３．ゲーム木における情報モデリング
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
21
展開形ゲーム
• 展開形ゲームでは，
プレイヤーの手番
の順序と情報を
ゲームの木で表す．
• 各枝は，各プレイで
選択された行動に
対応する．
• ノード集合は，プレ
イヤーの識別でき
る情報構造に分割
される．
• 例えば，図2のゲー
ム木には，3つの情
報集合と2つの部
分ゲームがある．
b1
b2
[h1]-------->[h2]-------->[0.5,0]
|
|
a1 |
a2 |
|[h3]
V
V
[-0.5,-1]
[0,2]
a1->a2;
a1->b2;
a1->a2;
a1->b2;
b1->a2
b1->a2
b1->b2
b1->b2
---------------------------------------------a1 [ 0, 2] [ 0, 2] [ 0, 2] [ 0, 2]
*
*
*
*
*
*
b1 [-0.5,-1] [-0.5, -1] [0.5, 0]
[0.5, 0]
*
*
*
*
---------------------------------------------図2．展開形のゲーム木とその行動戦略の利得表
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
22
行動戦略
• 両プレイヤーはともに2種類の行動から1つを選
ぶが，後手は先手の行動を観察できるので，行
動戦略(behavior strategy)は4種類ある．
• これを標準形に変換すると図2の下の利得表と
なり，４つの均衡を得る．
• 実際にプレイされるのは [a1,a2]あるいは
[b1,b2]のうちいずれかの行動ペアであり，それ
ゆえ行動ルールの一部は実際に使われない反
事実的条件文(counterfactuals)となる．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
23
展開形ゲームを解くPrologモデル
• 以下は筆者のプログラム(nash1c.pl)を用いて，行動戦略におけるNEやSPE
を求めた結果である．ただし、木生成用の別のプログラムを用いてゲーム木
を表している。
• 行動戦略の標準形ゲームに翻訳したときの均衡
?- nash(behavior_strategy(g50(weak)),Players,A,P), Players=[1,2].
A = [a1, [ (a1->a2), (b1->a2)]]
P = [0, 2] ;
A = [b1, [ (a1->a2), (b1->b2)]]
P = [0.5, 0] ;
A = [a1, [ (a1->b2), (b1->a2)]]
P = [0, 2] ;
A = [b1, [ (a1->b2), (b1->b2)]]
P = [0.5, 0] ;
No
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
24
３．１部分ゲーム完全均衡
• 完全情報ゲームとはすべての情報集合が単一要素集
合，つまりプレイヤーがいつでも自分の手番のノードを
識別できる場合である．そうでない場合は不完全情報
ゲームと呼ばれる．ただし不完全情報でも通常，一度
通った経路は覚えているという完全想起(perfect
recall)が仮定される．
• 部分ゲーム完全均衡(subgame perfect equilibrium;
SPE)はR. Seltenによって導入された．SPEはどの部
分ゲームでも最適反応である行動戦略である．ただし
部分ゲームとは，各情報集合以降のプレイが，他の部
分ゲームと交差せず，一つのゲームの木になっている
ものとする．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
25
3.2 後向き帰納推論
• 後向き帰納推論(backward induction)を図2の木に対して適用
すると、後手は情報集合[h2]以降の部分ゲーム，つまり先手の
プレイb1を観察後，b2だけが最適反応である．また先手がa1を
プレイすれば，後手はどう選んでも最適反応である．先手はこ
れを知っているから，ｂ1が最適であると結論する．
• こうして[b1,b2]のみが合理的な解として残る。すべての葉から
上のような後向き推論を施せば，部分ゲーム完全均衡に一致
する．
b1
b2
->[h1]------->[h2]------->(0.5,0)
|
|
a1 |
a2|
|
|
V
V
(0,2)
(-0.5,-1)
b1
b2
->[h1]------> (0.5,0)
|
a1 |
|
V
(0,2)
-> b1,b2
(0.5,0)
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
展開形ゲーム（完全情報）の
部分ゲーム完全性のPrologモデル
• 最初の2つの均衡の部分ゲーム完全性を検証する
?- subgame_perfect(g50(weak), Players,A,P), Players=[1,2].
trial([0, 2], [a1, a2], [a1, [ (a1->a2), (b1->a2)]])
subgame(player:1/[1, 0], [a1, [ (a1->a2), (b1->a2)]], [0, 2])ne
subgame(player:2/[0, 2], [a1, [ (a1->a2), (b1->a2)]], [0, 2])ne
subgame(player:2/[0, 2], [b1, [ (a1->a2), (b1->a2)]], [0.5-1, -1])
defeated_by([[b1, [ (a1->a2), (b1->b2)]], [0.5, 0]])
trial([0.5, 0], [b1, b2], [b1, [ (a1->a2), (b1->b2)]])
subgame(player:1/[1, 0], [b1, [ (a1->a2), (b1->b2)]], [0.5, 0])ne
subgame(player:2/[0, 2], [a1, [ (a1->a2), (b1->b2)]], [0, 2])ne
subgame(player:2/[0, 2], [b1, [ (a1->a2), (b1->b2)]], [0.5, 0])ne
A = acts([b1, [ (a1->a2), (b1->b2)]])
P = payoffs([0.5, 0])
Yes
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
26
27
4. 知識水準でのゲームモデリング
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
28
共通知識の研究
• 合意定理
– Aumann[Aumann 76]は，共通知識(common knowledge)を初めて定式
化し，不一致に合意しえないという直観をきちんと証明した．
• 投機定理（無取引結果）
– MilgromとStokeyはAumannの結果を不完全情報下の取引ゲームに一
般化し，合理的取引の不可能性の結果を示した．
– またこの結果は各自のペイオフが、シグナルの単調変換である場合の０
和ゲームとその合理化可能戦略均衡に一般化できる（戦略的補完性の
議論の応用）。
• 取引者のモデリング
– 以下ではMilgromとStokey[Milgrom 82]の例に沿って，3種類の知識水
準での取引者とその推論をPrologによってモデリングする．
– 共通知識研究の文脈も含めたゲーム理論の入門書として、[Fudenberg
91] が便利だろう。より手ごろな入門書で和書では例えば[Muto 01]があ
る。 [Imai 01]は進化ゲームなど最近の動向の紹介。
– また筆者のプログラム(trade.pl)と関連するレビュー記事 [Indo 03]も参照．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
29
共通知識の研究（２）：後方帰納
• Aumann(1995 GEB 8: 6-19)
– 完全情報ゲームにおいて、ゲーム開始時点で、各プレイヤー
の「合理性」を共通知識と仮定すると、論理的証明能力を持
つプレイヤーは後方帰納解（バックワードインダクション解）を
推論できる。
• Aumann(1998 GEB 23: 97-105)
– 上の結果は、プレイヤーの合理性が反事実的条件文の意味
でモデリングされている必要がある。すなわち、プレイヤーが
到達しないと知っているノードにおいても期待効用最大化を
仮定している。
– 上の仮定を緩和し、実質含意の意味での合理性（つまり実際
に到達するノードでの最大化行動のみ）を仮定した場合、上
記の結果は覆る。ただし、ローゼンタールのムカデゲームな
ど特殊ケースでは、実質含意のモデリングでも、後方帰納解
が導かれる。
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
30
4.1 不完全情報と取引のモデリング
•
•
状態の有限集合Ω，事象の集合2Ω，取引者の集合をN={1,2}とする．
各プレイヤーiの情報構造Hi は，Ωの非空部分集合すなわち情報集合を値とする状
態s∈Ωの関数Hi(s)⊆Ω，φ≠Hi(s)として定義される．
Players＼ state
Partition＼
s1
s2
s3
s4
s5
---------------------------------------------------H1
a
b
b
c
c
H2
x
x
y
y
z
----------------------------------------------------
図3．パーティション情報構造の例(Milgrom and Stokey,1982)
•
•
図3はMilgromとStokeyの例題における取引者の情報構造を表す．この例題のよう
に，各プレイヤーの情報構造がΩのパーティションである場合をパーティション情報
構造という． Prologでは例えば次のように書ける．
情報構造
partition(1,s1,[s1]).
partition(1,S,[s2,s3]):-member(S,[s2,s3]).
partition(1,S,[s4,s5]):-member(S,[s4,s5]).
partition(2,S,[s1,s2]):-member(S,[s1,s2]).
partition(2,S,[s3,s4]):-member(S,[s3,s4]).
partition(2,s5,[s5]).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
31
相互知識の推論
• 状態sにおける各取引者の知識はK(s)E⇔Hi(s) ⊆E，また
• 共通知識はCK(s)E⇔M(s)=∪s∈E Hi(s) (∀i∈N)，M(s)⊆E．
• つまり共通知識は共通部分を有する情報集合の合併操作の収束先である
M(s)の下での知識である．またこれはプレイヤーが互いに可能と考えうる
状態を列挙することに等しい．図3の情報構造でM(s)はつねにΩに達する．
• 相互推論
think(J,S,is_possible(O)):- partition(J,S,H), member(O,H).
think(J,S,K):- K = think(_J1,O,_O1),think(J,S,is_possible(O)),K.
test_think(S,S1,X):- X=[S1,S2,S3,S4,S5,S6],
think(1, S1,
think(2, S2,
think(1, S3,
think(2, S4,
think(1, S5,
think(2, S6,
is_possible(S)
)
)
実行例
)
?- test_think(s5,s1,C).
)
C = [s1, s1, s2, s3, s4,
)
Yes
).
s5]
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
32
4.2 取引者のモデリング
• 図3の情報構造を仮定し，2名の取引者が交代手番で取引意向を表明する
過程をシミュレーションする．取引が行われた場合の各取引者の勝率などは
図4のようであるとする．
State
p(w1)
p(w2)
p(w2|s)
-------------------------------------------s1
.20
.05
1/5
s2
.05
.15
3/4
s3
.05
.05
1/2
s4
.15
.05
1/4
s5
.05
.20
4/5
---------------------------------------------
• 図4．取引ゲームの勝率(Milgrom and Stokey,1982)
• 取引が成立するためには，任意の時点以降，両者の意向がつねに一致しな
ければならない．合理的な取引者は自分のパーティションから，相手のパー
ティションや相手が想像する自分のパーティションについて推理する．ただし
各取引者は自分の勝率が1/2を越えないと取引しようとしないものとする．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
33
モデル１：素朴な取引者
% model of trader (1) --- naive expectation
% ------------------------------------------------- %
trader(naive,J,S,Q,D):partition(J,S,H),
win_prob_on_event(J,H, Q),
decision(Q,D).
decision(Q, ok):- Q > 0.5.
decision(Q, reject):- Q < 0.5.
decision(Q, indifferent):- Q = 0.5.
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
34
モデル２：浅読みの取引者
% model of trader (2) --- 2nd order expectation
% with a sort of certainty reasoning
% ------------------------------------------------- %
trader(sophist,J,S,Q,reject):trader(naive,J,S,Q,reject);
trader(naive,J,S,Q,indifferent).
trader(sophist,J,S,Q,ok):trader(naive,J,S,Q,ok),
partition(J,S,H),
\+ ( member(S1,H), agent(J1), J1 \= J,
trader(naive,J1,S1,_Q1,reject)).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
35
モデル３：合理的期待
% model of trader (3) --% expectation under common knowledge of rationality
% ------------------------------------------------- %
trader(rational,J,(T,S),Q,D):state(S), time(T/N), T > 0,
agent(J), move(J,T/N,yes),
delay(T,1,T1), %T1 is T - 1,
partition(J,T1/N,S,H),
win_prob_on_event(J,H, Q),
decision(Q,D).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
36
観察
• 最初の2タイプの取引者は静的パーティションである．
• 合理的な取引者(モデル3)は，各時点で相手からの取
引の申し出の可能性を再推論し，不可能な状態を削除
することにより，動的にパーティションを（またそれゆえ
に共通知識を）更新する．
• シミュレーションによって，理論どおり，モデル3の取引
者はどの状態でも取引に応じないことが，確かめられ
る．
• 一方，過渡的には合理的に期待するエージェントでも
合意するケースがあることが分かった．
• また例題の情報構造を非パーティションに変更するこ
とにより，取引発生を確認できた（[Indo 03]）．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
取引交渉のモデリング：情報と知識の更新
/* dynamic knowledge updated by messages */
%----------------------------------------------partition(J,T/N,S,H):time(T/N),
partition(J,S,H1),
remove_impossible_states(J,T/N,S,H1,H).
%
know(J,T/N,S,E):time(T/N),
agent(J),
state(S),
partition(J,T/N,S,H),
% remove_impossible_states(J,T/N,S,E,H),
(length(H,1)->E=H;true),
event(E),
subset(H,E).
%
remove_impossible_states(J,T/N,S,E,H):time(T/N),
agent(J),
state(S),
event(E),
findall(X,
think(J,T/N,S,is_impossible(X)),
D),
subtract(E,D,F),
sort(F,H).
think(J,T/N,S,is_impossible(O)):agent(J),
time(T/N),
state(S),
state(O),
\+ think(J,T/N,S,is_possible(O)).
%
think(J,0/N,S,is_possible(O)):time(0/N),
think(J,S,is_possible(O)).
think(J,T/N,S,is_possible(O)):time(T/N),
T \= 0,
%T1 is T - 1,
delay(T,1,T1),
think(J,T1/N,S,is_possible(O)),
is_consistent_with_information(T,S,O).
/* the supporting evidence of state */
%----------------------------------------------is_consistent_with_information(T,S,O):time(T/_N),
state(S),
state(O),
agent(J),
trader(rational,J,(T,S),_Q,D), % real.
trader(rational,J,(T,O),_Q1,D). % expected.
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
37
Prologによる取引シミュレーション（１）
•
ホームページに掲載したPrologプログラムtrade.plは， Milgromと
Stokeyの例題における相互知識推論と意思決定をシミュレートする．これ
は基本的に帽子パズルと同じアルゴリズムによって再現される．以下にそ
の実行画面の一部を示す．
?- trader(naive,J,s3,Q,D).
J=1
Q = 0.666667
D = ok ;
J=2
Q = 0.666667
D = ok ;
?- trader(rational,J,(T,s3),Q,D).
J=1
T=1
Q = 0.666667
D = ok ;
J=2
T=2
Q = 0.666667
D = ok ;
J=1
T=3
Q = 0.5
D = indifferent ;
No
?- trader(sophist,J,s3,Q,D).
J=2
T=4
Q = 0.5
D = indifferent ;
J=1
Q = 0.666667
D = ok ;
J=1
T=5
Q = 0.5
D = indifferent ;
J=2
Q = 0.666667
D = ok ;
J=2
T=6
Q = 0.5
D = indifferent
No
Yes
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
38
Prologによる取引シミュレーション（２）
•
状態ｓ４では元のパーティションの場合，
シミュレーション結果を見ると，確かに最初
は１も仮の合意をしているが，２の返答を聞
いた後，やはり翻意して拒絶する．
?- trader(rational,J,(T,s4),Q,D).
J=1
T=1
Q = 0.555556
D = ok ;
J=2
T=2
Q = 0.666667
D = ok ;
J=1
T=3
Q = 0.25
D = reject ;
≫Milgrom & Stokey のNo Trade
Resultの検証
（Continued)
J=2
T=4
Q = 0.75
D = ok ;
J=1
T=5
Q = 0.25
D = reject ;
J=2
T=6
Q = 0.75
D = ok
Yes
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
39
取引シミュレーション(非パーティション)
• プログラムtrade.plで，エージェント
のパーティションの部分を次のよう
に変更した後，ｓ４で trader/5 を実
行すると，取引への合意が達成さ
れる．
• また他のいずれの状態においても，
合意が成立する．
• 非パーティション情報構造のモデル
partition(1,s1,[s1,s2,s3,s5]).
partition(1,S,[s2,s3]):member(S,[s2,s3]).
partition(1,s4,[s4,s5]).
partition(1,s5,[s5]).
partition(2,s1,[s1]).
partition(2,s2,[s1,s2]).
partition(2,S,[s3,s4]):member(S,[s3,s4]).
partition(2,s5,[s1,s3,s4,s5]).
?- trader(rational,J,(T,s4),Q,D).
J=1
T=1
Q = 0.555556
D = ok ;
J=2
T=2
Q = 0.666667
D = ok ;
J=1
T=3
Q = 0.555556
D = ok ;
J=2
T=4
Q = 0.666667
D = ok ;
J=1
T=5
Q = 0.555556
D = ok ;
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
40
41
おわりに
•
Prologは定理自動証明研究から派生したプロ
グラミング言語であり，期待どおり，比較的簡
単な各種のゲーム分析とプレイヤーの推論を
表せた．ゲーム木の扱いなどになお改良の余
地があるが，今後，ゲームデザインとインテリ
ジェンスの関係を理解するために役立てたい．
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003
42
参考文献
• [Aumann 76] Aumann, R. J.: Agreeing to disagree, Annals
of Statistics 4: 1236-1239 (1976).
• [Fudenberg 91] Fudenberg, D. and J. Tirole: Game Theory，
MIT press (1991).
• [Imai 01] 今井晴雄･岡田章: ゲーム理論の新展開，勁草書房
(2001).
• [Indo 02] Indo, K.: Implementing Nash implementation
theory with Prolog: A logic programming approach, 第6回実
験経済学コンファレンス予稿(2002)
• [Indo 03] Indo, K.: Common knowledge，mimeo (2003),
http://www.us.kanto-gakuen.ac.jp/indo/kw/ck03b.html.
• [Milgrom 82] Milgrom, P. and N. Stokey: Information, trade
and common knowledge, Journal of Economic Theory 26:
17-27 (1982).
• [Muto 01] 武藤滋夫: ゲーム理論入門，日経文庫 (2001).
The 17th Annual Conference of the Japanese Society for Artificial Intelligence, 25-27, June 2003

Download Report