1対1のマッチング問題におけるベイジアンゲーム

メカニズムのもとでのゲーム

仮に、マッチメイカーが1対1のマッチング問題の真の状態、すなわちエージェントたちの真の選好を観察できるのであれば、観察した真の状態を基準に社会的に望ましいマッチングを特定し、それを遂行すればよいことになります。しかし、実際には、選好はエージェントが持つ私的情報であるため、マッチメイカーは真の状態を観察できず、したがって社会的に望ましいマッチングを事前に特定することはできません。そこで、マッチメイカーはエージェントたちに自身の選好を申告させた上で、申告された選好を基準に社会的に望ましいマッチングを特定し、それを遂行しようとします。このような資源配分ルールをメカニズムと呼ばれる概念として定式化しました。ただ、メカニズムに直面したそれぞれのエージェントは自身の真の選好を正直に申告するとは限りません。エージェントはより望ましい相手とマッチするために戦略的に行動しますが、その一環として、偽りの選好を申告する可能性があるからです。エージェントの選好は私的情報であるため、エージェントが嘘をついて真の選好とは異なる選好を申告しても、マッチメイカーはそれが嘘であるかどうかを知る術がないのです。エージェントたちが偽りの選好を表明する場合、マッチメイカーは偽りの選好の組を基準にマッチングを決定することとなり、それは真の意味で社会的に望ましいマッチングとは異なるものになってしまう可能性があります。情報の非対称に起因するこのような問題をインセンティブの問題と呼びます。

インセンティブの問題を引き起こす原因が情報の非対称性である以上、インセンティブの問題を解決するためには、何らかの方法を通じて情報の非対称性を解消する必要があります。具体的には、それぞれのエージェントにとって、自分の真の選好を正直に申告することが得であるようなメカニズムを設計すれば、そのようなメカニズムのもと、エージェントたちは自分の真の選好を自ら進んで正直に申告するため、結果として情報の非対称性は解消されます。以上のことをよりテクニカルに表現すると、メカニズムを提示されたエージェントたちが直面する戦略的状況をゲームとして記述したとき、そのゲームにおいて、「すべてのエージェントが自身の選好を正直に申告する」ことが均衡になるのであれば、そのようなメカニズムのもとで情報の非対称性は解消されるということです。ただ、そもそも、そのようなメカニズムを設計することは可能なのでしょうか。こうした問いについて考えるために、まずは、メカニズムを提示されたエージェントたちが直面する戦略的状況をゲームとして記述します。

1対1のマッチング問題において、マッチメイカーはメカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)を設計し、それをエージェントたちに提示します。仮にすべてのエージェントが提示されたメカニズム\(\phi \)に同意するのであれば、それぞれのエージェント\(i\in M\cup W\)は自身の選好\(\succsim _{i}\in \mathcal{R}_{i}\)をマッチメイカーへ申告することになります。その際、他のエージェントたちが申告する選好を事前に観察できません。また、エージェントは真の選好を正直に申告するとは限りません。いずれにせよ、エージェントたちが申告してきた選好からなる組\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)に対し、マッチメイカーはあらかじめ提示したメカニズム\(\phi \)にもとづいてマッチング\(\phi \left( \succsim _{M\cup W}\right) \in \mathcal{M}\)を選び取り、これを遂行します。その結果、それぞれのエージェント\(i\)は相手\(\phi _{i}\left( \succsim_{M\cup W}\right) \in M\cup W\)とマッチします。メカニズム\(\phi \)を提示されたエージェントたちが直面する以上のような戦略的状況をゲームとみなした上で、それを\(G\left( \phi \right) \)と表記し、これをメカニズム\(\phi \)のもとでのゲームと呼ぶこととします。以降では、このゲーム\(G\left( \phi \right) \)を構成する要素を具体的に特定します。

まず、このゲームのエージェントはマッチングに臨むエージェントたちであるため、ゲーム\(G\left( \phi \right) \)のエージェント集合は問題としている1対1のマッチング問題のエージェント集合\(M\cup W\)と一致します。

それぞれのエージェント\(i\in M\cup W\)は自身がマッチし得る相手どうしを比較する選好関係\(\succsim _{i}\)を私的情報として持っています。つまり、ゲーム\(G\left( \phi\right) \)におけるエージェント\(i\)のタイプは選好\(\succsim _{i}\)であり、タイプ集合は選好集合\(\mathcal{R}_{i}\)と一致します。エージェント\(i\)のタイプ\(\succsim_{i}\)はタイプ集合\(\mathcal{R}_{i}\)に属する様々な値を取り得ますが、\(\succsim _{i}\)の真の値を知っているのはエージェント\(i\)だけです。他の任意のエージェントやマッチメイカーは、\(\succsim_{i}\)のとり得る値の範囲\(\mathcal{R}_{i}\)を知っていますが、その中のどの値が真の値であるかは知らないものと仮定することで、エージェント\(i\)の選好が私的情報であるという状況を表現します。

