はじめに

ゲーム理論を元に制度を設計して、資源の最適配分を目指すマーケットデザインという研究分野がある。マーケットデザインは社会問題の解決だけではなく、営利事業や企業内の課題解決にも役立ってきた。

この記事では、筆者が参加した以下の二つのイベントについて報告する。
・ERATO小島マーケットデザインプロジェクトキックオフシンポジウム
https://sites.google.com/g.ecc.u-tokyo.ac.jp/erato-kojima-kickoff/
・第23回情報科学技術フォーラム（FIT2024）
ERATO小島マーケットデザインプロジェクトにおける情報学
https://www.ipsj.or.jp/event/fit/fit2024/abstract/data/html/event/event_A-2.html

ERATO小島マーケットデザインプロジェクト(以下MDPJと略)とは、限られた資源という制約の中で、よりよい社会活動を行うために、数理モデルとゲーム理論で参加者のインセンティブと行動を分析し、望ましい制度を科学的に設計して，実社会の制度の改善を目指すために、経済理論・実証経済学・計算機科学・離散数学の専門家がチームを組んで、実際の社会課題に適用しようというプロジェクトである。このプロジェクトは、(独)科学技術振興機構が実施するプログラムの一環であり、マーケットデザインを専門とする経済学者・小島武仁東大教授が率いている。

前者のキックオフシンポジウムでは、MDPJの概要と、マーケットデザインの実際の適用例が紹介された。後者のFIT2024では、MDPJの概要と、MDPJに参画する計算機科学や離散数学の専門家による、マーケットデザインを実際の数理モデルに落とし込んで解くための、泥臭い手段が紹介された。

キックオフシンポジウム

マーケットデザインの説明と、社会実装の例が紹介された。

小島武仁教授@東大大学院経済学研究科

マーケットデザインとは制度設計の科学である。従来、制度設計にあたっては、経験・前例・試行錯誤を繰り返して手探りでやってきた。マーケットデザインとは、数理モデルとゲーム理論で参加者のインセンティブと行動を分析、制度の帰結としての配分を予測する科学である。
近年では、望ましい配分から最適な制度を逆算して、望ましい社会の実現に寄与してきた。マッチングの制度設計の例としては、研修医の希望と病院の希望を反映して、誰をどこに配属するかマッチングするという、研修医の病院配属問題がある。

ここでいう制度とは、希望に基づく結果を出すアルゴリズムであり、以下の二つの特徴を持つ。
・ミスマッチの発生を最小化
Xさんは病院Aに行きたくて、病院AもXさんに来てほしいのに、XさんがA病院に来ないようなことがミスマッチ
・真の希望を入力するインセンティブの提供(耐戦略性)
偽りの希望を入れるより、真の希望を入れた方が良い結果になる

Gale-Shapleyアルゴリズムでミスマッチをゼロ(安定マッチング)かつ耐戦略性を満たせることが、数学の定理で証明されている。このように希望を元に望ましい配分を出力するのがマーケットデザインである。

研修医の病院配属以外の実用例としては、学校選択制、ドナー交換型の生体腎移植、フードバンクに対する寄付された食料の配分、周波数帯の利用権、web広告枠などのオークションによる配分がある。

社会の情報化に伴い、マーケットデザインが有効な場面が急増し続けている。

マーケットデザインは、社会科学の理論を工学的に応用することが可能であるが、ポテンシャルと比べて社会実装の成功例がまだまだ限られている。理由としては、次の二点が考えられる。

社会からの制約に対して柔軟に対応できる、汎用性の高い一般理論が確立していない
制度導入効果の信頼性の高い事前測定や、厳密な事後検証が十分にできていない
MDPJは、あらゆる制度を科学的に設計する社会を実現するプロジェクトである。理論を研究し、事前に検証し、制度を実装し、効果を事後検証してフィードバックするループをまわすものである。

マーケットデザインの入門書の紹介
Who Gets What: マッチメイキングとマーケットデザインの経済学 A.E.ロス
https://www.amazon.co.jp/dp/ 4532356881/
マッチング理論とマーケットデザイン小島武仁、河田陽向
https://www.amazon.co.jp/dp/453555935X/

アルビン・ロス教授@ハーバードビジネススクール & 小島武仁教授

