WIIS

教材一覧
教材一覧
教材検索
ONE-TO-ONE-MATCHING PROBLEM

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

目次

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有

1対1のマッチング問題

初期時点においてプレイヤーたちが2つのグループに分かれているとき、何らかのルールにもとづいてグループ間でプレイヤーたちをマッチングさせてペアを作る状況を想定します。ただし、それぞれのプレイヤーは自分とは異なるグループに所属する高々1人のプレイヤーとのみマッチできるものとします。つまり、それぞれのプレイヤーは1人の相手とマッチするか誰ともマッチしないかのどちら一方であり、複数の相手とマッチする状況は排除されます。加えて、ペアを決める際にプレイヤーたちは金銭などの交換媒体を使うことはできないものとします。つまり、それぞれのプレイヤーは特定の相手とマッチするために対価として金銭を支払ったり、逆に、自分が特定の相手とマッチすることを認める対価として金銭を受け取ることはできないということです。また、それぞれのプレイヤーは、自分とは異なるグループに所属するプレイヤーたちを比較する選好、すなわち好みの体系を持っているものとします。選好の内容はプレイヤーごとに異なりますが、これはプレイヤーの私的情報であり、他のプレイヤーたちがそれを事前に観察することはできません。以上のような資源配分問題を1対1のマッチング問題(one-to-one matching problem)や1対1の両側マッチング問題安定結婚問題(stable marriage problem)、または結婚問題(marriage problem)などと呼びます。

例(1対1のマッチング問題)
1対1のマッチング問題を始めて明示的に分析したのは Gale and Shapley (1962)です。そこで想定されている状況は以下の通りです。\(n\)人の男性と\(m\)人の女性がいる状況において夫婦を作ります。一夫一妻制を想定するため、それぞれのプレイヤーは1人の異性と結婚するか未婚のままでいるかのどちらか一方です。それぞれのプレイヤーは、婚姻相手としての望ましさという基準をもとに異性に対して順位をつけています。ただし、この順位は各々が頭の中に思い描いているものであるため、それぞれのプレイヤーは、他のプレイヤーたちが考える順位を事前にすることはできません。それぞれのプレイヤーは特定の異性と結婚するために対価として金銭を支払ったり、逆に、特定の異性と結婚することを認める対価として金銭を受け取ることはできないものとします。1対1のマッチング問題は以上のような文脈のもとで定式化されたため、多くの場合、安定結婚問題や結婚問題などと呼ばれます。
例(1対1のマッチング問題)
男女1人ずつのペアでチームを作って行う競技について考えます。テニスや卓球、バドミントンの混合ダブルス、フィギュアスケートのペア、社交ダンスのペアなどが具体例です。\(n\)人の男性プレイヤーと\(m\)人の女性プレイヤーがいる状況において、それぞれのプレイヤーは異性とペアを組めば競技に参加できますが、誰ともペアを組まなければ競技に参加できません。それぞれのプレイヤーは、競技のペアとしての望ましさという基準をもとに異性のプレイヤーたちに対して順位をつけています。ただし、この順位は各々が頭の中に思い描いているものであるため、それぞれのプレイヤーは、他のプレイヤーたちが考える順位を事前にすることはできません。それぞれのプレイヤーは特定の相手とペアを組むために対価として金銭を支払ったり、逆に、特定の相手とペアになる対価として金銭を受け取ることはできないものとします。

 

プレイヤー集合

1対1のマッチング問題をモデルとして定式化します。まずはプレイヤーの表現です。1対1のマッチング問題に参加するプレイヤーからなる集合をプレイヤー集合(player set)やプレイヤー空間(player space)などと呼びます。1対1のマッチング問題ではプレイヤーたちが2つのグループに分かれているため、一方のグループに属するすべてのプレイヤーからなる集合を\(M\)で表記し、もう一方のグループに属するすべてのプレイヤーからなる集合を\(W\)で表記します。\(M\)と\(W\)は互いに素な集合であるものとします。つまり、\begin{equation*}M\cap W=\phi
\end{equation*}を仮定します。同一のプレイヤーが両方のグループに属する可能性を排除するということです。多くの場合、プレイヤー集合は有限であるものと仮定します。その上で、集合\(M\)に属するプレイヤーが有限\(n\)人であり、集合\(W\)に属するプレイヤーが有限\(m\)人である場合、プレイヤー集合を、\begin{eqnarray*}M &=&\left\{ m_{1},\cdots ,m_{n}\right\} \\
W &=&\left\{ w_{1},\cdots ,w_{m}\right\}
\end{eqnarray*}と特定します。便宜上、集合\(M\)に属するそれぞれのプレイヤーを男性(man)と呼び、集合\(W\)に属するそれぞれのプレイヤーを女性(woman)と呼ぶこととします。男性の人数\(n\)と女性の人数\(m\)の大小について特に指定しませんが、多くの場合、男女が同数であること、すなわち\(n=m\)が成り立つ状況を想定して分析を行います。

