Doing good with spam is hard

Martin Hoefer; Lars Olbrich; Alexander Skopalik

doi:10.1007/978-3-642-04645-2_24

Doing good with spam is hard

Martin Hoefer^*
, Lars Olbrich
, Alexander Skopalik

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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
Publisher	Springer
Pages	263-274
Number of pages	12
ISBN (Electronic)	978-3-642-04645-2
ISBN (Print)	978-3-642-04644-5
DOIs	https://doi.org/10.1007/978-3-642-04645-2_24
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
Publisher	Springer
Volume	5814
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Symposium on Algorithmic Game Theory, SAGT 2009
Abbreviated title	SAGT 2009
Country/Territory	Cyprus
City	Paphos
Period	18/10/09 → 20/10/09

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-642-04645-2_24

Cite this

@inproceedings{42e8b9c93e6f4f54b5c74704ef585226,

title = "Doing good with spam is hard",

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.",

keywords = "n/a OA procedure",

author = "Martin Hoefer and Lars Olbrich and Alexander Skopalik",

year = "2009",

month = dec,

day = "14",

doi = "10.1007/978-3-642-04645-2\_24",

language = "English",

isbn = "978-3-642-04644-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "263--274",

editor = "Marios Mavronicolas and Papadopoulou, \{Vicky G.\}",

booktitle = "Algorithmic Game Theory",

address = "Germany",

note = "2nd International Symposium on Algorithmic Game Theory, SAGT 2009, SAGT 2009 ; Conference date: 18-10-2009 Through 20-10-2009",

}

Hoefer, M, Olbrich, L & Skopalik, A 2009, Doing good with spam is hard. in M Mavronicolas & VG Papadopoulou (eds), Algorithmic Game Theory : Second International Symposium, SAGT 2009, Proceedings. Lecture Notes in Computer Science, vol. 5814, Springer, pp. 263-274, 2nd International Symposium on Algorithmic Game Theory, SAGT 2009, Paphos, Cyprus, 18/10/09. https://doi.org/10.1007/978-3-642-04645-2_24

Doing good with spam is hard. / Hoefer, Martin; Olbrich, Lars; Skopalik, Alexander.
Algorithmic Game Theory : Second International Symposium, SAGT 2009, Proceedings. ed. / Marios Mavronicolas; Vicky G. Papadopoulou. Springer, 2009. p. 263-274 (Lecture Notes in Computer Science; Vol. 5814).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Doing good with spam is hard

AU - Hoefer, Martin

AU - Olbrich, Lars

AU - Skopalik, Alexander

N1 - Conference code: 2

PY - 2009/12/14

Y1 - 2009/12/14

N2 - 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.

AB - 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.

KW - n/a OA procedure

UR - https://www.scopus.com/pages/publications/71549147845

U2 - 10.1007/978-3-642-04645-2_24

DO - 10.1007/978-3-642-04645-2_24

M3 - Conference contribution

AN - SCOPUS:71549147845

SN - 978-3-642-04644-5

T3 - Lecture Notes in Computer Science

SP - 263

EP - 274

BT - Algorithmic Game Theory

A2 - Mavronicolas, Marios

A2 - Papadopoulou, Vicky G.

PB - Springer

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

Y2 - 18 October 2009 through 20 October 2009

ER -

Doing good with spam is hard

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this