We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA = O( + log n), where is the length of the longest path in the player strategy sets, and n is the size of the network. where κ is the length of the longest cycle in the network, and c is a constant.
In REF , the authors consider bottleneck routing games in networks with player cost C i and social cost C. They prove that the price of stability is 1 (the price of stability measures the ratio of the best Nash equilibrium social cost versus the coordinated optimal solution).
Atomic Routing Games on Maximum Congestion
AAIM
Mathematics Computer Science