My research this year has focused on analyzing Braess's Paradox.  Braess’s Paradox is a problem that can arise when adding a new link in a network.  The additional link should improve overall performance, but Braess’s Paradox says that in a selfish network the extra link can actually increase overall latency (i.e. slow down traffic).  The idea is that it is possible to add "bad" links so that selfish users clog a link that was originally fast, and thus slow down performance for everyone.

Originally it had been know that delay could increase by as much as k+1 when adding k edges, but it was not known if this was the worst case possible.  This year we have been able prove that indeed this is the worst case possible.  Along the way, we have also been able to find new ways to prove known theorems.  We have been able to re-derive that selfish (Nash) flows are unique, decreasing flow must decrease overall latency, and increasing delay along an edge must decrease flow along that edge.  We are now looking for necessary and sufficient conditions for Braess's Paradox to occur, and are attempting to generalize our models to multi-commodity flows.

Additional information regarding Braess's paradox can by found on Tim Roughgarden's homepage.