Computer Science with Applications 2

Basic game theory: Pure Nash Equilibria

Introduction

Game theory, as its name suggests, is a tool for analyzing games. Here the word 'game' takes on a more general meaning than one would normally expect. A game here is simply a collection of:

A finite number of players
A set of strategies that each player can take
A payoff function for each player based on the strategy that the player takes

This general framework fits our conventional notion of games, such as competitive sports, chess and gambling. We can also model many of the following real-world events as games:

Auctions
Competition between firms (strategies - how each firm positions itself. payoff - profits)
Any form of election is a game amongst potential candidates. The way each candidate markets himself is a strategy (i.e. appealing to working class voters, young voters, or special interests) and the payoff is the result of the election.

As a result, game theory has found applications in numerous fields such as economics, computer science, and evolutionary biology.

Basic Terminology

Given the players, strategies and payoffs, one can represent the game in normal (or strategic) form, which tells us the associated payoff for every possible combination of strategies. We call each combination of strategies played by the players a strategy profile and we use a matrix to represent the payoff associated with each strategy profile. For example, this matrix:

should be interpreted to mean:

given the profile (A, A), both Players 1 and 2 gain 2 each.
given the profile (A, B), Player 1 gains nothing, Player 2 gains 1.
given the profile (B, A), Player 1 gains 1, Player 2 gains nothing.
given the profile (B, B), both Players 1 and 2 gain 1 each.

We can classify games as pure, where players make their choices deterministically, or as mixed, where players are allowed to randomize their strategies.

Pure Nash Equilibrium

One of the most important concepts of game theory is the idea of a Nash equilibrium. Consider two players Alice and Bob, who are playing a pure strategy game. We say that Alice and Bob's choice of strategies (the strategy profile) is in Nash equilibrium if

given Bob's strategy, Alice is playing the best strategy she can (to maximize her payoff), and
given Alice's strategy, Bob is playing the best strategy he can.

This concept is important because this strategy pair can be considered stable as neither player has an incentive to deviate from his choice.

In some games, two or more choices can yield the same payoff. As a result, more than one choice can maximize a player's payoff. A player is said to be indifferent between two strategies that yield the same payoff.

Note that being in equilibrium does not necessarily mean the best cumulative payoff for all the players involved; sometimes players might improve their payoffs if they could somehow agree on strategies different from the Nash equilibrium. The Prisoners' Dilemma scenario provides an excellent example of this scenario.

Example 1: Prisoners' Dilemma

The classic Prisoners' Dilemma game is expressed as follows (from Wikipedia):

Two suspects are arrested by the police. The police have
insufficient evidence for a conviction, and, having separated
both prisoners, visit each of them to offer the same deal. If
one testifies (defects from the other) for the prosecution
against the other and the other remains silent (cooperates
with the other), the betrayer goes free and the silent
accomplice receives the full 10-year sentence. If both remain
silent, both prisoners are sentenced to only six months in
jail for a minor charge. If each betrays the other, each
receives a five-year sentence. Each prisoner must choose to
betray the other or to remain silent. Each one is assured that
the other would not know about the betrayal before the end of
the investigation. How should the prisoners act?

The natural instinct would be to say that the best option for everyone is to choose Silent. However, this strategy profile is not stable! To see why, suppose that Player 1 agrees to be Silent. Player 2 is better off switching to Betray. However, if both players choose to Betray, no one person is better off switching to Silent.

We will analyze this game using the definition of Nash Equilibrium:

Given (Silent, Silent), any one player is better off deviating and choosing to Betray (a gain of 5 instead of 4).
Given (Silent, Betray), Player 1 gets nothing if he/she sticks with her choice, but improves his gain to 1 if he chooses to follow suit and Betray (receiving 1 as opposed to 0).
Similarly, given (Betray, Silent), Player 2 is better off betraying.
Given (Betray, Betray), neither player has any incentive to switch since he would lower his payoff from 1 to 0. This profile is a Nash equilibrium!

As one can see, the so-called best option is not stable. While the (Betray, Betray) profile offers hardly any payoff, it is stable in the sense that it offers a guarantee of some degree of payoff.

Example 2: Matching Pennies

Matching Pennies is a classic example of a zero-sum game (payoffs in each strategy profile add up to zero).

Players 1 and 2 each have a penny and they will secretly choose heads or tails. They then reveal their choices simultaneously. If the pennies match, then Player 1 wins and receives a dollar from Player 2. Otherwise, Player 2 wins and receives a dollar from Player 1.

This game has no pure strategy Nash equilibria. To see why, suppose Player 1 and Player 2 both choose heads. Player 2 would be better off choosing tails given that he/she knows that Player 1 is playing heads, which means that Player 2 has an incentive to deviate. The same argument holds for the other strategy profiles.

Matching Pennies is a good example of a game where mixed strategies are useful: one could choose to play Heads or Tails with 50% chance each.

Example 3: Battle of the sexes

This game is a simple example of a coordination game (payoffs are higher when players make similar choices).

Alice and Bob have a date tonight (yes, tonight). Alice prefers to watch the ballet, while Bob would much rather watch soccer. However, since they are (presumably) in love, they would both prefer to spend time with each other than to go separately.

This game has two pure strategy Nash equilibria - (Ballet, Ballet) and (Soccer, Soccer).

Finding Pure Strategy Nash Equilibria

We can find the Nash equilibria for a game by applying the definition directly. For each strategy profile, we consider the following:

Fixing Player 2's strategy, we check if Player 1 is better off changing his/her strategy.
Fixing Player 1's strategy, we check if Player 2 is better off changing his/her strategy.

If neither Player can improve his payoff by either of these methods, then this strategy profile corresponds to a Nash equilibrium. It is easy to see that this method is a direct implementation of the definition.

As a side note, there is second method for finding Nash equilibria that is based on finding the best response that one player can make in response to the other player's choice.