Game Theory: An Introduction to Nash Equilibrium

According to Wikipedia, Nash Equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally.  

Basically what you are trying to find is the best possible choice for each player while fixing the action of the other player.  Let's take a look at some examples.

The Prisoner's Dilemma is one of the most famous motivating examples of game theory. It involves two people who are in for a crime. If both of them admit they are guilty, then they both have to do hard time (ie 25 years=-25). If one of them rats out the other (fink) and the other stays silent, then the one who stays silent will get 50 years. If they both stay silent, each one will get 1 month. What is the Nash Equilibrium?

For player 1, that is, the one who chooses the row, let us fix (keep constant) the column, or what the second player would play. From these choices, which choice will give the better payoff for the first player? Repeat this for all the columns (the first number is the one that represents the first player). Now for the rows, which the second player must choose for each row, what choice would be the best (which payout should be the highest looking at the second number). This might seem a little confusing with words, so let's look at this with an example. A pair that has the best payoffs for both players is a pure Nash Equilibrium. There is a possibility that there might not be any NE or everything might be a NE (ie where all the payoffs are equal). Yet, all games must have a NE, and it is best to look at mixed strategies, which assumes probabilistic outcomes.

A more formal approach:

You are trying to find the best response for a given player while fixing one of the other player's alternatives.

For example: Let's say that player 1 has alternatives A and B and player 2 has alternatives C and D.  Let's say that when fixing C, player 1 prefers A, and when fixing D, player 1 prefers B.  Let's then say that when player 2 fixes A, he prefers D, and when he fixes B, he prefers C as well as D (ie. equal utility or payoff). When a player prefers an alternative, it usually means he or she will receive a higher payoff or gain more utility as a result.

What is the end result?

B₁(C)={A}

B₁(D)={B}

B₂(A)={D}

B₂(B)={C,D}

NE: (B,D).  See that the best response produces the same choice as the choice that was fixed for the other player.

Hence, from our analysis, the NE is both of them ratting out each other. Although that might seem unlikely, perhaps a real-life example might be more applicable: Golden Balls, a British TV show that is a multi-level form of game theory. If you are not sure of the show, if you Youtube it, seeing it will show its application to game theory.

Game theory does not always work in practice, but for both people they have a desire to steal since there is a chance for 100% payoff, and it is mainly by moral restraint that people do not choose to steal. This case, if modeled once again would reveal that both people stealing is a Nash Equilibrium. To put into practice, let us consider the following bi-martrix.

Assume the total pot is C, and for a split, both get C/2.

There are three pure strategy NE: (Steal, Split), (Split, Steal), and (Steal, Steal).  Interestingly, (Split, Split) is the only pure strategy that is not a NE.

The proceeding bi-matrix form is what should be done given any number of alternatives. Note that the number of rows and columns do not necessarily need to be the same.

Sometimes it is possible for there to be no NE.  Let's look at the following example.