Search Search

Near-Optimal Outcomes in Markets Large and Small

Friday, October 9, 2015
12:00 PM - 1:00 PM
Location: Baxter 125
Brendan Lucier, Researcher, Microsoft Research, New England


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.

Series: Linde Institute/Social and Information Sciences Laboratory Seminar Series (SISL)
For more information, please phone 626-395-4083 or email

Upcoming events

Event archive