Bounding the inefficiency of equilibria in nonatomic congestion games
成果类型：
Article
署名作者：
Roughgarden, T; Tardos, É
署名单位：
Cornell University
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/j.geb.2003.06.004
发表日期：
2004
页码：
389-403
关键词：
摘要：
Equilibria in noncooperative games are typically inefficient, as illustrated by the Prisoner's Dilemma. In this paper, we quantify this inefficiency by comparing the payoffs of equilibria to the payoffs of a best possible outcome. We study a nonatomic version of the congestion games defined by Rosenthal [Int. J. Game Theory 2 (1973) 65], and identify games in which equilibria are approximately optimal in the sense that no other outcome achieves a significantly larger total payoff to the players-games in which optimization by individuals approximately optimizes the social good, in spite of the lack of coordination between players. Our results extend previous work on traffic routing games. (C) 2003 Elsevier Inc. All rights reserved.