マーケットデザインと受入保留アルゴリズム

最近，ブログエントリを書くときの枕が読んだ本のことが多いですが，今回も御多分に洩れずであります*1．

現実の中でのマーケットデザイン

つい先日まで，以下の本を読んでました．マーケットデザインという分野を過分にしてしらなかったんですが，大元はゲーム理論の一種だったんですね．著者のロスさんらが，自身で証明した理論について現実問題に当てはめ，実際にうまく機能することを示した，その過程が描かれていて，非常に面白い本でした．臓器移植や公立学校の希望選択，新米医者の医局配属といった，いわゆるマッチングの問題が，周到に仕組みをデザインすることで，全体的な満足度が高い状態で解決された例をみると，なるほどなーという感想しかでないです．

Who Gets What (フー・ゲッツ・ホワット) ―マッチメイキングとマーケットデザインの新しい経済学

この本の中では，主に公共に関わるマーケットのマッチング問題について，主に述べられていました．ですが私自身がこれを読もうと思ったきっかけは，新しいサービスやプラットフォームを構築するときには，マーケットデザインの考え方が割とうまく当てはめられるんじゃないかな，と思ったからです．典型的にはネットオークションは一種のマーケットですし，その流れで今ではメルカリのようなもう少しシンプルな個人売買のプラットフォームも同様だといえます．特にWebを介したB2CやB2B2Cのサービスは，割と多くがマッチング問題に関わるものではないかと思います*2．

そしてこの本の中でくどいくらいに繰り返し言われていたのは，アルゴリズム以外の部分，つまりはそのマーケットがどういう人たちで構成されていて，どういうセンシティブな問題があり，どういった政治的事情が絡んでいるか，といった細部まで踏み込んで緻密なデザインを行わなければ，マーケットはうまく機能しないということでした．さっきのヤフオクやメルカリなんかも，レビュー機能であったり決済代行機能であったり，それ以外にもさまざまな工夫や調整を行うことで，厚みのあるマーケット*3を構築できたのだろうなぁと思います．神は細部に宿るではないんですが，世の中そんなに簡単にスパッと割り切れるものではないということなんだなぁと，なんかしみじみ思ってしまいました．

よくあるマッチング問題

この本の中でメインで述べられていたのが，受入保留アルゴリズムというものです．本中の例だと，よりよい就職先を希望する医者の卵と，よりよい新人を採用したい医局側が，どうやればうまくマッチングするかという話が例として出されていました．なにもせず自由競争に任せてしまうと，他の医局に取られる前に有望そうな新人を先に取ってしまえということで，青田刈りのような状況になってしまいます．その青田刈りが行き着いた先には，まだ専門教育をちゃんと受ける前の段階の学生に対するアプローチ合戦が起こり，やりたいことや能力の評価がうまくできずマッチングミスが逆に増えてしまう，という結果が待っていました*4．

これを防止するために協定が結ばれ，一定期間より前には医局側が採用することができないというルールが決められたりもしましたが，時が経つにつれ内密に口利きがされたりという事例が相次ぎ，なし崩し的に元に戻ってしまう，という状態だったようです*5．このような現象が起こるのは，単純な希望順のマッチングを行うだけだと，一部の人気医局に希望が集中して，第1希望にあぶれてしまったが最後，第2希望も第3希望もすでに埋まってしまっており，希望順位の低いところにいかなければいけない制度のせいだったりします．そうすると，本当の希望順リストを書くよりも，確実にいけそうなところを第1希望にみたいなことが横行することになってしまうわけです．なので，この状態を解決するためには，本心の希望順リストを書いた上で，それが正しく機能するマッチングシステムを作らなければいけないのですね．

受入保留アルゴリズム

そこで出てくる受入保留アルゴリズムは，簡単にいうと，第1希望のマッチングを行った際に，マッチングしたペアの選択がその場で確定するわけではなく，仮のマッチングとして保留しておき，続く第2希望のマッチングでやってきた新たな希望者と合わせて，再度マッチングを行う，というプロセスをとります．つまりこの場合，最初のステップでたとえ第1希望でうまく滑り込めたとしても，より優秀な人が後のステップでその医局を希望してきたら，その人がマッチングすることになります．そして最初に滑り込めてた人は，第2希望の医局にマッチング希望を出すわけです．これを繰り返して，全員がマッチングしたら，その時に初めて結果が確定します．厳密なアルゴリズムについては，このあたりの講義資料でも読んでいただければと思います．

ということで，実際に実装して試してみました．上の例で示した医者-医局マッチングは，複数の対象を選択することができる応用的な問題なので，ここではもっとシンプルに1対1のマッチング問題を試しています．これは
安定結婚問題 - Wikipedia として知られている問題で，例としてお見合いパーティーにおける男性→女性の告白を考えます*6．実際に実行した結果も下に貼っていますが，3回ほど回して，6ステップ，12ステップ，22ステップでそれぞれ10対10のマッチングが安定状態に至りました*7．

gist.github.com

そんな感じで，数理的な問題を実問題に落とし込めると楽しいだろうなぁと思った，そんな夜でした．この本はさすがに一般書すぎるので，もう少しメカニズムデザインについてちゃんと書いてある書籍を読みたいですね...何かおすすめあるんでしょうか．

*1:まぁ，お仕事に関する部分で書けるようなことがあまりない，というのが実際のところなのですが．

*2:Web以前からやられてますが，有名なリクルートのリボンモデルなんかは，まさにですよね．未読ですけど，須藤さんのこの記事なんかには，ちゃんとした分析が書いてあるのかなーと思います．

*3:この本の中では，多くのプレイヤーが集まり，活発に取引が行われている状況のことを，「厚みのある」という表現であらわしています

*4:過度な市場信奉者に対しての煽りでもないですが，シンプルな市場メカニズムに任せていれば最善の結果が得られるわけでは，必ずしもないということですね．

*5:なんか我が国の新卒就職市場を見ているようですね．

*6:フェミニズム的な意味で微妙な例だとは思いますが，他にパッとわかりやすい例が思い浮かばなかったので，ご勘弁ください．

*7:そもそも数学的に，このアルゴリズムは必ず安定状態に至ることが証明されています．ただ安定ではあるが，最善の結果とは限らない点はポイントです．正確には，voter側にとって最高，picker側にとって最悪の形で安定状態になります．