期刊
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
卷 25, 期 6, 页码 1224-1236出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/JSAC.2007.070816
关键词
congestion games; incentive compatibility; welfare maximization; approximations
Congestion games are non-cooperative games where the utility of a player from using a certain resource depends on the total number of players that are using the same resource. While most work so far took a distributed game-theoretic approach to this problem, this paper studies centralized solutions for congestion games. The first part of the paper analyzes the problem from a computational perspective. We analyze the computational complexity of the welfare-maximization problem, for which we provide both approximation algorithms and lower bounds. We study this optimization problem under different kinds of congestion effects (externalities) among the players: positive, negative, and unrestricted. Our main algorithmic result is a constant approximation algorithm for congestion games with unrestricted externalities. In the second part of the paper, we also take the strategic behavior of the players into account, and present centralized truthful mechanisms for congestion-game environments. Our main result in this part is an incentive-compatible mechanism for m-resource n-player congestion games that achieves an O(root m logn) approximation to the optimal welfare. We also describe an important and useful connection between congestion games and combinatorial auctions. This connection allows us to use insights and methods from the combinatorial-auction literature for solving congestion-game problems.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据