Truthful mechanisms for selfish routing and two-parameter agents

Clemens Thielen; Sven O. Krumke

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

Truthful mechanisms for selfish routing and two-parameter agents

Clemens Thielen, Sven O. Krumke

University of Kaiserslautern

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

Abstract

We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs proportional to the usage of her edge. Moreover, we consider a mechanism design setting with two-parameter agents, which generalizes the well-known setting of one-parameter agents by allowing a fixed cost component as part of each agent's private data. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. This characterization also motivates our choice of linear cost functions without fixed costs for the edges in the selfish routing setting.

Original language	English
Title of host publication	Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings
Pages	36-47
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-04645-2_5
State	Published - 2009
Externally published	Yes
Event	2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus Duration: 18 Oct 2009 → 20 Oct 2009

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
Country/Territory	Cyprus
City	Paphos
Period	18/10/09 → 20/10/09

Keywords

Algorithmic mechanism design
Nash flows
Selfish routing

Access to Document

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

Cite this

Thielen, C., & Krumke, S. O. (2009). Truthful mechanisms for selfish routing and two-parameter agents. In Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings (pp. 36-47). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5814 LNCS). https://doi.org/10.1007/978-3-642-04645-2_5

@inproceedings{96f8a3316da640c899ea0c126633ffd7,

title = "Truthful mechanisms for selfish routing and two-parameter agents",

abstract = "We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs proportional to the usage of her edge. Moreover, we consider a mechanism design setting with two-parameter agents, which generalizes the well-known setting of one-parameter agents by allowing a fixed cost component as part of each agent's private data. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. This characterization also motivates our choice of linear cost functions without fixed costs for the edges in the selfish routing setting.",

keywords = "Algorithmic mechanism design, Nash flows, Selfish routing",

author = "Clemens Thielen and Krumke, {Sven O.}",

year = "2009",

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

language = "English",

isbn = "3642046444",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "36--47",

booktitle = "Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings",

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

}

Thielen, C & Krumke, SO 2009, Truthful mechanisms for selfish routing and two-parameter agents. in Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5814 LNCS, pp. 36-47, 2nd International Symposium on Algorithmic Game Theory, SAGT 2009, Paphos, Cyprus, 18/10/09. https://doi.org/10.1007/978-3-642-04645-2_5

Truthful mechanisms for selfish routing and two-parameter agents. / Thielen, Clemens; Krumke, Sven O.
Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings. 2009. p. 36-47 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5814 LNCS).

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

TY - GEN

T1 - Truthful mechanisms for selfish routing and two-parameter agents

AU - Thielen, Clemens

AU - Krumke, Sven O.

PY - 2009

Y1 - 2009

N2 - We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs proportional to the usage of her edge. Moreover, we consider a mechanism design setting with two-parameter agents, which generalizes the well-known setting of one-parameter agents by allowing a fixed cost component as part of each agent's private data. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. This characterization also motivates our choice of linear cost functions without fixed costs for the edges in the selfish routing setting.

AB - We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs proportional to the usage of her edge. Moreover, we consider a mechanism design setting with two-parameter agents, which generalizes the well-known setting of one-parameter agents by allowing a fixed cost component as part of each agent's private data. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. This characterization also motivates our choice of linear cost functions without fixed costs for the edges in the selfish routing setting.

KW - Algorithmic mechanism design

KW - Nash flows

KW - Selfish routing

UR - http://www.scopus.com/inward/record.url?scp=71549173431&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:71549173431

SN - 3642046444

SN - 9783642046445

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

SP - 36

EP - 47

BT - Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings

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

Y2 - 18 October 2009 through 20 October 2009

ER -

Truthful mechanisms for selfish routing and two-parameter agents

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this