« サッカーの衝撃、ブラジルよりフランスから・・ | トップページ | 「美の基準とは やせすぎモデル問題」を読んで・・(朝日新聞) »

ノーベル経済学賞に輝いた婚活(マッチング)理論~OR4

今日はまた、全然違う話を少し書いて終わりのつもりだったのに、ネットで

ノーベル経済学賞関連のニュースを見た途端、マニアック魂がムラムラし

てしまった♪ 予定変更で、軽く手を付けてみよう。先日記事にした、数学

ABC予想ほど高級な話ではないけど、非常に実用的で身近な話だし、

本気で考えると相当ハイレベルな話にもなるはずだ。

      

10月15日、スウェーデン王立科学アカデミーが授賞したのは、アルビン・

ロス(Alvin Roth)教授とロイド・シャプリー(Lloyd Shapley)教授の2人。

彼らは、安定的な(stable)割り当てが得られるマッチング理論(Matching

 theory)を研究。既に、臓器移植での提供者と患者の組合せや、医学実

習生と研修先病院の組合せ、公立学校の選択制度などで実用化。分かり

やすい具体例が、複数の男女が結婚相手を選ぶ婚活理論、あるいはプロ

ポーズ理論らしい。

    

要するに、「ゲーム理論」の一種で、より広く言うならOR(オペレーション・リ

サーチ)だろう。与えられたシステム(計算可能な単純化された状況)で、最

適なものを導くための研究だ。当サイトには、既に3本のOR記事がある。

特に2本目と3本目は、この記事と似た感じのタイトルだ(実際はかなり違う)。

       

   

cf. OR(オペレーションズ・リサーチ)~理系の鳩山新首相の専攻

   お見合いでベストの相手にプロポーズする方法♪

                          ~鳩山新首相の専攻「OR」2

   10人とのお見合いで最高の相手にプロポーズする方法♪~鳩山の「OR」3

    

     

          ☆          ☆          ☆

ノーベル賞の公式HPを見ると、わざわざpdfファイルまで付けてくれてるの

で、早速ダウンロードして速読。すごく簡単な英語だから、美味しい所だけ

はすぐ理解できた。10人ずつの男女が、「安定的」マッチング(=組合せ,

カップリング)に至るにはどうすればいいか。

      

ここで「安定性」(stability)とは、誰も現在の状況を壊して別のマッチング

を臨んだりしない状況を指す。例えば、愛し合う夫婦が2組、計4人集まっ

たとしても、安定的だろう(人間的現実は別として、単なる理論的には♪)。

一方、「夫婦1」の夫と「夫婦2」の妻が愛し合い、「夫婦1」の妻が「夫婦2」の

夫と愛し合っていれば、離婚して再婚を目指すことになる。つまり安定して

ない、あるいは不安定なのだ。ORとしては普通、安定性を目指す。

     

安定的なマッチングを得るには、「deferred acceptance」と呼ばれるシ

ステムを用いる。通信社AFPはこれを「受入保留」と訳してるが、内容的に

は、「ずっと保留・延期し続けた後の受け入れ」ということだ。

    

日本語で近いのは、「キープ理論」だと思う。ベストかどうか分からないけど、

とりあえず今の彼 or 彼女をキープしとこうって考えは、今時珍しくないだろ

う。で、もっといい相手がやって来ればすぐ乗り換える♪ この尻軽な戦略こ

そ、実は安定的マッチングに到達できるらしいのだ(あくまで机上の理論とし

て)。ちなみに、この乗り換え=パートナー・チェンジは、「3人 vs 3人」以上

の場合でないと生じない。つまり、「2人 vs 2人」ではあり得ないのだ。

    

   

           ☆          ☆          ☆

具体的には、日本の慣習に合わせて、仮に、男がプロポーズ役としよう(pdf

ファイルでは女)。まず、それぞれの男が一番好きな女性にプロポーズする。

当然、魅力的な女性には複数のプロポーズが行われ、そうでない女性には

誰もプロポーズしない。プロポーズされた女性は、最も魅力的な男性を差し

当たりキープ(retain=保持)するが、プロポーズを受け入れた訳ではない。

     

