Game-theoretic models relevant for computer science applications usuallyfeature a large number of players. The goal of this paper is to develop ananalytical framework for bounding the price of anarchy in such models. Wedemonstrate the wide applicability of our framework through instantiations forseveral well-studied models, including simultaneous single-item auctions,greedy combinatorial auctions, and routing games. In all cases, we identifyconditions under which the POA of large games is much better than that ofworst-case instances. Our results also give new senses in which simple auctionscan perform almost as well as optimal ones in realistic settings.
展开▼
