The trick to finding the Nash Equilibrium in mind strategy is that players must choose their probability distribution over their actions such that the other player is indifferent between his/her available actions.
The result of this is that the other player will not have any incentive to deviate if he/she is indifferent between his/her actions.
Let’s again look at the game of matching pennies to find the Nash Equilibria.
Player 1’s perspective: Split probability between heads(p) and tails(1-p) such that Player 2 gets the same reward irrespective of what he/she chooses: Reward of Player 2 , when Player 2 choose “heads” = Reward of Player 2 , when Player 2 chooses “tails” Reward of Player 2 when Player 2 chooses heads = [(p)*(-1)] + [(1 – p)*(1)] Reward of Player 2 when Player 2 chooses tails = [(p)*(1)] + [(1 – p)*(-1)] Using the above mentioned relation of equality: [(p)*(-1)] + [(1 – p)*(1)] = [(p)*(1)] + [(1 – p)*(-1)] On solving for p: p = 0.
5.
Therefore, Player 1 must play heads and tails with equal probability to prevent Player 2 from deviating.
Player2’s perspective: Split probability between heads(q) and tails(1-q) such that Player 1 gets the same reward irrespective of what he/she chooses: Reward of Player 1 , when Player 1 chooses “heads” = Reward of Player 1 , when Player 1 choose “tails” Reward of Player 1 when Playe r1 chooses heads = [(q)*(1)] + [(1 – q)*(-1)] Reward of Player 1 when Player 1 chooses tails = [(q)*(-1)] + [(1 – q)*(1)] Using the above mentioned relation of equality: [(q)*(1)] + [(1 -q)*(-1)] = [(q)*(-1)] + [(1 – q)*(1)] On solving for q: q = 0.
5.
Therefore, Player 1 must play heads and tails with equal probability to prevent Player 2 from deviating.
As a result, the Nash equilibrium strategy for the game “matching pennies” is (0.
5, 0.
5) for both player 1 and 2.
Summary of Mixed Strategy (What does it exactly mean to play a mixed strategy): It is a way to randomize (calculative) and confuse opponents Randomizing works better when the opponent is not predictable Mixed Strategies are a concise description of what might actually happen in the real world Deriving a Solution Using Game Theory So far, we have been rigorously dealing with the model problem to understand key game Theory concepts.
It’s time to get back to the penalty scenario we saw in the introduction.
Consider the following game matrix for the striker-goalkeeper situation: Here, the striker represents the row player and the goalkeeper represents the column player.
The payoff/rewards in this matrix represent the probabilities of success.
For instance, if both the goalkeeper and the striker play left, then the latter has a probability of scoring a goal by 0.
58 and the goalkeeper has a probability of saving by 0.
42.
Take special note that rewards in each cell add up to 1.
Thanks to the rigorous study we have done so far, we know how to calculate the Nash equilibrium for this game, aka the ideal strategy for both goalie and kicker: The striker’s best strategy is to make the goalkeeper indifferent to which side he jumps.
Therefore: Reward when goalie jumps to the left = Reward when goalie jumps to the right [(0.
42)*(p) + (0.
07)*(1-p)] = [(0.
05)*(p) + (0.
30)*(1-p)] On solving: p = 0.
38 This means that the equilibrium strategy for the striker is { left(0.
38), right(0.
62)}.
Similarly, the goalkeeper’s best strategy is to make the striker indifferent between which side he kicks.
Therefore: Reward when kicker kicks to the left = Reward when kicker kicks to the right [(0.
58)*(q) + (0.
95)*(1-q)] = [(0.
93)*(q) + (0.
70)*(1-q)] On solving: q = 0.
42 This means that the equilibrium strategy for goalie is { left(0.
42), right(0.
58)}.
The Final Nash equilibrium strategy is kicker{ left(0.
38), right(0.
62)} and goalie{ left(0.
42), right(0.
58)}.
How is Game Theory Useful for Data Science Professionals?.We have been solving many diverse games now and I am sure most of you must be wondering (maybe yelling) by now: How is it useful for Data Scientists?.How do we know the payoff values before solving the game?.Do these solutions generalize in the real world?.The rewards in the penalty kick game we just solved were actually based on the data collected from FIFA World Cup matches.
The Game Theory concepts we covered so far are used once the inferences from the data are made.
The inferences from our data analysis can then be used to model a normal form game which enables us to find the best possible action plan as per the game matrix.
In fact, Game Theory is closely used in conjunction with Big Data analytics to make optimized and strategic decisions.
Nash Equilibrium models the population dynamics very well.
Nash equilibrium strategies tend to closely follow real-world scenarios.
For instance: The penalty kick example we just discussed is a part of a study which was released in 2003.
The Nash Equilibrium results were found to be astonishingly close to observed real world strategies.
End Notes To read more about this study, you can read the work of Ignacio Palacios Huerta.
This study proves how professional soccer players play strategically using the Nash Equilibrium strategy.
You can find the study here (refer to page 399-402 for the example we covered).
I would also suggest watching this talk by Professor Milind Tambe (Director of AI for Social Good) and how he used Game Theory concepts and inferences from past data for social good.
However, this talk will only make perfect sense once you have understood this article well: Game Theory concepts are being used in various competitive domains, like Economics, Politics, Professional Sports, Business, etc.
And as data availability grows, so do the prospects of the application of game theory.
I look forward to hearing your views in the comments section below.
You can also read this article on Analytics Vidhyas Android APP Share this:Click to share on LinkedIn (Opens in new window)Click to share on Facebook (Opens in new window)Click to share on Twitter (Opens in new window)Click to share on Pocket (Opens in new window)Click to share on Reddit (Opens in new window) Related Articles (adsbygoogle = window.
adsbygoogle || []).
push({});.