2回戦では、第1回戦で断られた男性が、第2候補にプロポーズする。こ

の時、既にキープ状態になってる女性も、まだ独身だから、第2候補に選ん

でいいらしい(AFPより)。ただし、既に以前、断られてしまった男は、再度プ

ロポーズしても負けるだけだから、別の女性にプロポーズするのだと思う。

既に男をキープしてる女性は、2回戦でもっと素敵な男がプロポーズしてく

れた場合は、さっさと乗り換える♪

   

これを繰り返して本当に必ず終わりが来るのか、証明は難しいはずだが、

何となくいずれ終了しそうな感じはある。つまり、当初は不人気だった女性

に男がプロポーズすることになるだろうし、そうすると競合相手が少ない(ま

たはいない)から、男がキープしてもらえる確率が高まるからだ。

           

最後は、もはやプロポーズする男がいなくなり、がその時点まで「保持」し

てたキープ君を「受け入れ」て終了。この時、安定的な割り当て(allocation)

に必ずなるらしいのだ。。

    

   

           ☆          ☆          ☆

その略証(=省略した証明)となる(?)pdfファイルも、また別に公式サイト

にあったが、難しそうなので差し当たりパス。ここでは、最も簡単な2人 vs

2人の場合で、具体的にチェックしてみよう。A男とB男、C美とD美、計4人

で考える。

   

(1) まず、A男とB男の好みがいずれもC美、D美の順だと仮定しよう。

    ① C美とD美の好みがいずれもA男、B男の順の時

       1回戦 A男のプロポーズをC美がキープ、B男は拒否される。

       2回戦 B男のプロポーズをD美がキープ。

       C美とD美がプロポーズを受け入れて終了。

    

       このマッチングだと、A男&C美は大満足だが、B男&D美は

       満が残るカップルになる。ただ、A男&C美にはもう勝てないか

       ら、全体として安定するわけだ。

    

    「② C美がA男、B男の順で、D美がB男、A男の順」の時も、同様に

     安定する(B男には不満が残る)。残り2つ(③④)の時も同様。よっ

     て(1)は常に安定する。

    

    

(2) 次に、A男がC美、D美の順で、B男がD美、C美の順だと仮定しよう。

     ① C美がB男、A男の順で、D美がA男、B男の順の時

       1回戦 A男のプロポーズをC美がキープ、B男をD美がキープ。

       そのままC美とD美がプロポーズを受け入れて、直ちに終了。

    

       このマッチングだと、男2人は満足だけど、女2人には不満が残

       る。ただし、プロポーズは男だけだから、全体としてはもはや安

       定している。おそらく、そう考えるのだろう。

      

以下、(2)の②~④、更に(3)(4)と示せば、すべての場合証明が完成

結局、婚約解消や不倫を目指すような、「不安定な」マッチングは生じない

のだ。愛し合う2人が別の相手と結ばれてしまうな不運や、そこからの文字

通り「ドラマチックな」展開は、あり得ない。。

         

そもそも「不安定な」マッチングというのは、男2人の第1候補が別々なら

起きない。男2人とも1回戦で成功して終了だ。一方、男2人の第1候補が

一致してれば、その女の側の趣味でキープが行われる。よって、1回戦で

相思相愛カップルが出来るから、その後、その2人を切り崩すことなどでき

ず、残った2人でもう一つのカップルになるしかない。したがって、不満が残

りつつも安定するのであって、これが簡単で本質的な証明だろう。

      

ちなみに、男の側からプロポーズした場合は男がより満足な結果となり、女

の側からプロポーズした場合は女がより満足な結果となる。プロポーズする

側が有利だから、「平等性」の問題が残るとAFPは書いてた。全体の満足度

の数値や証明はともかく、上の例でもそんな感じにそうなってるし、プロ

ポーズは自分の好みで行うのだから、不平等かどうかはともかく、自然な結

果だろう。。

     

      

               ☆          ☆          ☆

一方、3人 vs 3人だと一気に変化が複雑になるので、全部は確認できない

が、面白い場合を1つだけ考えてみよう。A男、B男、C男と、D美、E美、F

美、計6人とする。A男の好みはD・E・Fの順。B男とC男の好みは、E・D・

