Strategyproof-Exposing Mechanisms Descriptions
One of the crowning achievements of the field of Mechanism Design has been the design and usage of the so-called “Deferred Acceptance” matching algorithm. Designed in 1962 and awarded the Nobel Prize in 2012, this algorithm has been used around the world in settings ranging from matching students to schools to matching medical doctors to residencies. A hallmark of this algorithm is that unlike many other matching algorithms, it is “strategy-proof”: participants can never gain by misreporting their preferences (say, over schools) to the algorithm. Alas, this property is far from apparent from the algorithm description. Its mathematical proof is so delicate and complex, that (for example) school districts in which it is implemented do not even attempt to explain to students and parents why this property holds, but rather resort to an appeal to authority: Nobel laureates have proven this property, so one should listen to them. Unsurprisingly perhaps, there is a growing body of evidence that participants in Deferred Acceptance attempt (unsuccessfully) to “game it,” which results in a suboptimal match for themselves and for others.
By developing a novel framework of algorithm description simplicity—grounded at the intersection between Economics and Computer Science—we present a novel, starkly different, yet equivalent, description for the Deferred Acceptance algorithm, which, in a precise sense, makes its strategyproofness far more apparent. Our description does have a downside, though: some other of its most fundamental properties—for instance, that no school exceeds its capacity—are far less apparent than from all traditional descriptions of the algorithm. Using the theoretical framework that we develop, we mathematically address the question of whether and to what extent this downside is unavoidable, providing a possible explanation for why our description of the algorithm has eluded discovery for over half a century. Indeed, it seems that in the design of all traditional descriptions of the algorithm, it was taken for granted that properties such as no capacity getting exceeded should be apparent. Our description emphasizes the property that is important for participants to correctly interact with the algorithm, at the expense of properties that are mostly of interest to policy makers, and thus has the potential of vastly improving access to opportunity for many populations. Our theory provides a principled way of recasting algorithm descriptions in a way that makes certain properties of interest easier to explain and grasp, which we also support with behavioral experiments in the lab.
Joint work with Ori Heffetz and Clayton Thomas.
Yannai A. Gonczarowski is an Assistant Professor of Economics and of Computer Science at Harvard University—the first faculty member at Harvard to have been appointed to both of these departments. Interested in both economic theory and theoretical computer science, Yannai explores computer-science-inspired economics: he harnesses approaches, aesthetics, and techniques traditionally originating in computer science to derive economically meaningful insights. Yannai received his PhD from the Departments of Math and CS, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem, where he was advised by Sergiu Hart and Noam Nisan. Yannai is also a professionally-trained opera singer, having acquired a bachelor’s degree and a master’s degree in Classical Singing at the Jerusalem Academy of Music and Dance. Yannai’s doctoral dissertation was recognized with several awards, including the 2018 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society, and the ACM SIGecom Doctoral Dissertation Award for 2018. For the design and implementation of the National Matching System for Gap-Year Programs in Israel, he was awarded the Best Paper Award at MATCH-UP’19 and the inaugural INFORMS AMD Michael H. Rothkopf Junior Researcher Paper Prize (first place) for 2020. Yannai is also the recipient of the inaugural ACM SIGecom Award for Best Presentation by a Student or Postdoctoral Researcher at EC’18. His first textbook, “Mathematical Logic through Python” (Gonczarowski and Nisan), which introduces a new approach to teaching the material of a basic Logic course to Computer Science students, tailored to the unique intuitions and strengths of this cohort of students, was published by Cambridge University Press in 2022.