teacup. [ 掲示板 ] [ 掲示板作成 ] [ 有料掲示板 ] [ ブログ ]


スレッド一覧

  1. 11(0)
  2. ハーゲンダッツの苦味成分と健康被害(0)
  3. 株暴落を手招きする投資家を絶対許してはいけない!(0)
スレッド一覧(全3)  他のスレッドを探す  スレッド作成

*掲示板をお持ちでない方へ、まずは掲示板を作成しましょう。無料掲示板作成

新着順:1953/3559 記事一覧表示 | 《前のページ | 次のページ》

マッチング理論とアルゴリズム

 投稿者:Legacy of Ashesの管理人  投稿日:2013年 5月22日(水)22時27分56秒
  通報 返信・引用 編集済
  http://www.asyura2.com/12/hasan78/msg/252.html

ノーベル経済学賞、シャプレー教授が発見した驚きのアルゴリズム

共同受賞、ロス教授との見事な「マッチング」

2012年10月25日(木)  安田 洋祐

 先週月曜日に発表された今年のノーベル経済学賞は「(マッチング問題における)安定配分の理論とマーケットデザインの実践に関する功績」を讃えて、米ハーバード大学のアルビン・ロス教授とカルフォルニア大学バークレー校のロイド・シャプレー名誉教授に授与された。

 ただし、2人同時受賞とは言っても、両氏がそれぞれ打ち立てた業績は、かなり違う特徴を持つ。ロス教授の愛弟子で筆者の親友でもある小島武仁・米スタンフォード大学助教授が、2012年10月18日付本サイトでロス教授の業績について心のこもった解説を書いていた。小島氏と同じく「マーケットデザイン」を専門とする筆者は、もう1人の受賞者・シャプレー教授の理論に迫り、解説したいと思う。

 マッチング現象を初めて数学の問題として定式化し、誰もが一番ふさわしい相手とマッチできる「安定配分の理論」を生み出したのがシャプレー教授(および故デヴィッド・ゲール)だ。それに対し、その理論を発展させて現実の制度設計(=マーケットデザイン)にまで応用したのがロス教授である。この意味で、実は受賞者2人の業績自体がお互いを補い合う形で見事にマッチングしているのである!

 では、マッチング問題における安定配分の理論を中心に、「理論家シャプレー」の貢献を振り返ってみよう。

わずか7ページの論文で全てが始まった

 安定配分の理論が生まれたのは今からちょうど半世紀前のことである。1962年に数学誌に掲載された「大学入学と結婚の安定性(College Admissions and the Stability of Marriage)」と題するわずか7ページの論文によって、シャプレー教授は共著者であった故デビッド・ゲールと共にマッチングに関する数理分析の分野を切り開いた。

 彼らが考察したマッチング問題は、人と人、人と組織など、2つのグループのメンバー同士をパートナーとしてマッチさせる問題を幅広く扱うものだ。論文タイトルにも含まれる「大学入学」(学生と学校のマッチング)や「結婚」(男性と女性のマッチング)をはじめとして、労働市場(労働者と企業のマッチング)やビジネス上の取引(卸売店と小売店のマッチング)など、経済活動と結びつきが深い応用例を数多く含んでいる。

 ゲールとシャプレーは、社会に溢れるこうしたマッチング現象をまとめて分析するためのフレームワークを確立し、その代表的な解として「安定性」という概念を提唱したのである。

 安定性とはざっくり言うと、たとえマッチング結果から個人やペアが逸脱したとしても、決してその逸脱者たちが当初の結果と比べて得をすることがない、という性質を指す。彼らはこの短い論文(繰り返すが7ページしかない)の中で、安定性を満たすマッチング結果(これを「安定マッチング」と呼ぶ)がどんなマッチング問題にも必ず存在することを示した。さらにそれを見つけるアルゴリズム(機械的な作業手順)まで明らかにしたのである。

 安定マッチングのもとでは、すべての参加者にとって「自分がマッチできる(手の届く)可能性のある相手の中でベストなパートナーとマッチしている」という状況が成立する。これは同時に、マッチング結果が安定マッチングから他の結果へと変わると少なくとも一人は現状よりも損をする、ということを意味する。経済学では、誰も損することなく誰かが得できるような改善の余地が残されていない状況を「パレート効率的」(パレート最適とも呼ばれる)と言う。安定マッチングはこの効率性の条件も満たしているのだ。

 つまりまとめると、安定マッチングとは「お互いの好みを反映し尽くした効率的なマッチング結果」なのだ。ゲールとシャプレーは、このような理想的なマッチングを簡単に見つけることができる仕組みを生み出したわけである。

