EE8212 Optimization Techniques for Engineers

Game Theory

1
 The Prisoner's Dilemma
There was a robbery at a jewellery shop in Galle. OIC of Galle Police
station arrested two people Daniel and Miguel. They were found in
possession of stolen jewellery. OIC remanded them separately and came
out with the following suggestion.
• If you confess and your partner does not, you go free and your partner
gets 20 years at jail.
• If both confess, each gets 5 years.
• If both are silent, each gets 2 years for possessing stolen property.

How can they get the

OPTIMUM decision?
2
 Introduction
Life is full of conflict and competition. Some
examples are,
• indoor games
• war
• political campaigns
• advertising and marketing by business firms.

Game theory is a mathematical theory that

deals with conflict situations like these.
3
 Mathematically a game has
following characteristics
• 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

4
 Which of these situations are games ?

• Provincial council elections

• GCE (Ordinary Level) examination
• GCE (Advanced Level) examination
• War in Syria
• Boarding ruhunu kamari train from fort station on
a friday afternoon
• Starting a new mobile telephone company
• Marriage
• Divorce

5
 Which of these situations are games ?

• Provincial council elections

• GCE (Ordinary Level) examination
• GCE (Advanced Level) examination
• War in Syria
• Boarding ruhunu kamari train from fort station on
a friday afternoon
• Starting a new mobile telephone company
• Marriage
• Divorce

6
• 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 or her as
large payoff as possible.
• The four main components that interact
with each other in a game are, players,
strategies, outcome and payoffs.

7
 Games are defined by
• 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.

8
 Games are defined by
• 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.
• 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.

9
 Games are defined by
• 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.
• 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.
• 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.

10
 Two Person Zero Sum games
A two person zero-sum(TPZS) game is one in
which the payoffs add up to zero. They are
strictly competitive in that what one player gains
the other looses
In general a two person game is characterised by

Strategies of player 1
Strategies of player 2
The payoff table

11
Ex: 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. They are to

show one finger or two.

Payoff table is a table showing the pay off to players for

each combination of strategies of the players. In each
cell of the payoff table there are two numbers.
• The first number is the payoff to player 1
• The second number is the payoff to player 2

12
Payoff table for the above game can be written as,

Player2
Strategy 1 2
1 1, -1 -1, 1
Player1 2 -1, 1 1, -1

Table 1: Payoff table for the game

In a TPZS game, the amount won by player 1 is equal

to amount lost by player 2. Hence in each cell the
second number can be obtained by multiplying the
first number by -1.

13
The payoff table can be simplified by showing only the
payoff to player 1. This is shown in table 2.

Player2
Strategy 1 2
1 1 -1
Player1 2 -1 1
Table 1: Payoff table for player 1

14
Games with saddle points
Let us consider the TPZS game shown in Table 3.

Player 2 Minimum
Strategy 1 2 3
1 -3 -2 6 -3
Player 1 2 2 0 2 0 Maximin
3 5 -2 -4 -4

Maximum 5 0 6
Minimax

Table 3: Payoff table for player 1

15
How does Player 1 analyse the payoff table to select the best
strategy?
One option is to use the maximin principle, where each player
chooses the strategy which contains the best of the worst
possible outcomes. In other words, the player chooses to
maximise the minima.

Player 2 is also making a strategic decision using the same logic.

Player 2 is trying to minimise Player 1’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 by selecting a
strategy other than the saddle point strategy. This situation where
the players always play one strategy is called a pure strategy.
16
Ex: Here is a very simplified model of price competition. Coca Cola and
Pepsi are two companies that sell bottled drinks. Each company has a fixed
cost of Rs 5000 per period, regardless whether they sell anything or not. The
two companies are competing for the same market and each firm must
choose a high price (Rs 2 per bottle) or a low price (Rs 1 per bottle). Here
are the rules of the situation;

1) At a price of Rs 2, 5000 bottles can be sold for a total revenue of Rs

10000.
2) At a price of Rs 1, 10000 bottles can be sold for a total revenue of Rs
10000.
3) If both companies charge the same price, they split the sales evenly
between them.
4) If one company charges a higher price, the company with the lower price
sells the whole amount and the company with the higher price sells nothing.
5) Payoffs are profits = (revenue - Rs 5000 fixed cost)

17
Ex: Here is a very simplified model of price competition. Coca Cola and Pepsi are
two companies that sell bottled drinks. Each company has a fixed cost of Rs 5000
per period, regardless whether they sell anything or not. The two companies are
competing for the same market and each firm must choose a high price (Rs 2 per
bottle) or a low price (Rs 1 per bottle). Here are the rules of the situation;

1) At a price of Rs 2, 5000 bottles can be sold for a total revenue of Rs 10000.

2) At a price of Rs 1, 10000 bottles can be sold for a total revenue of Rs 10000.
3) If both companies charge the same price, they split the sales evenly between
them.
4) If one company charges a higher price, the company with the lower price sells the
whole amount and the company with the higher price sells nothing.
5) Payoffs are profits = (revenue - Rs 5000 fixed cost)

Here is the payoff table for Pepsi:

Coca cola
Rs 1 Rs 2
Rs 1 0 5000
Pepsi
Rs 2 -5000 0
18
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 -1 1 0
B 5 1 7 -20
C 3 2 4 3
D -16 0 0 16
Table 5: A game with a dominated strategy

Consider the game shown in Table 5. All the numbers in column B are less
than or equal to numbers in column C. We say player2’s strategy B dominates
strategy C, or strategy C is dominated by strategy B.

