Selfish Routing and the Price of Anarchy

A survey of recent work that analyzes the price of anarchy of selfish routing, a classical mathematical model of how self-interested users might route traffic through a congested network.

Abstract

Bvw Ax Vy !g A d fe g ih fj kg i l nm 3 il g og im 3l g qp rl se f p rl se g im 3l g up n t u gv B f !w x y v {z |g ih Xe y 3 o ye y t u y 3 o p rg ij d Xe d fe y }e y ¦l sm 4e f d uj d l rm dh fj g e y t h f 3e Hw e g o c f } d ue m dp n ¤ gv y d fe g ih uj rg i j g h f 3 ol g g ih f 3m 3g i h Xe 3 g ih ne ul se g e 1v l gg i i e y g ue g ip g 3 h ul se f ¦l g f g y m e g g Cv uh um e g i dh u 3 B c f og im gv l gh ul s om ¦ X g i l r ul gh e g e l se g g ¤p n l g o f 4 gv Be ug i g ih u 3m 3g h um g f g 3 ¢ o m h Xe kw g ¢e ul se kl gh ul g 3 e u u og m gv cl gh ul s om ¦ X gv c y o d fe g h fj f l g i y rt f om og q il se y t o u e dh q d uh t ug ih fj e f }w g o ye z q d g 4 y 3 g 3 og e H A gv Bl n u h f dp n h f dh m 3l g i t ol s 3¡ ¢ 4£ Bl s ol gt f ¤ a l gh t dh e f o 3 e y m ¦ uh ug i f sv { g t um 3g ih fj $e f og im gv ql gh ul s om ¦ X gv y o @ d fe g ih fj f ¥ c ug i f g 3 ¦m dh um h e y ol se y A dh §e f m dh Xe y og i fe g dh u r gv se u l g fe f g ¡ ¢ $£ q uë f g i f fe l g i y t g i m 3 u 3 g 3 ol g up n g o } m h e c u ie g ih e f ¤l s lae qà q ¶ ³AE ç f¾ éè nÇ È a¿¼ ¿Ç È qº aÌ » ¼ » à qAE çê » º Á» AE qÌ ÍÅ Ì {¿• ¿Ì ÍÇ È ìë îí ï aÀ ð ï ñ HÀ Å ¶ ³» ¼ ¿È q• ¦ ¶ ³¼ ¹ a ¶ ¶ ò ¶ !à f¿Ç Ð }¹ qÌ {Ë 3¹ ÑË !Ç Å º u ¶ !¿Ì {¿Ì ÍÇ Ã §» º aº q• ¿Ç sò Ì ÍÅ » ¶ !¼ nË ³Ç Ç º u ¶ ³• » XÌ