Doing good with spam is hard

Martin Hoefer*, Lars Olbrich, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationAlgorithmic Game Theory
Subtitle of host publicationSecond International Symposium, SAGT 2009, Proceedings
EditorsMarios Mavronicolas, Vicky G. Papadopoulou
Pages263-274
Number of pages12
ISBN (Electronic)978-3-642-04645-2
DOIs
Publication statusPublished - 14 Dec 2009
Externally publishedYes
Event2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus
Duration: 18 Oct 200920 Oct 2009
Conference number: 2

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5814 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Symposium on Algorithmic Game Theory, SAGT 2009
Abbreviated titleSAGT 2009
CountryCyprus
CityPaphos
Period18/10/0920/10/09

Fingerprint Dive into the research topics of 'Doing good with spam is hard'. Together they form a unique fingerprint.

Cite this