メカニズム\(\phi \)に直面したそれぞれのエージェント\(i\)は自身の選好\(\succsim _{i}\)を申告する必要があります。したがって、ゲーム\(G\left( \phi\right) \)においてエージェント\(i\)に与えられた行動は自身が申告する選好\(\succsim _{i}\)であり、行動集合は選好集合\(\mathcal{R}_{i}\)と一致します。それぞれのエージェントは自身の真の選好を正直に表明するとは限りません。

エージェントたちが選択する行動からなる組、すなわち申告する選好からなる組が\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)であるとき、それに対してメカニズム\(\phi \)はマッチング\(\phi \left( \succsim _{M\cup W}\right) \in \mathcal{M}\)を選び取ります。行動の組\(\succsim _{M\cup W}\)が変われば選ばれるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)も変化しますが、どのように変化するかはメカニズム\(\phi \)の内容に依存します。以上がゲーム\(G\left( \phi \right) \)において起こり得る結果です。

エージェント\(i\)が結果どうしを比較する評価体系は、自身がマッチングどうしを比較するマッチング集合\(\mathcal{M}\)上に定義された選好\(\succsim _{i}^{\mathcal{M}}\)として記述されます。一般に、エージェントがマッチングどうしを比較する選好\(\succsim _{i}^{\mathcal{M}}\)の形状はすべてのエージェントの選好からなる組\(\succsim _{M\cup W}\)に依存するため、そのことを明示するために\(\succsim _{i}^{\mathcal{M}}\)を\(\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \)と表記します。つまり、ゲーム\(G\left( \phi \right) \)におけるエージェント\(i\)の選好は\(\succsim _{i}^{\mathcal{M}}\left[\succsim _{M\cup W}\right] \)であり、これは状態\(\succsim _{M\cup W}\)に依存するため、エージェント\(i\)の選好がとり得る値からなる集合は、\begin{equation*}\mathcal{R}_{i}^{\mathcal{M}}=\left\{ \succsim _{i}^{\mathcal{M}}\left[
\succsim _{M\cup W}\right] \right\} _{\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}}
\end{equation*}となります。

以上でゲーム\(G\left( \phi \right) \)の要素がすべて出揃いました。つまり、このゲームはエージェントが私的情報を持つ不完備情報ゲームであり、以下のようなベイジアンゲーム\begin{equation*}G\left( \phi \right) =\left( M\cup W,\left\{ \mathcal{R}_{i}\right\} _{i\in
M\cup W},\left\{ \mathcal{R}_{i}^{\mathcal{M}}\right\} _{i\in M\cup
W}\right)
\end{equation*}として定式化されます。ただし、\(\mathcal{R}_{i}\)はエージェント\(i\)のタイプ集合と行動集合を兼ねています。これをメカニズム\(\phi \)のもとでのゲームと呼ぶこととします。

ゲーム\(G\left( \phi \right) \)を構成するすべての要素はエージェントたちの共有知識です。それぞれのエージェント\(i\in M\cup W\)は自身のタイプ\(\succsim _{i}\)の真の値（便宜的にこれを\(\succsim _{i}^{\ast }\)と表記します）を知っていますが、他の任意のエージェント\(j\ \left(\not=i\right) \)のタイプ\(\succsim _{j}\)の真の値\(\succsim _{j}^{\ast }\)は知りません。エージェント\(i\)が他のエージェント\(j\)について知っていることは、\(\succsim _{j}\)がとり得る値の範囲\(\mathcal{R}_{j}\)だけです。したがって、エージェント\(i\)が直面し得る状態からなる集合は、\begin{equation*}\left\{ \left( \succsim _{i}^{\ast },\succsim _{-i}\right) \right\}
_{\succsim _{-i}\in \mathcal{R}_{-i}}
\end{equation*}となります。他の任意のエージェントについても同様の議論が成立します。また、ベイジアンゲームの静学性と不完備性より、ゲーム\(G\left( \phi \right) \)においてエージェントたちは以下の手順で意思決定を行います。

