第 11 回研究会は講演者の来日が延期となったため, 中止となりました. 以下は当初の予定を記録しておくものです.
The seminal, and Nobel-Prize-winning, work of Gale & Shapley (1962) started the field of matching markets. Bolstered by the Internet and mobile computing revolutions, today these markets occupy a sizable fraction of our economy (e.g., the Adwords market, Uber, Airbnb, Up-work) and have yielded effective solutions to important sociological challenges (e.g., markets for assigning students to schools, kidney exchange, and medical residents).
The discipline of algorithm design has had an umbilical connection to matching markets: At the birth of this field lies the highly sophisticated Gale-Shapley stable matching algorithm, whose quintessential game-theoretic property of incentive compatibility follows as a free gift from polynomial time solvability -- it was established two decades after the discovery of the algorithm by Dubins and Freedman.
This talk will provide a panoramic overview of this and other success stories in matching markets, such as a solution to the Adwords problem, which have sophisticated algorithms at their core. The talk will conclude with the general and powerful scheme of Hylland & Zeckhauser (1979) for running a one-sided matching market. Obtaining an efficient algorithm for this scheme is an outstanding 40-year-old open problem.