Inefficiency in Networks with Multiple Sources and Sinks

Hyejin Youn; Michael Gastner; Hawoong Jeong

Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1

Research Article

Inefficiency in Networks with Multiple Sources and Sinks

Download

400 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-02466-5_32,
    author={Hyejin Youn and Michael Gastner and Hawoong Jeong},
    title={Inefficiency in Networks with Multiple Sources and Sinks},
    proceedings={Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1},
    proceedings_a={COMPLEX PART 1},
    year={2012},
    month={5},
    keywords={flow optimization transportation network Nash equilibrium multi-commodity flow},
    doi={10.1007/978-3-642-02466-5_32}
}

Hyejin Youn
Michael Gastner
Hawoong Jeong
Year: 2012
Inefficiency in Networks with Multiple Sources and Sinks
COMPLEX PART 1
Springer
DOI: 10.1007/978-3-642-02466-5_32

Hyejin Youn¹^,*, Michael Gastner, Hawoong Jeong¹

1: Korea Advanced Institute of Science and Technology

*Contact email: visang@kaist.ac.kr

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 transportation network Nash equilibrium multi-commodity flow

Published: 2012-05-11

: http://dx.doi.org/10.1007/978-3-642-02466-5_32