Nash Equilibrium

A Nash Equilibrium is a strategy profile in which no players can improve by deviating from their strategies.

Formally, in a two-player extensive game, a Nash Equilibrium is a strategy profile $\sigma$ where the two inequalities are satisfied: $\{\begin{array}{l}{u}_1(\sigma )\ge {\max }_{{\sigma }_1^{\prime }\in {\sum }_1}{u}_1({\sigma }_1^{\prime },{\sigma }_2)\\ u_2(\sigma )\ge {\max }_{{\sigma }_2^{\prime }\in {\sum }_2}{u}_2({\sigma }_1,{\sigma }_2^{\prime })\end{array}$

• For instance, the first equation states for take any strategy ${\sigma }_1^{\prime }$ for player $1$ in the set of all strategies ${\sum }_1$ for player $1$, the expected payoff $u_1(\sigma )$ for player $1$ in this strategy profile $\sigma$ cannot improve

An approximation of a Nash Equilibrium, called $ϵ$-Nash Equilibrium, is a strategy profile where $\{\begin{array}{l}{u}_1(\sigma )+ϵ\ge {\max }_{{\sigma }_1^{\prime }\in {\sum }_1}{u}_1({\sigma }_1^{\prime },{\sigma }_2)\\ u_2(\sigma )+ϵ\ge {\max }_{{\sigma }_2^{\prime }\in {\sum }_2}{u}_2({\sigma }_1,{\sigma }_2^{\prime })\end{array}$

Other Way to Think About Nash Equilibrium

When every player is playing with a best response strategy to each of the other player’s strategies, the combination of strategies is called a Nash Equilibrium. No player can expect to improve play by changing strategy alone.

Steps to solve strategic games:

1. Set up the game
   1. Extensive form (i.e. tree diagram)
   2. Strategic form (i.e. table diagram)
2. Define each player’s set of strategies
3. Look for strictly dominant strategies
   1. If every player has a strictly dominant strategy, you’re done!
4. Eliminate strictly dominated strategies.
5. Find the pure strategy Nash equilibria of the game.
6. Find the mixed strategy Nash equilibrium of the game

Two ways to think about Nash Equilibrium:

1. At a Nash equilibrium, each player’s strategy is a Best Response to the other players’ strategies.
2. A Nash equilibrium is a mutual best response.

The Nash equilibrium is a decision-making theorem within game theory that states a player can achieve the desired outcome by not deviating from their initial strategy. In the Nash equilibrium, each player’s strategy is optimal when considering the decisions of other players.

In two-player Zero-Sum Games, playing a Nash equilibrium ensures you will not lose in expectation.

Exploitability: Distance form a Nash equilibrium Nash Equilibrium exists in any finite game.

There are two types of Strategy Equilibrium:

1. Pure strategy equilibrium
   • Using Method 1: , because no player has an incentive to change their action.
   • Using Method 2 (Best-Reply):
2. Mixed strategy equilibrium?
   1. Assign probability to each strategy for each player
   2. Calculate the probability of each outcome of the game

Real-world AI must be robust to adversarial adaptation and exploitation.

Some other notes:

• Every game with a finite set of outcomes has at least one equilibrium (However, not guaranteed that this equilibrium is from pure strategy)
• Nash equilibria will not contain strictly dominated strategies.
• Some Nash equilibria might contain weakly dominated strategies.

Exploitability

A best response $BR({\sigma }_{-i})$ is a strategy for player $i$ that is optimal against ${\sigma }_{-i}$ .

Exploitability of ${\sigma }_i$ is defined as $u_i({\sigma }_{\ast })-u_i({\sigma }_i,BR({\sigma }_i))$ where ${\sigma }_{\ast }$ is a Nash equilibrium.

Related

Resources:

• https://nashpy.readthedocs.io/en/stable/text-book/index.html

• Nash’s Existence Theorem

• Correlated Equilibrium