This document provides an overview of game theory concepts including:
1) Two person zero-sum games which have exactly two players with completely opposed interests, known as TPZS games. These games can have pure or mixed strategies.
2) Pure strategies are predetermined courses of action selected with certainty. Games with pure strategies may have a saddle point.
3) Mixed strategies involve selecting courses of action probabilistically to maximize expected gains or minimize losses. Mixed strategies are used when games do not have a saddle point.
This document provides an overview of game theory concepts including:
1) Two person zero-sum games which have exactly two players with completely opposed interests, known as TPZS games. These games can have pure or mixed strategies.
2) Pure strategies are predetermined courses of action selected with certainty. Games with pure strategies may have a saddle point.
3) Mixed strategies involve selecting courses of action probabilistically to maximize expected gains or minimize losses. Mixed strategies are used when games do not have a saddle point.
This document provides an overview of game theory concepts including:
1) Two person zero-sum games which have exactly two players with completely opposed interests, known as TPZS games. These games can have pure or mixed strategies.
2) Pure strategies are predetermined courses of action selected with certainty. Games with pure strategies may have a saddle point.
3) Mixed strategies involve selecting courses of action probabilistically to maximize expected gains or minimize losses. Mixed strategies are used when games do not have a saddle point.
This document provides an overview of game theory concepts including:
1) Two person zero-sum games which have exactly two players with completely opposed interests, known as TPZS games. These games can have pure or mixed strategies.
2) Pure strategies are predetermined courses of action selected with certainty. Games with pure strategies may have a saddle point.
3) Mixed strategies involve selecting courses of action probabilistically to maximize expected gains or minimize losses. Mixed strategies are used when games do not have a saddle point.
Contents Game theory....................................................................................................................................................................... 3 Introduction....................................................................................................................................................................3 1.Two person zero sum game (with two players)...........................................................................................................3 1.2 Pure Strategies: Game with Saddle Point.................................................................................................................4 1.3 Mixed Strategies: Game without Saddle Point.........................................................................................................5 REFERENCE................................................................................................................................................................. 7
2 Game theory
Introduction
Game theory is a type of decision theory in which one’s choice of action is determined after taking into account all possible alternatives available to an opponent playing the same game, rather than just by the possibilities of several outcome results. Game theory does not insist on how a game should be played but tells the procedure and principles by which action should be selected. Thus it is a decision theory useful in competitive situations.
Game is defined as an activity between two or more persons according to a set of rules at the end of which each person receives some benefit or suffers loss. The set of rules defines the game. Going through the set of rules once by the participants defines a play.
1.Two person zero sum game (with two players)
The game in which there are exactly two player and the interest of the players completely opposed are referred as two- person zero sum games. They are called zerosum games because one player wins whatever the other player loses. In short it is denoted by TPZS game.
For example,
All parlous game and sports, like Tic-tac-toe, chess, cribbage, backgammon, and tennis ect., are TPZS games .
Two person zero sum game (with more than two players) TPZS games with more than two people involved are
(i) Team sports with only two sides, but with more than one player in each side
(ii) Many people involved in surrogates for military conflict, so it should come as no surprise that many military problems can also be analyzed as TPZS games.
Games which are not TPZS
(i) Those parlourgames in which the players cannot be clearly separated into two sides are not TPZS games .
(ii) Those poker and Monopoly games when played by more than two people are not TPZS games.
(iii) Most real economic “games” are not TPZS, because there are too many players, and also the interests of the players are not completely opposed.
3 Two-person zero-sum games may be deterministic or probabilistic. The deterministic games will have saddle points and pure strategies exist in such games. In contrast, the probabilistic games will have no saddle points and mixed strategies are taken with the help of probabilities.
1.2Pure Strategies: Game with Saddle Point
(i) Pure strategy:
Particular course of action that are selected by player is called pure strategy (course of action). i.e each player knows in advance of all strategies out of which he always selects only one particular strategy regardless of the other players strategy, and objective of the player is to maximize gain or minimize loss.
Saddle point
If the minmax value = maxmin value, then the game is said to have a saddle (equilibrium) point Procedure to determine saddle point
Step:-01
Select the minimum (lowest ) element in each row of the payoff matrix and write them under 'row minima' heading. Then select the largest element among these elements and enclose it in a rectangle.
Step:-02
Select the maximum (largest) element in each column of the pay of matrix and write them under 'column maxima' heading. Then select the lowest element among these elements and enclose it in a circle.
Step:-03
Find out the elements which is same in the circle as well as rectangle and mark the position of such elements in the matrix. This element represents the value of the game and is called the saddle point.
4 Example:-1
For the game with payoff matrix
Player B
Player A -1 2 -2
6 4 -6
Determine the best strategies for players A and B and also the value of the game. Is this game (i) fair (ii) strictly determinable?
Solution:-
Player B Row minimum
Player A -1 2-2-2
64 -6 -6
Column maximum 6 4 -2
Select minimum from the column maximum values.
ie. Minimax = 1, (marked as circle )
Select maximum from the row minimum values.
ie. Maximin = 1, ( marked as rectangle)
Player A will choose strategy I, which yields the maximum payoff of -2
Player B will choose strategy III.
The value of game is -2, which indicates that player A will gain -2 unit and player B will sacrifice -2 unit.
Since the maximin value = the minimax value =-2, therefore the game has saddle point and the game is not fair game. (since value of the game is non-zero)
5 Also maxmin=minimax=value of game, therefore the game is strictly determinable.
It is a pure strategy game and the saddle point is (A-I, B-III)
The optimal strategies for both players given by pure strategy , Player A must select strategy II and player B must select strategy III.
1.3 Mixed Strategies: Game without Saddle Point
(ii) Mixed strategy:
Course of action that are to be selected on a particular occasion with some fixed probability are called mixed strategies. i.e there is a probabilistic situation and objective of the players is to maximize expected gain or minimize expected losses by making choice among pure strategy with fixed probabilities.
In mixed strategy, If there are 'n' number of pure strategies of the player, there exist a set S={p1,p2,.....pn} where pj is the probility with which the pure strategy, j would be selected and whose sum is unity.
i.e p1+p2+.....+pn=1 and pj>=0 for all j=1,2,...n.
Pure Strategy: It is the predetermined course of action to be employed by the player. The players knew it in advance. It is usually represented by a number with which the course of action is associated.
1. The Rule of Dominance
The general rule of dominance can be formulated as follow
1. If all the elements of a column( sayithcolumn) are greater than or equal to the corresponding elements of any othercolumn ( say jthcolumn), then ith column is dominated by jth column. 2. If all elements of rth row are less than or equal to the corresponding elements of any other raw says, sth row, then rth row is dominated by sth row. 3. A pure strategy of a player may also be dominated if it is inferior to some convex combination of two or more pure strategies as a particular case inferior to the average of two or more pure strategies.
This situation is a rather special one, where the answer can be obtained just byapplying the concept of dominated strategies to rule out a succession of inferior strategiesuntil only one choice remains.A strategy is dominated by a second strategy if the second strategy is always atleast as good (and sometimes better) regardless of what the opponent does. Adominated strategy can be eliminated immediately from further consideration
6 REFERENCE
1. KantiSwarup, P.K.Gupta and Man Mohan, “Operations Research, Eighth Edition”,
Sultan Chand & Sons, New Delhi, 1999.
2. S.Hillier and J.Liebermann, Operations Research, Sixth Edition, McGraw Hill
Company, 1995.
3. Operations Research problems and solution, Third edition , J.K Sharma, Mackmillan
Publishers India Ltd, 2012.
4. .Theory of Games and Economic Behavior, 1944.
5.. Game Theory by Guillermo Owen, 2nd edition, Academic Press, 1982.
6. .Game Theory and Strategy by Philip D. Straffin, published by the Mathematical Association of America, 1993.
