Brief notes on Nash equilibrium
Notes taken from a HKU talk in 2.2003
- The Dominant strategy for a player of a game = a strategy that a rational player would not change no matter what.
- If all players of a game has a dominant strategy, then the outcome of a game can be predicted. The outcome is called the "solution" of the game.
- Example : "confess" is the dominant strategy of 1 2-person prisoners' dilemma.
- But not all games have a solution in the above sense.
- Nash's contribution #1 : defined a more general concept of a solution (Nash equilibrium).
- Nash equilibrium : a decision matrix where each player will not change its decision provided that the other player do not change theirs.
- Example : In a boring lecture, every student wants to leave, but they also don't want to be the first to leave. So they all end up staying.
- Mixed Nash equilibrium : Nash equilibrium when it comes to mixed strategies e.g. 70% of the time decision A and 30% of the time decision B in repeated games.
- Nash's contribution #2 : (won the Nobel prize for) proving that every finite n-player non-cooperative game has a mixed Nash equilibrium.
- Proof : (i) existence of M.N.eq. for a game corresponds to the existence of a fixed point in some polynomial eqt that corresponds to the game. (ii) Applies fixed point theorem to show that there is a fixed point for the polynomial for every game.
Category.Logic and Maths