Tilting at Windmills: The Economic Efficiency of Large Games

Abstract:

 

It is well-established that when participants in a system behave strategically, this can lead to sub-optimal outcomes in the worst case.  But computer science applications typically exhibit conditions not present in these worst-case scenarios.  Instead, they often feature a large number of participants who have a degree of uncertainty about the game they're playing.  The goal of this talk is to develop an analytical framework for bounding the inefficiency of games under such conditions. 

 

Our framework is based on a novel extension of smoothness, a standard technique for developing inefficiency, or price-of-anarchy, bounds in fixed games, to a sequence of games.  We first define an approximate utility -- one that a delusional player might imagine he faces.  We prove that this utility well-approximates the actual utility under realistic structural assumptions regarding market size and noise.  We then show that this approximate utility is smooth with respect to the actual game.

 

We demonstrate the wide applicability of our framework through instantiations for 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 worst-case instances.

 

Based on joint work with Michal Feldman, Brendan Lucier, Tim Roughgarden, and VasilisSyrkganis.