例(プレイヤー集合)
問題としている1対1のマッチング問題に参加する男性が\(4\)人であり、女性が\(3\)人であれば、プレイヤー集合は、\begin{eqnarray*}M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\right\} \\
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}などとなります。

 

プレイヤーどうしを比較する選好関係

1対1のマッチング問題において、それぞれの男性\(m\in M\)は女性どうしを比較する選好関係(preference relation)を持っているものとみなし、それを\(\succsim _{m}\)で表記します。ただし、1対1のマッチング問題では男性がいかなる女性ともマッチしない可能性は排除されていないため、男性は女性どうしを比べるだけでなく、女性とマッチしないという選択肢も考慮した選好を形成するものとします。男性\(m\)がいかなる女性とマッチしないことを、便宜上、自分自身\(m\)とマッチすることとみなし、そのような選択肢を\(m\)で表記するものと定めます。以上を踏まえた上で、男性\(m\)の選好関係\(\succsim _{m}\)は集合\(W\cup\left\{ m\right\} \)上に定義された二項関係であり、自分自身を含めた任意の相手\(i,j\in W\cup \left\{ m\right\} \)に対して、\begin{equation*}i\succsim _{m}j\Leftrightarrow \text{男性}m\text{は相手}i\text{を相手}j\text{以上に好む}
\end{equation*}を満たすものとして定義されます。つまり、男性\(m\)にとって\(i\)が\(j\)以上に望ましい場合にはそのことを\(i\succsim_{m}j\)で表記するということです。

男性\(m\)の選好関係\(\succsim _{m}\)が与えられたとき、任意の相手\(i,j\in W\cup \left\{ m\right\} \)に対して、\begin{equation*}i\succ _{m}j\Leftrightarrow i\succsim _{m}j\wedge \lnot \left( j\succsim
_{m}i\right)
\end{equation*}を満たすものとして集合\(W\cup \left\{ m\right\} \)上の新たな二項関係\(\succ _{m}\)が定義可能です。つまり、男性\(m\)にとって\(i\)が\(j\)以上に望ましく、なおかつ\(j\)が\(i\)以上に望ましくない場合にはそのことを\(i\succ _{m}j\)で表記するということです。言い換えると、\(i\succ _{m}j\)が成り立つこととは、男性\(m\)にとって\(i\)が\(j\)よりも望ましいことを意味します。この二項関係\(\succ _{m}\)を男性\(m\)の狭義選好関係(strict preference relation)と呼びます。

男性\(m\)の選好関係\(\succsim _{m}\)が与えられたとき、任意の相手\(i,j\in W\cup \left\{ m\right\} \)に対して、\begin{equation*}i\sim _{m}j\Leftrightarrow i\succsim _{m}j\wedge j\succsim _{m}i
\end{equation*}を満たすものとして集合\(W\cup \left\{ m\right\} \)上の新たな二項関係\(\sim _{m}\)が定義可能です。つまり、男性\(m\)にとって\(i\)が\(j\)以上に望ましく、なおかつ\(j\)が\(i\)以上に望ましい場合にはそのことを\(i\sim _{m}j\)で表記するということです。言い換えると、\(i\sim _{m}j\)が成り立つこととは、男性\(m\)にとって\(i\)と\(j\)が同じ程度望ましいことを意味します。この二項関係\(\sim _{m}\)を男性\(m\)の無差別関係(indifferencerelation)と呼びます。

