Simple Proofs of Important Results in Market Design
19Alvin Roth (Stanford University)
https://simons.berkeley.edu/talks/alvin-roth-stanford-university-2023-10-27
Online and Matching-Based Market Design
Two of the founding papers of matching and market design are Gale and Shapley (1962) and Shapley and Scarf (1974). Each introduced an important algorithm: deferred acceptance (DA) and top trading cycles (TTC), respectively. And each included fundamental theorems that could be proved very simply, sometimes essentially verbally.
Some important subsequent theorems also allow very simple proofs (although the simple proofs were seldom the first to be discovered). I’ll make an attempt to introduce (parts of) modern matching theory using only simple proofs, some fairly recent, largely concerning DA and TTC.