Network routing games, and more generally congestion games play a central role in algorithmic game theory, comparable to the role of the traveling salesman problem in combinatorial optimization. It is known that the price of anarchy is independent of the network topology for non-atomic congestion games. In other words, it is independent of the structure of the strategy spaces of the players, and for affine cost functions it equals 4/3. In this paper, we show that the situation is considerably more intricate for atomic congestion games. More specifically, we consider congestion games with affine cost functions where the players' strategy spaces are symmetric and equal to the set of bases of a k-uniform matroid. In this setting, we show that the price of anarchy is strictly larger than the price of anarchy for singleton strategy spaces where it is 4/3. As our main result we show that the price of anarchy can be bounded from above by 28/13 ≈ 2.15. This constitutes a substantial improvement over the price of anarchy bound 5/2, which is known to be tight for network routing games with affine cost functions.
展开▼
