魚心あれば水心 − 最適なペアを決めるマッチング・アルゴリズムの話

Apple初期にMac OSを開発した中心メンバーに、アンディ・ハーツフェルドという伝説的なプログラマがいた。Appleを退社後、独自にSwitcherというユーティリティ製品を開発するのだが、これはシングルタスクだったMacOS上で、複数のアプリを同時に動かせるという独創的なソフトだった。ところで以前、彼のインタビューをよんでいたら、彼が人生で最初に作ったプログラムが、高校のダンスパーティーの男女ペアを自動算出するものだったと書いてあり、笑ってしまった。世界中どこにいたって、魚心と水心の組み合わせは、つねに揉め事の種なのだ。

男女のお見合いから、研究室の配属、そして就活の就職先選びまで、世の中には「求める側」と「与える側」の組み合わせ問題に満ちている。あるいは、デマンド側サプライ側、と言いかえてもいい(男女のどっちが供給側かはともかく)。その典型は、サプライチェーンであろう。需要と供給をどうマッチングさせるのが最適なのか。最適とは、ここでは「お互いに満足度が高い」という風に規定しておこう。

「部分最適から全体最適へ」というのは、SCMの標語でもあった。では、最適なマッチングを具体的に決めるには、どうしたら良いのか? こうした問いに答える研究分野があることを、恥ずかしながらわたしはつい最近、初めて知った。

それを学んだのは昨年11月に、沖縄で開催された経営情報学会に参加したときである。たまたま「マーケットデザインとその周辺」というオーガナイズドセッションに講師として呼ばれ、そこでご一緒した大阪大学の安田洋祐先生と、電通大の岩崎敦先生から、「マッチングメカニズム」論の初歩と、ゲール=シャプレイ・メカニズムとよばれる仕組みのお話しをきくことができた。さらに、こうした研究の業績によって、シャプレイ教授は2012年にノーベル経済学賞を受賞したこともうかがった。そこで今回は、その時の印象的な講義をふりかえりながら、おさらいのために少し一緒に勉強してみたい。

ゲール=シャプレイ・メカニズムとは、マッチング問題を解くための基本的なアルゴリズムである。マッチング問題は、パーティでの男女の組み合わせに象徴されるように、デマンド側とサプライ側が互いに相手への好みを持つ場合に、より満足度の高い組み合わせは何か、という問題だ。ゲール=シャプレイ(GS)メカニズムは、その最適解を生成する手順である。

ここで、まずマッチング問題の前提を少し整理しておこう。まず、何らかの場があって、そこに
- デマンド(需要)側
- サプライ(供給)側
が同数いる。ここでは仮に、男の子がデマンド側で、女子がサプライ側としておこう。それから、誰もが相手に対する好みの順番(『選好順序』)をもっている。が、それは相手側には直接、分からない。また、この選好順序は、ジャンケンのような循環順序ではない、とする。満足度は数値化できないかもしれないが、とにかく優劣は決められるのだ。そして、他に特段の制約条件はない、とする。つまりお金持ちの子が最初に相手を選べるとか、貧乏人はペアを組めない、といった例外はもうけない、フェアな世界だとする。

GSメカニズムの基本的手順は、以下の通りである:
 デマンド側が、自分にとって最高順位のサプライ側にマッチングを申し込む
 サプライ側は、自分にとって最高順位のデマンドを「キープ」し、あとは拒否する
 デマンド側は、拒否されたら次の順位のサプライ側にマッチングを申し込む
 サプライ側は、より選好順位の高いデマンドが来たらキープ相手を変更する
 デマンド側がすべて受け入れられた状態になったら完了
この手順が最後まで行き着いたら、結果は自動的に最適状態になっていることが、数学的に証明されている。最適状態とは、どのペアを取り替えても、これ以上満足度の増える組み合わせが存在しない、というほどの意味だ。

非常に単純・明快な手順ではないか?

ゲールとシャプレイは、「大学入学と結婚の安定性」(1962)という、ちょっとふるった名前の論文で、最初にこの研究成果を明らかにした。この問題は、学問の地図でいうと、経済学という大国の中の、ミクロ経済学州にある、ゲーム理論という大都市の中に位置する。そこには数学国出身の賢そうな人々が多く住んでいる。わたしのように化学工学という小国出身で、今はプロジェクト・マネジメント論というもっとマイナーな地方都市にうつり住む者にとっては、縁遠い土地柄である。ま、自分が知らなかったことへの妙な良い訳はともかく、50年も前の知見を、今ようやく学んでいる訳だ。

このGSメカニズムは、現実の制度への豊富な適用事例をもっているのも特徴だ。たとえば日本では、2003年度から、臨床研修医を病院へ配属するためのマッチングの仕組みとして実際に使われている。また、 早稲田学院から早稲田大学の各学部への配分メカニズムも、そうなのだという。もっとも、わたしはGSメカニズムの仕組みをきいて、思わず触媒表面上の活性点で起きている分子レベルの化学反応メカニズムを連想してしまった。とういことは、自然界でも、これに似た仕組みがあちこちで動いているように思える。さすがである。

なお、マッチングが1対Nで、定員があったりする場合、GSメカニズムは次のような手順になる。
2 サプライ側は、定員まで「キープ」し、あとは拒否
4 新たにデマンド要求があった場合、サプライ側は選好順序に従って「キープ」を入れ替える

