How to cite

@misc{mit-multiagent-learning-lecture-1,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Lecture 1: Setting and equilibria: the Nash equilibrium},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/nfgs_nash.html}
}

Lecture 1

Setting and equilibria: the Nash equilibrium

Instructor

Prof. Constantinos Daskalakis

Lecture date

Tue, Sep 15, 2026

Normal-form games model simultaneous-move interactions with a single move (think about rock-paper-scissors). Despite their simplicity, normal-form games will provide a natural ground for looking into important concepts in multiagent settings, such as notions of equilibria (Nash, maxmin, correlated, $\dots$ ), and learning from repeated play. In the second part of the course, we will move on to notions of games that explicitly capture more complex phenomena, such as sequential moves and imperfect information.

L1.1 Normal-form games and the Nash equilibrium

When introducing a (finite) normal-form game, we need to specify the following quantities:

The set of players $[ n ] = \{1 , \dots , n\}$ .
For each player $i \in [ n ]$ , a finite set of actions $A_{i}$ .
For each player $i \in [ n ]$ , the payoff function $u_{i} : A_{1} \times \dots \times A_{n} \to \mathbb{R}$ .

To represent a normal-form game, it is common to use a matrix representation.

Example L1.1 .

For instance, in the $2 \times 2$ game on the right, called “prisoner’s dilemma”, the rows correspond to the actions of Player 1, and the columns correspond to the actions of Player 2.

The entries at row $$i$$ , column $$j$$ are the payoffs of the two players when Player 1 plays action $$i$$ and Player 2 plays action $$j$$ .

Strategies A randomized strategy (also known as mixed strategy) for a generic player $i \in [ n ]$ is a distribution over the set of actions. We can represent such an object as a vector $x_{i} \in \Delta (A_{i})$ , that is, such that $x_{i} \ge 0$ and $\sum_{a_{i} \in A_{i}} x_{i , a_{i}} = 1$ . To lighten the notational burden, we will write the expected utility when all players play according to strategies $x_{1} , \dots , x_{n}$ reusing the same letter $u_{i}$ as the payoff, i.e.,

\displaystyle u_{i} \left(x_{1} , \dots , x_{n}\right)

\displaystyle \coloneqq \mathbb{E}_{a_{1} \sim x_{1}\\ \dots \\ a_{n} \sim x_{n}} \left[u_{i} \left(a_{1} , \dots , a_{n}\right)\right]

\displaystyle = \sum_{a_{1} \in A_{1}} \dots \sum_{a_{n} \in A_{n}} x_{1 , a_{1}} \dots x_{n , a_{n}} ⋅ u_{i} \left(a_{1} , \dots , a_{n}\right) .

We will sometimes intersperse deterministic actions and mixed strategies freely and write expressions such as $u_{i} (a_{1} , x_{2} , \dots , x_{n})$ to mean the expected utility when player 1 plays action $a_{1}$ and the other players play according to the strategies $x_{2} , \dots , x_{n}$ .

L1.1.1 Dominant-strategy equilibrium

The question of what constitutes rational play for players can get complicated depending on the game. But, in some lucky cases, like the prisoner’s dilemma game above, it turns out that some actions are just better than others, no matter what the other players do. In such cases, we say that a player has a dominant strategy. In the case above, both Player 1 and Player 2 have a dominant strategy to confess $$.$$ In this case, we expect that the players will play their dominant strategy, and this is called a dominant-strategy equilibrium.

L1.1.2 Maxmin strategies

The benefit of dominant-strategy equilibria is that they require no counterspeculation: some strategies just are better no matter what anyone else does. However, in many games, no player has a dominant strategy. Consider, for example, rock-paper-scissor: all actions are symmetric, and no action is strictly better than the others. How can we find a good strategy for that?

One way to think about this is to consider the worst-case scenario: what is the best strategy for a player if they assume the other players are trying to minimize their payoff? This is the idea behind maxmin strategies. A maxmin strategy for Player $$i$$ is a strategy $x_{i}$ that maximizes the minimum payoff that Player $$i$$ can get, that is,

\displaystyle x_{i} \in \text{arg max}_{x_{i} \in \Delta \left(A_{i}\right)} \operatorname*{min}_{x_{j} \in \Delta \left(A_{j}\right)\\ \mathord{\text{for all}} j \ne i} u_{i} \left(x_{i} , x_{- i}\right) ,