安定マッチングを導く「GSアルゴリズム」とは

 では、彼らが見つけ出した、安定マッチングを導くアルゴリズムとはどのようなものだろうか。これは考案者にちなんでゲール=シャプレー(GS)アルゴリズムと呼ばれたり、後述するように、その作業の中身から受け入れ保留アルゴリズムと呼ばれたりしている。

 以下では、男性グループと女性グループとの間の1対1のマッチング(合コンをイメージして欲しい)という状況を挙げて、アルゴリズムを解説していく。男性、女性はそれぞれ何人でも構わない。また、説明の単純化のため、各人とも「誰ともマッチせずに1人でいるのは最悪だ」と思っていることにしよう。

 GSアルゴリズムでは、まず参加者たち全員から相手グループのメンバーに対する好みをランキングしてもらう必要がある。そして、提出された好みに基づいてマッチメイカーである第三者が機械的に以下の作業をする。厳密に言うと、GSアルゴリズムはどちらのグループから提案(プロポーズ)するかによって2通りの方法があるのだが、以下では、ゲール教授とシャプレー教授の元の論文に沿って、男性側提案バージョンを紹介する(女性側提案バージョンは、男女の役割を入れ替えればよい)。

<GSアルゴリズムの手順>
各男性が第一希望の女性に一斉にプロポーズ
複数の男性からプロポーズされた女性は、その中でベストの男性を「キープ」(仮マッチ)して後はリジェクト
リジェクトされた男性が第二希望の女性にプロポーズ
女性は毎回ベストな男性をキープ、残りをリジェクト
男性はリジェクトされるたびに残りの中でベストの女性にプロポーズ
 リジェクトされる男性がいなくなるまで以上の作業を続け、この作業がストップした段階でマッチング結果が確定する。各ラウンドで決まるパートナーと直ちにペアが確定するのではなく、あくまで暫定的な仮マッチとなっているのがポイントだ。

 安定マッチングを導くためには、すぐに結果を求めずに、あえて「受け入れを保留する」のが肝心なのである。ここでは男女が1対1でパートナーとなる状況を想定しているが、女性が複数の男性を受け入れるような1対多数の形にも簡単にアルゴリズムを拡張することができる。

 以上、ノーベル賞受賞の決め手となったシャプレー教授の主要功績がお分かりいただけただろうか。この例の男女を、労働者と企業、学生とゼミ(研究室)、研修医と病院、と置き換えることで、様々な現実のマッチング問題にGSアルゴリズムが応用できることが分かるだろう。日本でも、2003年度から、臨床研修医を病院へ配属するためのマッチングの仕組みとしてGSアルゴリズムが実際に使われている。

 さて、上で議論したマッチング問題やGSアルゴリズムでは、マッチングに伴う金銭の授受が考慮されていなかった。実はシャプレーは、1971年に出版されたマーティン・シュービック米エール大学名誉教授との共同研究でこの問題にも取り組んでいる。

 彼らは、売買契約のように金銭授受が可能な場合のマッチング問題について初めて考察し、その理論的に重要な性質を明らかにした。他にも、74年にはハーバート・スカーフ米エール大学名誉教授との共同研究で、参加者がそれぞれ保有するお互いのモノとモノとを交換する「交換問題」を考察した。

