Chapter 7: Game Theory

Basic Terminology and Classification of Games

Game theory is a mathematical theory that deals with the general features of competitive cases and places particular emphasis on the decision making processes of the rivals. It is useful to know some basic concepts related to games, before moving on to the subject.

Basic Concepts of Game Theory

The basic concepts related with game theory are as follows:

Players: Each individual (interested party) is called a player who makes decisions that are interdependent. This interdependence gives rise to each player to regard the other player’s possible decisions in formulating his or her own decision.

Strategy: A strategy is a complete description of a player’s course of action during the game. There are two kinds of strategies, pure strategy and mixed strategy. A pure strategy is an unconditional decision always to select a particular course of action. For example, in the game of Rock-Paper- Scissors, if a player would choose to only play Rock for each interdependent trial, regardless of the other player’s strategy, it would be the player’s pure strategy. A mixed strategy is a decision to choose a course of action for each play in accordance with some particular probability.

Pay-off: A pay-off is numerical value which indicates the amount gained or lost by a player at the end of the game contingent upon the course of actions all of other players.

Pay-off Matrix: A pay-off matrix shows the gains and losses that result from a combination of players’ strategy choices. The entries of pay-off matrix can be negative, positive or equal to zero. If an element of pay-off matrix is positive, the column player pays this amount to the row player. If an element of pay-off matrix is negative, the row player pays the absolute values of this amount to the column player.

Saddle Point: A saddle point is an element of the pay-off matrix that is simultaneously the smallest element in its row and the largest element in its column. Furthermore, saddle point is also regarded as an equilibrium point in the theory of games.

Classification of Games

Games can be classified according to some certain features. One of the most obvious is to classify a game by the number of players. A game can be designated as being one-person, two-person or n-person game. A player in a game may be corporation, team, and nation besides an individual.

Another basis for classifying games is the goals of players coincide or conflict based on possible winnings. A constant-sum game is a game of total conflict and the sum of total possible winnings remains constant no matter what actions the players take. Poker, for example, is a constantsum game because the player compete for a constant sum of money, though its distribution shifts in the course of play. The decisions of each players do not affect the available winnings. A zero-sum game is a special case of a constant-sum game. In variable-games, one player’s gain does not strictly imply another player’s loss. This means that total available winnings may change depending on the other players’ actions. For example, The Prisoner’s Dilemma is a variable-sum game.

Variable-sum games can be divided even further as being either cooperative or non-cooperative games. Players of cooperative games can communicate and are permitted to make binding agreements, while non-cooperative games players can communicate but they cannot make binding agreements, such as an enforceable contract. For example, a car seller and a buyer will be engaged in a cooperative game if they agree on a specific price and sign a contract. However, as they attempt to bargain a price, they participate in a non-cooperative game.

Another class of games is symmetric and asymmetric games. In symmetric games, all players have the same actions and even in case of interchanging players, the actions of players remain the same. The other words, the actions in a symmetric game depend on the strategies used, not on the players of the game. The Prisoner’s Dilemma is an example of a symmetric game. On the other hand, there are not identical strategy sets for the players in the asymmetric games. Decision making in asymmetric games depends on the different types of strategies and actions of players. A new firm which is entering in a market can be given as an example for an asymmetric game, because different firms adopt different strategies to enter in the same market.

A game is defined to be any situation in which

• There are at least two players,
• Each player has a finite number of strategies,
• Each player’s chosen strategies determine the outcome of the game,
• Each player acts rationally to maximize his/her gains,
• The different strategies of each player and the amount of gain is known to each player in advance.

Two-Person Zero-Sum Games

Game theory provides a mathematical framework for strategic decision-making processes in situations of conflict. The simplest type of competitive situations are two-person zero-sum games. These games involve only two players and one player’s gain causes the other player’s loss of an equal magnitude. In a two-person constant sum game, the sum of all players’ pay-offs is the same for any outcome.

Two-Person Zero-Sum Games

