Linde Institute/SISL Seminar: Brendan Lucier

Abstract

Theoretical computer scientists often study markets with a pessimistic view, analyzing performance in the worst case.  However, realistic game-theoretic applications typically feature properties that exclude these worst-case scenarios.  For example, many important markets approach optimality as the number of participants grows large, assuming a sufficient degree of uncertainty in the game.  This talk aims at a middle ground.  We develop an analytic framework for establishing robust, worst-case performance guarantees that improve for large, well-behaved games.

We will survey recent results bounding the worst-case inefficiency of equilibria in (potentially small) market games, using the smoothness technique.  We will then extend this framework to a sequence of games.  We demonstrate the applicability of our framework through instantiations of several well-studied models, including simultaneous single-item auctions, greedy combinatorial auctions, and routing games. In all cases, we identify conditions under which the efficiency of large games is much better than that of small, worst-case instances.

Based on joint work with Michal Feldman, Nicole Immorlica, Tim Roughgarden, and Vasilis Syrkganis.