Doing Good with Spam Is Hard

We study economic means to improve network performance in the well-known game theoretic traffic model due to Wardrop. We introduce two sorts of spam flow - auxiliary and adversarial flow - that have no intrinsic value. Auxiliary/adversarial flows are a separate commodity with the sole objective to minimize/maximize the latency at the induced Wardrop equilibrium of the selfish flow. By this means a separate access to the edges is not necessary and the latency of the regulating flow does not distort the arising latency cost. We present networks where auxiliary flow is able to improve the network performance. However, we show that the optimal auxiliary flow is

NP

-hard to compute and not approximable within a factor of less then

$\frac 43$

. The minimal amount of auxiliary flow needed to induce the best possible equilibrium is even hard to approximate by any subexponential factor. These hardness results are complemented by proving

NP

-hardness for the optimal adversarial flow. All hardness results hold even for single-commodity networks.