where the notation $x_{- i}$ is popular syntactic sugar to denote the tuple $(x_{j})_{j \ne i}$ .¹1This notation appears often in game theory, since we are often interested in studying the effect of changing a single player $$i$$ ‘s strategy, while keeping all “the other” strategies $x_{- i}$ fixed. Thinking back about rock-paper-scissors, it is clear that the maxmin strategy is to play uniformly at random: the opponent could exploit any other strategy more than the uniform one, by playing the counteraction more often.

The above idea has some merits, especially in two-player zero-sum games, that is, those two-player games where $u_{1} (a_{1} , a_{2}) + u_{2} (a_{1} , a_{2}) = 0$ for all combinations of actions. In those games, players are in direct competition, so it makes sense to assume that the opponent is “out to get us.” But in more general games, the maxmin strategy can be too conservative, since it assumes that all other players have nothing better going on than to minimize our payoff, even if that hurts them.

L1.1.3 The Nash equilibrium

In general, defining what constitutes “optimal play” is tricky. But we can start from what is convincingly not optimal play: if we predict that the players should play according to some strategies $x_{1} , \dots , x_{n}$ , then it is not optimal if it turned out that any player would be better off by switching to something else. This is the idea behind the Nash equilibrium.

Definition L1.2 (Nash equilibrium) .

A strategy profile $(x_{1} , \dots , x_{n}) \in \Delta (A_{1}) \times \dots \times \Delta (A_{n})$ is a Nash equilibrium if no player benefits from unilaterally deviating from their strategy. In symbols,

\displaystyle \forall i \in \left[ n \right] , x_{i}' \in \Delta \left(A_{i}\right) , \qquad \qquad u_{i} \left(x_{i}' , x_{- i}\right) \le u_{i} \left(x_{1} , \dots , x_{n}\right) .

Remark L1.3 .

Without loss of generality, when verifying if a profile

(x_{1} , \dots , x_{n})

is a Nash equilibrium, it is sufficient to consider only deterministic deviations

x_{i} \in A_{i}

. Indeed, if a player has a profitable randomized deviation, this must mean that at least one of the actions they are randomizing over is profitable.

It is clear that a dominant-strategy equilibrium is a special case of a Nash equilibrium, since in a dominant-strategy equilibrium, by definition,