女性\(w\in W\)の選好関係\(\succsim_{w}\)についても同様に考えます。つまり、1対1のマッチング問題では女性がいかなる男性ともマッチしない可能性は排除されていないため、それぞれの女性\(w\in W\)は男性どうしを比べるだけでなく、男性とマッチしない選択肢も考慮した選好関係\(\succsim _{w}\)を形成します。女性\(w\)がいかなる男性ともマッチしないことを自分自身\(w\)とマッチすることと同一視するのであれば、女性\(w\)の選好関係\(\succsim _{w}\)は集合\(M\cup\left\{ w\right\} \)上に定義された二項関係であり、自分自身を含めた任意の相手\(i,j\in M\cup \left\{ w\right\} \)に対して、\begin{equation*}i\succsim _{w}j\Leftrightarrow \text{女性}w\text{は相手}i\text{を相手}j\text{以上に好む}
\end{equation*}を満たすものとして定義されます。先と同様、女性\(w\)の狭義選好関係\(\succ _{w}\)は任意の相手\(i,j\in M\cup \left\{ w\right\} \)に対して、\begin{equation*}i\succ _{w}j\Leftrightarrow i\succsim _{w}j\wedge \lnot \left( j\succsim
_{w}i\right)
\end{equation*}を満たすものとして定義され、女性\(w\)の無差別関係\(\sim _{w}\)は任意の相手\(i,j\in M\cup \left\{ w\right\} \)に対して、\begin{equation*}i\sim _{w}j\Leftrightarrow i\sim _{w}j\wedge j\sim _{w}i
\end{equation*}を満たすものとして定義されます。

すべてのプレイヤーの選好関係からなる組を\(\succsim _{M\cup W}=\left( \succsim _{i}\right) _{i\in M\cup W}\)で表記し、これを選好プロファイル(preference 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) \)です。また、プレイヤーの集合\(T\subset M\cup W\)について、\(T\)に属するプレイヤーたちの選好関係からなる組を\(\succsim _{T}=\left( \succsim _{i}\right) _{i\in T}\)で表記し、\(T\)に属さないプレイヤーたちの選好関係からなる組を\(\succsim_{-T}=\left( \succsim _{i}\right) _{i\in \left( M\cup W\right) \backslash T}\)で表記します。\(\succsim _{M\cup W}=\left( \succsim _{T},\succsim _{-T}\right) \)です。

例(プレイヤーどうしを比較する選好関係)
プレイヤー集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\right\} \\
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}であるとき、男性\(m_{1}\in M\)の選好関係\(\succsim _{m_{1}}\)の例としては、\begin{equation*}w_{2}\succ _{m_{1}}w_{1}\succsim _{m_{1}}w_{3}\succ _{m_{1}}m_{1}
\end{equation*}が挙げられます。つまり、男性\(m_{1}\)にとって女性\(w_{2}\)は女性\(w_{1}\)よりも望ましく、女性\(w_{1}\)は女性\(w_{3}\)以上に望ましく、女性\(w_{3}\)は異性とマッチしないこと\(m_{1}\)よりも望ましいということです。男性\(m_{2}\)の選好関係\(\succsim _{m_{2}}\)の例としては、\begin{equation*}m_{2}\succ _{m_{2}}w_{1}\sim _{m_{2}}w_{2}\sim _{m_{2}}w_{3}
\end{equation*}が挙げられます。つまり、男性\(m_{2}\)にとって異性とマッチしないこと\(m_{2}\)が最も望ましく、すべての女性\(w_{1},w_{2},w_{3}\)の間に差がないということです。他のプレイヤーの選好についても同様に考えます。

多くの場合、任意の男性\(m\)の選好関係\(\succsim _{m}\)は以下の条件\begin{equation*}\forall i,j\in W\cup \left\{ m\right\} :\left( i\succsim _{m}j\vee j\succsim
_{m}i\right)
\end{equation*}を満たすものと仮定し、任意の女性\(w\)の選好関係\(\succsim _{w}\)は以下の条件\begin{equation*}\forall i,j\in M\cup \left\{ w\right\} :\left( i\succsim _{w}j\vee j\succsim
_{w}i\right)
\end{equation*}を満たすものと仮定します。つまり、自身を含めた2人の相手\(i,j\)が任意に与えられたとき、プレイヤーは\(i\)を\(j\)以上に好むか、\(j\)を\(i\)以上に好むか、その少なくとも一方であるという仮定です。これを完備性(completeness)の仮定と呼びます。この仮定の意味を以下で解説します。

男性\(m\)の選好\(\succsim _{m}\)に注目します。自身を含めた2人の相手\(i,j\in W\cup \left\{m\right\} \)を任意に選んだとき、論理的には以下の\(\left( a\right) \)から\(\left( d\right) \)の4通りが起こり得ます。ただし、\(1\)は真を表す真理値であり、\(0\)は偽を表す真理値です。

$$\begin{array}{cccccc}\hline
\quad & i\succsim _{m}j & j\succsim _{m}i & i\sim _{m}j & i\succ _{m}j & j\succ _{m}i \\ \hline
\left( a\right) & 1 & 1 & 1 & 0 & 0 \\ \hline
\left( b\right) & 1 & 0 & 0 & 1 & 0 \\ \hline
\left( c\right) & 0 & 1 & 0 & 0 & 1 \\ \hline
\left( d\right) & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:完備性

