Doing Good with Spam is Hard

Speaker

Lars Olbrich
Title Doing Good with Spam is Hard
When 02.07.2009
Where Lecture Room Informatik 7
Abstract 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 with a factor of less then 4/3. The minimal amount of auxiliary flow needed to induce the best possible equilibrium is even hard to approximate by any subexponential factor. These hardness resultsare complemented by proving NP hardness for the optimal adversarial flow.