  In this work we study the power and limitations of fair interventions in
weighted congestion games. Specifically, we focus on interventions that aim at
improving the equilibrium quality (price of anarchy) and are fair in a suitably
defined sense. Within this setting, we provide three key contributions. First,
we show that no fair intervention can reduce the price of anarchy below a given
factor depending solely on the class of latencies considered. Interestingly,
this lower bound is unconditional, i.e., it applies regardless of how much
computation interventions are allowed to use. Second, we design a taxation
mechanism that is fair and achieves a price of anarchy matching this
unconditional lower bound, all the while being polynomial-time computable.
Third, we show that no intervention (fair or not) can achieve a better
approximation if polynomial computability is required. We do so by proving that
the minimum social cost is NP-hard to minimize below a factor identical to the
one previously introduced. In doing so, our work shows that the algorithm
proposed by Makarychev and Sviridenko (Journal of the ACM, 2018) to tackle
optimization problems with a "diseconomy of scale" is optimal, and provide a
novel way to derandomize its solution via equilibrium computation.
