Welfare maximization in congestion games

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.