Home » Operations Research » Introduction to Game Theory
Introduction to Game Theory
1 Game Theory
2 Characteristics of game theory
2.1 Chance of Strategy
2.2 Number of players
2.3 Number of activities
2.4 Payoff
2.5 Competitive Game
2.6 Strategy
2.7 Pure Strategy
2.8 Mixed Strategy
2.9 Zero-Sum Game
2.10 Two-Person Game
2.11 Two-Person Zero-Sum Game
2.12 Payoff Matrix
3 Example of Two-person zero-sum game
In this tutorial we will discuss about the game theory, various types of game and various terms related to game theory.
Usually when we heard about the game, the first thought came to our mind is about the game from sports (like cricket, hockey, football, etc.) or a computer game.
But the game defined in game theory is a game between two opposing parties with conflicting interest. Game theory deals with decision making processes of players in conflicting and competitive situations where strategy of a player depends upon the strategy of opponent player.
Game is defined as an activity between two or more persons involving activities by each person according to a set of rules. (The set of rules defines the game and going through the set of rules once by the participants defines a play.)
Game theory is a type of decision theory which depends upon competitive situations. A competitive situation is a situation in which there are two or more opposite parties with conflicting interest and the action of one depends upon the action taken by the opponent. At the end of the game each person receives some benefit or satisfaction or suffers loss.
Characteristics of game theory
Various types of games can be classified on the basis of the following characteristics.
Chance of Strategy
If in a game, activities are determined by skill, it is said to be a game of strategy; if they are determined by chance, it is a game of chance. Thus a game may involve game of strategy as well as a game of chance.
A game is called an n-person game if the number of persons playing is n. (Person mean an individual or a group aiming at a particular objectives.)
Number of activities
A game is said to be a finite game if it has a finite number of (activities) moves each of which involves only a finite number of alternatives, otherwise the game is said to be infinite.
A quantitative measure of satisfaction a person gets at the end of each play is called a payoff. It is a real valued function of variables in the game.
Competitive Game
A competitive situation is called a competitive game if it has the following four properties :
There are finite number ($n$) of competitors called players such that $n>2$. If $n = 2$, then such a game is called Two-Person game.
Each player has a finite number of moves.
A play is said to occur when each player chooses one of his moves. The moves are assumed to be made simultaneously, i.e. no player knows the move of the other until he has decided on his own.
Every combination of moves determines an outcome known as payoff (which may be points, money) which results in a gain of payments to each player. Negative gain implies the loss of same amount.
In most of the games a number of competitive action (called strategies) are involved which may be finite or infinite. Such a game is called games of strategy e.g. chess, playing card games etc. In the game of strategy, two or more opponent or decision makers are involved which are called players.
Pure Strategy
A strategy is called pure strategy if a player knows exactly what the other player is going to do, i.e. a deterministic situation is obtained and objective function is to maximize the gain. Therefore, the pure strategy is a decision rule always to select a particular course of action.
Mixed Strategy
A strategy is called mixed strategy if a player is guessing as to which activity is to be selected by the other on any particular occasion, i.e. a probabilistic situation is obtained and objective function is to maximize the expected gain.
The different strategies adopted by players affect the respective outcome of the game which may present a lose, a gain or draw. i.e., each outcome of the game can be represented by a single payoff number which represent a loss or gain or draw as a outcome of adopting particular strategy.
Zero-Sum Game
If the players make payments only to each other, i.e. the loss of one is the gain of others, and nothing comes from outside, the competitive game is said to be zero-sum.
Two-Person Game
The game in which only two persons (players) are involved is called Two-Person game.
Two-Person Zero-Sum Game
A game with only two players is called two-person zero-sum game if the losses of one player are equivalent to the gains of the other, so that the sum of their gains is zero.
Payoff Matrix
In a two-person zero-sum game, the resulting game can be easily represented in the form of matrix called payoff matrix or gain matrix. Thus, a payoff matrix is a table which shows how the payment is made at the end of a play or game.
Let us consider a game with two players $A$ and $B$ in which player $A$ has $m$ strategies (moves) and player $B$ has $n$ strategies (moves). The game can be described in form of a payoff matrix such that
Row designations for each matrix are strategies available to $A$.
Column designations for each matrix are the strategies available to $B$.
The cell $a_{ij}$ is the payment to $A$ in $A$'s payoff matrix when A chooses the $i^{th}$ strategy and $B$ chooses the $j^{th}$ strategy.
In a two-person zero-sum game, the cell entry in $B$'s payoff matrix will be negative of the cell entry in $A$'s payoff matrix. The two payoff matrices are as follows :
Payoff Matrix for Player A
Player A \ Player B
$1$
$\cdots$
$j$
$n$
$1$ $a_{11}$ $a_{12}$ $\dots$ $a_{1j}$ $\cdots$ $a_{1n}$
$2$ $a_{21}$ $a_{22}$ $\cdots$ $a_{2j}$ $\cdots$ $a_{2n}$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$i$ $a_{i1}$ $a_{i2}$ $\cdots$ $a_{ij}$ $\cdots$ $a_{in}$
$m$ $a_{m1}$ $a_{m2}$ $\cdots$ $a_{mj}$ $\cdots$ $c_{mn}$
Payoff Matrix for Player B
$1$ $-a_{11}$ $-a_{12}$ $\dots$ $-a_{1j}$ $\cdots$ $-a_{1n}$
$2$ $-a_{21}$ $-a_{22}$ $\cdots$ $-a_{2j}$ $\cdots$ $-a_{2n}$
$i$ $-a_{i1}$ $-a_{i2}$ $\cdots$ $-a_{ij}$ $\cdots$ $-a_{in}$
$m$ $-a_{m1}$ $-a_{m2}$ $\cdots$ $-a_{mj}$ $\cdots$ $-c_{mn}$
Example of Two-person zero-sum game
Consider the game of two players $A$ and $B$. In this game two players simultaneously reveal 1, 2, or 3 fingers each.
If the sum of the revealed fingers is even, player B pays to player A the sum in dollars, if the sum is odd, player A pays to player B the sum in dollars.
For this two-person zero-sum game, the pure strategies can be identified with the individual activities. Further, both players have the same set of pure strategies, {1, 2, 3}.
Let $A_1$, $A_2$ and $A_3$ represents pure strategy for Player $A$ if player $A$ reveal 1, 2 or 3 fingers respectively.
Let $B_1$, $B_2$ and $B_3$ represents pure strategy for Player $B$ if player $B$ reveal 1, 2 or 3 fingers respectively.
The payoff matrix is given in
Player A / Player B
$B_1$
$A_1$ 2 -3 4
$A_2$ -3 4 -5
Such a game is called a Two-person Zero-sum game.
In this tutorial, you learned about the basic concepts of game theory and some important characteristics of game theory.
To learn more about different methods to solve a game please refer to the following tutorials:
Let me know in the comments if you have any questions on game theory and your thought on this article.
Categories Game Theory, Operations Research Tags game theory, operations research
Chi-square test of goodness of fit with examples
Maximin-Minimax Principle to solve game