\(\left( a\right) \)は男性\(m\)にとって\(i\)と\(j\)が同じ程度望ましい場合、\(\left( b\right) \)は男性\(m\)にとって\(i\)が\(j\)よりも望ましい場合、\(\left(c\right) \)は男性\(m\)にとって\(j\)が\(i\)よりも望ましい場合に相当します。一方、\(\left( d\right) \)では\(i\)と\(j\)の間の優劣に関する情報が存在しないため、この場合、そもそも\(i\)と\(j\)を比べることができません。ただ、\(\succsim _{m}\)が完備性を満たす場合には\(i\succsim _{m}j\)と\(j\succsim _{m}i\)の少なくとも一方が成り立つことが保証されるため、\(\left(d\right) \)が起こる可能性は排除されます。つまり、\(\succsim _{m}\)が完備性を満たす場合には、2つの選択肢\(i,j\)を任意に選んだとき、\(\left( a\right) ,\left( b\right),\left( c\right) \)の中のどれか1つが成り立つことが保証されます。言い換えると、\(i\sim _{m}j\)と\(i\succ _{m}j\)と\(j\succ _{m}i\)の中のどれか1つが必ず成り立つことが保証されるということです。女性\(w\)の選好\(\succsim _{m}\)についても同様に考えます。完備性のもとでは、プレイヤーがどのような選択肢の組を提示された場合においても、迷うことなく両者の優劣を判断できることになります。

多くの場合、任意の男性\(m\)の選好関係\(\succsim _{m}\)は以下の条件\begin{equation*}\forall i,j,k\in W\cup \left\{ m\right\} :\left( i\succsim _{m}j\wedge
j\succsim _{m}k\Rightarrow i\succsim _{m}k\right)
\end{equation*}を満たすものと仮定し、任意の女性\(w\)の選好関係\(\succsim _{w}\)は以下の条件\begin{equation*}\forall i,j,k\in W\cup \left\{ w\right\} :\left( i\succsim _{w}j\wedge
j\succsim _{w}k\Rightarrow i\succsim _{m}k\right)
\end{equation*}を満たすものと仮定します。つまり、自身を含めた3人の相手\(i,j,k\)が任意に与えられたとき、\(i\)を\(j\)以上に好み、\(i\)を\(k\)以上に好む場合には、\(i\)を\(k\)以上に好むことが保証されるということです。これを推移性(transitivity)の仮定と呼びます。

推移性の意味を深く理解するために、完備性を満たすが推移性を満たさない選好関係のもとでどのような問題が生じ得るかを考えます。男性\(m\)の選好\(\succsim _{m}\)に注目します。\(\succsim _{m}\)が推移性を満たさない場合には、推移性の定義の否定に相当する以下の命題\begin{equation}\exists i,j,k\in W\cup \left\{ m\right\} :\left[ i\succsim _{m}j\wedge
j\succsim _{m}k\wedge \lnot \left( i\succsim _{m}k\right) \right] \quad \cdots (1)
\end{equation}が成り立ちます。\(\succsim_{m}\)が完備性を満たす場合には、\(\left( 1\right) \)中の相手\(i,k\)の間に、\begin{equation*}k\succ _{m}i\Leftrightarrow \lnot (i\succsim _{m}k)
\end{equation*}という関係が成り立つため(確認してください)、これを用いて\(\left( 1\right) \)を言い換えると、\begin{equation*}\exists i,j,k\in W\cup \left\{ m\right\} :\left( i\succsim _{m}j\wedge
j\succsim _{m}k\wedge k\succ _{m}i\right)
\end{equation*}となります。つまり、\(i\)を出発点としたとき、\(k\)のほうが\(i\)よりも厳密に望ましく(\(k\succ _{m}i\))、さらに\(j\)は\(k\)以上に望ましい(\(j\succsim _{m}k\))という形で、\(i\)を出発点にそれより厳密に望ましいか、あるいは同等以上の相手へ移行することで\(j\)へ至ったにも関わらず、最初の\(i\)はこの\(j\)以上に望ましい(\(i\succsim _{m}j\))という奇妙な状況が発生しています。つまり、\begin{equation*}\cdots \succ _{m}i\succsim _{m}j\succsim _{m}k\succ _{m}i\succsim
_{m}j\succsim _{m}k\succ _{m}i\succsim _{m}j\succsim _{m}k\succ _{m}\cdots
\end{equation*}という形で選好が循環してしまうということです。女性\(w\)の選好\(\succsim _{m}\)についても同様に考えます。選好関係に対して推移性の仮定を設けることは、こうした状況が発生する可能性を排除することを意味します。

