Algorithms for Strategic Agents | Computer Science Department at Princeton University

Date and Time

Thursday, March 31, 2016 - 12:30pm to 1:30pm

Location

Computer Science Small Auditorium (Room 105)

Type

CS Department Colloquium Series

Speaker

Matt Weinberg, from Princeton University, Computer Science

Host

Mark Braverman

When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional objectives 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 potential 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 one aspect of this agenda and present a new algorithmic framework to solve any optimization problem in a way that is robust to strategic manipulation. I will further apply this framework to extend Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), design mechanisms for job scheduling (Nisan and Ronen 1999), and resolve other problems at the interface of algorithms and game theory.

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

Matt received his PhD in EECS from MIT in 2014, where he was advised by Costis Daskalakis. He is now a postdoc at Princeton University in the Computer Science department. His research focuses on designing algorithms that address constraints imposed by the strategic nature of people that interact with them. For his thesis work on this topic, he received MIT's George M. Sprowls award and the SIGecom Doctoral Dissertation award. Matt received his B.A. in Math from Cornell University.