Algorithmic Game Theory (Lecture 11: Selfish Routing and the Price of Anarchy)

This segment presents the main result of the lecture: the worst-case examples for price of anarchy in selfish routing networks are surprisingly simple, resembling the basic Braess's paradox network. It sets the stage for a more formal proof and discussion. This course segment analyzes the inefficiency of equilibria in pre-existing games (unlike the mechanism design segment, which focused on designing optimal games). The focus is on "games in the wild," such as traffic networks, where strategic behavior leads to equilibria that may or may not be near-optimal. The goal is to determine when equilibria are near-optimal, using the "price of anarchy" (ratio of equilibrium cost to optimal cost) as a metric. The analysis primarily uses full-information games, with a key result showing that worst-case examples are surprisingly simple, even for complex networks with non-linear cost functions. This segment explains Braess's paradox using a traffic network example. It demonstrates how adding a seemingly beneficial option (a teleportation device) can worsen the equilibrium outcome, leading to increased commute times. The concept of "price of anarchy" is introduced as a measure of this inefficiency. This segment details the key technical differences between the mechanism design (part one) and the analysis of equilibrium inefficiency (part two). It emphasizes the absence of dominant strategies, the need to analyze non-trivial equilibria, and the unlikelihood of achieving full or even approximate optimality in naturally occurring games.This segment discusses the hope and evidence of finding application domains where equilibria are near-optimal, despite the absence of game design control. It mentions 15 years of research in various domains supporting this possibility. This segment explains how a theorem simplifies the computation of the worst-case price of anarchy by showing that the worst-case examples are simple networks with two nodes and two links. This significantly reduces the complexity of the analysis, allowing for straightforward computation of the worst-case price of anarchy for various classes of cost functions. This segment demonstrates how the degree of the polynomial used to model cost functions affects the worst-case price of anarchy. It provides specific examples for degrees 1, 2, 3, and 4, showing how the worst-case price of anarchy changes with increasing polynomial degree, highlighting the implications for modeling real-world scenarios like transportation networks. This segment addresses the question of when the price of anarchy is small. It explains that highly non-linear cost functions are an obstruction to a small price of anarchy, while cost functions well-modeled by low-degree polynomials result in a price of anarchy close to one, even in complex networks. This provides valuable insight into the relationship between cost function characteristics and network performance. This segment explains the methodology for determining lower bounds on the price of anarchy using piggy-like networks. It highlights the simplicity of finding lower bounds by exhibiting a single example and formalizes the approach for deriving a generic lower bound, analogous to the four-thirds lower bound obtained from Pigou's example.This segment analyzes the equilibrium flow and price of anarchy in piggy-like networks. It demonstrates how the equilibrium flow is easily determined and how the price of anarchy can be calculated as the ratio of equilibrium cost to optimal cost. The analysis includes a discussion of simplifying assumptions and their justification. This segment provides a formal definition of "piggy-like networks," a simplified network structure used for analyzing price of anarchy. The definition includes two free parameters: traffic rate and the cost function of one link, which allows for systematic exploration of different scenarios and the derivation of lower bounds on the price of anarchy. This segment details the first part of the proof, demonstrating that if edge costs are frozen at their equilibrium values, no flow can achieve a lower cost than the equilibrium flow. This establishes a crucial intermediate result for the overall proof. This segment explains how to calculate the total flow across a specific edge in a network by summing the flows of all paths that include that edge. The example using the Braess paradox network clearly illustrates the calculation, showing how different paths contribute to the total flow on each edge.This segment defines equilibrium flow in a network, explaining that in equilibrium, all used paths must be shortest paths considering the current traffic congestion. It highlights the iterative nature of finding equilibrium, where shortest paths depend on the current traffic pattern.This segment introduces cost functions to the network model, representing the travel time on each edge as a function of traffic. It then defines the concept of equilibrium flow in the context of these cost functions, emphasizing that in equilibrium, all used paths must have the minimum cost.This segment introduces two key facts about equilibrium flows: their existence and essential uniqueness. The explanation clarifies that while multiple equilibria might exist, they all result in the same total cost, simplifying analysis.This segment defines the price of anarchy as the ratio of the cost of an equilibrium flow to the cost of an optimal flow. It explains the significance of this metric in evaluating the efficiency of a network's traffic flow under decentralized decision-making. This segment meticulously details the mathematical derivation of a lower bound for the optimal flow using the equilibrium flow. It starts by explaining the "dream" scenario where the equilibrium flow on each edge is close to optimal, then introduces an error term and shows how to handle it through summation over all edges. The derivation culminates in proving that the optimal flow is at least a 1/α fraction of the equilibrium flow, where α is a constant (e.g., 4/3), providing a crucial result for analyzing the efficiency of the equilibrium flow compared to the optimal flow.