Prologで抽象的な社会選択環境でのナッシュ遂行理論をシミュレートする

本プログラム(impl.pl)についての略説・お断り

date: 23 Jan;2 Feb;16 Feb 2003.
update: 15 Mar; 8-9,11-16, 23 Nov 2005, 1 Feb 2006.

はじめに

本プログラムは抽象的な社会選択環境でのナッシュ遂行理論の基本要素と例題を Prologで動かしてみようと実験的に作成したものです。
最新のバージョンは、impl13bです。ドキュメントとしては本ページ以外にimpl12以前のものについて、学会報告や紀要で紹介してあります。

論文など

紀要：ナッシュ遂行のシミュレーション。(pdf 315KB) ●
学会報告:Implementing Nash Implementation Theory on Prolog: A Logic Programming Approach ●(postscript 221KB)　スライド(150KB)● その付録(700KB)●

ソースコード

以下のソースコードは、Prolog言語を用い、Sep 2002--Jan 2003にかけて作成された。 Mar 2005に一部改訂、Oct-Nov 2005にコードの修正を含む見直し、また強ナッシュ遂行への拡張を行った。

暫定版（02/9/3）●source (impl903.pl)
簡略版●source ( jasmin02.pl) 経営情報学会（JASMIN）の報告要旨中のプログラム。メカニズムのところだけ、論文では独裁的Sccであるが、Moore＆Repulloのそれになっている。
改訂版（03/1/8）●source (impl12.pl) swi-prolog 5.0.9に対応.
強ナッシュ遂行への拡張（05/10/24-11/15）●source (impl13b.pl) 強ナッシュ遂行への一般化と共に、基本的な部分のコードを洗い直した。 Suh(1996)の例題(モデル名：suh)を遂行する表メカニズムgST ◇（test_implによる実験結果）や Moore&Repullo(1990)の例題(モデル名：mr)を遂行する表メカニズムgTmr および条件μ２とメカ二ズムgMR2を改訂した。 ◇（gMR2のモデルmrに対する全出力）

主な構成要素

主な構成要素は次のようです。

合理的選好順序（領域モデル）
特殊な集合の生成・検証：
- 劣位集合(Lcc)、
- 本質的集合(Ess)、
- 最適反応、
- その他
社会選択対応SCCとその諸性質:

Maskinの単調性や（弱い）拒否権なし（NVP)、
パレート最適性、
Moore-Repullo の条件μ、
Danilovの本質的単調性、ブロック関係など
C_starのアルゴリズム：
メカニズムgMR, gMR2で用いられるSjostromの忌避的代替案反復消去。
C_Tのアルゴリズム：
強ナッシュ遂行で用いられるSuhのアルゴリズム。C_starの一般化
C_T_mなどの帰納的ルールの参照と変数状態をウォッチするルール。

SCCの自動生成。またこれらを応用した、諸命題・諸定理の具体例の生成および検証。
たとえば２人非制限領域の場合の不可能性定理、最小自由主義の背理の検証。
メカニズムの（強）ナッシュ均衡および（強）ナッシュ遂行シミュレーション
- Maskin-Vindの正準メカニズムgM：本質的単調性を満たすSCCを３人以上のメンバーで遂行する。多くの研究者によって改良され、今の形になった。
- 最小化メッセージスペースgMM：選好プロフィールの報告を、リングバッファの隣と自分自身に制限しても同じ結果が得られる。
- Moore&Repullo(1990)のメカニズムｇMRとｇMR2：とくに後者は２人の制限領域の場合。
- 独裁メカニズムｇDict：独裁者（Dictator）を指定し、そのいわれるとおりにする。
- DanilovのメカニズムgD：２人非制限領域（線形）での遂行。
- 表型メカニズムgST: Suh(1996)の例題を強ナッシュ遂行する間接メカニズム。
- 表型メカニズムgTmr:Moore and Repullo(1991)の例題をナッシュ遂行する間接メカニズム。
ドメインモデルの設定(set_model)
- モデルベースごとに設定済みのデフォールトのSCCとゲームフォームを変更して利用でき、
- 標準のナッシュ均衡と強ナッシュ均衡を切り替えできる。
シミュレーション用スクリプト test_impl/0
- test_implは、on-SCCのケースでは、各選好プロフィール（状態）でSccに一致する１つの均衡を見つけようとします。
- off-SCCのケースでは反例となる均衡を見つけようとします。

