教材一覧
教材一覧
教材検索

1対1のマッチング問題

1対1のマッチング問題におけるマッチングメカニズム

目次

Twitter
Mailで保存

インセンティブの問題

2つのグループに別れたプレイヤーたちを何らかのルールにもとづいてグループ間で1対1でマッチングさせてペアを作る状況を1対1のマッチング問題と呼ばれる環境として定式化しました。続いて問題になるのは、どのようなマッチングを作るべきか、その最適な方法を考えることです。ただ、話がそう単純ではないことを以下で順を追って解説します。

それぞれのプレイヤーは自身とマッチし得る相手どうしを比較する選好を持っていますが、これは自分だけが知っている情報であり、他のプレイヤーたちはそれを事前に観察できません。仮に、あるプレイヤーが他のプレイヤーたちに対して、マッチングを行う前に自身の選好を打ち明けたとしましょう。しかし、それを聞いた他のプレイヤーたちは、その発言の真偽を確認する術がありません。そのプレイヤーは嘘をついているかもしれないし、本当のことを言っているかもしれない。プレイヤーにとって選好は自身の頭の中にある情報である以上、そのプレイヤーが事前に伝えてきた選好の真偽を他のプレイヤーが判定することは原理的に不可能です。これは全てのプレイヤーの選好について当てはまります。このとき、それぞれのプレイヤーにとって自身の選好は私的情報(private information)であると言います。それぞれのプレイヤーが考える選好はその人だけが私的に持っている情報であり、他のプレイヤーたちはそれを事前に知ることはできないということです。市場への参加者の中に私的情報を持つプレイヤーが存在するとき、その市場では情報の非対称性(asymmetric information)が成立していると言います。1対1のマッチング問題ではプレイヤーの間に情報の非対称性が成立しています。

マッチングのためのルールを設計するマッチメイカー(match maker)は、何らかの意味において社会的に望ましいマッチングを実現しようとします(社会的な望ましいことの意味については後述)。仮にマッチメイカーがプレイヤーたちの真の選好を観察できるならば、観察した真の選好の組を基準に社会的に望ましいマッチングを特定し、それを遂行すればよいことになります。しかし、実際には、先に解説したような情報の非対称性が成立しているため、マッチメイカーはプレイヤーたちの真の選好を観察できず、したがって社会的に望ましいマッチングを事前に特定することはできません。マッチメイカーはプレイヤーたちに自身の選好を申告させた上で、申告された選好の組を基準に社会的に望ましいマッチングを特定し、それを遂行せざるを得ません。ただ、それぞれのプレイヤーが申告する選好は、そのプレイヤーの真の選好と一致するとは限りません。プレイヤーは望ましい相手とマッチするために戦略的に行動しますが、その一環として、偽りの選好を表明する可能性があるからです。プレイヤーの選好は私的情報であるため、プレイヤーが嘘をついて真の選好とは異なる選好を申告しても、マッチメイカーはそれが嘘であるかどうかを知る術がないのです。プレイヤーたちが偽りの選好を表明する場合、マッチメイカーは偽りの選好の組を基準にマッチングを決定することとなり、それは真の意味で社会的に望ましいマッチングとは異なるものになってしまう可能性があります。情報の非対称性に起因するこのような問題をインセンティブの問題(incentive problem)と呼びます。

インセンティブの問題を引き起こす原因が情報の非対称性である以上、インセンティブの問題を解決するためには、何らかの方法を通じて情報の非対称性を解消する必要があります。言い換えると、何らかの方法を通じて、それぞれのプレイヤーの真の選好を収集する必要があります。ただ、繰り返しになりますが、プレイヤーに選好を申告させても正直に答えるとは限りませんし、そもそも正直に答えているかどうかを判別する方法が存在しません。

ただ、それぞれのプレイヤーにとって、自分の真の選好を正直に申告することが最も得であるようなマッチングルールを設計すれば、そのようなルールのもと、プレイヤーたちは自分の真の選好を自ら進んで正直に表明するため、結果として情報の非対称性は解消されます。さらに、そのマッチングルールが同時に、申告された選好の組を基準に社会的に望ましいマッチングを導くような形で設計されていれば、真の意味で社会的に望ましいマッチングを遂行できることになります。ただ、そもそも、そのようなマッチングルールを設計することは可能なのでしょうか。また、可能である場合、具体的にはどのようなルールがそのような要件を満たすのでしょうか。このような問題への解を得ることが私たちの目標です。

