Game-theoretic models relevant for computer science applications usually
feature a large number of players. The goal of this paper is to develop an
analytical framework for bounding the price of anarchy in such models. 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 POA of large games is much better than that of
worst-case instances. Our results also give new senses in which simple auctions
can perform almost as well as optimal ones in realistic settings.

本文开发了一个框架，为计算机科学应用中涉及到的包含多个参与者的博弈论模型提供了红利保障，以减小其混沌的程度，实现了对多个经典模型的实例化，包括 “同时出价单项竞拍”、“贪婪组合式拍卖” 和 “路由博弈”，并鉴定了在什么情况下多方博弈的 POA 更好，同时也给出了简单竞拍可以在现实中表现出几乎和最优竞拍一样的效果的新的方面。

大型博弈中的混乱代价

The Price of Anarchy in Large Games

The analysis of network routing games typically assumes, right at the onset,
precise and detailed information about the latency functions. Such information
may, however, be unavailable or difficult to obtain. Moreover, one is often
primarily interested in enforcing a desired target flow as the equilibrium by
suitably influencing player behavior in the routing game. We ask whether one
can achieve target flows as equilibria without knowing the underlying latency
functions.
Our main result gives a crisp positive answer to this question. We show that,
under fairly general settings, one can efficiently compute edge tolls that
induce a given target multicommodity flow in a nonatomic routing game using a
polynomial number of queries to an oracle that takes candidate tolls as input
and returns the resulting equilibrium flow. This result is obtained via a novel
application of the ellipsoid method. Our algorithm extends easily to many other
settings, such as (i) when certain edges cannot be tolled or there is an upper
bound on the total toll paid by a user, and (ii) general nonatomic congestion
games. We obtain tighter bounds on the query complexity for series-parallel
networks, and single-commodity routing games with linear latency functions, and
complement these with a query-complexity lower bound. We also obtain strong
positive results for Stackelberg routing to achieve target equilibria in
series-parallel graphs.
Our results build upon various new techniques that we develop pertaining to
the computation of, and connections between, different notions of approximate
equilibrium; properties of multicommodity flows and tolls in series-parallel
graphs; and sensitivity of equilibrium flow with respect to tolls. Our results
demonstrate that one can indeed circumvent the potentially-onerous task of
modeling latency functions, and yet obtain meaningful results for the
underlying routing game.

该研究提出了一种新的基于 ellipsoid 算法的方法，通过构建边缘通行费，不需要准确的延迟函数信息，就可以在多商品流量情况下实现目标流量作为平衡，并在系列并行网络和单商品交通流中得到良好结果。