\displaystyle \forall i \in \left[ n \right] , x_{i}' \in \Delta \left(A_{i}\right) , x_{- i}' \in \Delta \left(A_{- i}\right) , \quad u_{i} \left(x_{i}' , x_{- i}'\right) \le u_{i} \left(x_{i} , x_{- i}'\right) .

(note the stronger quantifiers.) As we will discuss more in depth shortly, in two-player zero-sum games, it turns out that Nash equilibrium and maxmin equilibrium are equivalent.

Before continuing, we consider two examples that help illustrate a couple of important properties of the Nash equilibrium.

Example L1.4 .

The only Nash equilibrium in the game of rock-paper-scissors is for all players to play the uniform strategy. This shows that in some games, no Nash equilibrium exists in pure (i.e., non-randomizing) strategies.

Example L1.5 (Theater or football) .

Consider the following small game:

This game has two obvious Nash equilibria: Player 1 insisting and Player 2 accepting, or vice versa (top right and bottom left corners). However, there is a third equilibrium as well: both players accept with probability 1/6 and insist with probability 5/6.

This is not a coincidence: in two-player nondegenerate games, there is always an odd number of Nash equilibria. This fact comes from more profound connections with some combinatorial objects that we will uncover quite soon.

L1.2 Existence of mixed-strategy Nash equilibrium

In 1950, John Nash established one of the most celebrated results in game theory:²2John Nash went on to win the Nobel prize in economics for his fundamental contributions to game theory. mixed-strategies Nash equilibria exist in all games, no matter the number of players or number of actions. The proof of Nash is nonconstructive, and fundamentally boils down to showing that one can think of Nash equilibria as fixed points. Two remarks are in order:

The idea that Nash equilibria can be thought of as fixed points should feel extremely natural. By definition, an equilibrium is a situation where nobody has an incentive to deviate—that is, no player has a more profitable strategy given the strategies of the other players. Hence, if we are able to introduce a function that maps a strategy profile to a profile of “improved strategies”, then a fixed point of such a function would be a Nash equilibrium. We could then use one of the many theorems in analysis that guarantee existence of fixed points. Of course, the devil is in the details: how to handle multiple profitable responses? how to ensure continuity of the deviation function? These are the questions that Nash had to answer.
The idea of viewing Nash equilibria as fixed points is not just natural, but also the only possible. We will make this formal towards the end of this course, when we discuss the computational complexity of Nash equilibria. In particular, we will show that the computation of fixed points of continuous functions and computation of Nash equilibria are computationally equivalent, in the sense that each problem can be reduced to the other in polynomial time.

In the remainder of the lecture, we will give a proof of the existence of Nash equilibria. While the first proof of Nash [Nas50[Nas50] Nash, J. F., Jr. (1950). Equilibrium Points in N-Person Games. Proc. Natl. Acad. Sci. U.S.A., 36(1), 48. link] invokes Kakutani’s fixed point theorem, a year later Nash noticed that a much more elementary proof can be given [Nas51[Nas51] Nash, J. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295. link]. We present a variation of the latter today.

L1.2.1 The Nash improvement function

As mentioned above, one can think about Nash equilibria as fixed points of a “profitable response” function from the set of mixed strategy to itself. Intuitively, this function must calculate a profitable response for each player. Furthermore, to invoke fixed point theorems, this function must be continuous. The key insight of Nash was to find a simple continuous function that, given a strategy profile, calculates a “profitable response” for each player. For lack of a better term, we will refer to this function with the term “Nash improvement function”.

Regret To formally define the Nash improvement function, we first introduce a simple quantity called regret, which will be a staple of this course. The regret that Player $$i$$ experiences with respect to action $a_{i} \in A_{i}$ is the difference between the payoff that Player $$i$$ would have obtained by playing $a_{i}$ , and the payoff that Player $$i$$ actually obtained:

\displaystyle r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right) \coloneqq u_{i} \left(a_{i} , x_{- i}\right) - u_{i} \left(x_{1} , \dots , x_{n}\right) .

The Nash improvement function The idea is simple: if an action $a_{i}$ has very large regret, then the current strategy profile cannot be an equilibrium, because Player $$i$$ would want to increase the probability of playing $a_{i}$ . Thus, an “improved” strategy for Player $$i$$ should move more probability mass to $a_{i}$ . We need to handle two complications: (1) if multiple actions have positive regret, how should we prioritize adding mass to those? and (2) for those actions whose regret is negative (that is, “bad” actions), should we forcefully decrease the mass?

Nash’s answers to the above questions are as follows: (1) add mass to all actions with positive regret, and the amount of mass added should be proportional to the regret; (2) do not decrease the mass for actions with negative regret. To retain the fact that the output of the improvement function must be a valid strategy, the step is renormalized so that the sum of the mass across all actions of any player is $$1$$ . We can formalize this process by using the following definition.

Definition L1.6 (Nash improvement function [Nas51]) .

Let $x_{1} \in \Delta (A_{1}) , \dots , x_{n} \in \Delta (A_{n})$ be arbitrary strategies. The Nash improvement function $\phi : \Delta (A_{1}) \times \dots \times \Delta (A_{n}) \to \Delta (A_{1}) \times \dots \times \Delta (A_{n})$ is the map

\displaystyle \phi_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right) \coloneqq \frac{x_{i , a_{i}} + \left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}}{1 + \sum_{a_{i}' \in A_{i}} \left[r_{i , a_{i}'} \left(x_{1} , \dots , x_{n}\right)\right]^{+}}

(1)

for every player $i \in [ n ]$ and action $a_{i} \in A_{i}$ . Here, $[ r ]^{+} \coloneqq \operatorname*{max} \{0 , r\}$ denotes the positive part of $$r$$ .

It is straightforward to verify that $\phi$ is well-defined and maps strategy profiles into strategy profiles. Indeed, the numerator in 1 is always nonnegative, and the denominator is always at least $$1$$ , implying that $\phi_{i , a_{i}} \ge 0$ for all $a_{i} \in A_{i}$ and player $i \in [ n ]$ . Furthermore,

