Class 7: Stable Matchings


Project 3 will be posted soon, and due on Thursday, 19 February.

Office hours schedule:

  • Mondays, 10-11am, 254 Monroe Hall (Denis)
  • Wednesdays, 5-6:30pm, Rice 442 (Jonas)
  • Thursdays, 11am-noon (after class), Rice 507 (Dave)
  • Fridays, 10:30am-noon, Monroe Basement (Joe)


Download (full resolution) PDF


stablematching.ipynb - Jupyter notebook with code for Gale-Shapley algorithm

D. Gale and L. S. Shapley, College Admissions and the Stability of Marriage. The American Mathematical Monthly. Jan 1962. (Superbowl commercial about optimality proof)

Alvin Roth and Elliott Peranson, The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review, Sept 1999.

If you don’t trust a central authority to do the matching fairly or keep the preferences secret, you can use secure computation:

Jack Doerner, David Evans, abhi shelat. Secure Stable Matching at Scale. In 23rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. 24-28 October 2016.

India’s Joint Entrance Examination, cut-off ranks for IIT Bombay