1. 自身の真のタイプ\(\succsim _{i}^{\ast }\in \mathcal{R}_{i}\)を知っているが他のエージェントたちの真のタイプ\(\succsim _{-i}^{\ast }\in \mathcal{R}_{-i}\)を知らないそれぞれのエージェント\(i\in M\cup W\)は自身の行動集合\(\mathcal{R}_{i}\)の中から特定の行動\(\succsim _{i}\)を選択する。その際、他のエージェントたちが選択した行動を観察できない。エージェント\(i\)が選択する行動\(\succsim _{i}\)は自身の真のタイプ\(\succsim _{i}^{\ast }\)であるとは限らない。
2. エージェントたちが選択した行動からなる組\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)に対して、メカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)がマッチング\(\phi \left( \succsim _{M\cup W}\right) \in \mathcal{M}\)を定める。
3. 真の状態\(\succsim _{I}^{\ast }\)とエージェントたちが選択した行動からなる組\(\succsim _{M\cup W}\)に応じて、それぞれのエージェント\(i\)は選好関係\(\succsim _{i}^{A}\left[\succsim _{M\cup W}^{\ast }\right] \)のもとで先のマッチング\(\phi \left( \succsim_{M\cup W}\right) \)を評価する。

エージェントの純粋戦略

メカニズム\(\phi \)のもとでのゲーム\(G\left( \phi \right) \)において、仮にすべてのエージェントが真の状態\(\succsim _{M\cup W}^{\ast }\)を把握しており、なおかつそのことが共有知識であるならば、それぞれのエージェント\(i\in M\cup W\)の選好が\(\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}^{\ast }\right] \)であることが確定するため、エージェントたちが直面する戦略的状況はもはや不完備情報ゲームではなく、以下のような完備情報ゲーム\begin{equation*}G\left( \phi ,\succsim _{M\cup W}^{\ast }\right) =\left( M\cup W,\left\{
\mathcal{R}_{i}\right\} _{i\in M\cup W},\left\{ \succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}^{\ast }\right] \right\} _{i\in M\cup W}\right)
\end{equation*}となります。ただし、\(M\cup W\)はエージェント集合、\(\mathcal{R}_{i}\)はエージェント\(i\)の行動集合、\(\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}^{\ast }\right] \)はエージェント\(i\)の選好関係です。これを\(\succsim _{M\cup W}^{\ast }\)のもとでの状態ゲームと呼ぶこととします。状態ゲーム\(G\left( \phi ,\succsim _{M\cup W}^{\ast }\right) \)は完備情報ゲームであるため、そこでのエージェントの戦略とは、単純に、エージェントが選択可能な行動の中から1つの行動を選ぶことを意味します。

ただ、実際にはゲーム\(G\left( \phi \right) \)において真の状態\(\succsim _{M\cup W}^{\ast }\)を把握しているエージェントは存在せず、それぞれのエージェント\(i\)は真の状態\(\succsim _{M\cup W}^{\ast }=\left( \succsim _{i}^{\ast },\succsim _{-i}^{\ast }\right) \)に関する断片的な知識、すなわち自身の真のタイプ\(\succsim _{i}^{\ast }\)に関する情報しか持っていないため、エージェントは複数の状態ゲームに直面し得る中で意思決定を行う必要があります。具体的には、エージェントが直面し得る状態ゲームからなる集合は、\begin{equation}\left\{ G\left( \phi ,\succsim _{i}^{\ast },\succsim _{-i}\right) \right\}
_{\succsim _{-i}\in \mathcal{R}_{-i}} \quad \cdots (1)
\end{equation}です。しかも、それぞれのエージェント\(i\)は自身が直面し得るそれぞれの状態ゲーム\(G\left( \phi ,\succsim _{i}^{\ast },\succsim _{-i}\right) \)に対して、そこで選択する行動をあらかじめ指定することはできません。なぜなら、エージェント\(i\)は他のエージェントたちのタイプ\(\succsim _{-i}\)を観察できず、ゆえに自分が\(\left( 1\right) \)に属するどの状態ゲームをプレーしているかを判別できないからです。したがって、エージェント\(i\)は特定の行動\(\succsim_{i}\)を事前に選び、その1つの行動のもとで、自分が直面し得る\(\left(1\right) \)に属するすべての状態ゲームに備えなければなりません。

エージェント\(i\)は自身のタイプ\(\succsim _{i}\)の真の値\(\succsim _{i}^{\ast }\)を知っているため、\(\succsim _{i}^{\ast }\)のもとで直面し得る状態ゲームの集合\(\left( 1\right) \)に対してのみ1つの行動を定めればよいと考えるかもしれませんが、この考えは誤りです。他のエージェント\(j\ \left( \not=i\right) \)の視点から考えてみると、エージェント\(j\)にとっての最適な行動はエージェント\(i\)の行動に依存するため、エージェント\(j\)はエージェント\(i\)の行動を予想しながら自身の行動を決定します。エージェント\(i\)の行動は自身のタイプ\(\succsim _{i}\)に依存しますが、エージェント\(j\)はエージェント\(i\)の真のタイプ\(\succsim _{i}^{\ast }\)を知らない以上、\(\mathcal{R}_{i}\)に属するそれぞれのタイプごとに、そこでのエージェント\(i\)の行動を予想した上で、その予想を踏まえた上で自身の行動を決定します。つまり、エージェント\(j\)の行動はエージェント\(i\)のそれぞれのタイプのもとでの行動に依存します。逆に、エージェント\(i\)の最適な行動はエージェント\(j\)の行動に依存しますが、エージェント\(j\)の行動がエージェント\(i\)のそれぞれのタイプのもとでの行動に依存する以上、エージェント\(i\)が自身の最適な行動を考えるためには、エージェント\(i\)は自身の真のタイプ\(\succsim_{i}^{\ast }\)とは限らない自身のそれぞれのタイプにおいて自分が何をするであろうか考える必要があります。つまり、真のタイプ\(\succsim _{i}^{\ast }\)とは異なるそれぞれのタイプ\(\succsim _{i}\)についても、エージェント\(i\)はその場合に自身が選択するであろう行動をあらかじめ定める必要があります。

