Inefficiency in networks with multiple sources and sinks

Hyejin Youn; Michael T. Gastner; Hawoong Jeong

doi:10.1007/978-3-642-02466-5_32

Inefficiency in networks with multiple sources and sinks

Hyejin Youn^*, Michael T. Gastner, Hawoong Jeong

^*Corresponding author for this work

Management and Organizations

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

Abstract

We study the problem of optimizing traffic in decentralized transportation networks, where the cost of a link depends on its congestion. If users of a transportation network are permitted to choose their own routes, they generally try to minimize their personal travel time. In the absence of centralized coordination, such a behavior can be inefficient for society and even for each individual user. This inefficiency can be quantified by the "price of anarchy", the ratio of the suboptimal total cost to the socially optimal cost. Here we study the price of anarchy in multi-commodity networks, (i.e., networks where traffic simultaneously flows between different origins and destinations).

Original language	English (US)
Title of host publication	Complex Sciences - First International Conference, Complex 2009, Revised Papers
Pages	334-338
Number of pages	5
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-02466-5_32
State	Published - 2009
Event	1st International Conference on Complex Sciences: Theory and Applications, Complex 2009 - Shanghai, China Duration: Feb 23 2009 → Feb 25 2009

Publication series

Name	Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
Number	PART 1
Volume	4 LNICST
ISSN (Print)	1867-8211

Other

Other	1st International Conference on Complex Sciences: Theory and Applications, Complex 2009
Country/Territory	China
City	Shanghai
Period	2/23/09 → 2/25/09

Keywords

Flow optimization
Multi-commodity flow
Nash equilibrium
Transportation network

ASJC Scopus subject areas

Computer Networks and Communications

Access to Document

10.1007/978-3-642-02466-5_32

Cite this

Youn, H., Gastner, M. T., & Jeong, H. (2009). Inefficiency in networks with multiple sources and sinks. In Complex Sciences - First International Conference, Complex 2009, Revised Papers (PART 1 ed., pp. 334-338). (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering; Vol. 4 LNICST, No. PART 1). https://doi.org/10.1007/978-3-642-02466-5_32

@inproceedings{836b4ebe6f5e4542a6f1c212a4d9ecd1,

title = "Inefficiency in networks with multiple sources and sinks",

abstract = "We study the problem of optimizing traffic in decentralized transportation networks, where the cost of a link depends on its congestion. If users of a transportation network are permitted to choose their own routes, they generally try to minimize their personal travel time. In the absence of centralized coordination, such a behavior can be inefficient for society and even for each individual user. This inefficiency can be quantified by the {"}price of anarchy{"}, the ratio of the suboptimal total cost to the socially optimal cost. Here we study the price of anarchy in multi-commodity networks, (i.e., networks where traffic simultaneously flows between different origins and destinations).",

keywords = "Flow optimization, Multi-commodity flow, Nash equilibrium, Transportation network",

author = "Hyejin Youn and Gastner, {Michael T.} and Hawoong Jeong",

year = "2009",

doi = "10.1007/978-3-642-02466-5_32",

language = "English (US)",

isbn = "3642024653",

series = "Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering",

number = "PART 1",

pages = "334--338",

booktitle = "Complex Sciences - First International Conference, Complex 2009, Revised Papers",

edition = "PART 1",

note = "1st International Conference on Complex Sciences: Theory and Applications, Complex 2009 ; Conference date: 23-02-2009 Through 25-02-2009",

}

Youn, H, Gastner, MT & Jeong, H 2009, Inefficiency in networks with multiple sources and sinks. in Complex Sciences - First International Conference, Complex 2009, Revised Papers. PART 1 edn, Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, no. PART 1, vol. 4 LNICST, pp. 334-338, 1st International Conference on Complex Sciences: Theory and Applications, Complex 2009, Shanghai, China, 2/23/09. https://doi.org/10.1007/978-3-642-02466-5_32

Inefficiency in networks with multiple sources and sinks. / Youn, Hyejin; Gastner, Michael T.; Jeong, Hawoong.
Complex Sciences - First International Conference, Complex 2009, Revised Papers. PART 1. ed. 2009. p. 334-338 (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering; Vol. 4 LNICST, No. PART 1).

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

TY - GEN

T1 - Inefficiency in networks with multiple sources and sinks

AU - Youn, Hyejin

AU - Gastner, Michael T.

AU - Jeong, Hawoong

PY - 2009

Y1 - 2009

N2 - We study the problem of optimizing traffic in decentralized transportation networks, where the cost of a link depends on its congestion. If users of a transportation network are permitted to choose their own routes, they generally try to minimize their personal travel time. In the absence of centralized coordination, such a behavior can be inefficient for society and even for each individual user. This inefficiency can be quantified by the "price of anarchy", the ratio of the suboptimal total cost to the socially optimal cost. Here we study the price of anarchy in multi-commodity networks, (i.e., networks where traffic simultaneously flows between different origins and destinations).

AB - We study the problem of optimizing traffic in decentralized transportation networks, where the cost of a link depends on its congestion. If users of a transportation network are permitted to choose their own routes, they generally try to minimize their personal travel time. In the absence of centralized coordination, such a behavior can be inefficient for society and even for each individual user. This inefficiency can be quantified by the "price of anarchy", the ratio of the suboptimal total cost to the socially optimal cost. Here we study the price of anarchy in multi-commodity networks, (i.e., networks where traffic simultaneously flows between different origins and destinations).

KW - Flow optimization

KW - Multi-commodity flow

KW - Nash equilibrium

KW - Transportation network

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

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

U2 - 10.1007/978-3-642-02466-5_32

DO - 10.1007/978-3-642-02466-5_32

M3 - Conference contribution

AN - SCOPUS:84885891627

SN - 3642024653

SN - 9783642024658

T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering

SP - 334

EP - 338

BT - Complex Sciences - First International Conference, Complex 2009, Revised Papers

T2 - 1st International Conference on Complex Sciences: Theory and Applications, Complex 2009

Y2 - 23 February 2009 through 25 February 2009

ER -

Inefficiency in networks with multiple sources and sinks

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this