Fair and Stable Matching (Student)

What Is Computational Thinking?

Computational thinking is a high-level thought process that considers the world in computational terms. It begins with learning to see opportunities to compute something, and it develops to include such considerations as computational complexity; utility of approximate solutions; computational resource implications of different algorithms; selection of appropriate data structures; and ease of coding, maintaining, and using the resulting program. Computational thinking is applicable across disciplinary domains because it takes place at a level of abstraction where similarities and differences can be seen in terms of the computational strategies available. A person skilled in computational thinking is able to harness the power of computing to gain insights. At its best, computational thinking is multidisciplinary and cross-disciplinary thinking with an emphasis on the benefits of computational strategies to augment human insights. Computational thinking is a way of looking at the world in terms of how information can be generated, related, analyzed, represented, and shared.

Module Background

In 1998, the National Resident Match Program changed how they match medical students with hospitals for their residencies. Motivating this change was a concern about fairness. This module looks at a variety of different types of matching problems and discusses the properties that are desirable in each case. Students learn about the classic Gale Shapley algorithm as a means of understanding the notion of stability and fairness as two such desiderata. They discuss how to measure fairness in problem instances that admit multiple stable matchings. Through several prompts, students are motivated to define and compute several different measures of fairness and to compare and contrast their various definitions of fairness. The module concludes by presenting recent results from the research literature that show a surprising convergence of a local measure of fairness, that considers each individual’s median level of satisfaction, with a global measure of fairness based on the median distance measured within a partially ordered set defined on the set of stable matchings.