Quick links

Algorithms for Strategic Agents

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

Matt Weinberg
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.
 
Follow us: Facebook Twitter Linkedin