情報科学とゲーム理論／マーケット
デザイン
九州大学大学院システム情報科学研究院
研究院長，主幹教授
横尾 真
E-mail: yokoo@inf.kyushu-u.ac.jp1

九州大学大学院システム情報科学研究院／学府• 学部は工学部電気情報工学科＋理学部物理学科情報理学コース• 研究組織（研究院）と教育組織（学府）が分離• 電気と情報が一体となっている組織，教
員数は教授／准教授／助教で100名超2

アウトライン• イントロダクション:
ゲーム理論／マーケットデザイ
ンとは?
• マーケットデザインの具体例1:
入札• マーケットデザインの具体例2:
マッチング
3

横尾の研究分野• 情報科学– 人工知能
• マルチエージェントシステム• 複数の自律的な主体（人間，ソフトウェア等）の相互作用に着目した研究分野• 各主体（エージェント）は異なる目的を持つ• マルチエージェントシステムの基礎理論として，ゲーム理論（応用数学の一分野）が用いられることが多い• エージェント間の合意形成のルール作り＝マーケットデザイン

4ゲーム理論とは• フォン・ノイマンとモルゲンシュタ
インを始祖とする応用数学の一分野• 経済学のみならず，政治学，法学，心理学，情報科学等への応用が拡大• 社会現象を，プレイヤ，戦略，インセンティブ等で簡潔に記述される「ゲーム」として定式化• 人々のインセンティブを考慮して，より良い社会制度を設計するための重要な解析ツール5

ゲーム理論は何の役に立つか (I)• ゲーム理論はマルチエージェントシ
ステムの解析のためのツールとして（特に以下の場合に）有効–システムが中央集権的に作られていない–全体の効用という概念がない–各エージェントが博愛的とは限らない

6

ゲーム理論は何の役に立つか (II)• ゲーム理論でよく用いられる仮定：– 各プレイヤ／エージェントは一貫性のある（consistentな） 選好／効用を持っている– 各プレイヤは合理的＝上記の効用を最大化しようと努力する– 各プレイヤは，ある戦略に従って行動する
これらの仮定は，人間に関しては（かなり不正確な）近似でしかないが，自律エージェントに関しては極めて妥当
7

ゲーム理論は何の役に立つか (III)• ゲーム理論は言語のようなもの• ミクロ経済学者と計算機科学者の相互理解のために極めて重要• この言語を話すなら，以下の文の意味することは明瞭．一方，この言語を理解しない人に対して，この意味を説明することは困難 or 不可能– “Our newly developed mechanism isstrategyproof, individually rational, and Paretoefficient.”• 注意点：数学なので，前提が成立すれば帰結に疑いの余地はない ⇨ 前提が厳密に成立するか?
8

ゲーム理論は何の役に立つか (V)• 伝統的にはミクロ経済学の一分野• 人間の経済活動を観察し，それを解析／説明するための理論• 工学系出身者としては，説明のためだけのマーケット理論だと物足りないデザイン• 検索連動型広告や学校選択制等の新しい“マーケット” を構築するための理論として発展していく可能性
9マーケットデザインとは• ゲーム理論その他の経済学で得られた知見を生かして現実のマーケット／経済制度の修正又は設計を行う研究分野• マーケット／市場の意味するところは広汎（検索連動型広告，学校選択制等）• ロイド・シャプレイとアルビン・ロスは，マーケットデザイン／マッチング理論研
究に関する成果に対して2012年ノーベル経済学賞を受賞• 主要な実践例：入札とマッチング
10

アウトライン• イントロダクション:
ゲーム理論／マーケットデザインとは?
• マーケットデザインの具体例1:
入札• マーケットデザインの具体例2:
マッチング
11

通常の入札• 最も高い入札をした入札者が，自分の入札値で落札• 他者の入札値を事前に察知できれば利益になる$8000$7000$6000
12Vickrey入札• 最高値の入札者が落札• 支払う金額は二番目に高い入札値
二番目に高い入札値($7000) を支払う

$8000

$7000

$6000
13

Vickrey入札の性質
自分の支払う意思のあるぎりぎりの金額（評価値）を入札するのが最適（正直が最良の策／誘因両立性）• より正確には：– 評価値を𝑣𝑣, 支払額を𝑝𝑝– 落札した場合の効用／うれしさを 𝑣𝑣 − 𝑝𝑝, 負けた場合の効用を0と設定 (大きい方が良い)– 任意の状況に関して以下が成立•

正直に𝑣𝑣を入札した
場合の効用≥ 他の値を入札した
場合の効用

14