A two-person zero-sum game has the feature that for any choice of strategies, the sum of the gains for the players is zero. In these games, every dollar one player wins comes out of the other player’s pocket. Thus, two players have totally conflicting interest and there would be no cooperation between the players. Characteristics of twoperson zero-sum games are given as follows:

1. There are two players which have m and n strategies, respectively, can be represented by a m×n matrix. First player’s strategies can be represented by rows and second player’s strategies can be represented by columns. First player is called the row player and second player is called the column player.
2. The row player must choose 1 of m strategies and the column player must choose 1 of n strategies, simultaneously.
3. If the row player chooses his ith strategy and the column player chooses his j th strategy, the row player gains aij and the column player gains, b ij .

In two-person zero-sum games, the sum of aij and b ij is zero for each (aij, bij) strategies. In zero-sum games, b ij is equal to -aij , therefore we do not need to write in the payoff matrix. These games are based the assumption developed by John von Neumann and Oscar Morgenstern. It is implies that each player chooses a strategy that allows him to do the best he can, given that other player knows the strategy he is following.

Two-person zero-sum games are also called matrix games. The pay-off matrix of these games can be represent in a matrix form.

Mixed Strategies

In this game, Player One can be sure of a reward of at least (-1), and Player Two can hold Player One to a reward of at most (1). Therefore, it is unclear how to determine the value of the game and the optimal strategies. For any choice of strategies by both players, there is always a player who can benefit by unilaterally changing his/her strategy. For instance, if both players display “Heads”, then Player One could have increased his reward (-1) to (1). From this reason, no choice of strategies by the players is stable. In this case, the game theory offers each player to assign a probability distribution over their set of strategies. To express this mathematically, let

x ₁ = probability that Player One displays “Heads”
x ₂ = probability that Player One displays “Tails”
y ₁ = probability that Player Two displays “Heads”
y ₂ = probability that Player Two displays “Tails”.

Because these values are probabilities, they would need to be nonnegative and add to 1. Strategies (x ₁ , x ₂ ) for Player One and (y ₁ , y ₂ ) for Player Two are referred as mixed strategies. Any strategy which is not exactly deterministic, but instead involves chance, is called mixed strategy. A pure strategy is a special case of a mixed strategy because a player always chooses the same action and it does not involve chance.

To analyse the effect of the players using mixed strategies, it can be used the concept of expected pay-off. Expected pay-off is similar to the concept of expected value in probability theory. Expected pay-off is the weighted average of pay-offs, where the weights are the probabilities that each will occur.

According to the expected pay-off principle, if player one knows that his/her opponent (player two) is playing a given mixed strategy, and will continue to play it regardless of what player one does, player one should play his/her strategy which has the largest expected pay-off.

Every m×n matrix game has a solution, either in pure or mixed strategies.

Dominance Strategies

While we have so far focused on 2×2 games, beyond of these games, the next most complicated games are 2×n and m×2 games. In such games, it may seem more complicated to determine the best action for either player because there are more strategies. In some of these situations, decision maker can eliminate one or more strategies. For eliminating one or more strategies, the principle of dominance is used. The principle of dominance states that if one strategy of a player dominates over the other strategy in all cases then the later strategy can be ignored. In other words, a dominant strategy over the other only if it’s potential outcome is higher than the other’s potential outcome.

The principle of dominance is useful for two person zerosum games without saddle points. In cases of 2×n and m×2 games, the dominance property can be used to reduce the size of pay-off matrix by eliminating the strategies that would never be selected.

Graphical Solution of 2×n and m×2 Games

One of the ways to find optimal mixed strategies is a graphical solution method. This method may be used whenever one of the players has only two pure strategies. After dominated strategies are eliminated from 2×n or m×2 sized games, then the optimal solutions of 2×2 sized games are found with as discussed before.

This method can only be used in games with no saddle points, and having a pay-off matrix ( m ×2) and (2×n) sized games.