Date and Location: Monday, December 19, 12:00, A 0.23
Presenter: Vasilis Gkatzelis
Title: Decentralized Welfare-Optimizing Mechanisms for Scheduling Games
Author: Vasilis Gkatzelis  (NYU)

Abstract: Game Theory and its algorithmic counterpart, Mechanism Design, are by now standard tools for studying massive decentralized engineering systems such as the Internet.In this context, one of the most prominent issues concerns the design of mechanisms inducing socially efficient outcomes, such as that of Vickrey. Unfortunately these socially optimal mechanisms more often than not require full information and prohibitively large computational resources, something opelessly impractical in large distributed environments.

In this work we study simple mechanisms that require only local information to operate properly. The specific setting in which we describe our work is a classic computationally hard scheduling problem in computer science (namely that of unrelated machine scheduling to minimize the total weighted completion time; here, selfish jobs choose a machine on which to be processed in order to minimize the time at which they are released), though we expect that our results extend to other settings with similar characteristics. Our findings indicate that one can design simple and local mechanisms inducing outcomes whose social cost is bounded by a small constant times that of the socially efficient solution. Furthermore, we exhibit a somewhat counter-intuitive phenomenon by noting that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system. The latter is explained by observing that the additional costs are actually well aligned with negative externalities that players impose on others. We also find that the use of randomization in the design of local mechanisms can lead to yet more improvement in the total welfare.

Most of the policies we consider have attractive properties--notably, they induce exact potential games. This fact, along with the other game-theoretic insights gained, allow us to give a new combinatorial approximation algorithm for the underlying optimization problem. This constitutes an example where ideas from economics are key to the development of algorithms for computationally difficult combinatorial problems.