Selfish Routing and the Price of Anarchy

Abstract

Selfish routing is a classical mathematical model of how self-interested users might route traffic through a congested network. The outcome of selfish routing is generally inefficient, in that it fails to optimize natural objective functions. The price of anarchy is a quantitative measure of this inefficiency. We survey recent work that analyzes the price of anarchy of selfish routing. We also describe related results on bounding the worst-possible severity of a phenomenon called Braess's Paradox, and on three techniques for reducing the price of anarchy of selfish routing. This survey concentrates on the contributions of the author's PhD thesis, but also discusses several more recent results in the area.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 07, 2006
Accession Number
ADA637949

Entities

People

  • Tim Roughgarden

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Availability
  • Classification
  • Computer Science
  • Computers
  • Contracts
  • Information Operations
  • Instructions
  • Mathematical Models
  • Models
  • Monitoring
  • Security
  • Standards
  • Universities

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research
  • Strategic Security Studies