Algorithms for Strategic Agents

January 10, 2014
Matthew Weinberg | Massachusetts Institute of Technology

In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents (who may choose to lie) whose incentives may not align with your own? This talk will present recent results on black-box reductions from mechanism to algorithm design. That is, we show how to solve optimization problems while properly incentivizing strategic agents using only black-box access to an algorithm for (a modified version of) the same optimization problem when the input is directly given. This talk will not assume any knowledge of economics or game theory.

I will also briefly discuss other results on revenue maximization and prophet inequalities.

Speaker Details

Matt is a PhD candidate at the Massachusetts Institute of Technology, where he is advised by Costis Daskalakis. His research lies mostly at the intersection of Computer Science and Economics, including Algorithmic Game Theory, Online Algorithms, and Applied Probability. He obtained his B.A. in Math from Cornell University.