  In this work, we consider the problem of minimising the social cost in atomic
congestion games. For this problem, we provide tight computational lower bounds
along with taxation mechanisms yielding polynomial time algorithms with optimal
approximation.
  Perhaps surprisingly, our results show that indirect interventions, in the
form of efficiently computed taxation mechanisms, yield the same performance
achievable by the best polynomial time algorithm, even when the latter has full
control over the agents' actions. It follows that no other tractable approach
geared at incentivizing desirable system behavior can improve upon this result,
regardless of whether it is based on taxations, coordination mechanisms,
information provision, or any other principle. In short: Judiciously chosen
taxes achieve optimal approximation. Three technical contributions underpin
this conclusion. First, we show that computing the minimum social cost is
NP-hard to approximate within a given factor depending solely on the admissible
resource costs. Second, we design a tractable taxation mechanism whose
efficiency (price of anarchy) matches this hardness factor, and thus is
worst-case optimal. As these results extend to coarse correlated equilibria,
any no-regret algorithm inherits the same performances, allowing us to devise
polynomial time algorithms with optimal approximation.