\displaystyle \forall i \in \left[ n \right] , \qquad \sum_{a_{i} \in A_{i}} \phi_{i , a_{i}} \left( x_{1} , \dots , x_{n} \right) = \frac{\sum_{a_{i} \in A_{i}} \left(x_{i , a_{i}} + \left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}\right)}{1 + \sum_{a_{i}' \in A_{i}} \left[r_{i , a_{i}'} \left(x_{1} , \dots , x_{n}\right)\right]^{+}} = 1 ,

where we used the fact that $\sum_{a_{i} \in A_{i}} x_{i , a_{i}} = 1$ since $x_{i}$ is a valid strategy. Finally, observe that $\phi$ is a continuous function. The following example visualizes the Nash improvement function in the small games we have seen so far.

Example L1.7 .

The plots below visualize the displacement $\phi (x_{1} , x_{2}) - (x_{1} , x_{2})$ induced by the Nash improvement function for four games, whose payoff matrices are noted below each plot, after projecting away the probability of the first action of each player (and keeping around only the probability of the second action, which is sufficient to uniquely recover the strategy of the player since each player only has two actions). The black dots denote the fixed points of the Nash improvement function. These correspond exactly to the Nash equilibria of the game, as we make formal below.

The background of the plots highlights the angle of displacement induced by the Nash improvement function, according to the gradient wheel shown below here.

[If the color scheme seems arbitrary, as a small spoiler it will play a fundamental role in the proof of the computational complexity of Nash equilibria, which we will discuss later on in this course. In particular, the three regions of the coloring scheme will be key in defining an important combinatorial construction called Sperner coloring.]

L1.2.2 Quantifying the increase in utility of the improvement step

We validate our intuition that the Nash improvement function is a “profitable response” function. The following result shows that if a player has positive regret for any action, then the Nash improvement function unilaterally increases that player’s utility. This is a key property that will allow us to show that the fixed points of the Nash improvement functions must be Nash equilibria.

Theorem L1.8 .

For any strategy profile $(x_{1} , \dots , x_{n})$ , and any player $i \in [ n ]$ , the Nash improvement function $\phi$ satisfies

\displaystyle u_{i} \left(\phi_{i} \left(x_{1} , \dots , x_{n}\right) , x_{- i}\right) - u_{i} \left(x_{1} , \dots , x_{n}\right) = \frac{\sum_{a_{i} \in A_{i}} \left(\left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}\right)^{2}}{1 + \sum_{a_{i} \in A_{i}} \left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}} .

So, if even one action of a player $$i$$ has positive regret, then the Nash improvement function unilaterally strictly increases the utility of that player.

Proof.

Since we are focusing on a generic player $$i$$ and keeping all the other ones fixed (and playing strategies $x_{- i}$ ), we will reduce the notational burden by using the following shorthands:

\displaystyle r_{i , a_{i}}

\displaystyle \coloneqq r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right) ,\mathord{\text{(regret of action }} a_{i} \mathord{\text{ fixing }} x_{- i} )

\displaystyle u_{i , a_{i}}

\displaystyle \coloneqq u_{i} \left(a_{i} , x_{- i}\right) ,\mathord{\text{(utility of action }} a_{i} \mathord{\text{ fixing }} x_{- i} )

\displaystyle x_{i , a_{i}}'

\displaystyle \coloneqq \phi_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right) = \frac{x_{i , a_{i}} + r_{i , a_{i}}^{+}}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}} \quad \left(\mathord{\text{prob. of }} a_{i} \mathord{\text{ in improved strat.}}\right) ,

where the notation $z^{+}$ is a shorthand for the positive part of $$z$$ , that is, $z^{+} \coloneqq [ z ]^{+} \coloneqq \operatorname*{max} \{0 , z\}$ .

The increase in utility is then computed as

\displaystyle \sum_{a_{i} \in A_{i}} u_{i , a_{i}} ⋅ \left(x_{i , a_{i}}' - x_{i , a_{i}}\right)

\displaystyle = \sum_{a_{i} \in A_{i}} u_{i , a_{i}} ⋅ \left(\frac{x_{i , a_{i}} + r_{i , a_{i}}^{+}}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}} - x_{i , a_{i}}\right)

\displaystyle = \sum_{a_{i} \in A_{i}} u_{i , a_{i}} ⋅ \frac{r_{i , a_{i}}^{+} - \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+} ⋅ x_{i , a_{i}}}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}}