組合せ入札• 複数種類の商品 (財) が同時に販売される• 各商品は複数個存在する場合もある• 財の価値の間に依存関係が存在– 補完的: パソコンとメモリ– 代替的: iPhoneとGalaxy
15

組合せ入札の利点• 財の価値に依存関係がある場合：– 個々の財の価値は単独では決められない• パソコンがなければメモリは無価値• iPhoneが買えればGalaxyは要らない– 財がバラバラに売られていると，入札額を決めるのが困難• 財の任意の組合せに対する入札を許すことにより，安心して入札ができる– 両方欲しい，どちらか片方だけ欲しいという入札が可能

16

組合せ入札の適用事例• FCCの周波数帯域のオークション• 空港での離発着権の割当て• トラック配送の請負
• 調達
• …

17

King of Mechanisms?
Vickrey-Clarke-Groves (VCG) メカニズム• 組合せ入札に限らず様々な場面で使える万能メカニズム• 誘因両立性& 社会的余剰（全員の効用の総和）を最大化• アイデアは単純– 社会的余剰を最大化する選択肢を選ぶ– 参加者は（必要に応じて）迷惑料を支払う

自分が参加し迷惑料 ＝ なかった場合の社会的余剰

自分が参加した場
ー 合の，自分を除いた社会的余剰
18

VCGの例
三人の入札者， 二種類の財のオークション

coffee cake both
Bidder1 $6$0 $6
Bidder2 $0$0$8

Bidder3 $0$5$5

結果:•入札者1 がコーヒーを, 3 がケーキを落札•入札者1の支払額は $8－$5＝$3
19•入札者3の支払額は $8－$6＝$2

VCGに関する素朴な疑問• 迷惑料／支払額は操作可能?
• 二項目が大きくなれば減らせる• 普通に考えれば，自分を除いた社会的余剰は操作不可能• 自分が別の架空名義（別のメールアドレス等）を使えるなら操作可能?
自分が参加し迷惑料 ＝ なかった場合の社会的余剰

自分が参加した場
ー 合の，自分を除いた社会的余剰
20

架空名義操作が有効な例
入札者は二人coffee cake bothcoffee cake both
$0 $6$5 $11 Bidder1 $6
Bidder1 $6
Bidder2 $0$0

$8

Bidder2 $0$0

$8

Bidder3 $0$5

$5

入札者1が入札者3という名義を使って入札を分割:•入札者1が両方の財を得る •入札者1 が両方の財を得る•支払額: $8 ー $0 ＝ $8
•支払額: $3 + $2 = $5
正直申告:

21

架空名義操作に関する研究• 最初は当然，既存研究があるものだと思ってエキスパートと議論• 実はVCGに関する架空名義操作の影響解析，
架空名義操作不可能なメカニズムの開発は世界初の研究成果• ゲーム理論を学んだ当初に抱いた素朴な疑問が良い研究テーマになっている
22

アウトライン• イントロダクション:
ゲーム理論／マーケットデザインとは?
• マーケットデザインの具体例1:
入札• マーケットデザインの具体例2:
マッチング
23

マッチング• 学生／児童 ⇔研究室／学校，労働者⇔企業，研修医⇔病院等の望ましい組合せを求める問題• Deferred Acceptance (DA) メカ
ニズム (Gale & Shapley 1964)がよく知られている•3/1024

安定結婚問題• 男性，女性がそれぞれ3人ずついる• 各男性は3人の女性に対して，各女性は3人の男性に対して，好みの順番が決まっている• 好みの順番は，当然，人によって異なる（たまたま同じかも知れない）• 簡単のため，同点はないものとする• 6人から，不安定なペアが存在しないように，ペアを3組作りたい25

不安定なペアとは?

K A• 女性：Alice, Becky, Carol• 男性：John, Ken, LeeJ B• Aliceにとって，J > K > L• Johnにとって，A > B > C• もしAliceのペアがKenで，JohnのペアがBecky
だと，AliceとJohnは，今のペアと別れてペアとなった方が二人ともより幸福• このようなペアを不安定なペアと呼ぶ• 不安定なペアを含まない組合せを安定マッチン
グと呼ぶ
26

安定マッチングを見つける: Deferred Acceptance(DA) mechanism (Gale & Shapley, 1962)• 男性／女性は，独身，婚約中のどちらか• 初期状態では全員独身• 独身の女性が残っていれば，以下の処理を繰り返し適用– 独身の女性は，これまでにまだプロポーズをしていない男性のうちで，最も好みの男性にプロポーズする（男性が婚約中でも気にしない）．一人の男性には一回しかプロポーズできない– 男性は，現在婚約中の女性よりも，より良い相手がプロポーズしてきたら，現在の婚約を解消して，最も好みの女性と改めて婚約する• 独身の女性がいなくなれば，現在婚約中のペアでマッチングを決定
27

