Near-Optimal Outcomes in Markets Large and Small
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.