ロス教授はマーケットデザインでノーベル経済学賞を受賞しており、小島教授はロス教授の教え子である。この二人の対談する動画が日本語字幕付きで投影された。
米国医師労働市場の再配置をマーケットデザインで設計した。医学部を卒業したカップルの配属が上手くいっていなかったが、この配属プログラムでカップルを近い病院に配属することができた。多くのマッチング理論が、1962年のシャープレイの論文を参照している。
この派生形で、日本の医師の東京一極集中の防止や、学校のマッチング(きょうだいは同じ学校にしたい、人種や学力は多様性を持たせたい等)、保育園のマッチング(きょうだいを同じか近所の保育園に割り当てるのは難しい)がある。
他にも腎臓移植の問題がある。今は死体腎移植が多いが、最初は生体腎移植だった。
日本でドナー交換腎移植をするのに障害になるのは、脱感作療法(相性の良くない腎移植をする方法)は患者には良くないが病院は楽ができるため広く行われているが、マーケットデザインの専門がいればこれをせずに済む。
最初はペア交換で、単純だが米国全土にはスケールしない、病院間の調整が多いのが最大の障壁である。日本の腎移植は、人口当たりではそれほどでもないが件数は多い。
腎臓移植はわかりやすい例だが、学校選択は効果が測りにくい。自分の子供が安心して学校で過ごせるか見極めなければならない。
マーケットデザインは、医師に限らず若い研究者のマッチングにも役立ち、自分に合った仕事に就けるようにできる。
プレファレンスシグナリングとは、求職者が雇用主に対して送る自分の優秀さや関心を示すシグナルであるが、医療労働市場でも実用化されている。経済分野では関心を示すシグナルを2か所に送っていたが、30か所に送れる分野もあるが、30か所も面接に行くことは実際問題できない。

マッチングがうまくいっていないのは、難民や移民の再定住マッチングであり、米国南部では政治問題になっているし、ヨーロッパでも問題になっている。これは一種のマッチング市場であって、保護施設かビザか入国許可が必要である。政治的にはできるだけ絞りたい。今移民はボロ船に乗って海を渡ったりして入国してくるが、これが飛行機に乗って移民するようになればマーケットデザインが上手くいったということになる。米国では、HIASというマッチングアルゴリズムを使って難民をうまく配置しているユダヤ系の団体もある。

最後にMDPJに興味がある人、参加したい人へのメッセージを。マーケットデザインは、素晴らしい経済学の分野である。どんな困難がどの市場にあってどう解決するか研究するものである。制度設計を考えるためにはゲーム理論は欠かせない。

野田俊也講師@東大マーケットデザインセンターPM

MDPJには、5つのグループがあり、野田氏の属する社会実装グループは唯一、学術領域に規定されないグループである。従来の社会科学研究は理論で終わるものもあるが、社会実装で得られた知見を理論研究に還元するのがミッションである。

マーケットデザインの実績としては、組織内の人材配置の効率化、入試制度、リサイクル市場の再設計、待機児童問題、ワクチンや災害時の支援物資の資源配分、暗号資産がある。ノーベル経済学賞も、2012年にマッチングの研究、2020年に電波オークションの研究に対して授与されている。

主要な研究成果の一つに、ゲールとシャープレイの安定マッチングの論文がある。これは両側マッチング問題と言って、男性と女性、生徒と学校、研修医と病院のような二つのグループのそれぞれに属する、人や組織をマッチングさせるためのもので、参加者がそれぞれマッチ相手の候補に対して持つ好みに基づいてマッチングする。

ブロッキングペアを持つマッチングは望ましくない。マッチングが良いマッチングであるかどうかは、参加者の好みになる。今マッチしていない二人が駆け落ちすれば二人とも得するような組み合わせがブロッキングペアであり、ブロッキングペアがある時に元のマッチングは不安定であるという。

多くのマーケットデザインの応用場面で、ブロッキングペアの存在は望ましくない。例えばある生徒と高校の組み合わせがブロッキングペアである時に、その生徒は志望する高校の合格最低点をクリアしているのに入学できない。ある研修医と病院の組み合わせがブロッキングペアならば、この研修医と病院はマッチング制度に参加しない方が得であり、マッチング制度からみんな抜けてしまえば制度は崩壊する。

ブロッキングペアのない安定マッチングを手作業で見つけるのは、DA(deferred acceptance)アルゴリズムを使わなければ非常に困難である。逆にDAアルゴリズムを使えば、希望を入力した瞬間に解答は出る。

学校選択制を例にDAアルゴリズムを説明する。

