Atomic routing games on maximum congestion

Costas Busch; Malik Magdon-Ismail

doi:10.1007/11775096_9

Atomic routing games on maximum congestion

Costas Busch, Malik Magdon-Ismail

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

8 Scopus citations

Abstract

We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA = O(ℓ + log n), where ℓ is the length of the longest path in the player strategy sets, and n is the size of the network. Further, κ-1 ≤ PoA ≤ c(κ² + log² n), where κ is the length of the longest cycle in the network, and c is a constant.

Original language	English (US)
Title of host publication	Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings
Publisher	Springer Verlag
Pages	79-91
Number of pages	13
ISBN (Print)	3540351574, 9783540351573
DOIs	https://doi.org/10.1007/11775096_9
State	Published - 2006
Externally published	Yes
Event	2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 - Hong Kong, China Duration: Jun 20 2006 → Jun 22 2006

Publication series

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

Conference

Conference	2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006
Country/Territory	China
City	Hong Kong
Period	6/20/06 → 6/22/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11775096_9

Cite this

Busch, C., & Magdon-Ismail, M. (2006). Atomic routing games on maximum congestion. In Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings (pp. 79-91). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4041 LNCS). Springer Verlag. https://doi.org/10.1007/11775096_9

Atomic routing games on maximum congestion. / Busch, Costas; Magdon-Ismail, Malik.
Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings. Springer Verlag, 2006. p. 79-91 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4041 LNCS).

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

Busch, C & Magdon-Ismail, M 2006, Atomic routing games on maximum congestion. in Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4041 LNCS, Springer Verlag, pp. 79-91, 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, Hong Kong, China, 6/20/06. https://doi.org/10.1007/11775096_9

Busch C, Magdon-Ismail M. Atomic routing games on maximum congestion. In Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings. Springer Verlag. 2006. p. 79-91. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11775096_9

@inproceedings{1d7ff461f6e8416d96078d0f1a75538c,

title = "Atomic routing games on maximum congestion",

abstract = "We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA = O(ℓ + log n), where ℓ is the length of the longest path in the player strategy sets, and n is the size of the network. Further, κ-1 ≤ PoA ≤ c(κ2 + log2 n), where κ is the length of the longest cycle in the network, and c is a constant.",

author = "Costas Busch and Malik Magdon-Ismail",

note = "Copyright: Copyright 2015 Elsevier B.V., All rights reserved.; 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 ; Conference date: 20-06-2006 Through 22-06-2006",

year = "2006",

doi = "10.1007/11775096_9",

language = "English (US)",

isbn = "3540351574",

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

publisher = "Springer Verlag",

pages = "79--91",

booktitle = "Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings",

}

TY - GEN

T1 - Atomic routing games on maximum congestion

AU - Busch, Costas

AU - Magdon-Ismail, Malik

PY - 2006

Y1 - 2006

N2 - We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA = O(ℓ + log n), where ℓ is the length of the longest path in the player strategy sets, and n is the size of the network. Further, κ-1 ≤ PoA ≤ c(κ2 + log2 n), where κ is the length of the longest cycle in the network, and c is a constant.

AB - We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy, PoA, is determined by topological properties of the network. In particular, PoA = O(ℓ + log n), where ℓ is the length of the longest path in the player strategy sets, and n is the size of the network. Further, κ-1 ≤ PoA ≤ c(κ2 + log2 n), where κ is the length of the longest cycle in the network, and c is a constant.

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

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

U2 - 10.1007/11775096_9

DO - 10.1007/11775096_9

M3 - Conference contribution

AN - SCOPUS:33746266711

SN - 3540351574

SN - 9783540351573

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

SP - 79

EP - 91

BT - Algorithmic Aspects in Information and Management - Second International Conference, AAIM 2006, Proceedings

PB - Springer Verlag

T2 - 2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006

Y2 - 20 June 2006 through 22 June 2006

ER -

Atomic routing games on maximum congestion

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this