読者です 読者をやめる 読者になる 読者になる

2012年ノーベル経済学賞受賞者シャプレー教授死去を悼み、その業績を振り返る。

Economics

www.economist.com

 

2016年3月12日に亡くなられたシャプレー氏は、

1962年にマッチング理論に関する基礎的な論文を発表し

その後ロス氏によって産業界への応用が進み、

その功績が認められたことによって

2012年、ロス氏とともにノーベル経済学賞受賞されました。

 

 

1962年に発表された論文は

Collage admissions and the Stability of Marriage

といいます。

 

この論文中では

ふたつのグループ間の安定マッチングを求めるアルゴリズム

Gale-Shapley(GS) アルゴリズムが提唱されています。

 

特に、男女の結婚マッチング、

病院における研修医のマッチングアルゴリズム

大学の入学許可のアルゴリズムがその具体例として有名でしょうか。

 

 

このアルゴリズムに関しては様々な解説がなされているので

詳説はそちらに譲ります。

business.nikkeibp.co.jp

 

 

この記事では、

二者間のマッチング (two-sided matching) に関する

最新の研究業績について紹介しながら、

シャプレー教授の業績の意義についてお話したいと思います。

 

 

私は博士課程の間に経済学系研究科の神取先生の授業をとって

GSアルゴリズムのことを知りました。

そして、2015年に発表された、

A supply and demand framework for two-sided matching market

(Azevedo and Leshno)

http://www.columbia.edu/~jl4130/AL-Supply-and-demand-matching.pdf

という論文について、授業中発表することとなりました。

 

オール英語で3時間、神取先生に絞られましたが

楽しかった・・・。(フフ。)

 

この論文の新規性は、

シャプレーの論文中でグループの集合の元が有限個であるのに対し、

片方のグループの集合が稠密で、元が非可算無限個ある点にあります。

 

 

この場合において安定マッチングが一意に定まることが示され、

さらに、

その安定マッチングは

各々のグループを需要と供給とした時の均衡点に一致する、

ということが示されています。

 

さて、GSアルゴリズム

ふたつのグループの構成員が有限個である場合を示していました。

構成員が非可算無限であるものは

現実の応用上、存在し得ないと考えられます。

 

なのになぜこの論文が面白いかというと、

観測データ数の増加などによって、

ひとつのグループに対しマッチングする対象が

多数存在するケースが起こるようになったことが理由として挙げられます。

 

その、構成員が多数存在するグループを稠密な集合であると仮定し

その安定マッチングを計算することで

近似解をより少ない計算量で求めることができるということを

この論文中では示唆しています。

 

 

この Azevedo and Leshno の業績は

シャプレーの論文から50年以上経過していますが、

その基本的な概念(GSアルゴリズム)が未だに採用されていることに

驚きを感じました。

 

シャプレーの業績は

その後50年に渡って

最先端の研究でも、現実の社会でも活用されるフレームワークとなったのです。

 

元は大変シンプルな、7ページの論文ですが、

世に大きな変革をもたらした素晴らしい論文であるといえます。

 

シャプレー氏のご冥福をお祈り申し上げます。

素晴らしい研究をありがとうございました。

 

※記事中間違いがありましたら、ぜひぜひご指摘くださいませ。