開発環境・期間・改訂

2002年９月まで。一部を除きSWI-PROLOGの旧版(1.9.0)のWindows版のみでテストした。
翌年1/8の改訂からはSWI-PROLOG 5.0.9 Windows版に対応した。数値計算の精度、動作の安定が得られた。
2002年9月以降の改訂：メカニズムgM、gMR、gMR2のデバッグ。条件μとSCC抽出ルーチン改良、シミュレーション用CUIの改良（test_nashとtest_impl）、メニュー wsid追加。
2005/11/08 強ナッシュ遂行のモデリングを追加した。翌11/09、ゲームフォームgTmr追加。
- 強ナッシュ均衡への一般化、
- Suhの例題のための表メカニズムgST
- 強ナッシュ遂行シミュレーション、
- および帰納的集合C_Tのアルゴリズム、
- (11/9)Moore＆Repulloの例題のための表メカニズムgTmr。
- (11/12-16)条件μ(iv)とgMR2の改訂。またtest_nashにおけるメッセージ生成を、若干効率化しました。
また今回、じゅうらいのコードについても大幅に見直した。
- メッセージ空間とゲームフォーム、
- 最適反応とナッシュ均衡、
- 遂行シミュレーション(test_impl)、

利用方法

実行環境：
数世代台前までのPC、そう、Windows Me標準装備の時代以前のノートPCでも、このプログラムは動きます。が、実験すると、遅くてイヤになるでしょう。多くのコードはWindowsXPでクロック1GHz程度のマシンで開発しました。
使い方：
- まず選好領域とデフォールトのSCCを設定する。
- その領域上でSCCの自動抽出ができる。
- またメカニズムの遂行シミュレーションでは、
  - まずオンラインモードとファイル一括出力処理のいずれかを選ぶ（ただしオンラインモードではメッセージ生成が不完全になるバグあり）。
  - 前者はナッシュ均衡の単生成やud22のような小領域上の遂行シミュレーションや正直遂行の簡易シミュレーション向き。
  - 後者はメカニズムの全出力を精査したい場合。
計算手間：
- 最適反応を記録（br_result/1）し、再利用するので、最初のナッシュ均衡を探すまでにやや時間がかかるが、いったん実行すれば再現ランはかなり早くなる。
- メッセージ生成は、正直遂行をデフォールトとし、整数値も０に制限した(Mode=truthful(0))。よってもし遂行できるSCCであれば、計算が楽になる。ただし遂行不能な場合、バックトラックを始める。
- 理論どおりフル生成するには、モードでfull(Z)を選び、整数部Zを変数にしておく。ただし時間がかかる。
- 領域を設定するコマンド(setup_domain)で、メカニズムの出力を、前処理で事実節に登録しておけるようにした。
- しかし、フル生成すれば、いずれにせよ小さな領域でも、かなりの時間を要することがある。 (impl12以前のバージョンでは、)たとえば制限領域jpで遂行可能なg１をｇMでテストするのに、 1.2GHzCeleron+128MBメモリのノートPCで、ほぼ３日かかった。０抑制すれば数時間、正直モードなら数十秒から数十分といったところ。
- impl13bでは、1.6GHz程度のマシンで、０設定、正直モードでなら、オンラインモードで数秒から数分で、ud22（ｇＤ）、ｍｒ（ｇＭＲ２）、ｊｐ（ｇＭ）などの主なモデルを試せる(test_impl)。

不具合(?)