ところで上記の手順、きいてしまえば当たり前な内容、にも思える。どこが独創的なんだ? 数学的な証明はたしかに簡単じゃなさそうだけれど、普通、こうしてるじゃないか?

ところが普通は、上記のGSメカニズムとは、ちょっとだけ違うことをやっているのである。そして、そのちょっとだけの違いが、大いなる影響を生み出しているのだ。

世の中で普通にやられているのは、希望順位優先方式とよばれる方法である。別名を、「ボストンメカニズム」ともよぶ。ここでは、就活生の企業への就職を例にとって説明しよう。簡単のため、世の中に学生は全部で5名、企業は3社だけとする。世の就職関連業者がきいたら泣き出しそうなほど、シンプルな社会である。 学生の名はA・B・C・D・Eで、成績もこの順番である。企業はX社、Y社、Z社とする。なお、X社は大企業なので、募集定員は3名である。YとZ社は1名ずつだ。

希望順位優先方式(ボストンメカニズム)では、次のような手順で、就職者を決める。
1 全学生の第1希望において定員を満たすまで、企業は成績順に内定を決める
2 内定されていない学生と、定員の残る企業で、次の希望順位について1を繰り返す
シンプルだし、現実に、ほとんどのケースではこのようなマッチングが行われている。

だが、この手順ではまずいことが起きるのだ。それを「戦略的選好」とよぶ。

いま、学生の就職したい企業の順番(選好順序)は、以下のようだったとする。
Aさん、Dさん、E君:  X>Y>Z
B君、Cさん: X>Z>Y

ボストンメカニズムを適用すると、こうなる。
第1ラウンド:全員がX社を志望する。そこでX社は上位3名の、A・B・Cの採用を決め、内定を出す
第2ラウンド:DさんとE君は、第二志望のY社に志願を出す。Y社は、成績が上のDさんを内定する
第3ラウンド:E君がZ社に内定して、完了。
この結果、E君は、自分の希望順位では最低のZ社に就職することになる。

それが競争原理・弱肉強食のこの世の宿命だろう、って? ところが、である。E君はここで奸計を思いつく。彼は内心を隠して、自分の選好順位は「Y>X>Z だ」という風に振る舞うのである。

するとどうなるか? 上記の手順をあてはめると、こういう結果になる(読者の皆さんも紙の上で、ご自分で追いかけてみてほしい)。
X社:Aさん、B君、Cさん
Y社:E君
Z社:Dさん
おわかりだろうか? E君は次善のY社に就職し、正直だったDさんが割をくうのだ。

つまり、希望順位優先方式(ボストンメカニズム)は、嘘に弱いのだ。嘘をついた者が得をして、正直者が損をする。これを「戦略的選好」の問題とよぶ。この例では、嘘をついたことによる利得は所詮たいしたことが無いが、もっと深刻な例だって考案することができる。このような制度設計をしてはいけないことは、社会的に明らかだろう。

ところがGSメカニズムでは、「本音を言う」のが最適戦略になるのだ。ためしにGSメカニズムで上の例を追いかけてみると、E君が本音を言おうが嘘をつこうが、結果としては
X社:Aさん、B君、Cさん
Y社:Dさん
Z社:E君
となることを確かめてほしい。

GSメカニズムでは「戦略的操作」(つまり嘘)は有効にならないことが、数学的に保証されている。なぜ、その違いが生まれるかというと、GSメカニズムでは「仮にキープ」するが、後になってひっくり返すことを認めているからである。つまり、『内定取り消し』が公式に許容されているのだ。ボストンメカニズムでは、決定は先着順であった。ここが違うのである。

もっとも、GSメカニズムにも、弱点が無い訳ではない。たとえば、意図して嘘をつく訳ではないが、自分の選好順位とは反する選択をするような、非合理な人間が出てくると、うまく機能しなくなる。好みに反する選択をするとは、すなわち、自分が何を志望し、何をしたいのか、自分でもよく分からない人たちである。

いや、若い内には、そもそも自分が本当に何をしたいのか、何に向いているのかなど、自分でも分からないのが当たり前なのだ。いわゆる「自分探し」である。そして、むしろ周囲の方がよほど客観的に、向き不向きを見抜いていたりする。しかし、当たり前のことだが、いつまでも「仮決め」でふらふらしていると、肝心のパーティーでダンスが踊れなくなる。誰とも踊らないうちに、歳をとってしまうだろう。それに魚心あれば水心、一緒に踊っている内に、相手への選好順序がせり上がったりするのも、人間の心理なのだ。

ゲール=シャプレイのアルゴリズムはすばらしい数学的成果である。だが、それは各人の選好順位が固定したものだという前提の上に成り立つ、一種のスタティックな最適化手法だといえよう。わたし達が現実からいろいろなことを学び、それによって価値観が変化していくような、ダイナミックな場合の最適なメカニズムデザインは、まだまだこれから考え抜いていかねばならないのだ。


参考
安田 洋祐:「経済学で理想のパートナーを探そう! ゲール=シャプレーアルゴリズムを合コンのマッチング問題から考える」 東洋経済オンライン 
上田 俊(九州大学):「ゲーム理論 アドバンスドトピック
by Tomoichi_Sato | 2016-01-31 20:32 | 考えるヒント | Comments(0)
<< 書評:「アプリ開発チームのため... 講演のお知らせ:「生産スケジュ... >>