In Game Theory, how can players ever come to an end if there still is perhaps a greater option to make your mind up for? Possibly one player still wants to alter their decision. But in the event that they do, perhaps the opposite player wants to alter too. How can they ever hope to flee from this vicious circle? To resolve this problem, the concept of a Nash equilibrium, which I’ll explain in this text, is prime to game theory.
This text is the second a part of a four-chapter series on game theory. If you happen to haven’t checked out the primary chapter yet, I’d encourage you to try this to get accustomed to the most important terms and ideas of game theory. If you happen to did so, you are ready for the subsequent steps of our journey through game theory. Let’s go!
Finding the answer
We are going to now try to search out an answer for a game in game theory. A solution is a set of actions, where each player maximizes their utility and subsequently behaves rationally. That doesn’t necessarily mean, that every player wins the sport, but that they do one of the best they’ll do, on condition that they don’t know what the opposite players will do. Let’s consider the next game:
If you happen to are unfamiliar with this matrix-notation, it is advisable to have a look back at Chapter 1 and refresh your memory. Do you keep in mind that this matrix gives you the reward for every player given a particular pair of actions? For instance, if player 1 chooses motion Y and player 2 chooses motion B, player 1 will get a reward of 1 and player 2 will get a reward of three.
Okay, what actions should the players resolve for now? Player 1 doesn’t know what player 2 will do, but they’ll still try to search out out what could be one of the best motion depending on player 2’s selection. If we compare the utilities of actions Y and Z (indicated by the blue and red boxes in the subsequent figure), we notice something interesting: If player 2 chooses motion A (first column of the matrix), player 1 will get a reward of three, in the event that they select motion Y and a reward of two, in the event that they select motion Z, so motion Y is best in that case. But what happens, if player 2 decides for motion B (second column)? In that case, motion Y gives a reward of 1 and motion Z gives a reward of 0, so Y is best than Z again. And if player 2 chooses motion C (third column), Y continues to be higher than Z (reward of two vs. reward of 1). Meaning, that player 1 should never use motion Z, because motion Y is all the time higher.
We compare the rewards for player 1for actions Y and Z.
With the aforementioned considerations, player 2 can anticipate, that player 1 would never use motion Z and hence player 2 doesn’t need to care in regards to the rewards that belong to motion Z. This makes the sport much smaller, because now there are only two options left for player 1, and this also helps player 2 resolve for his or her motion.
We came upon, that for player 1 Y is all the time higher than Z, so we don’t consider Z anymore.
If we have a look at the truncated game, we see, that for player 2, option B is all the time higher than motion A. If player 1 chooses X, motion B (with a reward of two) is best than option A (with a reward of 1), and the identical applies if player 1 chooses motion Y. Note that this may not be the case if motion Z was still in the sport. Nevertheless, we already saw that motion Z won’t ever be played by player 1 anyway.
We compare the rewards for player 2 for actions A and B.
As a consequence, player 2 would never use motion A. Now if player 1 anticipates that player 2 never uses motion A, the sport becomes smaller again and fewer options need to be considered.
We saw, that for player 2 motion B is all the time higher than motion A, so we don’t have to think about A anymore.
We will easily proceed in a likewise fashion and see that for player 1, X is now all the time higher than Y (2>1 and 4>2). Finally, if player 1 chooses motion A, player 2 will select motion B, which is best than C (2>0). In the long run, only the motion X (for player 1) and B (for player 2) are left. That’s the answer of our game:
In the long run, just one option stays, namely player 1 using X and player 2 using B.
It will be rational for player 1 to decide on motion X and for player 2 to decide on motion B. Note that we got here to that conclusion without exactly what the opposite player would do. We just anticipated that some actions would never be taken, because they’re all the time worse than other actions. Such actions are called strictly dominated. For instance, motion Z is strictly dominated by motion Y, because Y is all the time higher than Z.
One of the best answer
Such strictly dominated actions don’t all the time exist, but there may be the same concept that’s of importance for us and is named a best answer. Say we all know which motion the opposite player chooses. In that case, deciding on an motion becomes very easy: We just take the motion that has the best reward. If player 1 knew that player 2 selected option A, one of the best answer for player 1 could be Y, because Y has the best reward in that column. Do you see how we all the time looked for one of the best answers before? For every possible motion of the opposite player we looked for one of the best answer, if the opposite player selected that motion. More formally, player i’s best answer to a given set of actions of all other players is the motion of player 1 which maximises the utility given the opposite players’ actions. Also remember, that a strictly dominated motion can never be a best answer.
Allow us to come back to a game we introduced in the primary chapter: The prisoners’ dilemma. What are one of the best answers here?
How should player 1 resolve, if player 2 confesses or denies? If player 2 confesses, player 1 should confess as well, because a reward of -3 is best than a reward of -6. And what happens, if player 2 denies? In that case, confessing is best again, because it could give a reward of 0, which is best than a reward of -1 for denying. Meaning, for player 1 confessing is one of the best answer for each actions of player 2. Player 1 doesn’t need to worry in regards to the other player’s actions in any respect but should all the time confess. Due to the game’s symmetry, the identical applies to player 2. For them, confessing can be one of the best answer, regardless of what player 1 does.
The Nash Equilibrium
If all players play their best answer, we’ve reached an answer of the sport that is named a Nash Equilibrium. This can be a key concept in game theory, due to a very important property: In a Nash Equilibrium, no player has any reason to alter their motion, unless every other player does. Meaning all players are as completely happy as they will be within the situation they usually wouldn’t change, even when they may. Consider the prisoner’s dilemma from above: The Nash equilibrium is reached when each confess. On this case, no player would change his motion without the opposite. They may grow to be higher if each modified their motion and decided to disclaim, but since they’ll’t communicate, they don’t expect any change from the opposite player and so that they don’t change themselves either.
You could wonder if there may be all the time a single Nash equilibrium for every game. Let me inform you there can be multiple ones, as within the Bach vs. Stravinsky game that we already got to know in Chapter 1:
This game has two Nash equilibria: (Bach, Bach) and (Stravinsky, Stravinsky). In each scenarios, you’ll be able to easily imagine that there isn’t a reason for any player to alter their motion in isolation. If you happen to sit within the Bach concerto along with your friend, you wouldn’t leave your seat to go to the Stravinsky concerto alone, even when you favour Stravinsky over Bach. In a likewise fashion, the Bach fan wouldn’t go away from the Stravinsky concerto if that meant leaving his friend alone. Within the remaining two scenarios, you’d think otherwise though: If you happen to were within the Stravinsky concerto alone, you’d wish to get on the market and join your friend within the Bach concerto. That’s, you’d change your motion even when the opposite player doesn’t change theirs. This tells you, that the scenario you will have been in was not a Nash equilibrium.
Nevertheless, there can be games that don’t have any Nash equilibrium in any respect. Imagine you’re a soccer keeper during a penalty shot. For simplicity, we assume you’ll be able to jump to the left or to the proper. The soccer player of the opposing team may also shoot within the left or right corner, and we assume, that you just catch the ball when you resolve for a similar corner as they do and that you just don’t catch it when you resolve for opposing corners. We will display this game as follows:
You won’t find any Nash equilibrium here. Each scenario has a transparent winner (reward 1) and a transparent loser (reward -1), and hence one among the players will all the time want to alter. If you happen to jump to the proper and catch the ball, your opponent will wish to alter to the left corner. But then you definitely again will want to alter your decision, which is able to make your opponent select the opposite corner again and so forth.
Summary
This chapter showed the way to find solutions for games by utilizing the concept of a Nash equilibrium. Allow us to summarize, what we’ve learned thus far:
- An answer of a game in game theory maximizes every player’s utility or reward.
- An motion is named strictly dominated if there may be one other motion that’s all the time higher. On this case, it could be irrational to ever play the strictly dominated motion.
- The motion that yields the best reward given the actions taken by the opposite players is named a best answer.
- A Nash equilibrium is a state where every player plays their best answer.
- In a Nash Equilibrium, no player wants to alter their motion unless every other play does. In that sense, Nash equilibria are optimal states.
- Some games have multiple Nash equilibria and a few games have none.
If you happen to were saddened by the proven fact that there isn’t a Nash equilibrium in some games, don’t despair! In the subsequent chapter, we are going to introduce probabilities of actions and this may allow us to search out more equilibria. Stay tuned!
References
The topics introduced listed here are typically covered in standard textbooks on game theory. I mainly used this one, which is written in German though:
- Bartholomae, F., & Wiens, M. (2016). . Wiesbaden: Springer Fachmedien Wiesbaden.
An alternate in English language might be this one:
- Espinola-Arredondo, A., & Muñoz-Garcia, F. (2023). . Springer Nature.
Game theory is a slightly young field of research, with the primary most important textbook being this one:
- Von Neumann, J., & Morgenstern, O. (1944). Theory of games and economic behavior.