完備性と推移性をともに満たす選好を選好順序(preference ordering)や合理的な選好関係(rational preference relation)などと呼びます。男性\(m\)の選好関係\(\succsim _{m}\)が選好順序であるものとします。つまり、\begin{eqnarray*}&&\left( a\right) \ \forall i,j\in W\cup \left\{ m\right\} :\left( i\succsim
_{m}j\vee j\succsim _{m}i\right) \\
&&\left( b\right) \ \forall i,j,k\in W\cup \left\{ m\right\} :\left(
i\succsim _{m}j\wedge j\succsim _{m}k\Rightarrow i\succsim _{m}k\right)
\end{eqnarray*}がともに成り立つということです。このとき、自身を含めた2人の相手\(i,j\in W\cup \left\{ m\right\} \)を任意に選ぶと、\(\succsim _{m}\)の完備性より\(i\)と\(j\)は比較可能です。さらに、3人目の相手\(k\in W\cup \left\{m\right\} \)を任意に選ぶと、やはり\(\succsim _{m}\)の完備性より\(i\)と\(k\)は比較可能であり、\(j\)と\(k\)は比較可能です。したがって、\(i,j,k\)の中の任意の2人が比較可能であり、さらに\(\succsim _{m}\)の推移性より、それらを循環しない形で男性\(m\)にとって望ましい形で並べることができます。4人目の相手についても同様に考えると、結局、選好順序\(\succsim _{m}\)のもとでは集合\(W\cup\left\{ m\right\} \)のすべての要素を循環しない形で並べることができることになります。加えて、自身を含めた2人の相手\(i,j\in W\cup \left\{ m\right\} \)を任意に選んだとき、選好順序\(\succsim _{m}\)のもとでは\(i\succ _{m}j\)または\(j\succ _{m}i\)または\(i\sim _{m}j\)の中のどれか1つが必ず成り立ちます。したがって、男性\(m\)の選好関係\(\succsim _{m}\)が選好順序である場合、男性\(m\)は狭義選好\(\succ_{m}\)と無差別関係\(\sim _{m}\)を用いて集合\(W\cup \left\{ m\right\} \)のすべての要素を最も望ましい相手から最も望ましくない相手まで順番に並べることができます。例えば、\begin{equation*}i_{1}\succ _{m}i_{2}\sim _{m}i_{3}\sim _{m}i_{4}\succ _{m}i_{5}\cdots
\end{equation*}という具合にです。女性\(w\)の選好関係\(\succsim _{w}\)が選好順序である場合にも同様の議論が成り立ちます。

男性\(m\)の選好関係\(\succsim _{m}\)が選好順序であるものとします。その上で、場合によっては、自身を含めた任意の2人の相手\(i,j\in W\cup \left\{ m\right\} \)の間に\(i\sim _{m}j\)という関係が成り立たないものと仮定します。つまり、男性\(m\)にとって同じ程度望ましい複数の相手が存在しないという仮定です。これを狭義選好の仮定(assumption of strict preference)と呼びます。このとき、任意の2人の相手\(i,j\)の間に\(i\succ _{m}j\)または\(j\succ _{m}i\)のどちらか一方が成り立つため、集合\(W\cup \left\{m\right\} \)の要素であるすべての相手を狭義選好\(\succ _{m}\)だけを用いて一列に並べることができます。例えば、\begin{equation*}i_{1}\succ _{m}i_{2}\succ _{m}i_{3}\succ _{m}i_{4}\succ _{m}i_{5}\cdots
\end{equation*}という具合にです。女性\(w\)の選好関係\(\succsim _{w}\)についても同様に考えます。選好順序だけを仮定する場合、すべての相手を最も望ましい相手から最も望ましくない相手まで順番に並べることができますが、その中に同じ程度望ましい複数の相手が存在する可能性は排除されません。一方、選好順序に加えて狭義選好を仮定する場合、すべての相手を最も望ましい相手から最も望ましく相手まで順番に並べることができ、なおかつ、その中に同じ程度望ましい複数の相手は存在しないことが保証されます。

例(プレイヤーどうしを比較する選好関係)
プレイヤー集合が、\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}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。この場合、プレイヤー\(i\)は自身がマッチし得るすべて相手に対して重複しない形で順位をつけることができるため、プレイヤーたちの選好を以下のような表を用いてシンプルに表現できます。