各学校は定員まで入学させたい受験生に合格通知を送る
生徒は一番希望する学校の合格通知のみを保留し、他の学校は辞退する
辞退を受けた学校は、その分定員が開くので、合格順位に沿って補欠合格の通知を送る
1～3を空き定員や不合格者リストが空になるまでループする。

この方法は、中身がブラックボックスなAIに学生を選抜させるものではなく納得性が高い。実際には学校ではなく、生徒が学校に合格通知を送る方が望ましい性質が多い。ニューヨークの公立高校入試や、オーストラリアの大学入試などでは実際に、この方法が使われている。

DAアルゴリズムを実際に使用するには、微妙なカスタマイズが必要となる。場合によっては、まったく新しいメカニズムが必要となる。例えば、研修医カップルは近くの病院に配属する必要があるとか、学校では生徒の人種は偏ってはならないとかの縛りがある。

実際にマッチング理論を適用したい場合はぜひ、MDPJと共同研究や受託研究をお願いしたい。具体的には、情報の整理、経費の負担、データの提供、実験の実施などをしてもらいたい。

シスメックス奥山健雄氏

ジョブ型人事制度の導入と従業員エンゲージメントの向上がミッションで、キャリアを自分で築く実感を持ってもらうために、従業員と組織のお互いが選び、選ばれる環境を作っていこうとしている。

考え方・カルチャーを一気に変えることができないので、まずは新入社員配属マッチングをその第一歩とした。職種別採用で部門プレゼン+新入社員プレゼンでジョブマッチングする。新入社員には、選択肢すべてに優先順位を付けるように依頼した。全社的には、特定の地域や業務内容に人が偏らない、部門側の配属希望、社員側の配属希望のバランスを取っている。

取り組みの工夫ポイントとしては、定員に柔軟性があるか、スキル要件が緩い部門には、多めの定員を設定している。新入社員・部門側双方に、自分で選ぶことが意識されて、情報収集やアピールに積極的になり、配属への安心感・納得感の醸成ができた。

新入社員や二年目社員のキャリア申告の結果は、マッチングを導入した2021年度以降、異動希望や退職が減った。将来的には異動をマッチングさせたい。

社内公募はブロッキングペアを潰すシステムだが、別のブロッキングペアが生まれる可能性があるので望ましくない、社内公募やっている会社はマッチングを導入してほしい。

サイバーエージェント森脇大輔博士(経済学)

待機児童問題を解決するには、1.保育リソースの拡充 2.こども政策DXによる保育事務の省力化 3.マッチング理論による市場の効率化の3つのアプローチがある。

マッチング理論以外に、保護者への情報介入(スマホで簡単に保育所を探せる保育所マップの提供、生成AIで保活情報を提供するチャットボット、きょうだい係数の調整)、優先順位の見直し(不人気園を第一希望にすると入りやすいルールを廃止)で、耐戦略性のある利用調整ルールに。

現場向き合い力と実装力も重要。データの前処理やドメイン知識の理解など、泥臭いプロセスから逃げない力と、本当の課題は何か聞き出す現場向き合い力が必要。

オークネット市井勝彦氏

バイイングパワーの強化をはかって、バイヤー網を多様化した。バイヤー網多様化で生じた問題として、大手卸売は封印オークションを要望し、大ロットであるが、小売はリアルタイムオークションを要望(新規は相場観が乏しい)、小ロットを希望する。グローバル事業なので時差の問題もあるが、これは封印オークションで解決した。

オークション事業をやっているのにオークション理論はまったく知らなかったので、あわてて勉強した。耐戦略性があるのはバイヤーにとっても楽である。イノベーションがアカデミックなフィールドにある場合もある。

FIT2024

FIT2024は、情報処理学会と電子情報通信学会が共催する「第23回情報科学技術フォーラム」というイベントである。FIT2024で開催されたイベントの一つがここで紹介する、MDPJの情報学関係メンバーによる「ERATO小島マーケットデザインプロジェクトにおける情報学」であった。

小島武仁教授@東大大学院経済学研究科経済専攻経済学コース

前半部分はキックオフの時とほぼ同一なので省略する。
社会からの要請(制約)に対して、柔軟に対応できる汎用性の高い一般理論が確立されていない。制度導入効果の信頼性の高い、事前測定や事後検証をこれからやっていくとのこと。

MDPJには、理論経済学、実験実証経済学、計算機科学、離散数学、社会実装のグループがある。理論→事前検証→社会実装→事後検証のループをまわしてフィードバックしていく

