Lesson 2: Algorithmic Game Theory by Mohammad Hajiaghayi: Correlated Equilibrium, Minmax and Maximin

This session extended the study of Nash equilibrium by introducing several important equilibrium concepts and their computational properties. The lecture began with ε-Nash equilibrium, a relaxation of Nash equilibrium in which no player can improve their utility by more than ε through unilateral deviation. This notion captures practical considerations such as switching costs, finite computational precision, and approximate strategic behavior. The session emphasized that while every Nash equilibrium is an ε-Nash equilibrium, the converse is not true: there exist ε-Nash equilibria that are far from any true Nash equilibrium. Moreover, computing ε-Nash equilibria remains computationally hard in general.

The lecture then introduced correlated equilibrium, a powerful generalization of Nash equilibrium in which a trusted mediator (such as a traffic signal or recommendation system) suggests actions to players according to a joint probability distribution. Correlated equilibria can achieve better social outcomes, fairness, and coordination than independent mixed strategies, while remaining computationally tractable. Unlike Nash equilibria, correlated equilibria can be computed efficiently via linear programming, and every Nash equilibrium is a correlated equilibrium, though not every correlated equilibrium is a Nash equilibrium.

The final part of the session focused on maximin and minimax strategies, which model decision-making under worst-case assumptions. These concepts culminated in the celebrated Minimax Theorem of John von Neumann, which states that in finite two-player zero-sum games, the maximin value, minimax value, and Nash equilibrium value coincide. The lecture showed how these solutions can be formulated and computed using linear programming, highlighting an important class of games where equilibrium computation is tractable. The session concluded by connecting these equilibrium concepts to future topics, including price of anarchy, market equilibria, and auction design.

Видео Lesson 2: Algorithmic Game Theory by Mohammad Hajiaghayi: Correlated Equilibrium, Minmax and Maximin канала Mohammad Hajiaghayi