坂井豊貴、2013年9月、ちくま新書
「マッチングを勉強したい」と話したら、正人さんから勧められた2冊のうちの1冊。学生時代にゲーム理論の初日で挫折し、現在は研究テーマで迷走中だったが、過去の実体験と経済学が結びついた喜びを素直に感じて、前に進めそうな気になった。各章の後半で、日本における適用を考察しているが、1990年代後半からマッチング理論の様々な領域への適用を検討してきた米国に対して、政策議論に経済学の知見が結びつかないまま、現在に至ていることが、現在の日米の生産性の差につながっているように感じた。
はじめに
第1章 組み合わせの妙技－アルゴリズム交換とその威力
第2章 両想いの実現－マッチング理論のケーススタディ
第3章 競り落としの工夫－オークション理論と経済価値の発見
読書案内
おわりに
参考文献
はじめに
マッチングを勉強するのに「マーケットデザイン」の本とは？と思いながら読み始めたところ、「マーケットデザイン」は経済学の新しい分野で、どんなに優れたモノを作っても適切な持ち手に届けないと製品としての価値が生まれず、社会を豊かにすることは出来ないことから、物理的なものづくりに対して、経済学的ものづくりに関する学問分野だという。18世紀のアダム・スミスは『国富論』で市場の価格調整機能を「神の見えざる手」と表現したが、実際の市場はブラックボックスではない。経済学に基づき、市場のルールを設計するのがマーケットデザインである。1870年代に現代経済学の礎を築いたレオン・ワルラスは経済学を技術として活用することに深い関心を抱いていたが、マーケットデザインは、役に立つことが分かりやすく、また使いやすいのが特徴である。
第1章 組み合わせの妙技－アルゴリズム交換とその威力
腎移植にマッチング理論を用いて患者とドナーの組み替えを組織的に行えるよう、最初に分析したのがアルビン・ロス、タイフン・ソンメツ、ウトック・ユンベル教授達で、彼らの研究を端緒として腎移植マッチングの研究が進展し、パク博士らのアイデアで実現することになる。
腎移植マッチングで考察するのは腎臓を求め需要する患者と腎臓を与え供給するドナーの間で、需給の一致を実現させることで、腎臓という希少資源を社会で上手く配分することを意味している。多くのマーケットデザインの研究では「どう制度を作れば需給一致が実現するか」を考察する。つまり良い結果が導かれるよう、逆算して制度を設計していく発想がマーケットデザインという学問分野の特徴である。
ロスとソンメツ、ユンベルが2004年に発表した共同論文の腎移植マッチングモデルは、ロイド・シャプリーとハーバート・スカーフによる「住宅市場モデル」に基づいている。腎臓と住宅は「ひとりが一つしか要らない」という点が似ている。住宅市場モデルを扱う『コアと非分割性』は1974年のジャーナル・オブ・マスティカル・エノコミクス誌に掲載されている。住宅市場モデルとは、今の部屋に満足していない学生が、一同に会して、学生寮の部屋を交換するが、その場の最低限の取り決めとして、誰も今より嫌な部屋には移らないという「個人道理性」という条件を尊重する。4人の学生がいて、各自が部屋を持っており、今の部屋に対して満足しておらず、４つの部屋に対して順位（選好）を付ける。学生と部屋の組合せを「配分」と呼び、配分Ａより配分Ｂが優れていることを「パレート改善」するという。パレート改善することがない配分のことを「パレート効率的」という。
グループの抜け駆けを「ブロック」というが、ブロックが起こり得ない配分のことを「強コア配分」という。強コア配分の存在に関する重要な事実としては２つあり、
事実１：強コア配分は必ず存在する。強コア配分を実現しようという目標を立てることは意味をなす。
事実２：強コア配分は必ずただ一つしか存在しない。強コア配分の実現を目指すとして、どの強コア配分にしようか迷う余地はない。
配分は数が増えるにしたがって増えていくため、それが強コア配分かどうかを確認するのは大変になる。この問題を解決するために編み出されたのがデビッド・ゲールによるトップ・トレーディング・サイクル・アルゴリズム（ＴＴＣアルゴリズム）であるが、ＴＴＣアルゴリズムは1974年のシャプリーとスカーフの論文内で「これはゲールにより考案されたものだ」として初めて世に出ているが、ゲール自身の論文に掲載されたわけではないので、ＴＴＣアルゴリズムについて記載する場合は「ゲールによるＴＴＣアルゴリズム」と述べたうえで、シャプリーとスカーフの論文を引用する必要がある。
配分の個数はnの階乗!であるが、ＴＴＣアルゴリズムの下では、人々の選好がどのようであろうとも、各回のステップが必ず一つはサイクルができる。よって各回、最低一人はその場からいなくなる。そのためn人の学生がいるとしても、n回のステップでその場からいなくなり、終了する。
多数決のルールの下では正直に投票することが必ずしも得策ではないが、TTCアルゴリズムの下では、虚偽の指差しにより得をすることは一切ないことをロスが証明しており、この性質を「耐戦略性」と呼ぶ。
ラトガース大学のジンペン・マー准教授は1994年のインターナショナル・ジャーナル・オブ・ゲームセオリー誌に掲載した論文で、耐戦略性、パレート効率性、個人合理性を満たすルールは強コアルールの他には存在しないことを示した。ある特定のルールを、いくつかの性質を満たす唯一のものであると数学的に示すことを公理的特徴付けという。
トルコ出身の研究者、アティラ・アブドゥルカディログルとタイフン・ソンメルらは、住宅市場モデルを、既に自分の部屋を持つ学生（居住者）たちの間だけで部屋を交換するのではなく、空き部屋と新たな入寮者が存在するようなモデルに拡張し、そこで上手く働くようなＴＴＣアルゴリズムの修正を考え、『居住者がいる場合の住宅配分』というタイトルで、1999年のジャーナル・オブ・エコノミックセオリー誌に公刊されている。それが後に腎移植マッチングにつながっていく。
居住者＝患者
居住者の部屋＝患者のドナー
空き部屋＝献腎
入寮者＝ドナーを持たない患者と読み替えることができるが、住宅配分問題と異なるのは、空き部屋（献腎）の数が少なく、またそれは最初からあるものではなく、たまに提供されるという腎移植マッチング特有の事情がある。
ロスたちは2004年の論文では主にＴＴＣアルゴリズムに基づいた、つまりサイクルのサイズを制限しないアルゴリズムについて論じ、翌年のジャーナルに掲載した論文では『2組ごとの腎臓交換』ではドナー交換を2組間のみに留めるとどうなるかという問題を考察、その後の関連論文で得られた成果を要約すると、ドナー交換を3組、4組まで広げると、適合ペアの数は飛躍的に増加していく。
裏切りをどうしても阻止したいならば、メリーランド大学のローレンス・オーズベル教授とノースカロライナ州立大学のセイヤーモリル助教授らが提案した、不適合ペアのドナーの腎臓を先に取っておくというマッチング方法が良い。二人はこのアイデアをマクロ経済学の世代重複モデルから得たと述べている。
第2章 両想いの実現－マッチング理論のケーススタディ
ゲールとシャプリーは1962年に米国数学会の月誌に公刊した『大学入試と結婚の安定性』というタイトルの論文で、マッチングを定式化し、安定マッチングと呼ばれる組合せの概念を導入し、安定マッチングを短時間で見つける受入保留方式と呼ばれるアルゴリズムを与えた。これは今日、研修医マッチングや学校選択マッチング、大学の付属高校から大学学部への学生の割当など、多くの場面で活用されている。
ロスは研修医マッチングに続き、2000年代になってボストン市とニューヨーク市における公立学校のマッチング方式の改正に関わるが、マッチング理論を学校選択の文脈で活用することを最初に論じたのはボストン・カレッジのソンメツ教授とその共同研究者たちである。研修医マッチングでは各病院が研修医に対して選好を持っていたが、公立学校側に「どの学生が欲しい」ような選好は持たない。
ボストン市では、ロスが改革に携わる前は「早いもの勝ち」的なボストン方式と呼ばれる方法がとられていた。研修医マッチングでは各研修医が「最初の持ち分の病院」を持っていないので、TTC方式は利用できないが、学区の概念が意味を持つ学校選択マッチングでは、TTC方式は耐戦略性を満たし、財の配分においてパレート効率性を実現する。また自分の学区の学校より嫌な学校には割り当てられないという個人合理性も満たす。ボストン、受入保留方式、TTCのどの方式を採用するかで結果が大きく変わってくる。
第3章 競り落としの工夫－オークション理論と経済価値の発見
第2価格オークションとは勝者が入札額の中で二番目に高い金額を支払う方式である。相手がどのような行動を取ろうとも、自分にとって常に最適な行動をすることを支配戦略というが、第2価格オークションの下では、各参加者が自分の評価額をそのまま正直に入札するのが支配戦略になっており、耐戦略性を満たすという。
各買い手は他者の入札行動が分からないので、確率的に他社の入札行動を予想して、自分の利得の予想額が最大化するよう入札する（ゲーム理論のベイジアンナッシュ均衡という概念）。第1価格オークションの下で期待収益を計算すると、実はその金額は第2価格オークションでの期待収益と一致することを、1961年にウィリアム・ヴィックリーがジャーナル・オブ・ファイナンス誌に掲載した論文で示したもので、収益同値定理と言う。オークション理論という新領域の幕開けとなる貢献で、1996年にノーベル経済学賞を与えられている。
一個の財を売るときには第2価格オークションが耐戦略性を満たす優れた方式だが、複数個の財を売る同質財オークションにおいて耐戦略性を満たすのは新方式のヴィックリーオークションである。
ビッド支払いオークション：上位の限界評価から順に財を割り当てていき、その金額を支払ってもらう方式で、価格差別オークションとも呼ばれるが耐戦略性を満たすものではない。
次点価格オークション、次点価格オークションの耐戦略性を満たしそうな修正を加えても、また満たさない。
ヴィックリーオークション：例えば2個の財を得た勝者は「他者の入札額のうち、落札できなかったものの中で上位２つ」に当たる金額を支払う。
ハイエクは競争を「発見の手段」と表現したが、オークションに限らず、マーケットデザインの特徴は、あくまでルールを作るという点にある。計画経済のように結果を定めるのではなく、手段を定めるものである。18世紀にアダム・スミスが考察した自由市場の機能と、19世紀にレオン・ワルラスが重視した技術としての経済学、そして20世紀にフリードリヒ・フォン・ハイエクが「発見の手段」と評した競争のアイデア。それらの知見を21世紀に結実させ開花した地域の結晶がマーケットデザインである。
「マッチングを勉強したい」と話したら、正人さんから勧められた2冊のうちの1冊。学生時代にゲーム理論の初日で挫折し、現在は研究テーマで迷走中だったが、過去の実体験と経済学が結びついた喜びを素直に感じて、前に進めそうな気になった。各章の後半で、日本における適用を考察しているが、1990年代後半からマッチング理論の様々な領域への適用を検討してきた米国に対して、政策議論に経済学の知見が結びつかないまま、現在に至ていることが、現在の日米の生産性の差につながっているように感じた。
はじめに
第1章 組み合わせの妙技－アルゴリズム交換とその威力
第2章 両想いの実現－マッチング理論のケーススタディ
第3章 競り落としの工夫－オークション理論と経済価値の発見
読書案内
おわりに
参考文献
はじめに
マッチングを勉強するのに「マーケットデザイン」の本とは？と思いながら読み始めたところ、「マーケットデザイン」は経済学の新しい分野で、どんなに優れたモノを作っても適切な持ち手に届けないと製品としての価値が生まれず、社会を豊かにすることは出来ないことから、物理的なものづくりに対して、経済学的ものづくりに関する学問分野だという。18世紀のアダム・スミスは『国富論』で市場の価格調整機能を「神の見えざる手」と表現したが、実際の市場はブラックボックスではない。経済学に基づき、市場のルールを設計するのがマーケットデザインである。1870年代に現代経済学の礎を築いたレオン・ワルラスは経済学を技術として活用することに深い関心を抱いていたが、マーケットデザインは、役に立つことが分かりやすく、また使いやすいのが特徴である。
第1章 組み合わせの妙技－アルゴリズム交換とその威力
腎移植にマッチング理論を用いて患者とドナーの組み替えを組織的に行えるよう、最初に分析したのがアルビン・ロス、タイフン・ソンメツ、ウトック・ユンベル教授達で、彼らの研究を端緒として腎移植マッチングの研究が進展し、パク博士らのアイデアで実現することになる。
腎移植マッチングで考察するのは腎臓を求め需要する患者と腎臓を与え供給するドナーの間で、需給の一致を実現させることで、腎臓という希少資源を社会で上手く配分することを意味している。多くのマーケットデザインの研究では「どう制度を作れば需給一致が実現するか」を考察する。つまり良い結果が導かれるよう、逆算して制度を設計していく発想がマーケットデザインという学問分野の特徴である。
ロスとソンメツ、ユンベルが2004年に発表した共同論文の腎移植マッチングモデルは、ロイド・シャプリーとハーバート・スカーフによる「住宅市場モデル」に基づいている。腎臓と住宅は「ひとりが一つしか要らない」という点が似ている。住宅市場モデルを扱う『コアと非分割性』は1974年のジャーナル・オブ・マスティカル・エノコミクス誌に掲載されている。住宅市場モデルとは、今の部屋に満足していない学生が、一同に会して、学生寮の部屋を交換するが、その場の最低限の取り決めとして、誰も今より嫌な部屋には移らないという「個人道理性」という条件を尊重する。4人の学生がいて、各自が部屋を持っており、今の部屋に対して満足しておらず、４つの部屋に対して順位（選好）を付ける。学生と部屋の組合せを「配分」と呼び、配分Ａより配分Ｂが優れていることを「パレート改善」するという。パレート改善することがない配分のことを「パレート効率的」という。
グループの抜け駆けを「ブロック」というが、ブロックが起こり得ない配分のことを「強コア配分」という。強コア配分の存在に関する重要な事実としては２つあり、
事実１：強コア配分は必ず存在する。強コア配分を実現しようという目標を立てることは意味をなす。
事実２：強コア配分は必ずただ一つしか存在しない。強コア配分の実現を目指すとして、どの強コア配分にしようか迷う余地はない。
配分は数が増えるにしたがって増えていくため、それが強コア配分かどうかを確認するのは大変になる。この問題を解決するために編み出されたのがデビッド・ゲールによるトップ・トレーディング・サイクル・アルゴリズム（ＴＴＣアルゴリズム）であるが、ＴＴＣアルゴリズムは1974年のシャプリーとスカーフの論文内で「これはゲールにより考案されたものだ」として初めて世に出ているが、ゲール自身の論文に掲載されたわけではないので、ＴＴＣアルゴリズムについて記載する場合は「ゲールによるＴＴＣアルゴリズム」と述べたうえで、シャプリーとスカーフの論文を引用する必要がある。
配分の個数はnの階乗!であるが、ＴＴＣアルゴリズムの下では、人々の選好がどのようであろうとも、各回のステップが必ず一つはサイクルができる。よって各回、最低一人はその場からいなくなる。そのためn人の学生がいるとしても、n回のステップでその場からいなくなり、終了する。
多数決のルールの下では正直に投票することが必ずしも得策ではないが、TTCアルゴリズムの下では、虚偽の指差しにより得をすることは一切ないことをロスが証明しており、この性質を「耐戦略性」と呼ぶ。
ラトガース大学のジンペン・マー准教授は1994年のインターナショナル・ジャーナル・オブ・ゲームセオリー誌に掲載した論文で、耐戦略性、パレート効率性、個人合理性を満たすルールは強コアルールの他には存在しないことを示した。ある特定のルールを、いくつかの性質を満たす唯一のものであると数学的に示すことを公理的特徴付けという。
トルコ出身の研究者、アティラ・アブドゥルカディログルとタイフン・ソンメルらは、住宅市場モデルを、既に自分の部屋を持つ学生（居住者）たちの間だけで部屋を交換するのではなく、空き部屋と新たな入寮者が存在するようなモデルに拡張し、そこで上手く働くようなＴＴＣアルゴリズムの修正を考え、『居住者がいる場合の住宅配分』というタイトルで、1999年のジャーナル・オブ・エコノミックセオリー誌に公刊されている。それが後に腎移植マッチングにつながっていく。
居住者＝患者
居住者の部屋＝患者のドナー
空き部屋＝献腎
入寮者＝ドナーを持たない患者と読み替えることができるが、住宅配分問題と異なるのは、空き部屋（献腎）の数が少なく、またそれは最初からあるものではなく、たまに提供されるという腎移植マッチング特有の事情がある。
ロスたちは2004年の論文では主にＴＴＣアルゴリズムに基づいた、つまりサイクルのサイズを制限しないアルゴリズムについて論じ、翌年のジャーナルに掲載した論文では『2組ごとの腎臓交換』ではドナー交換を2組間のみに留めるとどうなるかという問題を考察、その後の関連論文で得られた成果を要約すると、ドナー交換を3組、4組まで広げると、適合ペアの数は飛躍的に増加していく。
裏切りをどうしても阻止したいならば、メリーランド大学のローレンス・オーズベル教授とノースカロライナ州立大学のセイヤーモリル助教授らが提案した、不適合ペアのドナーの腎臓を先に取っておくというマッチング方法が良い。二人はこのアイデアをマクロ経済学の世代重複モデルから得たと述べている。
第2章 両想いの実現－マッチング理論のケーススタディ
ゲールとシャプリーは1962年に米国数学会の月誌に公刊した『大学入試と結婚の安定性』というタイトルの論文で、マッチングを定式化し、安定マッチングと呼ばれる組合せの概念を導入し、安定マッチングを短時間で見つける受入保留方式と呼ばれるアルゴリズムを与えた。これは今日、研修医マッチングや学校選択マッチング、大学の付属高校から大学学部への学生の割当など、多くの場面で活用されている。
ロスは研修医マッチングに続き、2000年代になってボストン市とニューヨーク市における公立学校のマッチング方式の改正に関わるが、マッチング理論を学校選択の文脈で活用することを最初に論じたのはボストン・カレッジのソンメツ教授とその共同研究者たちである。研修医マッチングでは各病院が研修医に対して選好を持っていたが、公立学校側に「どの学生が欲しい」ような選好は持たない。
ボストン市では、ロスが改革に携わる前は「早いもの勝ち」的なボストン方式と呼ばれる方法がとられていた。研修医マッチングでは各研修医が「最初の持ち分の病院」を持っていないので、TTC方式は利用できないが、学区の概念が意味を持つ学校選択マッチングでは、TTC方式は耐戦略性を満たし、財の配分においてパレート効率性を実現する。また自分の学区の学校より嫌な学校には割り当てられないという個人合理性も満たす。ボストン、受入保留方式、TTCのどの方式を採用するかで結果が大きく変わってくる。
第3章 競り落としの工夫－オークション理論と経済価値の発見
第2価格オークションとは勝者が入札額の中で二番目に高い金額を支払う方式である。相手がどのような行動を取ろうとも、自分にとって常に最適な行動をすることを支配戦略というが、第2価格オークションの下では、各参加者が自分の評価額をそのまま正直に入札するのが支配戦略になっており、耐戦略性を満たすという。
各買い手は他者の入札行動が分からないので、確率的に他社の入札行動を予想して、自分の利得の予想額が最大化するよう入札する（ゲーム理論のベイジアンナッシュ均衡という概念）。第1価格オークションの下で期待収益を計算すると、実はその金額は第2価格オークションでの期待収益と一致することを、1961年にウィリアム・ヴィックリーがジャーナル・オブ・ファイナンス誌に掲載した論文で示したもので、収益同値定理と言う。オークション理論という新領域の幕開けとなる貢献で、1996年にノーベル経済学賞を与えられている。
一個の財を売るときには第2価格オークションが耐戦略性を満たす優れた方式だが、複数個の財を売る同質財オークションにおいて耐戦略性を満たすのは新方式のヴィックリーオークションである。
ビッド支払いオークション：上位の限界評価から順に財を割り当てていき、その金額を支払ってもらう方式で、価格差別オークションとも呼ばれるが耐戦略性を満たすものではない。
次点価格オークション、次点価格オークションの耐戦略性を満たしそうな修正を加えても、また満たさない。
ヴィックリーオークション：例えば2個の財を得た勝者は「他者の入札額のうち、落札できなかったものの中で上位２つ」に当たる金額を支払う。
ハイエクは競争を「発見の手段」と表現したが、オークションに限らず、マーケットデザインの特徴は、あくまでルールを作るという点にある。計画経済のように結果を定めるのではなく、手段を定めるものである。18世紀にアダム・スミスが考察した自由市場の機能と、19世紀にレオン・ワルラスが重視した技術としての経済学、そして20世紀にフリードリヒ・フォン・ハイエクが「発見の手段」と評した競争のアイデア。それらの知見を21世紀に結実させ開花した地域の結晶がマーケットデザインである。