横尾真教授@九大システム情報科学研究院情報学部門(専門はAI)

ゲーム理論は人間については不正確な近似だが、自立エージェントについては妥当と言える。ゲーム理論は経済学者と情報学者の共通言語である。工学系としては、説明だけの理論だと物足りない、検索連動型広告や学校選択制などの新しいマーケットを構築する新しい理論として発展していく可能性がある。
ビックレイ(Vickrey)入札(二位オークション)では、自分の評価値を素直に入力するのが最良の策であるので、誘因両立性と耐戦略性がある。

組み合わせ入札の利点としては、両方の財がほしい、片方だけでいいという希望が叶う。

周波数帯域、空港の離発着権、トラック配送の請負、調達では、ゲーム理論で誘因両立性と社会的余剰を最大化することができている。

マッチング研究を始めた経緯は、九大の工学部の研究室配属で、GaleとShapleyが提案したDA(Deferred Acceptance)メカニズムを使った研究室配属を教授会で提案して通ったのでやってみたことである。従来方式は第一希望優先方式(ボストン方式)だったが、学生同士の読み合いが発生し、自分より成績の良い学生の希望順位に応じて自分の希望を変更する学生が大量に出て、蓋を開けると望ましくない結果になっていた。しかし研究室配属にDAメカニズムを使おうとすると「准教授には1～2名、教授には2～3名の学生を割り当てる」というルールが実装できず、先行研究もなく、解いてみても難問で、学生のGPA(成績)を割り当てに使うが研究室個別の優先順位は用いないという条件で、なんとか解くことができた。

田村明久教授@慶大理工学部(専門は離散最適化で、元の専門は組合せ最適化)

どの医師が何時間働くかという割り当てベクトルと、どの医師がいくらもらうかと言う給与ベクトルの掛け算で示される、労働市場モデルの説明から始まった。医師は各々の貨幣価値の評価関数を持ち、自分の評価関数の値を最大化する。一方病院は、医師の評価額マイナス医師への支払額を最大化する。労働時間と給与の均衡点があればそれを求める(ない場合もある)。

これらの関数が共に凹関数ならば、ある種の前提条件の下で均衡が存在する。

(以下、M♮凸関数、M凸交叉定理等の説明が続くが理解できなかったので省略)
離散数学グループでは、離散凸解析、不可分財の構成配分、オンラインアルゴリズム、その他グラフ理論やトロピカル幾何学の専門家を募集しているとのこと。

塩浦昭義教授@東工大工学院経営工学系

単一需要モデルは最大重み二部マッチングであるが、複数需要モデルはM凸問題である。オークションの流れ自体は単一需要モデルでも複数需要モデルでも変わらず、ワルラス均衡では入札者の利得の合計が最大になる。

単一需要モデルならば均衡は常に存在するが、複数需要モデルでは一般に存在しない。存在する場合は均衡配分=評価値の和が最大の配分である。

粗代替性の入った複数需要モデルならば、均衡は常に存在する。

均衡配分は評価値の和が最大の配分(M♮凹関数和の最大化)で、均衡価格=双対最適解(L凸関数の最小化)となる。

筆者の感想

キックオフシンポジウムを聴講した時は、Gale-Shapleyアルゴリズムで安定マッチングができるのなら、自分が貢献できそうには思わなかったが、FIT2024に参加してその印象は大きく変わった。

横尾教授のお話で、ひとりの教員が指導する学生の人数を可変にするという、ありがちな条件をつけるだけで、いきなり世界最先端の新規研究になるという所に、難しさと面白さの両方を感じた。初めて聞くＭ凸問題やＭ♮凹関数の話題が多くて、数学的な内容はついていけなかった。

耐戦略性(参加者は小細工を考えるより、素直に希望を出した方が、良い結果を得られる)については、自分自身が四半世紀前に保育園待機児問題に取り組んだ時に聞いた話(例えばペーパー離婚で入園の優先順位が上がる等)と合わせて重要だと思った。

筆者はたまたま息子の大学のゲーム理論の教科書を読んで、会社の数学部で勉強会まで主催したので、面白いが実際の人間の行動とはまだギャップがあることは理解した上で、よりゲーム理論に興味を持つようになった。

キックオフで、オークネットの方が最近までオークション理論を知らずにオークションを運営していた話を聞いて、学術的な解決方法があることを知らずに現場の経験だけを重んじて、非効率的な業務運営をやっているというのは実は、あちらこちらにあるのではないかと思った。