一般に、情報の非対称性が成立する市場において、私的情報を持っている参加者をエージェント(agent)と呼びます。市場において情報の非対称性が成立するとき、エージェントが自身の利益を最大化するために戦略的に振る舞う結果、その市場ではインセンティブの問題が発生します。インセンティブの問題を解消することを目的に設計されるルールをメカニズム(mechanism)と呼び、メカニズムを設計する主体をプリンシパル(principal)と呼びます。プリンシパルは適切なメカニズムを設計することを通じて、エージェントたちの行動を社会的に望ましい方向へ誘導しようとします。1対1のマッチング問題におけるエージェントは何らかの相手とマッチしようとしているプレイヤーたちです。プレイヤーは選好を私的情報として持っています。プレイヤーたちがより望ましい相手とマッチするために真の選好とは異なる選好を申告する結果、1対1のマッチング市場ではインセンティブの問題が発生します。そこで、マッチメイカーはプリンシパルとして適切なメカニズム、すなわちマッチングルールを設計し、プレイヤーたちの行動を社会的に望ましい方向へ誘導しようとします。以上の視点を踏まえた上で、1対1のマッチング問題を描写するモデルを見直します。

 

タイプと状態

1対1のマッチング問題において、それぞれのプレイヤーは選好を私的情報として持つエージェントです。そこで、以降ではプレイヤーのことをエージェントと呼びます。エージェント\(i\in M\cup W\)が持つ私的情報をエージェント\(i\)のタイプ(type)と呼びます。具体的には、それぞれのエージェント\(i\)のタイプは、自分がマッチし得る相手どうしを比較する選好関係\(\succsim _{i}\)として集約的に表現できるものとみなします。

エージェント\(i\)の真のタイプ、すなわち真の選好は1つだけですが、それを観察できるのはエージェント\(i\)だけであり、他の任意のエージェントやマッチメイカーはそれを事前に観察できません。このような事情をモデル化するために、エージェント\(i\)の選好\(\succsim _{i}\)は様々な値を取り得るものとし、その中の真の値を知っているのはエージェント\(i\)自身だけであるものとみなします。具体的には、エージェント\(i\)の選好がとり得る値からなる集合を\(\mathcal{R}_{i}\)で表し、これをエージェント\(i\)の選好集合(preference set)やタイプ集合(type set)などと呼びます。\(\succsim _{i}\in \mathcal{R}_{i}\)です。エージェント\(i\)の選好\(\succsim _{i}\)は選好集合\(\mathcal{R}_{i}\)に属する様々な値を取り得ますが、\(\succsim _{i}\)の真の値を知っているのはエージェント\(i\)だけです。他の任意のエージェントやマッチメイカーは\(\succsim _{i}\)のとり得る値の範囲\(\mathcal{R}_{i}\)を知っていますが、その中のどの値が真の値であるかは知らないものと仮定することにより、エージェント\(i\)の選好が私的情報であるという状況を表現するということです。

すべてのエージェントの選好関係からなる組を\(\succsim _{M\cup W}=(\succsim _{i})_{i\in M\cup W}\)で表記し、これを選好プロファイル(preference profile)やタイププロファイル(type profile)などと呼びます。エージェント\(i\)以外のエージェントたちの選好の組を\(\succsim _{-i}=\left( \succsim _{j}\right) _{j\in\left( M\cup W\right) \backslash \left\{ i\right\} }\)で表記します。\(\succsim _{M\cup W}=\left( \succsim_{i},\succsim _{-i}\right) \)です。

すべてのエージェントの選好集合からなる集合を\(\left\{ \mathcal{R}_{i}\right\} _{i\in M\cup W}\)で表記し、その直積集合を\(\mathcal{R}_{M\cup W}=\prod_{i\in M\cup W}\mathcal{R}_{i}\)で表記します。\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)です。また、エージェント\(i\)以外のエージェントたちの選好集合の直積を\(\mathcal{R}_{-i}=\prod_{j\in \left( M\cup W\right) \backslash \{i\}}\mathcal{R}_{j}\)で表記します。\(\succsim _{-i}\in \mathcal{R}_{-i}\)です。

エージェントたちの選好の組\(\succsim _{M\cup W}\)は、問題としている1対1のマッチング問題の状態(state of the world)とも呼ばれます。すべてのエージェントたちの真の選好から構成される状態\(\succsim _{M\cup W}\)は、そのマッチング問題の真の状態(true state)に相当します。ただ、それぞれのエージェント\(i\)が知っているのは自身の真の選好\(\succsim _{i}\)だけであり、マッチング問題の真の状態\(\succsim _{M\cup W}\)を構成する残りの要素\(\succsim _{-i}\)については正確に知らず、\(\succsim_{-i}\)がとり得る値の範囲\(\mathcal{R}_{-i}\)だけを知っています。つまり、選好\(\succsim _{i}\)を持つエージェント\(i\)が直面し得る状態からなる集合は、\begin{equation*}\left\{ \left( \succsim _{i},\succsim _{-i}\right) \right\} _{\succsim
_{-i}\in \mathcal{R}_{-i}}
\end{equation*}であり、エージェント\(i\)はこのことを認識しています。他の任意のエージェントについても同様です。

 