$$\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}$$

表:プレイヤーの選好

 

マッチング集合

1対1のマッチング問題において、プレイヤーたちをマッチングさせることで実現し得るそれぞれの結果をマッチング(matching)や配分(allocation)などと呼びます。具体的には、男性の集合\(M\)と女性の集合\(W\)が与えられたとき、それぞれのマッチングは以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall m\in M,\ \forall w\in W:\left[ \mu \left(
m\right) =w\Leftrightarrow \mu \left( w\right) =m\right] \\
&&\left( b\right) \ \forall m\in M:\left[ \mu \left( m\right) \not\in
W\Rightarrow \mu \left( m\right) =m\right] \\
&&\left( c\right) \ \forall w\in W:\left[ \mu \left( w\right) \not\in
M\Rightarrow \mu \left( w\right) =w\right] \end{eqnarray*}を満たす写像\(\mu :M\cup W\rightarrow M\cup W\)として定義されます。ただし、マッチング\(\mu \)がそれぞれのプレイヤー\(i\in M\cup W\)に対して定める像\(\mu \left( i\right) \in M\cup W\)はマッチング\(\mu \)のもとでプレイヤー\(i\)とマッチする相手に相当します。条件\(\left( a\right) \)は、男女\(m,w\)を任意に選んだとき、マッチング\(\mu \)のもとで\(m\)が\(w\)とマッチすることと\(w\)が\(m\)とマッチすることが必要十分であることを意味します。このとき、\(m\)と\(w\)はマッチする(matched)と言います。つまり、マッチング\(\mu \)のもとで男女\(m,w\)がペアになる場合、お互いにマッチする異性は1人ずつであるということです。条件\(\left( b\right) \)は、男性\(w\)が女性とマッチしない場合、その男性\(w\)がマッチする相手は自分自身\(m\)であることを意味します。このとき、男性\(w\)はマッチしない(unmatched)と言います。条件\(\left( c\right) \)は、女性\(w\)が男性とマッチしない場合、その女性\(w\)がマッチする相手は自分自身\(w\)であることを意味します。このとき、女性はマッチしないと言います。

マッチング\(\mu \)が以上の3つの条件を満たす場合、それぞれのプレイヤーに対して自身を含めた何らかの相手を1人ずつ割り当てることが物理的に可能です。そのようなこともあり、以上の条件を満たすマッチングのことを実現可能なマッチング(feasible matching)と呼ぶ場合もあります。すべての実現可能なマッチングからなる集合を\(\mathcal{M}\)で表記し、これをマッチング集合(setof matchings)と呼びます。\(\mu \in \mathcal{M}\)です。

初期時点においてそれぞれのプレイヤー\(i\in M\cup W\)にマッチしている相手はいないことを踏まえると、\begin{equation*}\forall i\in M\cup W:\mu \left( i\right) =i
\end{equation*}を満たすマッチング\(\mu \)は明らかに実現可能です。これを初期マッチング(initial matching)や初期配分(initial allocation)などと呼びます。

例(マッチング)
プレイヤー集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\right\} \\
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}であるとき、\(m_{1}\)と\(w_{1}\)がマッチし、\(m_{2}\)と\(w_{2}\)がマッチし、\(m_{3}\)と\(w_{3}\)がマッチし、\(m_{4}\)がマッチしないというマッチングは、\begin{eqnarray*}\mu \left( m_{1}\right) &=&w_{1} \\
\mu \left( m_{2}\right) &=&w_{2} \\
\mu \left( m_{3}\right) &=&w_{3} \\
\mu \left( m_{4}\right) &=&m_{4}
\end{eqnarray*}を満たす写像\(\mu :M\cup W\rightarrow M\cup W\)として表現されます。マッチングの定義より、このとき、\begin{eqnarray*}\mu \left( w_{1}\right) &=&m_{1} \\
\mu \left( w_{2}\right) &=&m_{2} \\
\mu \left( w_{3}\right) &=&m_{3} \\
\mu \left( m_{4}\right) &=&m_{4}
\end{eqnarray*}もまた成立します。以上のマッチング\(\mu \)を、\begin{equation*}\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} \\
w_{1} & w_{2} & w_{3} & m_{4}\end{pmatrix}\end{equation*}と表現することも可能です。また、初期マッチングは、\begin{eqnarray*}
\mu \left( m_{1}\right) &=&m_{1} \\
\mu \left( m_{2}\right) &=&m_{2} \\
\mu \left( m_{3}\right) &=&m_{3} \\
\mu \left( m_{4}\right) &=&m_{4}
\end{eqnarray*}を満たす写像\(\mu :M\cup W\rightarrow M\cup W\)として表現されますが、これを、\begin{equation*}\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} & w_{1} & w_{2} & w_{3} \\
m_{1} & m_{2} & m_{3} & m_{4} & w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}と表現することも可能です。ちなみに、例えば、\begin{eqnarray*}
\mu \left( m_{1}\right) &=&w_{1} \\
\mu \left( m_{2}\right) &=&w_{1} \\
\mu \left( m_{3}\right) &=&w_{2} \\
\mu \left( m_{4}\right) &=&w_{3}
\end{eqnarray*}を満たす写像\(\mu :M\cup W\rightarrow M\cup W\)は実現可能なマッチングではありません。\(\mu \)のもとで異なる男性\(m_{1},m_{2}\)に対して同一の女性\(w_{1}\)がマッチしていますが、これは物理的に不可能だからです。

 