DAメカニズムの実行例• 女性は第一希望の男性にプロポーズ• AliceとBeckyが競合• BeckyがリジェクトJohnfirstCarolsecond Alice
third
Becky

KenCarol
Alice
Becky

LeeBecky
Carol
Alice

Alice

Becky

Carol

firstJohn

John

Lee

secondKen

LeeJohn

third

LeeKenKen
28

DAメカニズムの実行例• Beckyは第二希望のLeeにプロポーズ• BeckyとCarolが競合• Carolがリ
ジェクト

John
first
Carol
second Alice
third
Becky

KenCarol
Alice
Becky

Lee
Becky
Carol
Alice

Alice

Becky

Carol

firstJohn

John

Lee

secondKen

LeeJohn

third

LeeKenKen29

DAメカニズムの実行例

John• Carolは第二firstCarol希望のJohnにプロポーズ second Alice• CarolとAlice third
Becky

KenCarol
AliceBecky

LeeBecky
Carol
Alice

Alice

Becky

CarolfirstJohnJohn

LeesecondKenLeeJohnthird

LeeKenKenが競合，Aliceがリ
ジェクト• Aliceが第二希望のKenにプロポーズ

30

DAメカニズムの性質• 女性にとって正直が最良の策– 駄目元でトライしても後悔することはない• 任意の時点で以下が成立– 各女性にとって，婚約中の相手よりも望ましい男性には，すでに断られている– 各男性にとって，今まで断った女性よりも，より望ましい女性と婚約している
よって，終了時のマッチングは安定
31マッチング研究を始めた経緯 (I)• ゲーム理論／マーケットデザインの一分
野として，DAメカニズム等の一応の知識はあったものの，自分で研究するとは思っていなかった• Gale & Shapleyの論文は1962年 (横尾が生まれた年!)• 今頃になって，何か大事な研究テーマが残っているという気がしなかった32

マッチング研究を始めた経緯 (II)• 九州大学電気情報工学科での卒業研究配属（2011年度）を担当• 従来方式は第一希望優先方式（いわゆるボストン方式）

学生側は自身の希望する研究室を第1希望から第n希望まで申告
1. 全学生の第1希望において定員を満たすまで成績順に配属
2. 配属されていない学生と定員の残る研究室で次の希望順位について同様に繰り返す–

33

従来方式の問題点• 学生同士の読みあい– 自分より成績の良い学生の希望順位に応じて、自分の希望順位を変更• 読みを間違えると，望ましくない結果になる• 例：学生1の希望はA研究室，しかし，自分の成績だと第一希望で通る自信がもてず，B研究室を第一希望にした．しかし，蓋を開けてみると難関のA研究室は多くの学生が敬遠し，自分より成績が低い学生２が配属された– 学生1にとってもA研究室にとっても望ましくない（不安定なペア）
34

マッチング研究を始めた経緯 (III)• せっかくなのでDAで実施したいと教授会で提案して承認された• 従来は定員は教授3, 准教授2で固定，しかし，留年等が多くて学生が足りず，教授2, 准教授1を最低保証として，学生の希望が多ければ追加する
ことに変更• この変更にともない，従来方式だと学生の読み合いが複雑化して絶望的

35

マッチング研究を始めた経緯 (IV)
• 当初は，単にDAを使えば良いと思っていた• しかし，各教員の最小配属人数を保証する必要あり（教授2, 准教授1）• これぐらいは既存研究で当然やられているだろうと思ってプロフェッショナルに相談• ところが，この問題は難しくて解けない（厳密には，安定なマッチングが存在しないことがある）と言われて愕然とする (もう教授会で，DAでできると言ってしまった…)36マッチング研究を始めた経緯 (V)• 電気情報工学科での配属は共通の成績ベース（マスターリスト），研究室個別の優先順位は用いない• この場合，最低配属人数（下限制約）を満たす，学生にとって正直が最良の策となる方法が，なんとか作れた– 2011年度より現在に至るまで，九州大学電気情報工学科の卒研配属に開発したメカニズムが用いられている
37

