Algorithms for Strategic Agents

Опубликовано 27 июня 2016, 18:03

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.