In Congestion Games, Taxes Achieve Optimal Approximation: Taxes From the Poisson Relaxation of Minimum Social Cost Have Price of Anarchy at Most the Worst Hardness Factor sup ρ_ℓResearch Paper
In an atomic congestion game (Rosenthal, 1973) each of agents chooses a set of resources, such as the edges of a route, and the cost of a resource depends on how many agents use it. Selfish choices are inefficient: the price of anarchy (Koutsoupias and Papadimitriou, 1999) compares the social cost of the worst equilibrium with the minimum social cost, and…