Fの順。一方、D美の好みはC・B・Aの順。E美とF美の好みはA・B・Cの順。

         

   1回戦  A男をD美がキープ。B男をE美がキープ。

         C男はE美に拒否される。

   2回戦  C男がD美にプロポーズして新たにキープされ、A男が拒否

         される(=捨てられる)。

   3回戦  A男がE美にプロポーズしてキープされ、B男が拒否される。

   4回戦  B男がD美にプロポーズして、拒否される。

   5回戦  B男がF美にプロポーズして、キープされる。

   これにて終了。3人の女性はプロポーズを受け入れる。

   

結局、A男&E美、C男&D美、B男&F美の3ペアとなる。男3人がいずれ

も不満を残す結果だが、今のペアを壊して新たにチャレンジしても勝てない。

例えば、C男がE美を狙っても、E美の好みはA・B・Cの順だから、現在の

E美の相手であるA男には勝てないのだ。他も同様で、全体として安定する。 

以下はとりあえず、省略としよう。

             

      

          ☆          ☆          ☆

なお、ノーベル賞公式HPのpdfファイルには、「医者3人 vs 病院3つ」の

場合の図があった。

   

121017a

     

白の実線が医者の第一候補(first choice)、白の点線が医者の第二候補

121017b

  (second 

  choice)

  黒は病院側だ。医

  師の側からプロポ

121017c

  ーズした場合(左

  上)と、病院の側

  からプロポーズし

  た場合(左)とで、結

果は全く異なってる。

   

医者からのプロポーズの場合の展開のみ、簡単に書いておこう。

   1回戦  3人の医者が第一候補の病院aに集中。

         病院aは、第一候補の医者1をキープする。

   2回戦  医者2が第二候補の病院bに、医者3が第二候補の病院cに

         プロポーズして、それぞれキープされる。

   病院側が全員のプロポーズを受け入れて、終了。

   

医者の側は、医者1が大満足で、医者2と3が中くらいの満足。病院の側は、

病院aが大満足で、病院2と3は不満。確かに、プロポーズした医者の側の

方に有利な結果となってる。病院2と3は不満だが我慢するしかないので、

システム全体としては安定的となるのだ。

                

      

いずれ時間を作って、ハイレベルな数学的証明にもチャレンジしてみたい

と思ってる。上に示したようなシラミつぶし的方法では、時間がいくらあって

も、一般的証明は無理だろう。それでは、また明日。。☆彡

             

     

   

P.S. 10月29日の朝日新聞・朝刊に、「ノーベル経済学賞『マーケット

     デザイン』って何? 安田洋祐助教授に聞く」と題する記事が掲

     載された。深みも具体性も乏しい簡単な内容だったが、「10年前

     ならマーケットデザインを専門と言う学者はいなかったはず」との

     こと。理論の源流は古くても、発展・応用が進んだのはごく最近の

     ようだ。ちなみに私と同じく、「キープ」という言葉を使ってた。

      

      

P.S.2 13年2月5日の夜、NHK・Eテレの『オイコノミア』(経済学=エ

      コノミクスの語源らしい)で紹介されたらしい。私は見てないけど、

      続々と検索アクセスが入って来たから、ツイッター検索で調べる

      と、つぶやきがズラッと並んでた。単なる恋愛や合コンだと、ノリ

      が軽いから、現実はそれほど理論が上手くいかないと思う。ち

      なみに番組と関係なく(?)最近この記事のアクセスが増えてる。

   

   

P.S.3 13年2月9日深夜(10日の0時過ぎ)からの『オイコノミア』でも、

      バレンタインデー編として扱われたようだ。「ゲール・シャプレー

      メカニズム」とカッコ良く名付けたらしい。。

                

                                 (計 4452文字)

|

« サッカーの衝撃、ブラジルよりフランスから・・ | トップページ | 「美の基準とは やせすぎモデル問題」を読んで・・(朝日新聞) »

数学」カテゴリの記事

「経済・政治・国際」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




« サッカーの衝撃、ブラジルよりフランスから・・ | トップページ | 「美の基準とは やせすぎモデル問題」を読んで・・(朝日新聞) »