## 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 within 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 results are complemented by proving NP-hardness for the optimal adversarial flow. All hardness results hold even for single-commodity networks.

Original language | English |
---|---|

Title of host publication | Algorithmic Game Theory |

Subtitle of host publication | Second International Symposium, SAGT 2009, Proceedings |

Editors | Marios Mavronicolas, Vicky G. Papadopoulou |

Pages | 263-274 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-642-04645-2 |

DOIs | |

Publication status | Published - 14 Dec 2009 |

Externally published | Yes |

Event | 2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus Duration: 18 Oct 2009 → 20 Oct 2009 Conference number: 2 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5814 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 2nd International Symposium on Algorithmic Game Theory, SAGT 2009 |
---|---|

Abbreviated title | SAGT 2009 |

Country | Cyprus |

City | Paphos |

Period | 18/10/09 → 20/10/09 |