Bounding the inefficiency of equilibria in nonatomic congestion games

被引：168

作者：

Roughgarden, T ^{[1
]}

Tardos, É ^{[1
]}

机构：

[1] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA

来源：

GAMES AND ECONOMIC BEHAVIOR | 2004年 / 47卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/j.geb.2003.06.004

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

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.

引用

页码：389 / 403

页数：15