Selfish routing and the price of anarchy

By Tim Roughgarden. 2005

1,006 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Media Technology

Citations in the corpus

Challenges for Transparency (2017, background): “This phenomenon is sometimes described as the price of anarchy (Roughgarden, 2006).”
Decentralized Computation Offloading Game for Mobile Cloud Computing (2014, methodology): “Following the deﬁnition of PoA in game theory [30], we will quantify the efﬁciency ratio of the worst-case Nash equilibrium over the centralized optimal solution.”
A few good agents: multi-agent social learning (2008, methodology): “Let us first illustrate selfish routing using a simple example of MARS [19, 22].”
Transparency: Motivations and Challenges (2019, background): “This phenomenon is sometimes described as the price of anarchy [56].”
Steps Toward a Science of Service Systems (2007, background): “…and game theory (prisoners dilemma) hinges on the fact that sometimes individual and collective goals are not aligned – and therefore all value that a system could capture may not be captured if decisions and behavior are not coordinated properly (e.g., Beinhocker, 2006; Roughgarden, 2005).”
Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing (2015, methodology): “Following the deﬁnition of price of anarchy (PoA) in game theory [31], we will quantify the efﬁciency ratio of the worst-case Nash equilibrium over the centralized optimal solutions in terms of two important metrics: the number of beneﬁcial cloud computing users and the system-wide computation…”
Bounding the efficiency gain of differentiable road pricing for EVs and GVs to manage congestion and emissions (2020, background): “After Koutsoupias and Papadimitriou [18] proposed the concept of the price of anarchy, Roughgarden [19] proved that the price of anarchy is independent of the network topology when the cost function is linear and nonlinear.”
Security and Cooperation in Wireless Networks (2007, background): “Roughgarden [333] quantifies the worstpossible loss in network performance arising from non-cooperative routing behavior.”
Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation (2010, background): “In certain settings, such as a congestion game with linear cost functions, it may be possible to bound the efficiency, but in general, such a bound need not be possible [24, 28].”
CONGA: distributed congestion-aware load balancing for datacenters (2015, background): “Indeed, in theory, the sum metric gives a Price of Anarchy (PoA) of 4/3 in arbitrary topologies [43].”