希望順位は正直に書いて良いのか？

　皆さんが研究室への配属希望を提出するとき、行きたい研究室を素直に第一希望に書けばよいでしょうか。それとも、人気や定員を予想し、希望順位を変えた方がよいのでしょうか。答えは、大学が採用している配属ルールによって変わります。第一希望者を優先するのか、研究室側の希望を考慮するのかなどによって、配属結果は異なります。

　こうしたルールは、初めから自然に存在するものではなく、私たち人間が目的に応じてつくっています。研究室配属のほかにも、生徒と学校、研修医と病院、社員と部署など、社会には多くのマッチングの機会があります。人生の重要な局面に関わることも多いため、適切なマッチングルールを設計する必要があります。

　マッチング理論では、人と人、人と組織、あるいは組織同士の組み合わせを数学的に研究します。配属の望ましさを数学的に定義し、その基準を満たす組み合わせを見つけるアルゴリズムを設計して、現実の問題に役立てることが目的です。この知見を活用して現実の制度を設計する分野は、マーケットデザインと呼ばれます。

　私は、参加者のインセンティブという観点からマッチング制度を評価しています。制度を運営する側は、参加者の本当の希望を知らないため、希望順位を尋ねます。しかし、順位を偽って申告した方が有利になるなら、参加者は必ずしも正直に答えません。このためマッチング理論では、正直に希望を伝えようと思える「耐戦略性」を重視します。これは現実の制度設計でも重要です。例えば、米国ボストン市の公立学校選択で使われていた「ボストン方式」は、保護者に虚偽の順位申告を促すことが問題となりました。そこで2005年に制度が見直され、正直な申告を促す方式へ変更されました。

　ここでは、耐戦略性に関する私たちの研究を紹介します。一見合理的な方法に、順位和最小メカニズムがあります。第一希望を1点、第二希望を2点と数え、全員の点数の合計が最小になる配属を選ぶ方法です。参加者全員の希望を尊重したルールに見えますが、インセンティブの観点から分析すると弱点が見えてきます。図1は、希望順位を一様ランダムに生成した場合に、有利な虚偽申告が可能な参加者の平均割合を示しています。順位和最小メカニズムではその割合が約半数に上り、制度の見直しにつながったボストン方式を大きく上回りました。これは実際に半数の人が嘘をつくという意味ではありませんが、順位和最小メカニズムが戦略的な行動に対して脆弱である可能性を示しています。この計算実験のため、私たちは離散最適化の知見に基づき、有利な虚偽申告を高速に判定するアルゴリズムを開発し、その正しさを数学的に証明しました。これは、当時私の研究室の修士課程に在籍していた小久保直樹さん、東京科学大学の松井知己教授との共同研究です。

　よい制度とは、申告された希望順位の合計だけを最適化するものではありません。参加者が本当の希望を伝えるインセンティブがあるかを考慮することも大切です。制度のもとで人々がどのように行動するかまで考え、よりよいルールを設計することが、マッチング理論とマーケットデザインの目標です。