This is a preserved file from MMM Spring 2019. An updated version may exist at https://uvammm.github.io/

Class 7: Stable Matchings

Schedule

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)

Slides


Download (full resolution) PDF

Links

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