メカニズム

仮にマッチメイカーが問題としているマッチング問題の真の状態\(\succsim _{M\cup W}\)を観察できるならば、観察した\(\succsim _{M\cup W}\)を基準に社会的に望ましいマッチングをマッチング集合\(\mathcal{M}\)の中から選び取ることが原理的に可能であるため、インセンティブの問題は発生しません。しかし、実際には、マッチメイカーは真の状態\(\succsim _{M\cup W}\)を事前に観察できず、状態がとり得る値の範囲\(\mathcal{R}_{M\cup W}\)だけを知っています。このような状況においてインセンティブの問題を解消するために、マッチメイカーは何らかのマッチングルール、すなわちメカニズム設計する必要があります。

具体的には、マッチメイカーはエージェントたちに選好を申告させると同時に、申告された選好の組に応じて特定のマッチングを選択するルールをあらかじめ設計します。これをメカニズム(mechanism)や直接メカニズム(direct mechanism)などと呼びます。より正確には、メカニズムとは、エージェントたちが申告する選好の組\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)に対して、何らかのマッチング\begin{equation*}\phi \left( \succsim _{M\cup W}\right) =\left( \phi _{i}\left( \succsim
_{M\cup W}\right) \right) _{i\in M\cup W}\in \mathcal{M}
\end{equation*}を定める写像\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)として定式化されます。ただし、\(\phi _{i}\left( \succsim _{M\cup W}\right) \)はメカニズムが定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)においてエージェント\(i\)とマッチする相手です。

例(メカニズム)
エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2},m_{3}\right\} \\
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。

$$\begin{array}{ccccc}\hline
プレイヤー\diagdown 順位 & 1 & 2 & 3 & 4 \\ \hline
m_{1} & w_{1} & w_{3} & w_{2} & m_{1} \\ \hline
m_{2} & w_{3} & w_{1} & w_{2} & m_{2} \\ \hline
m_{3} & w_{1} & w_{3} & m_{3} & w_{2} \\ \hline
w_{1} & m_{2} & m_{3} & m_{1} & w_{1} \\ \hline
w_{2} & m_{3} & m_{2} & w_{2} & m_{1} \\ \hline
w_{3} & m_{2} & m_{1} & m_{3} & w_{3} \\ \hline
\end{array}$$

表:プレイヤーの選好

メカニズム\(\phi \)が「女性\(w_{1},w_{2},w_{3}\)の順番で優先的に最もマッチしたい相手とマッチさせる」というルールであるものとします。以上のメカニズム\(\phi \)に直面したエージェントたちが申告する選好が先の\(\succsim _{M\cup W}\)である場合、実現するマッチング\(\phi \left( \succsim _{M\cup W}\right) \)は、\begin{equation*}\phi \left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{3} & w_{1} & w_{2}\end{pmatrix}\end{equation*}となります。別のメカニズム\(\phi ^{\prime }\)が「男性\(m_{1},m_{2},m_{3}\)の順番で優先的に最もマッチしたい相手とマッチさせる」というルールであるものとします。以上のメカニズム\(\phi^{\prime }\)に直面したエージェントたちが申告する選好が先の\(\succsim _{M\cup W}\)である場合、実現するマッチング\(\phi ^{\prime }\left( \succsim_{M\cup W}\right) \)は、\begin{equation*}\phi ^{\prime }\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{2} \\
w_{1} & w_{3} & m_{3} & w_{2}\end{pmatrix}\end{equation*}となります。さらに別のメカニズム\(\phi ^{\prime\prime }\)が「マッチングを行わない」というルールであるものとします。以上のメカニズム\(\phi ^{\prime \prime }\)に直面したエージェントたちが申告する選好が先の\(\succsim _{M\cup W}\)である場合、実現するマッチング\(\phi ^{\prime \prime }\left( \succsim _{M\cup W}\right) \)は初期マッチングに他なりません。つまり、\begin{equation*}\phi ^{\prime \prime }\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{1} & w_{2} & w_{3} \\
m_{1} & m_{2} & m_{3} & w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}となります。

マッチメイカーはメカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)を利用して以下の流れのもとで資源配分を行います。

  1. マッチメイカーはメカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)を設計し、それをエージェントたちに提示する。
  2. それぞれのエージェント\(i\in M\cup W\)は提示されたメカニズム\(\phi \)に同意すれば次のステップへ進む。同意しない場合にはマッチングに参加せず、誰ともマッチしない(自身\(i\)とマッチする)。
  3. メカニズム\(\phi \)に同意したそれぞれのエージェント\(i\)は、自身の選好\(\succsim _{i}\in \mathcal{R}_{i}\)をマッチメイカーへ申告する。その際、他のエージェントたちが申告する選好を観察することはできない。また、エージェントは真の選好を正直に申告するとは限らない。
  4. 仮にすべてのエージェントがメカニズム\(\phi \)に同意する場合、マッチメイカーは全員が申告してきた選好からなる組\(\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\)とマッチする。

ここでの1つ目のポイントは、マッチメイカーはエージェントたちに交渉の余地のないオファー(take-it-or-leave-it offer)をしているという点です。つまり、エージェントたちは提示されたメカニズムに同意するか否かの二択に直面しており、メカニズムの内容に対してマッチメイカーと交渉する余地は与えられていません。

2つ目のポイントは、マッチメイカーは自身が最初に提示したメカニズムを後で撤回し、別のメカニズムを再提示することはできないという点です。このとき、マッチメイカーは自身が提示したメカニズムにコミット(commit)していると言います。なお、メカニズムに同意しないエージェントは誰ともマッチしない(自身とマッチする)ため、誰ともマッチしないことから得る満足度はそのエージェントにとっての留保効用(reservation utility)に相当します。

3つ目のポイントは、マッチメイカーはエージェントたちの真の選好の組を事前に観察できないため、直接メカニズムはエージェントたちが申告してきた選好の組に対してマッチングを定める形にならざるを得ないということです。しかも、それぞれのエージェントが申告する選好は真の選好であるとは限りません。エージェントは偽りの選好を表明することが得であると判断するならば戦略的に嘘をつく可能性があるからです。しかも、選好はエージェントの私的情報である以上、エージェントが表明する選好が真の選好であるか否かを第三者は判定できません。ただ、マッチメイカーがメカニズムを巧みに設計すれば、エージェントたちが真の選好を表明するように誘導すると同時に、社会的に望ましいマッチングを実現できる可能性があります。この点については後述します。

Twitter
Mailで保存

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

1対1のマッチング問題(安定結婚問題)

2つのグループに分かれたプレイヤーたちを何らかのルールにもとづいてグループ間で1対1でマッチングさせる資源配分問題を1対1のマッチング問題(安定結婚問題)と呼ばれるモデルとして定式化します。

1対1のマッチング問題の私的価値モデル

1対1のマッチング問題(安定結婚問題)において、プレイヤーの選好に関して非外部性と私的価値を仮定する場合、そのようなモデルを私的価値モデルと呼びます。

非分割財の交換問題における個人合理的メカニズム

非分割財の交換問題(シャプレー・スカーフの住宅市場)におけるメカニズムが与えられたとき、メカニズムの均衡において、メカニズムが定める配分が任意のプレイヤーにとって初期配分以上に望ましいことが保証されるならば、そのようなメカニズムは個人合理性を満たすと言います。

単一財オークションにおけるメカニズムのもとでのベイジアンゲーム

単一財オークション市場においてメカニズムを提示された入札者たちが直面する戦略的状況はベイジアンゲームとして定式化されます。そのようなゲームにおいて、それぞれの入札者は自身のタイプと信念にもとづいて他の入札者たちのタイプを予想し、その予想から算出される中間期待利得を最大化するような純粋戦略を採用するものとします。

1対1のマッチング問題における耐戦略的メカニズム

1対1のマッチング問題(安定結婚問題)におけるメカニズムにおいて、すべてのエージェントにとって自身の真の選好を正直に申告することが支配戦略である場合、そのようなメカニズムは耐戦略性を満たすと言います。

非分割財の交換問題におけるパレート効率的メカニズム

ある配分を出発点に誰かの満足度を高めようとすると他の人の犠牲が伴うような状態であるとき、その配分はパレート効率的であると言います。また、パレート効率的な配分を常に選び取るメカニズムをパレート効率的なメカニズムと呼びます。

非分割財の交換問題におけるコア選択メカニズム

ある配分を出発点に、そこからプレイヤーのグループ(提携)が内部で商品を交換することでグループ内でのパレート改善が可能である場合、その配分はその提携によってブロックされると言います。また、いかなる提携によってもブロックされない配分をコアと呼び、コアを常に選び取るメカニズムをコア選択メカニズムと呼びます。