A six-week course on game theory focuses on equilibria, particularly in routing games. The lecture proves Rosenthal's theorem: atomic selfish routing games always have at least one pure Nash equilibrium (using a potential function). The existence and (near) uniqueness of equilibria in non-atomic games are also discussed. The lecture then expands to mixed, correlated, and coarse correlated equilibria, noting their existence and computational tractability, ultimately impacting price of anarchy bounds. This segment explains the concept of atomic selfish routing, where a finite number of players with non-negligible size interact. It details the proof that with affine cost functions, the worst-case price of anarchy in these networks is exactly 2.5 times the cost of the optimum, highlighting that while multiple equilibria may exist, each remains within a small constant factor of the optimum.This segment raises the crucial question of equilibrium existence in atomic selfish routing games. It introduces the concern that the price of anarchy bounds become meaningless if no equilibrium exists, setting the stage for the exploration of pure Nash equilibria and their guaranteed existence in this specific game type. This segment introduces Rosenthal's theorem, a 40-year-old result proving the existence of at least one pure Nash equilibrium in every atomic selfish routing network, regardless of the cost function. This contrasts with games like rock-paper-scissors, which lack pure strategy equilibria. This segment provides a high-level overview of the proof of Rosenthal's theorem. It explains that the proof hinges on showing that every selfish routing network is a potential game, which guarantees the existence of a pure Nash equilibrium. The concept of anthropomorphizing players and collectively optimizing a potential function is introduced. The rarity of techniques for proving pure equilibria existence is also highlighted. This segment defines the potential function, a crucial element in proving Rosenthal's theorem. It explains how this function assigns a real number to every possible flow in the network and visually compares it to the total travel time, emphasizing the difference between the staircase representation of the potential function and the bounding box representation of the total travel time.This segment presents the core proof of Rosenthal's theorem. It demonstrates that the potential function simultaneously tracks the costs of all players, showing that a change in the potential function due to a player's deviation exactly equals the change in that player's cost. This property is then used to prove that the global minimum of the potential function corresponds to a Nash equilibrium. This segment explains the limitations of relying solely on mixed Nash equilibria for price of anarchy analysis due to their computational intractability. It introduces correlated equilibria as a more computationally tractable alternative, emphasizing the trade-off between existence, computational tractability, and behavioral plausibility.This segment formally defines correlated equilibria and provides intuitive semantics using the analogy of a trusted third party providing recommendations to players. It explains how this concept allows for a more computationally tractable approach to equilibrium analysis while maintaining a degree of behavioral plausibility.This segment uses the simple example of a traffic light to illustrate the concept of correlated equilibrium. It contrasts pure and mixed Nash equilibria with correlated equilibrium in the context of traffic flow, demonstrating how a correlated equilibrium can achieve coordination and efficiency.This segment continues the traffic light example, showing how a correlated equilibrium (represented by a traffic light) can resolve the coordination problem inherent in multiple pure Nash equilibria. It explicitly demonstrates that the traffic light system is not a pure or mixed Nash equilibrium but rather a correlated equilibrium. This segment provides a formal definition of the selfish routing game, introducing key elements like players, strategies, cost functions, and outcomes. It then defines pure Nash equilibrium and highlights its limitations, setting the stage for the introduction of more general equilibrium concepts.This segment introduces mixed strategy Nash equilibria as a more general concept than pure Nash equilibria, guaranteeing existence (Nash's theorem) but highlighting the computational intractability of finding such equilibria in general. This motivates the exploration of even more permissive equilibrium concepts. This segment outlines the progression from pure Nash equilibria (with limitations) to the need for more inclusive equilibrium concepts (mixed strategy, correlated, and coarse correlated equilibria) to address the non-existence of pure equilibria in certain models and to enable meaningful price of anarchy analysis. This segment delves into the properties of correlated equilibria, demonstrating their existence, computational tractability (solvable via linear programming or simpler learning algorithms), and behavioral plausibility in game theory. The discussion contrasts correlated equilibria with mixed Nash equilibria, highlighting their broader applicability and easier computation, while maintaining relevance to real-world scenarios. This segment focuses on the price of anarchy, a metric used to evaluate the efficiency of equilibria in games. The speaker explains how the price of anarchy changes as the equilibrium set becomes more permissive (from pure Nash equilibria to mixed Nash equilibria to correlated equilibria and finally to coarse correlated equilibria). The discussion culminates in the announcement of a proof of a tight bound on the price of anarchy for coarse correlated equilibria in selfish routing games, showcasing the practical implications of the theoretical concepts discussed. This segment introduces coarse correlated equilibria (CCE), a more general concept than correlated equilibria. It explains the differences between CCE and correlated equilibria in terms of the information available to players when considering deviations. The speaker highlights that CCE are easier to compute and more plausible behaviorally, making them a valuable tool for analyzing game-theoretic scenarios. The segment also emphasizes the relationship between CCE and correlated equilibria, showing that CCE are a superset of correlated equilibria.