偉大な理論家シャプレーの受賞は確実視されていた

 そして、交換問題における安定配分の自然な定義である「コア」(正確には「強コア配分」)が常に一つだけ存在することを示すと共に、それを導くための具体的なアルゴリズムを生み出している。コアとは、たとえ交換結果から個人やグループが逸脱したとしても、決してその逸脱者たちが(当初の結果と比べて)得をすることがない、という配分を指す。

 ちなみに、コアを導くために提案された「トップ・トレーディング・サイクル」(TTC)と呼ばれるアルゴリズムを思いついたのは著者たちではなく、彼らに研究のアドバイスをしたゲール氏だったことが論文内で言及されている。これは、マッチング分野におけるゲール氏の貢献がいかに大きいかを物語るエピソードと言える。

 もしも彼が存命していたなら、今回のノーベル賞を共同受賞したに違いない。4年前に他界したのが悔やまれる。TTCアルゴリズムはその後より一般的な形に拡張され、ロス教授らが学校選択制や腎臓移植の交換メカニズムとして採用を提言している。

 シャプレー教授による理論的貢献はマッチング問題だけに留まらない。おそらく彼の名前をもっとも有名にしたのは「シャプレー値」と呼ばれる、「協力ゲーム理論」で欠かすことのできない主要な概念の発見を通じてだろう。今回は詳細には触れないが、協力ゲーム理論とは、参加者たちが拘束力のある合意(あるいは契約)を結べることを前提に、グループ内での望ましい配分を分析・提案するアプローチである。今まで様々な解が提案されてきたが、シャプレー値はこの中で最も頻繁に用いられている。

 ゲーム理論には、この協力ゲーム理論の他に、拘束力のある合意を前提とせず個々人のインセンティブに基づいてゲームの結果を予測・解釈する「非協力ゲーム理論」と呼ばれるアプローチがある。シャプレー教授はゲーム理論創成期の1950年代から、協力ゲーム理論、非協力ゲームの両分野で数多くの重要な業績を残している。余談ではあるが、シャプレー教授の共同研究者の一人であり、2005年にノーベル経済学賞を受賞したゲーム理論学会の重鎮ロバート・オーマン(イスラエルのヘブライ大学教授)は、筆者も参加した数年前の国際学会で「ここにいるどのノーベル賞学者よりも、シャプレー氏はノーベル賞に値する」旨の発言をしていた。

 それくらいシャプレー教授の存在はゲーム理論の発展にとって大きく、遅きに失することなく無事に今回の受賞に至ったことで、ほっと胸を撫で下ろしている関係者も多いに違いない。

ゲーム理論の聖地プリンストン

 個人的な話で恐縮だが、筆者とシャプレー教授との間には、大学院生活を米プリンストン大学で過ごしたという共通点がある。シャプレー教授が数学科に在籍していた1950年代初頭は、まさにプリンストンがゲーム理論研究の世界的な中心地だった(現在でも、米スタンフォード大学や米ノースウェスタン大学などと並んで研究の一大拠点である)。

 44年に出版された大著『ゲームの理論と経済行動』によってゲーム理論を生み出した大天才ジョン・フォンノイマンはキャンパスからほど近い高等研究所に、共著者オスカー・モルゲンシュテルンは経済学部に在籍していた。

 非協力ゲーム理論における最も重要な解である「ナッシュ均衡」を発見して1994年にノーベル経済学賞を受賞したジョン・ナッシュ氏や、本稿で何度も言及したキー・パーソンのゲール氏はシャプレー教授の数年上の先輩にあたる。共同研究者のシュービック教授とスカーフ教授はいずれも同時期の学友だ。

 こうした恵まれた環境の中で、世界屈指のゲーム理論家集団が基礎研究を量産し、その成果がロス教授をはじめとする後続の研究者たちとの時空を超えたマッチングによって現実の世界に役立てられているのだ。

 半世紀遅れではあるが、彼らと同じ聖地でゲーム理論を学ぶことができた幸運と感慨に改めて浸ると共に、大先輩であるシャプレー教授の受賞を心より祝福したい。

安田 洋祐(やすだ・ようすけ)

