Inefficiency in networks with multiple sources and sinks

Hyejin Youn*, Michael T. Gastner, Hawoong Jeong

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationComplex Sciences - First International Conference, Complex 2009, Revised Papers
Pages334-338
Number of pages5
EditionPART 1
DOIs
StatePublished - Dec 1 2009
Event1st International Conference on Complex Sciences: Theory and Applications, Complex 2009 - Shanghai, China
Duration: Feb 23 2009Feb 25 2009

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
NumberPART 1
Volume4 LNICST
ISSN (Print)1867-8211

Other

Other1st International Conference on Complex Sciences: Theory and Applications, Complex 2009
CountryChina
CityShanghai
Period2/23/092/25/09

Keywords

  • Flow optimization
  • Multi-commodity flow
  • Nash equilibrium
  • Transportation network

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Inefficiency in networks with multiple sources and sinks'. Together they form a unique fingerprint.

Cite this