How to Compute in a Selfish Society

Опубликовано 17 августа 2016, 0:56

Algorithmic Mechanism Design is concerned with solving computational problems in situations where essential problem data is being held privately by selfish agents. Techniques from economics have long existed for aligning the incentives of the agents with the social good, yet they often require solving a hard optimization problem exactly. On the other hand, computer scientists have coped with intractability by designing approximation algorithms. Unfortunately, recent results have demonstrated that these two approaches are fundamentally at odds for deterministic mechanisms: combining truthfulness and polynomial-time computation results in an inevitable deterioration of the approximation ratio for many important problems. Fortunately, there is hope: randomized mechanisms are emerging that reconcile computational and economic constraints, yielding optimal approximate mechanisms for problems where deterministic mechanisms provably fail. In this talk, I will showcase recent results and techniques pertaining to the design of randomized mechanisms for welfare maximization problems. Specifically, I will (1) Overview recent positive results for paradigmatic problems such as combinatorial auctions and combinatorial public projects, (2) Outline how a black-box reduction can transforms any FPTAS for a social-welfare maximization problem into a truthful FPTAS , and (3) Argue that, in the future, there is hope for more powerful black box reductions for large classes of welfare-maximization problems.