Speaker: Katrina Ligett Time: Wednesday 12-1pm Place: NSH 1507 Title: Truthful, Near-Optimal Mechanism Design Abstract: In many situations, such as auctions, one would like to compute a function on inputs held by selfish players. The players may lie to try to influence the outcome of the algorithm in their favor. Mechanism design seeks to design a pricing scheme and algorithm that incentivize truth-telling. While there exist truthful mechanisms for a wide range of settings, the underlying problem is often NP-hard, and naive attempts at applying approximation algorithms may destroy the truthfulness of a mechanism. We will discuss a general technique, presented by Lavi and Swami in FOCS 2005, for converting approximation algorithms into truthful mechanisms.