Session 6: Deferred Acceptance Theory

Nick Arnosti

2022/02/07

Lesson Recap

Materials

Lecture Slides (pptx version available to instructors upon request).

Homework (solutions available to instructors upon request).

References:

Strategy-Proof Allocation Mechanisms at Differentiable Points. Satterthwaite and Sonnenschein, 1981. (Introduces the concept of “bossiness.”)

Machiavelli and the Gale-Shapley Algorithm. Dubins and Freedman 1981. (Shows that student-proposing DA is truthful for students.)

The Economics of Matching: Stability and Incentives. Roth, 1982. (Shows that no stable matching is truthful for both sides, and that student-proposing DA is truthful for students.)

An Efficient Algorithm for the “Stable Roommates” Problem. Irving, 1985. (Provides an efficient algorithm to determine whether a stable matching exists, and if so, find it.)

The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics. Roth, 2002. (Provides a table of centralized clearinghouses, indicating whether they are stable, and whether they are still in use.)

Impossibility of stable and nonbossy matching mechanisms. Kojima, 2010. (Provides an example showing that no stable mechanism can be non-bossy.)