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 mechiii

anisms, 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.