Game Theory

GAME THEORY INTRODUCTION Life is full of conflict and competition. Some examples are parlour games, war, political campaigns, advertising and marketing by business firms. Game theory is a mathematical theory that deals with conflict situations like these. Basic characteristics of a game. In a game: There are at least two players Each player wants to win The winner will get a payoff Players compete with each other Cooperation is not an advantage Rules of the game are clearly defined and known to all players, in advance Each player has a finite set of possible strategies The outcome of the game depends on the strategies chosen by each player Game theory is the study of how players should rationally play games. Each player would like the game to end in an outcome which gives him as large payoff as possible. The four main components that interact with each other in a game are players, strategies, outcome and payoffs. Games are defined by, a) The number of players. When there are two players it is called a two person game. When there are n players it is called an n person game etc. b) The net winnings of the game. A zero sum game is where the net winnings is zero. For example in a two person zero sum game what one player wins the other looses. c) Fairness of the game. A game which is not biased toward any player is called a fair game. A game in which a given player can always win by playing correctly is therefore called an unfair game. FORMULATION OF A TWO PERSON ZERO SUM GAME A two person zero-sum game is one in which the payoffs add up to zero. They are strictly competitive in that what one player gains the other loses. The game obeys a law of conservations of utility value, where utility value is never created or destroyed, only transformed from one player to another. To illustrate the basic characteristics of a two person zero sum game consider the following game. Odds and evens: Each player simultaneously shows one finger or two. If the number of fingers match player 1 receives Rs 1 from player 2, otherwise player 2 receives Rs 1 from player 1. In this game each player has two strategies. To show one finger or two. Table 1 shows the payoff table for player 1. In general a two person game is characterised by Strategies of player 1 Strategies of player 2 The payoff table

In a two person zero sum game the payoff table shows the payoff to player 1. Payoff to player 2 is just the negative of this one. Player2 1 1 -1

Strategy 1 2

Player1

2 -1 1

Table 1: Payoff table for odds and evens game Games with saddle points Let us consider the game shown in Table 2.

Strategy 1 Player 1 2 3

Player2 2 -2 0 -2

1 -3 2 5

Maximum

5

Minimum 3 6 2 -4

0 Minimax

-3 0 -4

Maximin

6

Table 2: Payoff table for player 1 How does player 1 analyse the payoff table to select the best strategy? One option is to use the maximin principle, where each player choses the strategy which contains the best of the worst possible outcomes. In other words, the player choses to maximise the minima and guarantee that the payoff will be less than player1’s maximin value. Player 2 is also making a strategic decision using the same logic. Player 2 is trying to minimise player1’s maxima. That is player 2 is adopting a minimax principle. In this example minimax=maximin=0. They coincide. When they coincide the game has a saddle point which is also called an equilibrium point. The players can only do worse, never by selecting a strategy other than the saddle point strategy. This situation where the players always play one strategy is called a pure strategy. Dominance A strategy S dominates strategy T if every outcome in S is at least as good as the corresponding outcome in T, and at least one outcome in S is strictly better than the corresponding outcome in T. A player should never play a dominated strategy.

A B C D

A 12 5 3 -16

B -1 1 2 0

C 1 7 4 0

D 0 -20 3 16

Table 3: A game with a dominated strategy Consider the game shown in table 3. All the numbers in column 2 are less than or equal to numbers in column 3. We say player2’s strategy B dominates strategy C, or strategy C is dominated by strategy B. Mixed strategies

Consider the following game.

A B Col Maximum

A 2 0

B -3 3

2

3

Row Minimum -3 0 Maximin

Minimax Table 4: A game without a saddle point In this game minimax is not equal to maximin. Which means there is no saddle point. Here neither player would want to play a pure strategy, because the other player would take advantage of such a choice. The only sensible plan is to use some random device to decide which strategy to play. For example player 1 might flip a coin to decide between strategies A and B. Such a plan, which involves playing a mixture of strategies according to a certain fixed probabilities is called a mixed strategy. The effect of one or both players using mixed strategies can be analysed using the concept of expected value. The expected value of getting payoffs a1, a2, a3, ……..ak with respective probabilities p1, p2, p3 ……pk is p1a1 + p2a2 + p3a3 + ………+pkak. You will notice that the expected value of a set of payoffs is just the weighted average of those payoffs, where the weights are the probabilities that each will occur. If player 2 uses the coin flipping strategy for the game shown in Table 4, she will play strategy A with probability ½ and strategy B with probability ½. Hence if player 1 plays strategy A, he will get a payoff of 2 with a probability of ½ and -3 with a probability of ½ Thus player 1’s expected payoff is ½(2)+ ½ (-3) = - ½ . Similarly if player1 plays strategy B the expected payoff is ½(0)+ ½(3) = 1½. It is clear that if player1 knows that player 2 is playing the mixed strategy ½ A, ½ B he should play strategy B. This reasoning is known as the Expected Value Principle. If you know that your opponent is playing a given mixed strategy, and will continue to play regardless of what you do, you should play your strategy which has the largest expected value. Now consider the situation from Player2’s point of view. If he use the mixed strategy ½ A, ½ B player 2 can take advantage of the situation and get a payoff of 1½. Player2 might consider using a different mixed strategy. There might be some choice of probabilities where player1 could not take advantage of ? Assume that Player2 plays a mixed strategy with probabilities x for A, (1-x) for B, where x is a number between 0 and 1. Player1’s expected payoffs for strategies A and B are, A: x(2) + (1-x)(-3) = -3 + 5x B : x(0) + (1-x)(3) = 3 -3x Player1 will not be able to take advantage of Player2’s mixed strategy, if these two expected values are the same. Equating these two expected values we get x= ¾ . If player2 plays a mixed strategy ¾ A , ¼ B he can assure that Player1 wins, on the average no more than ¾ per game. Player1s payoffs for strategies A and B are, A: ¾ (2) + ¼ (-3) = ¾ B: ¾ (0) + ¼ (3) = ¾

Now consider this game from Player1’s point of view. In trying to find a mixed strategy in which Player2 cannot take advantage of, Player1 does a similar calculation. A: x(2) + (1-x)(0) = 2x B: x(-3) + (1-x)(3) = 3-6x Equating these two expected payoffs we get x= 3/8. If player1 plays a mixed strategy 3/8 A, 5/8 B, he is assured winning, on the average , at least ¾ regardless of how Player2 plays. A: 3/8(2) + 5/8(0) = ¾ B: 3/8(-3) + 5/8(3) = ¾ So the solution of this game is • ¾ is the value of the game

• •

¾ A, ¼ B Player2’s optimal strategy 3/8 A, 5/8 B Player1’s optimal strategy

Every game has such a solution either in pure strategy or in mixed strategy.