藤代康誠 長谷部浩二メカニズムデザインは，ゲーム理論の枠組を用いて，設計者または社会全体にとって望ましい結果が生まれるような調度（メカニズム）を設計する手法である。特に，設計者がプレイヤーの行動を直接制御することなく，プレイヤーの合理的な行動によって望ましい結果が達成されるようにすることが中心的な課題である。こうした手法をもとに,これまでオークションをはじめとする数多くのメカニズムが提案されてきた．しかしながら，メカニズムが設計者の意図通りに目的を実現できるかどうかは，一般に判定が容易ではない．とりわけ，メカニズムで意図した結果が，支配戦略均衡によるものではなく，ベイジアンナッシュ均衡のようなより緩和された均衡によるものである場合，プレイヤー同士による相手の戦略に関する推論まで分析する必要があり，分析は困難なものとなる．そこで本研究は，認議論理をもとに，プレイヤーの知識状態や推論に注目したメカニズムの分析手法を奨案する．特にここでは，与えられたメカニズムによって意図した結果が実現できることを，Public Announcement Logicと呼ばれる論理体系の中で証明する方法について述べる.
1　研究の背景と目的
複数の自律的主体（エージェント）によって構成されるシステムを制御する手法として，ゲーム理論が注目されている。ゲーム理論は，複数の主体（プレイヤー）の行動が相互に影響し合う状況（ゲーム）において，各プレイヤーが自分の利益を可能な限り大きくすることを目標に行動を選択するとき，どのような結果が起こるのかを分析する理論である。（ゲーム理論の詳細については文献[1]などを参照のこと.）与えられた状況から起こり得る結果を予測するのがゲーム理論の主要な目的であるのに対し，起こってほしい結果を実現するルールを求める理論はメカニズムデザインと呼ばれ，ゲーム理論の応用として位置づけられている。メカニズムデザインでは，各プレイヤーが自身の利得の最大化を目指して行動した結果が，起こってほしい結果と一致するようにゲーム（メカニズム）を設計する。メカニズムデザインは，主に経済学の分野において，望ましい社会制度の設計を目的として研究されてきたが，近年ではマルチエージェントシステムをはじめとする自律分散型のシステムの設計にも応用されている。(メカニズムデザインの詳細については，文献[4] [5]などを参照のこと.）メカニズムデザインが現実の問題に適用されている例としては，オークションの分析が挙げられる．例えば，英国式とよばれるオークションの方式では，商品の価格を競り上げていき，最後まで入札を降りなかった人が，最後の一人になった時点の価格で商品を落札する.この方式のオークションにおける最良の戦略は，商品の価格が，その商品に対して感じている価値を超える直前までは入札を続け，それより高い価格になった瞬間に降りる，というものである．すなわち，英国式オークションでは，商品に対する自分の評価を偽った入札をする誘因は生じず，商品は最も高い評価を付けている人に落札されるような留ましいルール設計になっていることが示される.オークションの方式には英国式の他にも様々なものがある。例えば，英国式のように入札状況を公開しながら進行する方式だけでなく，入札状況を非公開にする方式も存在する。これらはそれぞれ公開入札方式・封印入札方式として区別されている。このように，現実の問題にメカニズムデザインを適用する際には，メカニズムを実行するための手続き（プロトコル）としてどのような方法を採用するかを考慮する必要がある。特に，プロトコルごとの情報公開の方法の違いは，プロトコル実行中のプレイヤーの知識に変化をもたらし，意思決定に影響を与える可能性がある．しかしながら，既存のメカニズムデザインの枠組では,そのようなプレイヤーの知識の変化による影響が十分に考慮されていない.そこで，本研究では，メカニズムを実行するためのプロトコルにおける情報公開の方法の違いが最終的な結果に及ぼす影響を，認識論理を用いて分析する．特にここではPublic Announcement Logicと呼ばれる論理を用い，プレイヤー問の知識に関する推論を定式化することにより，最終的な結果を考察する．プレイヤー間の知識に関する推論とは，具体的には,「プレイヤー 2は『プレイヤー 1は¢を知っている』ということを知っている」といった形の文で表されるような，知識の入れ子構造をもった事実に関する推論のことである。知識に関する推論は，相手の思考を読み，最良の意思決定をするために必要不可欠である。認識論理では，K t ¢という記法によって,「プレイヤー iは￠を知っている」という内容を表すことができる.この記法を用いると，前述の「プレイヤー 2は『プレイヤー 1はφを知っている』ということを知っている」という内容はK₂K₁φと簡潔に表すことができる。このように，認識論理を用いることで，知識に関する推論の形式的な分析が可能になる.本稿では，例として投票のメカニズムとそれに対するいくつかのプロトコルを考え，プレイヤーの知識の変化やそれに伴う意思決定をどのような方針で定式化するのかを示す.
2　対象とするメカニズム
本稿では，以下のメカニズムを用いて提案手法を説明する。ここでは比較的単純なメカニズムを対象とするが，本手法はより複雑なメカニズムに対しても適用可能である.ここで扱うメカニズムは2人の候補者のうち1人を投票によって選択するというものである．投票する権利を持った人（プレイヤー）は３人おり，各人は２人の候補者のうちどちらか一方を支持しているが，他のプレイヤーがどちらの候補者を支持しているかをあらかじめ知ることはできないとする。各プレイヤーは何らかのプロトコルにしたがってどちらの候補者に票を入れるのかを決定する。メカニズムおよびプロトコルの設計者の目標は，各プレイヤーに正直に投票をさせ，もっとも多くのプレイヤーに支持されている候補者を選択することである.この状況設定は形式的には以下の要素によって定義される。 ● プレイヤーの集合N = {1, 2, 3} ● 候補者の集合X = {a,b} ● 各プレイヤー iのタイプの集合Θ i = { a, b }, Θ = θ₁ × θ₂ × θ₃ ● 選択ルールf : Θ → Xただし，任意のθ ∈ θについて，
● メカニズムΓ = (Θ, ƒ) ● 各プレイヤー iの利特関数vi : Θ × Θ i → Rただし，任意のθ ∈ θと任意のθ ∈ θ ∈について,
(1) (2)
上記の定義において，タイプは各プレイヤーがどちらの候補者を支持しているのかを表す。選択ルールは,プレイヤーの真のタイプに対する望ましい候補者の選択を表す。メカニズムとしては，各プレイヤーがどちらかの候補者に投票し，より多くの票数を獲得した候補者が選択される方法を採用している．ただし，各プレイヤーが自分のタイプに正直に投票するとは限らない。プレイヤーは，意思決定の時点で自分のタイプと異なる候補者に投票した方が利得が高くなることを知っている場合には，自分のタイプを偽った投票をする．各プレイヤーの利待は， (i)自分のタイプと同じ候補者が選択されたか，(ii)自分の投票と同じ候補者が選択されたか，という２つの基準で定まるものとしている．式(1)においてθは各プレイヤーの投票を，θεはプレイヤー ε自身の真のタイプを表しており，式(2)， (3)はそれぞれ基準(i)， (ii)に対応している.
3論理体系
本研究では，PlazaによるPublic Announcement Logic (PAL) [2][3]を論理体系として用いる．PALは，通常の命題論理に，知識を表す様相演算子と，プレイヤーに対する情報の伝達を表す様相演算子を加えた論理体系である.原子命題としては，次のものを定義する． ●任意のｉ∈ N , ｘ∈ Xについて, decl(i) = x ●任意のi ∈ N ,  x ∈ Xについて,  eval(i) = x ●任意のi ∈ Nについて，decl(i) =?ここで，decl(i) = xは「プレイヤー」は候補者ェに投票する」という内容を表し，eval(i) = xは「プレイヤー iは真のタイプにおいて候補者rを支持する」という内容を表す。また，decl(i) =?はプレイヤー iが支配戦略を持たないことを表す。 さらに,「プレイヤー iは真のタイプにおいて支持する候補者に投票する戦略を取る」という内容を表す論理式decl(i) = Tを(eval(i) = a → decl(i) = a) ∧ (eval(i) = b → decl(i) = b)で定義する。なお，ここでは可読性を考廊し，述語論理の記法を用いて説明しているが，これらの概念はすべて命題論理の原始命題として記述することが可能である.非論理公理としては，次のものを定義する．ただし，プレイヤーｉは真のタイプにおいて候補者ｘを支持しているとする. (a)  eval(i) = x (b)   K i eval(i) = x (c) ¬K 3 K 4 eval(i) = x  (ただし,  i ≠ j) (d) 任意のプレイヤーの列i 1 , i 2 , . . . , i nについて, K έ, K έ, . . . K έ, decl(i) =? (e) 互いに異なる任意のi,j,k ∈ Nについて, decl(i) =? ∧ decl(j) =? → decl(k) = T (f)互いに異なる任意のi,j,k ∈ Nについて, decl(i) = T ∧ decl(j) = T → decl(k) = T上記の定義において,  (a)はゲームの設定を表し,  (b), (c)はタイプに関するベイジアンゲームの仮定を表す.また，(d)はプレイヤー全員の利得関数が共有知識であることを表す.  (e)は相手の戦略が予想できない場合に，仮に相手の戦略がランダムであると仮定したときの最適反応が自分のタイプの通りに投票することであることを反映している．(f)は相手が正直に投票する戦略を取ったときの最適反応が，正直に投票する戦略であることを表している．(d)，(e)，(f)は対象とするメカニズムによっては成り立たない場合もあるが,今回対象としているメカニズムでは成り立っている.
4 PALを用いたプロトコルの分析
ここまでの定式化によって，単純なプロトコルの性質を示すことができる。ここでは，対象とするプロトコルとして，一切情報を公開せず投票を実施することを考える。このプロトコルではベイジアンゲームの仮定が満たされており，全員が正直に投票をするという結果がベイジアンナッシュ均衡として達成されると考えられるが，実際にこの性質をここまでの定式化によって証明することができる.証明の概略は次の通りである。以下ではi, j, kは互いに異なるプレイヤーであるとする. 1.公理 (d), (e) により K idecl(j)   =?  ∧ K i decl(k) =?からK i decl(i) = Tを導くことができる. 2.公理 (d),  (f) により K i decl (i)   =?  ∧ K i K i decl(k) =?からK i decl(i) = Tを, K 3 K 4 decl(j)  =? ∧ K 3 K 4 decl(k)  =?からK j K i decl(i)   =   T を,  K k K i decl(j)   =?  ∧ K k K i decl(k) =?からK i decl(i) = Tをそれぞれ導くことができる. 3.  2.で導いた式に対して，2.と同様の操作を続けることで，任意のプレイヤーの列i 1 , i 2 , . . . , in について，K i 1 K i 2 . . . K i n decl(i) = Tを導くことができる.したがって，各プレイヤー iについて，decl(i) = Tが共有知識となることが証明できる.これはゲームの結果として全員が正直に投票することを意味している.以上で述べたプロトコルでは，プレイヤーに対して一切情報を公開しないことを仮定したが，プロトコルの実行過程においてより多くの情報が公開される状況を考えると，一般にdecl(i) = Tは共有知識とならない．例えば，次のようなプロトコルを考えることができる. Step 1.各プレイヤーが第2章で述べた投票を行う. Step 2. プロトコルの調停者からプレイヤーに対して投票結果に関する情報が知らされる. (ここでは，投票の結果選ばれた候補者の名前だけが知らされる場合や，各人が誰に投票したかまで知らされる場合など，様々なプロトコルが考えられる.） Step 3.  Step 1に戻り，各プレイヤーはこれまでに待た情報をもとに再度投票を行う．全員の投票が変化しなくなるまでこれを繰り返す.こうしたプロトコルにおいては，先に考えたプロトコルと比べ，各プレイヤーはより多くの知識を得ることができるため、正直な投票以外の戦略が最適反応となる場合がある。本提案手法は，こうした微妙なプロトコルの違いによる共有知識の成立の有無について分析することを目的としている.
５結論と今後の課題
本稿では，メカニズムのプロトコルが最終的な結果に及ぼす影響について，認識論理を用いて分析する手法を提案した．さらに，単純な投票のメカニズムとプロトコルに対して提案手法を適用し，最終的な結果が正直な投票となることを確認した．今回対象としたプロトコルは情報の公開がないものであったが，今後は提案手法を拡張し，様々な情報公開の方法を取るプロトコルについて分析できるようにすることを目指す.