マッチングどうしを比較する選好関係

それぞれのプレイヤー\(i\)は自分自身を含めた相手どうしを比較する選好関係\(\succsim _{i}\)を持っていますが、1対1のマッチング問題において実現可能な結果がマッチング\(\mu \in \mathcal{M}\)として表現されることを踏まえると、プレイヤー\(i\)は相手どうしを比較する選好\(\succsim_{i}\)だけでなく、マッチングどうしを比較する選好を持っていなければ、実現し得る結果どうしを比較できないことになってしまいます。そこで、それぞれのプレイヤー\(i\)はマッチングどうしを比較するマッチング集合\(\mathcal{M}\)上に定義された選好関係を持っているものとし、これを\(\succsim _{i}^{\mathcal{M}}\)で表記します。ただし、\(\succsim _{i}^{\mathcal{M}}\)は\(\mathcal{M}\)上に定義された二項関係であり、任意のマッチング\(\mu ,\mu ^{\prime }\in \mathcal{M}\)に対して、\begin{equation*}\mu \succsim _{i}^{\mathcal{M}}\mu ^{\prime }\Leftrightarrow \text{プレイヤー}i\text{はマッチング}\mu \text{をマッチング}\mu ^{\prime }\text{以上に好む}
\end{equation*}を満たすものとして定義されます。つまり、プレイヤー\(i\)にとって\(\mu \)が\(\mu ^{\prime }\)以上に望ましい場合にはそのことを\(\mu \succsim _{i}^{\mathcal{M}}\mu ^{\prime}\)で表記するということです。

プレイヤー\(i\)がマッチングどうしを比較する選好関係\(\succsim _{i}^{\mathcal{M}}\)が与えられたとき、任意のマッチング\(\mu ,\mu ^{\prime}\in \mathcal{M}\)に対して、\begin{equation*}\mu \succ _{i}^{\mathcal{M}}\mu ^{\prime }\Leftrightarrow \mu \succsim _{i}^{\mathcal{M}}\mu ^{\prime }\wedge \lnot \left( \mu ^{\prime }\succsim _{i}^{\mathcal{M}}\mu \right)
\end{equation*}を満たすものとしてマッチング集合\(\mathcal{M}\)上の新たな二項関係\(\succ _{i}^{\mathcal{M}}\)を定義します。また、任意のマッチング\(\mu ,\mu ^{\prime }\in \mathcal{M}\)に対して、\begin{equation*}\mu \sim _{i}^{\mathcal{M}}\mu ^{\prime }\Leftrightarrow \mu \succsim _{i}^{\mathcal{M}}\mu ^{\prime }\wedge \mu ^{\prime }\succsim _{i}^{\mathcal{M}}\mu
\end{equation*}を満たすものとしてマッチング集合\(\mathcal{M}\)上の新たな二項関係\(\sim _{i}^{\mathcal{M}}\)を定義します。

一般に、プレイヤー\(i\)がマッチングどうしを比較する選好\(\succsim _{i}^{\mathcal{M}}\)は、自身が相手どうしを比較する選好関係\(\succsim _{i}\)に依存して変化します。なぜなら、例えば、プレイヤーがある相手を低く評価する場合、自身がその相手とマッチするようなマッチングを低く評価するものとみなすのが自然であり、逆に、プレイヤーがある相手を高く評価する場合、自身がその相手とマッチするようなマッチングを高く評価するものとみなすのが自然だからです。このような事情を踏まえると、プレイヤー\(i\)がマッチングどうしを比較する選好\(\succsim_{i}^{\mathcal{M}}\)は、自身が相手どうしを比較する選好\(\succsim _{i}\)に依存して変化するという意味を込めて、これを\(\succsim _{i}^{\mathcal{M}}\left[ \succsim _{i}\right] \)と表記すべきです。

