Lesson 1: Algorithmic Game Theory by Mohammad Hajiaghayi: Intro to the Course and Nash Equilibria

This session introduced the foundations of algorithmic game theory and mechanism design, focusing on how strategic interactions among self-interested agents can be analyzed and guided through carefully designed systems. The discussion emphasized that, unlike classical optimization where a single objective is optimized, mechanism design must balance the objectives of a central designer with the individual incentives of participating agents. Examples such as airline boarding policies illustrated the challenge of designing mechanisms that simultaneously account for efficiency, fairness, and the diverse preferences of different participants. The notion of equilibrium was introduced as a state in which agents have no incentive to unilaterally change their behavior, providing a central framework for understanding strategic stability in economic and computational systems.

The lecture then developed the formal language of game theory through normal-form games. A game consists of a set of players, a set of actions available to each player, and utility functions that specify the payoff each player receives under every possible action profile. The concepts of actions, pure strategies, mixed strategies, and utility were formally defined. Particular attention was given to mixed strategies, in which players randomize over available actions according to probability distributions. The expected utility of a mixed strategy profile was explained as the weighted average of outcomes induced by the players’ probabilistic choices. These formal definitions provide the mathematical framework used throughout algorithmic game theory to model strategic decision-making.

Several classical examples were examined to illustrate different strategic phenomena. The Prisoner’s Dilemma demonstrated how individually rational decisions can lead to socially suboptimal outcomes. The Battle of the Sexes served as an example of a coordination game, where multiple equilibria may exist and players benefit from coordinating their choices despite differing preferences. The Matching Pennies game illustrated a fundamentally competitive interaction and highlighted the possibility that no pure Nash equilibrium may exist. Through these examples, the lecture introduced important equilibrium concepts, including dominant strategies and Nash equilibrium, and explained how Nash equilibrium captures situations in which no player can improve their utility by unilaterally deviating from their current strategy.

The final part of the session focused on the existence and computation of Nash equilibria, a topic that lies at the intersection of economics and computer science. Nash’s celebrated theorem guarantees that every finite game possesses at least one mixed-strategy Nash equilibrium, even when pure equilibria do not exist. The lecture outlined the computational approach for finding mixed equilibria in two-player games by guessing supports, constructing systems of linear equations, and verifying equilibrium conditions. This naturally led to a discussion of computational complexity, highlighting that while verifying a proposed equilibrium is relatively easy, computing one can be computationally challenging. In particular, the lecture briefly introduced the complexity class PPAD and noted landmark results showing that computing Nash equilibria is PPAD-complete, illustrating how algorithmic game theory combines economic reasoning with deep questions in computational complexity.

Видео Lesson 1: Algorithmic Game Theory by Mohammad Hajiaghayi: Intro to the Course and Nash Equilibria канала Mohammad Hajiaghayi