Clayton Thomas FPO (CS 105)
Clayton Thomas will present his FPO "Explainable Mechanism Design" on Wednesday, July 5, 2023 at 10am in CS 402 and Zoom.
Please see below for the members of his committee:
Readers: Huacheng Yu, Ran Raz
Examiners: Matt Weinberg (Adviser), Mark Braverman, and Leeat Yariv (Princeton Economics)
Meeting ID: 972 7504 1458
Talk abstract follows below. All are welcome to join.
Abstract: Mechanism design strives to construct protocols that achieve desirable outcomes in the presence of strategic behavior. Algorithmic mechanism design additionally factors in notions from theoretical computer science—the study of how efficiently these algorithms can communicate between and be implemented on computers. This thesis largely takes a different direction. We study how to effectively explain these algorithms and protocols to real humans. In Part I, we directly confront the objective of better explaining a certain canonical and widely-deployed class of algorithms, namely, matching mechanisms. To begin, we study certain prior frameworks for explanation, and find them to be very restrictive in this setting. Thus, we introduce a new framework for describing these algorithms to participants in a fundamentally different way, with the goal of exposing strategy proofness, a crucial property dictating one’s optimal behavior in these mechanisms. We propose new descriptions, conduct a laboratory experiment on real participants to test our framework, and prove rigorous theorems about the limits of simple descriptions in our framework (according to context-relevant formal notions of simplicity). Then, we investigate a host of additional types of descriptions and explanations using the theoretical tools we have developed.
In Part II, we investigate other novel directions in algorithmic mechanism design that stem from running mechanisms in the real world. We provide two new, worst case separations in the communication requirements of certain canonical mechanism
design problems: first, for incentivizing mechanisms vs. simply computing them; second, for providing strong incentive grantees vs. providing weak ones. We provide a framework for running more complex mechanisms with computationally limited bidders; this framework allows for a broad class of reasonable behaviors of the bidders, and guarantees good performance under modest computational resources.
In Part III, we investigate perhaps more-traditional properties of matching mechanisms, the vital class of mechanisms studied in Part I. We provide new proofs of classical results on both the structure and dynamics of these mechanisms—some of
these proofs are far simpler than known ones. Finally, we investigate a new random distribution over the preferences of agents in these mechanisms, characterizing the effect of heterogeneous attractiveness across different agents.