= Éva Tardos
{c}
<Éva Tardos> studies algorithms and the efficiency of systems in which participants act for themselves. Her work with <Tim Roughgarden> quantified inefficiency in selfish routing, relating equilibrium traffic to a centrally optimized flow.https://www.cs.cornell.edu/people/tardos[Research description]{ref}<How Bad is Selfish Routing? by Tim Roughgarden and Éva Tardos>[Network-routing model and inefficiency bounds]{ref}
A small example shows the issue. Route one unit of traffic over two parallel links, one with latency $x$ when carrying flow $x$ and one with fixed latency one. The selfish equilibrium sends everything over the first link, giving total latency one: no user can improve by switching to the other link. Splitting traffic equally gives total latency $\tfrac12\cdot\tfrac12+\tfrac12\cdot1=3/4$, which minimizes $x^2+1-x$. The equilibrium-to-optimum ratio is $4/3$.
This is a precise <price of anarchy> calculation. It demonstrates why individually sensible choices can create avoidable aggregate delay and why a guarantee about an optimization algorithm does not automatically describe an uncoordinated network.
\Image[https://toc.cs.uchicago.edu/articles/v004a004/eva.jpg]
{title=Éva Tardos, portrait identified by the linked author, institutional or Commons source}
{height=240}
Back to article page
