Abstract: When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional desiderata beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against strategic manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents.

In this talk, I will focus on robustness against strategic manipulation, and present a new algorithmic framework for these settings. Specifically, I will present a black-box reduction from solving any optimization problem in strategic settings, where the input is held by selfish agents with interests of their own, to solving a perturbed version of that same optimization problem in traditional settings, where the input is directly given. I will further apply this framework to resolve two longstanding open problems: extending Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), and designing truthful mechanisms for job scheduling on unrelated machines (Nisan and Ronen 1999). 

Finally, I will briefly show how strategic considerations motivate nice questions in "traditional" areas of algorithm design as well, and present some of my results in convex optimization, parallel algorithms, and prophet inequalities. 

BIO: Matt received his PhD in EECS from MIT in 2014, advised by Costis Daskalakis, where he was an NPSC, NSF, and Microsoft Graduate Research Fellow. He spent one semester as a Microsoft Research Fellow at the Simons Institute CS/Econ semester, and is now a postdoc at Princeton University in the Computer Science department. His research interests are broadly Algorithmic Game Theory, Mechanism Design and Online Algorithms, with a focus on designing algorithms that address constraints imposed by the strategic nature of the agents that interact with them. Matt received his B.A. in Math from Cornell University.