Welfare Maximization in Congestion Games

ABSTRACT 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 game-theoretic approach to this problem, we study centralized solutions for congestion games from a computational point of view. We analyze the computational complexity of the welfare-maximization problem, and provide both approximation algorithms and lower bounds. Throughout the paper, different kinds of congestion effects (externalities) among the players are considered: positive, negative, and unrestricted. Our main algorithmic result is a constant approximation algorithm for congestion games with unrestricted externalities. We 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 games. Finally, we initiate the study of strategic centralized mechanisms in congestion-game environments