\displaystyle = \frac{1}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}} \left(\sum_{a_{i} \in A_{i}} r_{i , a_{i}}^{+} ⋅ u_{i , a_{i}} - \sum_{a_{i}' \in A_{i}} \left(r_{i , a_{i}'}^{+} \sum_{a_{i} \in A_{i}} x_{i , a_{i}} ⋅ u_{i , a_{i}}\right)\right)

\displaystyle = \frac{1}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}} \left(\sum_{a_{i} \in A_{i}} r_{i , a_{i}}^{+} ⋅ \left(u_{i , a_{i}} - \sum_{a_{i}' \in A_{i}} u_{i , a_{i}'} ⋅ x_{i , a_{i}'}\right)\right)

\displaystyle = \frac{1}{1 + \sum_{a_{i}' \in A_{i}} r_{i , a_{i}'}^{+}} \left(\sum_{a_{i} \in A_{i}} r_{i , a_{i}}^{+} ⋅ r_{i , a_{i}}\right) .

Using the fact that $z^{+} ⋅ z = (z^{+})^{2}$ for all $z \in \mathbb{R}$ , we obtain the statement.

At this point, the following is a simple corollary.

Theorem L1.9 .

A strategy profile

(x_{1} , \dots , x_{n})

is a Nash equilibrium if and only if it is a fixed point of the Nash improvement function

\phi

Proof.

( $$⟹$$ ) If $(x_{1} , \dots , x_{n})$ is a Nash equilibrium, then by definition for all $i \in [ n ]$ and $a_{i} \in A_{i}$ , we have $r_{i , a_{i}} (x_{1} , \dots , x_{n}) \le 0$ . Hence, for all $i \in [ n ]$ and $a_{i} \in A_{i}$ , we have

\displaystyle \phi_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right) = \frac{x_{i , a_{i}} + \left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}}{1 + \sum_{a_{i}' \in A_{i}} \left[r_{i , a_{i}'} \left(x_{1} , \dots , x_{n}\right)\right]^{+}} = x_{i , a_{i}} ,

that is, $(x_{1} , \dots , x_{n})$ is a fixed point of $\phi$ .

( $$⟸$$ ) Conversely, suppose that $(x_{1} , \dots , x_{n})$ is a fixed point of $\phi$ . Then, for all $i \in [ n ]$ , from Theorem L1.8 we have

\displaystyle \frac{\sum_{a_{i} \in A_{i}} \left(\left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}\right)^{2}}{1 + \sum_{a_{i} \in A_{i}} \left[r_{i , a_{i}} \left(x_{1} , \dots , x_{n}\right)\right]^{+}} = u_{i} \left(\phi_{i} \left(x_{1} , \dots , x_{n}\right) , x_{- i}\right) - u_{i} \left(x_{1} , \dots , x_{n}\right) = 0 .

Hence, it must be $r_{i , a_{i}} (x_{1} , \dots , x_{n}) \le 0$ for all $i \in [ n ]$ and $a_{i} \in A_{i}$ (or the left-hand side would be strictly positive), and therefore $(x_{1} , \dots , x_{n})$ is a Nash equilibrium.

By invoking Brouwer’s fixed-point theorem, we recover the central result of this lecture: Nash equilibria always exist.

Corollary L1.10 .

Since

\phi

is continuous and maps the nonempty compact convex set

\Delta (A_{1}) \times \dots \times \Delta (A_{n})

into itself, by Brouwer’s fixed point theorem, it has a fixed point. By Theorem L1.9, this implies that every game has (at least) one Nash equilibrium in mixed strategies.

L1.3 Bibliography for this lecture

[Nas50]	Nash, J. F., Jr. (1950). Equilibrium Points in N-Person Games. Proc. Natl. Acad. Sci. U.S.A., 36(1), 48. `https://doi.org/10.1073/pnas.36.1.48`
[Nas51]	Nash, J. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295. `http://www.jstor.org/stable/1969529`

Notes

1This notation appears often in game theory, since we are often interested in studying the effect of changing a single player $$i$$ ‘s strategy, while keeping all “the other” strategies $x_{- i}$ fixed.

2John Nash went on to win the Nobel prize in economics for his fundamental contributions to game theory.