ｇDでは(ud22上のparなど）非独裁的パレート対応を遂行する。

以下のようにｇMR2ではMoore＆Reppullo(1991)の例題（領域とSCC:mr）で対応外の（s2，c）が均衡になる。

?- prefer_profile([1,2],s3,M),
prefer_profile([1,2],s4,M1),
Ms=[1:(M,c,a,0,0),2:(M1,c,a,0,0)],   % for new version impl13b.pl 
%Ms=[(M,c,a,0,0),(M1,c,a,0,0)],   % for earlier versions
nash(c,s2,Ms,gMR2(2,mr),h0,_,[1,2],yes).


For state s2, outcome c  [out, mr], rule 2  
and message profile: 
 1: ([[a, c, d, b, z], [b, d, c, a, z]], c, a, 0, 0)
 2: ([[a, d, c, b, z], [b, c, d, a, z]], c, a, 0, 0)

 agents=[1],Pzs=[1, 2, 3],Czs=[b, c, z],Lcc=[b, c, z] 
 
 agents=[2],Pzs=[1, 2, 4],Czs=[a, c, z],Lcc=[a, c, z] 
 
best response groups:
[[1], [2]]

This action profile is a  Nash equilibrium.

M = [[a, c, d, b, z], [b, d, c, a, z]]
M1 = [[a, d, c, b, z], [b, c, d, a, z]]
Ms = [1: ([[a, c, d, b, z], [b, d, c, a|...]], c, a, 0, 0), 2: ([[a, d, c, b|...], [b, c, d|...]], c, a, 0, 0)] 

Yes
?-

選好順序（１＼２）

[b, c, d, a, z]

[b, d, c, a, z]

[a, c, d, b, z]

ｃ（ｓ１）

ｃ（ｓ３）

[a, d, c, b, z]

ｃ（ｓ４）

ｄ（ｓ２）

図 1. 例題モデルｍｒにおける選好順序（状態）とSCC

診断

本システムのモデルｍｒにおける状態ｓ１、ｓ２、ｓ３、ｓ４は、 Moore＆Repullo(1990)では選好プロフィール γ、δ、θ、φにそれぞれ対応しています。 SCCはモデルｍｒで状態ｓ２のときｄ、それ以外はｃです。選好はｃとｄの間だけ変化します。１はつねにaをｂより好み、２はその逆、両者ともｚはつねに最悪です。上図１参照。
上記出力結果については、２者がそれぞれs3とs4のプロフィールと希望するＳＣＣ結果ｃを吐き、その代替案はともにａ、反論フラグ、整数ゲームはいずれも０。これがルール2の下でナッシュ均衡となっているが、一方、条件μ２を満たしているから、理論に反している。
SjorstromのアルゴリズムC_starはCzs（実際のattaibnable set)と一致しており、その共通集合（述語mreによる）は[c,z]である。
不本意ながら上記の開発時期にこのミスをつぶせず、ようやく、以下のように問題は修正できました。
処置
05/11/11-16 コード全体の見直しと強遂行の追加にともない、上記の問題も見直し、ようやく理解とモデリングの誤りが分かりました。
「attainable setの交わり [c,z]にｄが入らない」ということばかり気にしていましたが、そうではなく、cを出力させないことが重要でした。「最悪のｚがあれば条件μ(iv)をvacuousに満たす」という論文の一節で気づきました。
まず２以下の種類のケアレスミスを発見し訂正しました。
- ゲームフォームごとの制限(ristrict_on_forms/2)で、gMR2最後の６個目が無効とされていた。
- またmre/5で共通極大元を求めた後、Ｓｃｃ内のメンバーであることをチェックしていなかった。
しかし上記の現象は再現しました。つまりｓ２において（ｓ３、ｓ４）のプロフィールがクロスで主張されると、共通の極大要素としてｄをとることはできず、ｃを出力してしまう。
ちなみに条件μ(iv)の意味は、「すべての」選好プロフィールで「交差する極大要素でなければＳｃｃに入る縛りはないが、そうならばＳｃｃに入らないといけない」、そういう要素が欲っされています。
処置として、μ(iv)を分解して共通極大元を求めるルール select_common_maximal_element_in_scc/3を作成し、mre/5の代わりにgMRで用いるように変更しました。
条件μ２のコード自体はまちがいではありませんでした。論理的な意味としては、分解した新しいルールよりも以前のコード (impl12まで)の方がモデリングとしてはむしろ率直です。なお、検索の便宜で、コード中ではμをmjuとつづっています。

以前のバージョンでのその他の不具合

gMRなどで不安定。SWI-Prolog 5.0.9では少し改善される。
再帰のコードでデータ不整合による異常終了はありがちです。
なお実行中の中断は、Ctrl＋Cで可能ですが、制御が戻らないときは、タスクマネジャーからプロセスを殺すしかない場合もあります。

おわりにかえて

　比較的大きなPrologプログラムとして初めて手がけたものです。気づいていない不具合や理解の誤りが残っているかもしれません。あらかじめお詫び＆お断りしておきます。今回、強ナッシュ遂行への拡張を含めて、気になっていたバグをとることができました。reversionやeffectivity functionなど、やりのこしもあります。表型メカニズムの自動生成が目下の課題です。