ただ、プレイヤー\(i\)がマッチングどうしを比較する選好\(\succsim _{i}^{\mathcal{M}}\)は、自身が相手どうしを比較する選好\(\succsim_{i}\)だけに依存するのではなく、他のプレイヤーたちが各々の相手どうしを比較する選好\(\succsim _{-i}\)に依存するという状況も起こり得ます。なぜなら、例えば、他のプレイヤーの間で人気がある相手とマッチすることに喜びを感じるプレイヤーなどが存在し得るからです。このような事情を踏まえると、プレイヤー\(i\)がマッチングどうしを比較する選好\(\succsim_{i}^{\mathcal{M}}\)は、自身が相手どうしを比較する選好\(\succsim _{i}\)だけでなく、他のプレイヤーたちが各々の相手どうしを比較する選好\(\succsim _{-i}\)にも依存して変化するという意味を込めて、これを\(\succsim _{i}^{\mathcal{M}}\left[\succsim _{i},\succsim _{-i}\right] \)すなわち\(\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \)と表記すべきです。

例(マッチングどうしを比較する選好関係)
ある男性\(m\)は誰ともマッチしないことよりも、とりあえず異性とマッチしたいものと考えているものとします。同時に、他のプレイヤーたちがマッチする相手には無関心であるものとします。この場合、\(\mu\left( m\right) =m\)を満たすマッチング\(\mu \)と\(\mu ^{\prime }\left( m\right) \in W\)を満たすマッチング\(\mu^{\prime }\)をそれぞれ任意に選んだとき、\begin{equation*}\mu ^{\prime }\succ _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \
\mu
\end{equation*}という関係が成り立ちます。

例(マッチングどうしを比較する選好関係)
ある男性\(w\)は異性とマッチするくらいならば誰ともマッチしないほうがよいものと考えているものとします。同時に、他のプレイヤーたちがマッチする相手には無関心であるものとします。この場合、\(\mu \left(m\right) =m\)を満たすマッチング\(\mu \)と\(\mu ^{\prime }\left( m\right) \in W\)を満たすマッチング\(\mu ^{\prime }\)をそれぞれ任意に選んだとき、\begin{equation*}\mu \succ _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \ \mu ^{\prime
}
\end{equation*}という関係が成り立ちます。

 

環境

1対1のマッチング問題を表現するモデルの要素は以上ですべてです。つまり、1対1のマッチング問題を描写するためには、そこに参加するプレイヤーからなる集合である\(M\)と\(W\)、それぞれのプレイヤー\(i\in I\)が自身を含めた相手どうしを比較する選好関係\(\succsim _{i}\)、起こり得るすべてのマッチングからなる集合\(\mathcal{M}\)、そして、それぞれのプレイヤー\(i\)がマッチングどうしを比較する選好関係\(\succsim _{i}^{\mathcal{M}}\left[ \succsim_{M\cup W}\right] \)を特定することになります。以上の要素からなるモデルを、\begin{equation*}\left( M,W,\left\{ \succsim _{i}\right\} _{i\in M\cup W},\mathcal{M},\left\{
\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \right\} _{i\in
M\cup W}\right)
\end{equation*}と表記し、これによって1対1のマッチング問題の定義とします。このようなモデルを環境(environment)と呼ぶこともあります。

1対1のマッチング問題の分析では多くの場合、任意のプレイヤーについて、相手どうしを比較する選好が選好順序であることを仮定します。狭義選好の仮定については、それを仮定する場合とそうでない場合がありますが、後述するように、その違いは分析結果に影響を与えるため注意が必要です。

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

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

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

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

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

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

1対1のマッチング問題(安定結婚問題)におけるマッチングが安定的であること、また、メカニズムが安定的であることの意味を解説します。安定性は広義コアと概念として一致します。

1対1のマッチング問題
DAメカニズムのもとでの男女の利害の対立

1対1のマッチング問題(安定結婚問題)において安定性を追求する限りにおいて、男性求婚型DAメカニズムは男性にとって最良である一方で女性にとって最悪であり、逆に、女性求婚型DAメカニズムは女性にとって最良である一方で男性にとって最悪です。

DISCUSSION

質問とコメント

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

1対1のマッチング問題