7月27・28日、サイバーエージェントの次世代技術者による技術カンファレンス「CA BASE NEXT 2022」を開催しました。本記事では「なぜテック企業で「マーケットデザイン」が必要なのか」についてご紹介します。
目次
- 「マーケットデザイン」とは
- マッチング理論
- よくあるやり方：受入即決方式（ボストン方式）
- DAアルゴリズム（受入保留方式）
- DAアルゴリズムWEBアプリ
- マッチング理論
- サイバーエージェントにおける「マーケットデザイン」
- まとめ
「マーケットデザイン」とは
日常の生活や仕事・学校において、次のような問題に直面したことのある人もいるでしょう。
- 会社の新入社員の配属部署を、新入社員の希望と各部署の受入人数・希望をもとに決定したい。どのように決めるべきか。
- 学校の新入生を寮の各部屋に割り振るとき、どのように部屋を決めるべきか。
- 5個のタスクを5人の社員に割り振るとき、各社員にはそれぞれがより興味・やる気のあるタスクを任せたい。どのようにタスクを割り振るべきか。
- 本Aと本Bを売りたいが、Aだけが欲しい人もいれば、Bだけが欲しい人、両方欲しい人もいる。どのように売る相手と値段を決めるべきか。
これらは、人や物・資源を適材適所に配分する問題と見ることができます。そのような資源配分の問題は、上記のような私たちの身近なところから、後ほど説明するウェブサービスの中に至るまで、幅広い場面で直面します。この資源配分の問題において、経済学とコンピュータサイエンスの知見を用いて適切な配分を見つける仕組みを設計し、社会実装まで行うのが「マーケットデザイン」です。
マーケットデザインは、主に2つの分野からなります。1つはオークション理論です。オークション理論は、一つあるいは複数の財を売却する際に、適切な価格と買い手を見つけるための良いオークション制度を設計するものであり、社会において幅広く使われています。一方、資源配分を決定する際に金銭を用いることが馴染まない場合も多くあります。そのような状況で、人々の希望をもとにみなが納得できる適切な配分方法を見つける仕組みを考えるのがマッチング理論です。以下ではこのマッチング理論についてお話しします。
マッチング理論
次の例を用いて、マッチング理論がどのような問題を扱う分野なのか説明したいと思います。
男性はAさん、Bさん、Cさん、女性はXさん、Yさん、Zさんの3人ずつおり、それぞれマッチを希望する相手の希望順位は横に書かれているように決まっているものとします。Zさんについては第1希望のBさんと第2希望のAさんしか書かれていませんが、これは何らかの理由でCさんとのマッチは希望しないという状況であるものとします。また、それぞれ最大1人の異性とマッチが可能であるものとします。
よくあるやり方：受入即決方式（ボストン方式）
このような状況で男性と女性のマッチを決めるやり方にはどのような方法があるでしょうか。よくあるやり方として、以下のようなものがあげられます。こちらはマッチング理論の分野では、受入即決方式、あるいはボストン方式と呼ばれているものです。
- 男性はそれぞれ第1希望に、つまりAさんとBさんはXさんに、CさんはYさんに申し込む。Xさんは申し込んできた2人のうちより希望の高いAさんを受け入れ、Bさんを断る。YさんはCさんを受け入れる。
- 前ステップで断られたBさんは、まだマッチ相手の見つかっていないZさんに申し込む。ZさんはBさんを受け入れる。
結果として、このやり方では以下のようなマッチとなりました。
このマッチ結果は好ましいものと言えるでしょうか。ここではBさんとYさんに着目してみます。BさんはZさんと今マッチしていますが、Yさんをより望んでいます。一方Yさんも今はCさんとマッチしていますが、Bさんをより望んでいます。したがってここでは、BさんとYさんは今のマッチを解消して互いにマッチし直すことを望むため、今のマッチ結果では不満が残ってしまうと思われます。したがって、好ましいマッチングの条件の1つとして、次のものがあげられます。
良いマッチングの条件①
互いに「あの人の方が良かった…」と思うペアを残さない。
では、上記のマッチ結果を少し変更して、次のようなものにするとどうでしょうか。
この場合、Zさんはマッチを希望していないCさんとマッチしているため、Zさんは不満を持つでしょう。したがって、好ましいマッチングの条件の2つ目は以下のようなものになります。
良いマッチングの条件②
誰もマッチを希望していない相手とはマッチしない。
この2つの条件を満たすようなマッチ結果を常に返してくれるような方式があれば、良いマッチングの仕組みであるということができるでしょう。
DAアルゴリズム（受入保留方式）
先ほど説明した2つの条件を満たす良いマッチ結果を常に返してくれるような仕組みはあるのでしょうか。それはマッチング理論の分野でよく知られている受入留保アルゴリズム（DAアルゴリズム）というもので、今回の例では次のように動きます。
- 男性は第1希望に、つまりAさんとBさんはXさんに、CさんはYさんに申し込みます。Xさんはより希望の高いAさんを「保留」とし、Bさんを断ります。また、YさんはCさんを「保留」とします。
- Bさんはまだ断られていない中で最も希望の高いYさんに申し込みます。Yさんは、保留しているCさんと新しく申し込んできたBさんを比較して、Bさんを新たに保留し、Cさんを断ります。
- Cさんはまだ断られていない中で最も希望の高いZさんに申し込みます。ZさんはCさんとのマッチを希望していないため、Cさんを断ります。
- Cさんはまだ断られていない中で最も希望の高いXさんに申し込みます。Xさんは、保留しているAさんと新たに申し込んできたCさんを比較して、Cさんを新たに保留し、Aさんを断ります。
- Xさんはまだ断られていない中で最も希望の高いZさんに申し込みます。Zさんは現在保留している人はいなく、Aさんとのマッチは第2希望として希望しているため、Aさんを保留します。
- Aさん、Bさん、Cさんは、それぞれZさん、Yさん、Xさんに保留された状態となったため、この時点の各ペアをマッチさせて終了します。
この方式によって得られるマッチ結果は、先ほど述べた2つの条件を満たすようなものとなります。また、今回は男性側が提案する形のものを例としてあげましたが、女性側が提案する形のものを考えることもできます。その場合、男性側提案の場合と最終的なマッチ結果は異なることもありますが、先述の2つの条件は同様に満たすものとなります。
マッチング理論とは、このように2つのグループからなる参加者が、それぞれ相手側に対してマッチする相手の希望を持っている場合に、どのような仕組みによってマッチさせるのが良いかを考えるものです。今回は男性と女性のマッチングを例にとりましたが、冒頭で説明した社員と配属部署のマッチングなど、さまざまな分野に活用することが可能です。
DAアルゴリズムWEBアプリ
このDAアルゴリズムを簡単に実行することのできるWEBアプリを作成しました。興味を持たれた方はぜひ触ってみてください。
サイバーエージェントにおける「マーケットデザイン」
これまでは、マーケットデザインとはどのような分野なのか、マッチング理論がどういった問題を扱う分野なのかという話を例を用いてしてきました。ここからは、サイバーエージェントにおけるマーケットデザイン関連のプロジェクトの説明をします。
保育所の利用調整
一つ目は、東京大学マーケットデザインセンター（UTMD）と共同で行なっている「保育所の利用調整」に関するプロジェクトです。保育所の利用調整では、児童の保護者が自治体に入園を希望する保育施設のリストを提出し、各保育所の定員と各児童の優先指数をもとに、自治体によって優先度の高い児童から入所施設が割り当てられます。この利用調整は入園を希望する児童を保育所に割り当てるマッチングの問題であると見ることができます。私たちのプロジェクトでは、渋谷区や多摩市とともに、マッチング理論・マーケットデザインの知見を用いて保育所の利用調整を改善するため、以下の観点から実証実験と実装に取り組んでいます。
- 待機児童数やより希望の高い施設に入れる児童数を改善するマッチングアルゴリズムの開発・検証
- 保育施設の定員設計の最適化
- WEB申し込みUIの実験
これらの一連の取り組みから、多摩市の実際の制度の改善につながった事例があります。興味のある方は、こちらのプレスリリースをご覧ください。
マッチングサービスにおける被推薦機会の集中・不平等の緩和
多くのマッチングサービスでは、ユーザーの行動履歴データから興味スコアを行列分解などの推薦手法により算出し、それに基づいてユーザー推薦を行なっています。しかし、マッチングサービスにおいてよくある課題として、ユーザーが希望すると思われる興味スコアの高いユーザーを推薦すると、一部のユーザーが多く推薦されてしまい、被推薦機会の集中と不平等が生じてしまいやすいと指摘されています。
算出された希望をもとに、男性ユーザーに推薦する女性ユーザーと、女性ユーザーに推薦する男性ユーザーを決定する問題も、マッチング理論の枠組みを用いて考えられる問題です。算出された男性から女性への興味スコアと、その女性から男性への興味スコアの双方向の希望を考慮して、適切な推薦を行うことが重要です。
現在私たちがマッチングアプリタップルと取り組んでいるプロジェクトでは、TUマッチング（Matching with Transferable Utility）というマッチング理論のモデルを組み込むことにより、推薦アルゴリズムの改善に取り組んでいます。このプロジェクトについては推薦システムに関する国際カンファレンスである RecSys 2022 のインダストリアルトラックにポスター発表として採択されておりますので、興味のある方はこちらのプレスリリースをご覧ください。
社内活用
また、サービスだけでなく社内の業務改善のためにもマーケットデザイン・マッチング理論を活用しています。
WPPの論文レビュー
サイバーエージェントでは、White Paper Project（WPP）という、社内の技術・研究開発に関する情報を論文形式で執筆し共有する取り組みを行なっています。執筆された論文を、必ずしも専門でない読者にとって読みやすいものにするためには、論文原稿を他の著者にレビューしてもらった上で加筆修正することが有用です。この論文著者内で、比較的分野・興味の近い人同士で論文のレビューをしあえるように、論文著者をマッチさせるシステムを、TTC（Top Trading Cycles）アルゴリズムというマッチングアルゴリズムを用いて活用しています。
発表割り当て
私の所属する研究開発組織AI Labでは、各メンバーが持ち回りで自身のプロジェクトの状況について報告する進捗共有会という会を行なっています。この発表担当日の割り当ても、メンバーと候補日の割り当てという意味でマッチングの問題となります。人によって投稿する学会のスケジュールなどで担当可能な日が異なるため、各メンバーに希望日を書いてもらって担当日を割り振るシステムを、PS（Probabilistic Serial）アルゴリズムというマッチングアルゴリズムを用いて作成しています。
まとめ
これまで、サイバーエージェントにおけるマーケットデザインに関する取り組みをいくつか紹介してきました。限られた資源を配分する問題、人と人あるいは人とモノのマッチングを考える問題はさまざまなところにあります。
マッチングアルゴリズムを活用する際の流れを整理すると、以下のようになります。
まずアンケートをとるか、データから機械学習により人々の希望を集計します。次にこれらの希望と、状況によって課される制約をもとにアルゴリズムによってマッチングを行います。そしてこのマッチ結果を参加者に通知したり、推薦に用いたり、といった形で活用します。
マッチングの問題は世の中のあらゆるところにありますが、マッチング理論を活用しようとする際に一番課題となりやすい点は、一つ目の希望の集計の箇所になります。しかし、テック企業においては、この希望の集計はWEB上でアンケートをとるか、データから機械学習の手法により算出するなどして比較的容易に集計することができるため、これらの全行程を自動化してWEBサービスに組み込むことが可能です。であるならば、経済学・コンピュータサイエンスの世界で長年研究され蓄積されてきたマッチング理論・マーケットデザインの知見を活かさない手はないのではないでしょうか。
サイバーエージェントAI Lab経済学社会実装チームでは、今後もマーケットデザインの知見をサービスの改善に繋げられるよう、研究と社会実装を続けてまいります。
■「CA BASE NEXT 2022」のアーカイブ動画・登壇資料は公式サイトにて公開しています。ぜひご覧ください。
■採用情報
AI事業本部では、最新技術を駆使し事業の成長を牽引できる仲間を募集しています。