政策研究大学院大学助教授。2002年東京大学経済学部卒。2007年、米プリンストン大学経済学部博士課程修了(Ph.D.)、同年から現職。専門はゲーム理論とマーケットデザイン。編著書に『学校選択制のデザイン ゲーム理論アプローチ』(NTT出版)がある。Twitterアカウントは@yagena。(写真:宮原 一郎)

マーケットデザインが経済を変える

http://www.vcasi.org/node/538

3―2:ゲーム理論ってなに?

次に、マーケットデザインの理論的分析を支える屋台骨であるゲーム理論について簡単に解説を試みたい。ゲーム理論は20世紀半ばに誕生した数学の一分野である。1980年代以降その有用性が広く認識され、現在では、経済学を皮切りに政治学や社会学などの社会科学、さらには計算機科学や生物学などの自然科学にまで幅広く応用されるに至っている。その有用性や汎用性を生み出しているのが、ゲーム理論がもたらした以下の二つの大きな成果である。
 一つ目は、(原理的には)世の中のあらゆる社会現象や経済現象を「ゲーム」として記述することができる、という点だ。ゲームは、その現象に関係する当事者=「プレーヤー」、各プレーヤーに与えられた選択肢=「戦略」、プレーヤー達が選んだ戦略の組み合わせに応じて各人に与えられる得点=「利得」、という3要素から構成される。一見するとどんなに複雑そうに見える社会現象も、この3要素に分解してゲームとして記述することができる、というのがポイントだ。
 二つ目の成果は、ゲームの結果を予測する「解」という概念の発見である。せっかく複雑な現象をゲームの形で翻訳しても、もっともらしい結果を予測する解(=答え)が存在しなければ理論としては役に立たない。仏作って魂入れず、というわけだ。この難問を解決して、ゲーム理論に命を吹き込んだのが、2001年のアカデミー賞受賞映画「ビューティフルマインド」(http://www.abeautifulmind.com)の主人公としてお馴染みのナッシュである。彼が弱冠21歳で書き上げた博士論文の中で提唱した「ナッシュ均衡」という革新的な解は、(全てのプレーヤーについて)「仮に自分一人だけが戦略を変えたとしても得することができないような状態」を指す。一見すると、この定義から直接はその凄さが伝わりにくいかもしれないが、これはナッシュ均衡でない状況を考えてみると理解しやすい。
 仮にいま、あるゲームの結果(=戦略の組み合わせ)が、ナッシュ均衡でなかったとしよう。このことは、少なくとも一人は自分の戦略を変えて得することができるようなプレーヤーがいることを意味する。そうしたプレーヤーは戦略を変えるインセンティブを持つため、そもそもの結果が安定的にはならないだろう。つまり、ナッシュ均衡でない状態というのは不安定なのである。逆に言うと、社会で安定して観察される現象というのは、対応するゲームのナッシュ均衡になっているはずなのだ。ナッシュはさらに、ほぼすべてのゲームにおいて、ナッシュ均衡がきちんと存在することも証明した。この重要な結果によって、我々が実際にゲーム理論を使う場合には、解であるナッシュ均衡が見つからない、といった困った事態を心配しないですむのである。

関連記事:ナッシュ均衡とゲーム理論

http://6707.teacup.com/gamenotatsujinn/bbs/index/detail/comm_id/1143

 ここまでの議論をふまえると、ゲーム理論によって経済制度を以下の単純な手続きで分析できることが分かる。まず、分析対象である制度においてプレーヤー、戦略、利得の3要素を見つけだし、ゲームとして定式化する。次に、定式化されたゲームのナッシュ均衡を求める。最後に、ナッシュ均衡によって導かれた結果を分析、検証すればよい、というわけだ。以上の三段階の手続きによって、世の中のありとあらゆる複雑な社会現象が(原理的には)ゲーム理論によって分析できてしまうのである。周波数帯オークションのデザインに応用されたオークション理論や、研修医マッチングで活躍したマッチング理論などは、いずれもゲーム理論の一分野である。ゲーム理論がもたらした新しい知見が、現実のマーケットデザインを支えているのである。

http://

 
 
》記事一覧表示

新着順:1953/3559 《前のページ | 次のページ》
/3559