Understanding Nash Equilibrium with example
an important pre-requisite for GANs
After seeing the above image (apart from Inception & Leo Dicaprio), the first thing that comes to mind is Balance or Equilibrium !!
You must have heard of the Hollywood movie ‘A Beautiful Mind’ (2001) about the mathematician John Nash who actually came up with the Nash Equilibrium. We will be talking about this Nash Equilibrium. When you have a movie around a mathematical concept, you know it’s important !!
Moving on to the real meat !!
Nash Equilibrium , in an environment, is a stable state where none of the players involved can get a better result unless the opponent/other players change their strategy/decision.
Sounds confusing. Right? an example & a few concepts may help
Stable state (In the context of this blog): A state from which outcome for no player can go worse
Unstable state (In the context of this blog): A state from which outcome for at least one player can go worse.
Optimal state: The state producing the best outcomes/result. An optimal state may not be stable !! we will see how
Equilibrium: It is the most stable/balanced state possible in the environment.
Now, coming back on track, assume we have a happy family of 4
One day, the mother found chocolate boxes in the fridge to be completely empty !! and as it happens, the siblings (Neeraj & Aditi) became the prime suspects.
In order to catch up with the culprit, the mother had a word with the siblings & presented them with a situation
- If both of them denies, both of them can’t play for 2 weeks
- If Neeraj denies but Aditi accepts, Aditi can’t play for 1 week & Neeraj for 10 weeks & vice-versa
- If both accept, they can’t play for 3 weeks
So, the punishment matrix looks something like this:
Now, the question is, what should each sibling reply in their separate investigations? Also, the catch here is they won’t know what the other counterpart has answered. So, eventually, we have 4 states
Neeraj: Accepts; Aditi: Accepts (State 1)
Neeraj: Accepts; Aditi: Denies (State 2)
Neeraj: Denies; Aditi: Denies (State 3)
Neeraj: Denies; Aditi: Accepts (State 4)
So, what strategy (accept or denial) should Neeraj & Aditi choose?
Here comes Nash Equilibrium !!!
Nash Equilibrium can help a player take up the most ideal strategy in games/situations where the outcomes won’t just depend on his/her decisions, but on other players as well & we don’t know what others gonna answer/decided/strategize. Here, the two siblings are under the suspicion of eating up all chocolates & their punishment does depend on how the two players (siblings) reply & not just individual replies to their mother would help. Also, they don’t know what other has in his/her mind. Making it suitable for Nash equilibrium to jump in !!
As mentioned in the definition earlier, Nash Equilibrium is that stable state in the game where any individual player can’t get to a better outcome unless the other player(s) may change their decisions. Let us understand what this means.
In the above scenario, State 1 (both accepts & gets a 3-week suspension) is the Nash Equilibrium.
How? let’s find out
- State 1 (Nash Equilibrium)
A. Neeraj’s point of view:
If Neeraj Accepts, 1) If Aditi accepts: 3 weeks & If 2) Aditi denies, 1 week 3) If Neeraj switches to Denial, 10 weeks as
- His outcome improves when the opponent changed her strategy but he didn’t i.e. State 1 → State 2
- If he changes his strategy from acceptance to denial, he will get 10 weeks as Aditi accepts in State 1 i.e. State 1 → State 4. Hence, changing his strategy won't improve his current punishment/situation.
B. Aditi’s point of view
If Aditi Accepts, 1) If Neeraj accepts: 3 weeks & If 2) Neeraj denies, 1 week 3) If Neeraj switches to Denial, 10 weeks. Reasons being explained as above
So, it does suits are the definition of a Nash Equilibrium as No player(Neeraj & Aditi) can improve unless the opponent(s) change their decision
Why can’t other states be Nash Equilibrium? Let’s figure that out as well
- State 2 & State 4 (Unstable states)
These can’t be Nash Equilibrium state as
For State 2: Though Neeraj can’t improve on the outcome (already 1-week punishment), Aditi certainly can choose to ‘accept’ & reduce her punishment from 10 weeks to 3 weeks. But as Nash Equilibrium should hold for all possible players & Aditi may violet this, this can’t be a Nash Equilibrium as she can move to a better outcome by changing her decision which doesn’t hold for Nash Equilibrium
Similarly, for State 4: Though Aditica can't improve on the outcome (1-week punishment), Neeraj certainly can choose to accept & reduce her punishment from 10 weeks to 3 weeks. Reason being same as above
- State 3 (optimal but unstable):
This is interesting to understand why State 2 isn’t equilibrium where both Neeraj & Aditi denies & get 2 weeks of punishment and hence the optimal state given the punishment assigned to both players. This is because as quoted above if the counterparts change their decision to ‘accept’, the punishment increases to 10 weeks for either Neeraj or Aditi depending on the case & hence unstable state.
How is it useful for GANs? we will figure it out in my next. Till then keep yourself engaged with the below posts
For more on Data Science, you do have some delicacies ready to eat
- Generative modeling (4 parts)
- Transformers in NLP(4 parts)
- Dimension Reduction (3 parts)
- NLP Algorithms(7 parts)
- Reinforcement Learning Basics (5 parts)
- Starting off with Time-Series (7 parts)
- Object Detection using YOLO (3 parts)
- Tensorflow for beginners (concepts + Examples) (4 parts)
- Statistics for beginners (4 parts)