19
Ex: Two newspapers Sunday leader and Sunday times, each trying to
choose between front page cover stories about “shooting of a tourist in
Tangalle” and “Floods in Ratnapura”. The payoff table below presents
information for both players. In each outcome box, the upper-right value
represents Sunday Times payoff, while the lower left value represents
Sunday Leader payoff. Thus we see that if Leader and Times both choose
shooting incident for their cover stories, for example, Times will get 28% of
the readers, and Leader will get 42%. (The other 30% of readers are only
interested in the floods, so they would buy neither paper in that case.)

Sunday Times
Shooting Floods
28% 30%
Shooting
Sunday 42% 70%
Leader
70% 12%
Floods
30% 18%

20
 Sunday Times
Shooting Floods
28% 30%
Shooting
Sunday 42% 70%
Leader
70% 12%
Floods
30% 18%

Now we can analyze this table to determine each paper’s optimal strategy.
Leader has a dominant strategy: selecting shooting for its front page story. This
move is dominant because no matter which topic Times chooses, Leader would
get a higher percentage of readers by running an shooting front page story than
it would by running the floods story. Thus Leader’s optimal strategy is obvious.
For Times, however, there are no dominant or dominated strategies; its best
choice depends upon Leader’s decision. However, Times can see from the
payoff table that Leader’s dominant strategy is to choose shooting, and so
knows that will be Leader’s choice. Given this information, Times optimal
strategy becomes selecting the floods for its front page story (as this will attract
30% of the readers, while competitively running the shooting front page story
would only attract 28%).

21
22
23
1

24
25
Graphical solution procedure
Consider the following TPZS game.
Player 2
Stratergy 1 2 3
Player 1 1 -1 1 3
2 5 4 2

Table : Payoff table for player 2

In this game the player 1 has two strategies, and player 2 has three
strategies. Suppose player 1 decides to play strategy 1 with a probability of
x. Then he will be playing the strategy 2 with a probability (1-x).
Now let us assume that player 2 decides to play strategy 1. Then the
expected payoff to Player 2 is,
-x + 5(1-x) = -6x + 5 (1)
Similarly, if player 2 decides to play strategies 2 and 3 expected payoff to him
are,
X + 4(1-x) = -3x + 4 (2)
And 3x + 2(1-x) = x +2 (3)
26
 y f(x)=-6x+5
f(x)=-3x + 4
f(x)=x + 2

3
2 2

1
1

x
0.1 0.2Fig: 0.3 0.4
Expected 0.5
payoff 0.6 player
to 0.7 2 0.8 0.9

The thick green line shows the maximum benefit the player 2 can get for
different values of x.
27
Now the player 1 should try to minimize this maximum benefit. From
the graph it can be seen that this occurs at the intersection of the two
lines y=-3x + 4 and y= x+2

The corresponding value of x is 0.5.

So the player 1 should play strategy 1 at 50% of the time and strategy
2 at 50% of the time. Player 2 should play strategy 2 or 3. Value of the
game is 2.5 in player 2’s favour. Hence this is not a fair game.

28
 Nash Equilibrium

DEFINITION: Nash Equilibrium If there is a set of strategies with the

property that no player can benefit by changing her strategy while the
other players keep their strategies unchanged, then that set of
strategies and the corresponding payoffs constitute the Nash
Equilibrium.

However, Nash equilibrium does not necessarily mean the best payoff
for all the players involved; in many cases, all the players might
improve their payoffs if they could somehow agree on strategies
different from the Nash equilibrium: e.g., competing businesses forming
a cartel in order to increase their profits.

29
There is an easy numerical way to identify Nash equilibria on a payoff matrix. It is
especially helpful in two-person games where players have more than two
strategies. In this case formal analysis may become too long. This rule does not
apply to the case where mixed (stochastic) strategies are of interest. The rule
goes as follows: if the first payoff number, in the duplet of the cell, is the
maximum of the column of the cell and if the second number is the maximum of
the row of the cell - then the cell represents a Nash equilibrium.

Option A Option B Option C

Option A 0, 0 25, 40 5, 10

Option B 40, 25 0, 0 5, 15

Option C 10, 5 15, 5 10, 10

30
Ex: In a Two Person Zero Sum Game, players are each provided with an ace
of diamonds and an ace of clubs. Player 1 is also given the two of diamonds
and Player 2 the two of clubs. In a play of the game, Player 1 shows one
card, and Player 2, ignorant of Player 1’s choice, shows one card. Player 1
wins if the suits match, and Player 2 wins if they do not. The amount (payoff)
that is won is the numerical value of the card of the winner. But, if the two
deuces(2’s) are shown, the payoff is zero.

Prepare a payoff matrix for this game.

What is the optimal strategy for Player 1?

What is the value of the game.

Is this a fair game?

31
 Player 2

AD AC 2C
AD 1 -1 -2
Player 1
AC -1 1 1
2D 2 -1 0
Table : Payoff table for player 1
y
f(x)=-3x+2

2 f(x)=2x-1
f(x)=x

1 1
3
2 x
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

-1

Fig: Expected payoff to player 1 32

The optimal strategy for player 1 is,
• Never play Ace of Diamonds (dominated strategy)
• Play Ace of Clubs with a probability 0.6
• Play Two Diamonds with a probability 0.4

Value of the game = 0.2

Biased for Player 1’s favor. Therefore, this is an unfair game.

33