マッチング研究を始めた経緯 (VI)
• もう少し工夫すると，研究室の個別の優先順位も導入可能（マスターリストでタイブレーク）→ Adaptive DAメカニズム• さらに工夫すると，マスターリストを用いないメカニズムも実現可能• 実は，マッチングの結果に何らかの制約がある問題に関しては色々な課題が残っている• ビギナーズラックで良い課題に当たった！
• 安定性が金科玉条になってしまうとチャレンジできなかったかも…
38

ミクロ経済学／ゲーム理論と情報科学のcollaboration (I)• 境界領域での応用分野／研究テーマの広がり• ゲーム理論という言語が話せれば，ミクロ経済学者と情報科学者は意思疎通は可能• 気質の違いは否めない– 情報科学者は，計算機で実現できないと不満– 絵に描いた餅だと嬉しくない– ちゃんと妥当な時間内で計算できるか，人間の持っている知識や選好を計算機上で表現できるかも気にする39

ミクロ経済学／ゲーム理論と情報科学のcollaboration (II)• マーケットデザインでは実現可能性が重要• 情報科学者はコンピュータが使える．色々なツールを使いこなせる．必要があればカスタマイズしたり，自前でプログラムも書ける• メカニズムを実証する，計算量等の実現可能性を考慮した新しいメカニズムや均衡を設計／探索する等の場面でcollaborationが有効• 情報科学研究者は何でも屋，新しい領域を苦にしない→ 経済学／ゲーム理論と，情報科学を含む他分野の40
橋渡し?

ERATO小島マーケットデザイン
プロジェクト• 研究統括：小島武仁（東京大学），専門はミクロ経済学，ゲーム理論，マーケットデザイン– ERATOとしては初の「文系」• 2023年10月スタート，5.5年
理論経済学GL: 神取 道宏（東京大学）ゲーム理論に関する世界的権威・元プリンストン大学助教授・国際学会 Game Theory Society 会長
実験・実証経済学GL: 渡辺 安虎（東京大学）前職はノースウェスタン大とAmazon Japan・東大の産学連携機関の取締役として社会実装にも従事
計算機科学GL: 横尾 真（九州大学）国内外で多数の学術賞を受賞
人工知能分野最大の国際学会 AAAI アジア人初のフェロー
離散数学GL: 田村 明久（慶応義塾大学）離散凸解析と、そのマーケットデザイン・ゲーム理論への応用に関する第一人者
社会実装GL: 野田 俊也（東京大学）ブリティッシュコロンビア大より抜擢・東大UTMDの主要メンバーとして多くの社会実装を手掛ける

研究統括：小島 武仁（東京大学）
前スタンフォード大学教授（通常７年のところ、４年でテニュアを獲得）
日本経済学会中原賞・日本学士院学術奨励賞・Sloan Research Fellowship・Social Choice and Welfare Prizeなど、国内外で多数の受賞

最も生産的な現役の日本人経済学者に複数の指標で認定
41

参考資料

• マーケットデザインに関する書籍– The Handbook of Market Design, Nir Vulkan, Alvin
E. Roth, Zvika Neeman, eds., Oxford Press, 2013.
– 横尾 真，オークション理論の基礎，東京電機大学出版会，2006– 坂井 豊貴，マーケットデザイン: 最先端の実用的な経済学 (ちくま新書) , 2013
– 川越 敏司, マーケット・デザイン オークショ
ンとマッチングの経済学, (講談社選書メチエ),
2015

42

43

理論を適用する際の課題 (I)• ゲーム理論は数学，前提が成立すれば理論的帰結は疑いの余地がない
例：男女100名ずつのお見合いパーティーでDAメカニズムを用いてペアを構成– 理論的帰結は，安定なマッチングが得られ，女性にとっては正直が最良の策– 上記が本当に成立するか? 現実には成立するかどうか怪しい前提が隠れていないか?

44

理論を適用する際の課題 (II)• 前提：男性は，女性に関して，あらかじめ与えられた選好順序を持ち，その順序に従ってプロポーズしてきた女性から，婚約する女性を選ぶ• 自分が男性だとして，以下の状況を考える– 最初の状態では，Aliceの方をBeckyより，ごくわずかに好んでいた– Beckyのみが最初からプロポーズしてくれていた– 一方，Aliceは他の98人の男性から断られ，99人目に自分にプロポーズしてきた– ここでAliceを選べるか?
45

理論を適用する際の課題 (III)• 「自分を一番好きだと思ってくれる人が好き」という感情は自然• しかし，「一番好き」と言ってくれる人を優先するようにメカニズムを構築すると，嘘でも「一番好き」と言ってしまうインセンティブを与えてしまう• 真実を知りたければ，自分にとって都合の悪い真実でも受け入れる覚悟が必要
46