Game Theory

 THEORY OF GAMES

A game is a contest involving two or more competitors, each of whom wants to win.

 

A theory of games provides a series of mathematical models that may be useful in explaining interactive decision-making concepts, where two or more competitors are involved under conditions of conflict and competition.

 

The competitors are referred to as players. A player may be an individual, individuals, or an organization.

 

The models in the theory of games can be classified based on the following factors:

The number of players If a game involves only two players (competitors), then it is called a two-person game. However, if the number of players is more, the game is referred to as n-person game.

 

The sum of gains and losses If, in a game, the sum of the gains to one player is exactly equal to the sum of losses to another player, so that, the sum of the gains and losses equals zero, then the game is said to be a zero-sum game. Otherwise, it is said to be a non-zero-sum game.

 

Strategy The strategy for a player is the list of all possible courses of action that are likely to be adopted by him for every payoff (outcome). The particular strategy that optimizes a player’s gains or losses is called optimal strategy. The expected outcome, when players use their optimal strategy, is called the value of the game.

 

Generally, the following two types of strategies are followed by players in a game:

(a) Pure Strategy A particular strategy that a player chooses to play again and again regardless of other player’s strategy, is referred to as pure strategy. The objective of the players is to maximize their gains or minimize their losses.

 

(b) Mixed Strategy A set of strategies that a player chooses on a particular move of the game with some fixed probability is called mixed strategy. Thus, there is a probabilistic situation and the objective of each player is to maximize expected gain or to minimize expected loss by making the choice among pure strategies with fixed probabilities.

 

TWO-PERSON ZERO-SUM GAMES

A game with only two players is called a two-person zero-sum game, only if one player’s gain is equal to the loss of other player, so that the total sum is zero.

 

Payoff matrix The payoffs (a quantitative measure of satisfaction that a player gets at the end of the play) in terms of gains or losses, when players select their particular strategies, can be represented in the form of a matrix, called the payoff matrix.

 

Various methods to find the value of the game under the theory of games are as follows:

 

 

The objective of the study of the theory of games is to know how the players must select their respective strategies so that they can optimize their payoff. Such a decision-making criterion is referred to as the minimax-maximin principle.

 

Maximin principle For player A the minimum value in each row represents the least gain (payoff) to him if he chooses his particular strategy. He will then select the strategy that gives the largest gain among the row minimum values. This choice of player A is called the maximin principle, and the corresponding gain is called the maximin value of the game.

 

Minimax principle For player B, who is assumed to be the loser, the maximum value in each column represents the maximum loss to him if he chooses his particular strategy. He will then select the strategy that gives the minimum loss among the column's maximum values. This choice of player B is called the minimax principle, and the corresponding loss is the minimax value of the game.

 

Optimal strategy A course of action that puts any player in the most preferred position, irrespective of the course of action his competitor(s) adopt, is called an optimal strategy.

In other words, if the maximin value equals the minimax value, then the game is said to have a saddle (equilibrium) point and the corresponding strategies are called optimal strategies.

 

Value of the game Value of the game is the expected gain or loss in a game when a game is played a large number of times. This is the expected payoff at the end of the game, when each player uses his optimal strategy, i.e. the amount of payoff, V, at an equilibrium point.

 

A game may have more than one saddle point.

A game with no saddle point is solved by choosing strategies with fixed probabilities.

 

Rules to Determine Saddle Point

1) Select the minimum element in each row of the payoff matrix and write them to the right side of the row. Then, select the largest element among these elements and enclose it in a rectangle.

2) Select the maximum element in each column of the payoff matrix and write them under the bottom of the column. Then select the lowest element among these elements and enclose it in a circle.

3) Find out the element(s) that is the same in the circle as well as the rectangle and mark the position of such element(s) in the matrix. This element represents the value of the game and is called the saddle (or equilibrium) point.

 

MIXED STRATEGIES: GAME WITHOUT SADDLE POINT

In certain cases, no saddle point exists, i.e. maximin value ≠ minimax value. In all such cases, players must choose a mixture of strategies to find the value of the game and an optimal strategy.

 

THE RULES (PRINCIPLES) OF DOMINANCE

The rules of dominance are used to reduce the size of the payoff matrix. These rules help in deleting certain rows and/or columns of the payoff matrix that are inferior to at least one of the remaining rows and/or columns (strategies), in terms of payoffs to both players.

 

 

Dominance rule for a column

Every value in the dominating column must be less than or equal to the value of the corresponding dominated column. The column with the largest values (dominated column) must be deleted.

 

Dominance rule for row

Every value in the dominating row must be greater than or equal to the value of the corresponding dominated row. The row with the smaller values (dominated row) is deleted.