以上を踏まえると、メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)においてそれぞれのエージェントは、自身のそれぞれのタイプごとに自身が選択するであろう行動を包括的に定めておく必要があります。具体的には、ゲーム\(G\left( \phi \right) \)におけるエージェント\(i\)の戦略は写像\begin{equation*}s_{i}:\mathcal{R}_{i}\rightarrow \mathcal{R}_{i}
\end{equation*}として定式化されます。この戦略\(s_{i}\)のもとで、エージェント\(i\)は自分のタイプが\(\succsim_{i}\in \mathcal{R}_{i}\)の場合には行動\(s_{i}\left( \succsim _{i}\right) \in \mathcal{R}_{i}\)を選択します。言い換えると、自身のタイプが\(\succsim _{i}\)である場合、戦略\(s_{i}\)のもとでは、エージェント\(i\)はマッチメイカーに対して自身のタイプが\(s_{i}\left(\succsim _{i}\right) \)であると申告するということです。このような行動計画\(s_{i}\)をエージェントの純粋戦略（pure strategy）と呼びます。

すべてのエージェントの純粋戦略からなる組を\(s_{M\cup W}=(s_{i})_{i\in M\cup W}\)で表し、エージェント\(i\)以外のエージェントたちの純粋戦略からなる組を\(s_{-i}=(s_{j})_{j\in \left( M\cup W\right)\backslash \left\{ i\right\} }\)で表します。\(s_{M\cup W}=\left( s_{i},s_{-i}\right) \)です。

エージェント\(i\)が選択可能なすべての純粋戦略からなる集合をエージェント\(i\)の戦略集合（strategy set）や戦略空間（strategy space）などと呼び、これを\(S_{i}\)で表します。\(s_{i}\in S_{i}\)です。すべてのエージェントの戦略集合の直積を\(S_{M\cup W}=\prod_{i\in M\cup W}S_{i}\)で表します。また、\(S_{-i}=\prod_{j\in\left( M\cup W\right) \backslash \left\{ i\right\} }S_{j}\)とします。\(s_{M\cup W}\in S_{M\cup W}\)かつ\(s_{-i}\in S_{-i}\)です。

メカニズムのもとでのゲーム\(G\left( \phi \right) \)においてエージェントたちが選択する純粋戦略からなる組が\(s_{M\cup W}\)であるとき、以下の形でゲームが進行します。

1. 自身の真のタイプ\(\succsim _{i}^{\ast }\in \mathcal{R}_{i}\)を知っているが他のエージェントたちの真のタイプ\(\succsim _{-i}^{\ast }\in \mathcal{R}_{-i}\)を知らないそれぞれのエージェント\(i\in M\cup W\)は自身の純粋戦略\(s_{i}\)にもとづき選好\(s_{i}\left( \succsim _{i}^{\ast }\right)\in \mathcal{R}_{i}\)を選択し、それを申告する。その際、他のエージェントたちが申告する選好を観察できない。エージェント\(i\)が申告する選好\(s_{i}\left( \succsim _{i}^{\ast }\right) \)は自身の真の選好\(\succsim _{i}^{\ast}\)であるとは限らない。
2. エージェントたちが申告した選好からなる組\(s_{M\cup W}\left( \succsim _{M\cup W}^{\ast}\right) =\left( s_{i}\left( \succsim _{i}^{\ast }\right) \right) _{i\in M\cup W}\in \mathcal{R}_{M\cup W}\)に対して、メカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)がマッチング\(\phi \left( s_{M\cup W}\left( \succsim _{M\cup W}^{\ast }\right) \right) \in \mathcal{M}\)を定める。その結果、それぞれのエージェント\(i\)は相手\(\phi _{i}\left(s_{M\cup W}\left( \succsim _{M\cup W}^{\ast }\right) \right) \in M\cup W\)とマッチする。