Game Theory

Theory of Games
Preview of lecture
✓ Overview of game theory
✓ Classic examples of game theory
✓ History of game theory
✓ Classification of game theory
✓ Key elements in game theory
✓ Mathematical concept in Game Theory
✓ Procedure to solve 2x2 game without saddle point
✓ Algebraic Method for solving games without saddle point
Overview of Game Theory
Game theory is an approach to modelling behaviour in situations where the
outcome of your decisions depends on the decisions of others.
Game theory is the study of strategic, interactive decision making among rational
individuals or organizations.
Game theory is a branch of applied mathematics that provides tools for analyzing
situations in which parties ( called players) make decisions that are interdependent.
This interdependence causes each player to consider the other player’s possible
decisions( or strategies) in formulating strategy.
In addition, a player need not be an individual; it may be a nation, a corporation, or
a team comprising many people with shared interests.
A solution to a game describes the optimal decisions of the players, who may have
similar, opposed, or mixed interests, and the outcomes that may result from these
decisions.
Game theory is applied for determining different strategies in the business world.
It offers valuable tools for solving strategy problems.
Classic examples of game theory
(i) The Prisoner’s Dilemma; where two suspects are in police custody as
accomplices for the same crime, but there is not enough evidence for a felony
conviction. They are held and interrogated separately. If one prisoner testifies
against the other while the other stays silent, the testifying prisoner goes free and
the silent prisoner is convicted and serves ten years. If both prisoners stay silent,
both are convicted on a minor charge and serve six years. If both prisoners testify
against each other, each serves five years. How should the prisoners act? . The
answer is that both prisoners should testify against the other, an outcome that is
known as a Nash equilibrium. [i.e The players in each game depend on each other’s
rationality to make the optimal choices in every situation, thereby maximizing their
own utility]
(ii) Conflict of sales; Let us assume that the client had a drug with
dominant market share in a therapeutic area that is competitive, yet
has few players. One of their competitors was behaving aggressively
from a pricing perspective (e.g., continually matching and beating
the client’s price, even though the competitor gained little or no
market share from such actions). The competitor was in the process
of running a clinical trial to improve their product’s label. The client
wished to know how the competitor might behave depending on
the client’s next price move and the outcome of the clinical trial.
The conclusion of the exercise was that engaging in a price war
would not benefit any of the client or competitors. Therefore,
keeping the price high and trading “market share for peace” would
be the most profitable strategy.
(ii)Advertising War: Coke vs. Pepsi :- Without any advertising, each company earns

• $5b/year from Cola consumers. Each company can choose to spend $2b/year on advertising. Advertising does not
increase total sales for Cola, but if one company advertises while the other does not, it captures $3b from the
competitor

What will the Cola companies do? Is there a better feasible outcome

(iii)In your everyday life: Everything is a game, poker, chess, soccer, driving, dating, stock market advertising, setting
prices, entering new markets, building a reputation bargaining, partnerships, job market search and screening
designing contracts, auctions, insurance, environmental regulations international relations, trade agreements,
electoral campaigns, Most modern economic research includes game theoretical elements.

(iv)Game theory has been used to analyze parlour games, but its applications are much broader.
 History of game theory

• The individual closely associated with the creation of the theory of games is John von Neumann, one of the greatest
mathematicians of this century. Although others proceeded him in formulating a theory of games - notably Emile Borel - it was
von Neumann who published in 1928 the paper that laid the foundation for the theory of two-person zero-sum games.

• The theory of Games was born in 1944 with the publication of Theory of Games and Economic Behaviour by Hungarian-
born American mathematician John von Neumann and his Princeton University colleague Oskar Morgenstern, a German-born
American economist. In their book, . They observed that economics is much like a game, wherein players anticipate each
other’s moves, and therefore requires a new kind of mathematics, which they called game theory. Their choice of title was a
little unfortunate, since it quickly got shortened to “Game Theory,”
• Nobel Laureate and a Father of Game Theory, Lloyd S. Shapley(92), who shared the 2012 Nobel Memorial Prize in
Economic Science for work on game theory that has been used to study subjects as diverse as matching couples and allocating
costs
Classification of game theory

• It broadly classified into three main sub-categories of study

• (1) Classical game theory
• It focuses on optimal play in situations where one or more people must make a
decision and the impact of that decision and the decisions of those involved is known.
• Decisions may be made by use of a randomizing device like piping a coin .
• It focuses on questions like, What is my best decision in a given economic
scenario, where a reward function provides a way for me to understand how my
decision will impact my result.
• Examples:
• Poker, Strategic military decision making, Negotiations.
(2)Combinatorial game theory
It focuses on optimal play in two-player games in which each player takes turns changing in pre-defined
ways. In other word, combinatorial game theory does not consider games with chance (no randomness).
Generally two player strategic games played on boards. Moves change the structure of a game board.
Examples:
Chess, Checkers, Go.

(3)Dynamic game theory:

It focuses on the analysis of games in which players must make decisions over time and in which those
decisions will affect the outcome at the next moment in time. It often relies on differential equations to
model the behaviour of players over time.
It can help optimize the behaviour of unmanned vehicles or it can help you capture your baby sister
who has escaped from her playpen.
In general games with time, Games with motion or a dynamic component.
Examples:
Optimal play in a dog fight, Chasing your brother across a room.
 Key elements in game theory

Player: who is interacting

Strategies: what are the options of each player? In what order do players act?
How do strategies translate into outcomes? What are players’ preferences over
Payoffs:
possible outcomes?

Information/Beliefs: What do players know/believe about the situation and about one
another? What actions do they observe before making decisions?
Rationality: How do players think?
• Mathematical concept in Game Theory
• The following the prerequisite required for game theory

• Sum of gains and loss

• If in a game sum of the gains to one player is exactly equal to the sum of losses to another
player, so that sum of the gains and losses equal zero, the corresponding game is said to be zero
sum game.

• Types of games

• Games can be classified according to certain significant features, the most obvious of which
is the number of players. Thus, a game can be designated as being a one-person, two-person, or n-
person (with n greater than two) game, games in each category having their own distinctive
features.
• One-person games

• One-person games are also known as games against nature. With no opponents, the player only needs to list
available options and then choose the optimal outcome. When chance is involved the game might seem to be more
complicated, but in principle the decision is still relatively simple.

• For example, a person deciding whether to carry an umbrella. While this person may make the wrong decision,
there does not exist a conscious opponent. That is, nature is presumed to be completely indifferent to the player’s
decision, and the person can base his decision on simple probabilities. One-person games hold little interest for
game theorists.

• 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 zero- sum games because one player wins whatever the other player
loses. In short it is denoted by TPZS game.
• For example, All parlour 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 parlour games 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.

• Positive-sum game

• In game theory, a term positive sum refers to situations in which the total of gains and losses is greater than zero.

• A positive sum occurs when resources are somehow increased and an approach is formulated such that the desires
and needs of all concerned are satisfied.
• Perfect games

• Games of perfect information in which each player knows everything about the game at
all times. It is called perfect games

• For example, chess in which each player knows everything about the game at all times. In
chess exactly one of three outcomes must occur if the players make optimal choices: (i) White
wins (has a strategy that wins against any strategy of black),
• (ii) Black wins (iii) White and black draw.

• Imperfect games

• Games of imperfect information in which each player do not knows everything about the
game at all times. It is also called imperfect games

• For example, Poker in which players do not know all of their opponents’ cards.
Finite games

Games in which each player has a finite number of options, the number of players is finite, and the game cannot go on
indefinitely.

For example, chess, checkers, poker, and most parlour games are finite.

Cooperative games

In game theory, a cooperative game (or coalitional game) is a game with competition between groups of players ("coalitions") due to
the possibility of external enforcement of cooperative behaviour (e.g. through contract law).

Non cooperative games

Those are opposed to cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-
enforcing (e.g. through credible threats).

Pay off
The outcome of the game resulting from a particular decision (or strategy) is called pay off . It is assumed that pay off is also
known to the player in advance.
It is expressed in times of numerical values such as money, percent of market share or utility.
• Pay off matrix
• The pay offs in terms of gains or losses, when players select their
particular strategies, can be represented in the form of matrix is called pay off
matrix.
• Let A , A ,....A
1 2 m are possible strategies for player A Let B1,B2,....Bn
are possible strategies for player B.
• The total number of possible outcomes are m x n and it is assumed that
each player knows not only his own list of possible course of action but also his
opponent.
• For our convenience, we assume that player A always a gainer whereas
player B a looser.
 Let aij=pay off which player A gain from player B, if player A choose strategy i and player B chooses strategy J.

Pay of matrix player A is represented in the form of table

Player B's strategies

Player A's strategies B1 B2 .... Bn
A1 a11 a12 .... a1n
A2 a21 a22 .... a2n
.... ....
Am am1 am2 .... amn

Remarks
For the zero sum games, the gain of one player is equal to the loss of other and vice versa. i.e one player pay off table would
contain the same amounts in pay off table of other player with the sign changed. Therefore it is enough to construct pay of table
for one player.

Strategy
The strategy for a player is the list of all possible actions (moves or course of action) that he will take for every pay-off
(outcome) that might arise. It is assumed that all course of possible actions are known in advance to the player.
• Types of Strategy
• Usually player in game theory uses two types of strategy namely pure strategy
and mixed strategy .

• (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
(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 p +p +.....+p =1 and p >=0 for all j=1,2,...n.
1 2 n j

• Remark:
(i) If a player randomly chooses a pure strategy, we say that the player is using a "mixed strategy." In a
pure strategy a player chooses an action for sure, whereas in a mixed strategy, he chooses a probability
distribution over the set of actions available to him.
(ii)If a particular p =1 and all others are zero, then the player is said to select pure strategy J.
j
• Optimal strategy
• The particular strategy (or complete plan) by which a player optimizes his gains or losses without knowing the
competitor's strategies is called optimal strategy.

• Value of the game

• The expected outcome when players follow their optimal strategy is called the value of the game, It is denoted by V
• Basic assumptions of game
(i)Each player has available to him a finite number of possible strategies. The list may not be same for
each player.
(ii)Player A attempts to maximize gains and player B minimize losses.
(iii)The decisions of both players are made individually prior to the play with no communication
between them.

(iv)The decisions are made simultaneously and also announced simultaneously so that neither player
has an advantage resulting from direct knowledge of the other player 's decision.
(v)Both the players know not only possible pay offs to themselves but also other.
• Minmax-Maxmin principle

• The selection of an optimal strategy by each player without the knowledge of the competitor's strategy is the basic problem of
playing games. The objective of the study is to know how these players select their respective strategy so that they may optimize their pay
off. Such a decision making criterion is referred to as the minmax -maxmin principle

• Remarks

• Minmax-Maxmin principle given the best possible selection of strategy for both players in pure strategy problem.

• Saddle point

• If the minmax value = maxmin value, then the game is said to have a saddle (equilibrium) point
• Remarks
(i) The corresponding strategy at saddle point are called optimum strategy.
(ii) The amount of pay off at an saddle point is known as the value of the game.
(iii)A game may have more than one saddle point.
(iv)There are game without saddle point.

(v) Its name derives from its being the minimum of a row that is also the maximum of a column in a payoff matrix—to be illustrated
shortly—which corresponds to the shape of a saddle.
• Procedure to determine saddle point
• Step:-01
• Select the minimum (lowest ) element in each row of the pay off 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.
• Games without saddle point
• Suppose if there is no pure strategy solution for a game, then there is no saddle point exist. In these
situations, to solve the game both the player must determine the optimal mixtures of strategies to find saddle
point.

• The optimum strategy mixture of each player may be determined by assigning each strategy it probility of
being chosen. The optimal strategy so determined is called mixed strategy.

• Fair Game
• If the value of the game is zero (i.e. there is no loss or gain for any player), the game is called fair game. The
simplest type of game is one where the best strategies for both players are pure strategies. This is the case if and
only if, the pay-off matrix
• contains a saddle point.

• Strictly determinable
• A game is said to be strictly determinable if the maxmin and minmax values of the game are equal and both equal the value of the
game.
 Example:-01 (Games with sadle point)
Find the optimal plan for both the player

Player-B
I II III IV
Player-A
I -2 0 0 5

II 4 2 1 3

III -4 -3 0 -2

IV 5 3 -4 2

Solution:-
We use maxmin-minmax principle for solving the game.

Player-B Row Minimum

I II III IV
Player-A
I -2 0 0 5 -2

II 4 2 3
1 1

III -2
-4 -3 0 -4

5 3 -4 2 -4
IV

Column Maximum 5 3 5
1
• 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 II, which yields the maximum payoff of 1 Player B will choose
strategy III.

• The value of game is 1, which indicates that player A will gain 1 unit and player B will sacrifice 1
unit.
• Since the maximin value = the minimax value =1, therefore the game has saddle point and the game
is not fair game. (since value of the game is non zero)
• Also maxmin=minimax=value of game, therefore the game is strictly determinable.
• It is a pure strategy game and the saddle point is (A-II, B-III)
• The optimal strategies for both players given by pure strategy , Player A must select strategy II and
playerB must select strategy III.
• Select minimum from the column maximum values. ie. Minimax = -2,
(marked as circle )

• Select maximum from the row minimum values. ie. Maximin = -2, ( 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)
• 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
I and playerB must select strategy III
 Algebraic Method for solving games without saddle point
Let p1,p2,.....pm be the probability that the player A choose his strategy A1, A2,...Am respectively. where
p1+p2+....+pm=1
Let q1,q2,.....qn be the probability that the player B choose his strategy B1, B2,...Bn respectively. where
q1+q2+.....+qn =1

Player A's Player B's strategies Probability

strategies
B1 B2 .... Bn

A1 a11 a12 .... a1n p1

A2 a21 a22 .... a2n p2

.... … .… .... … …

Am am1 am2 .... amn pm

Probability q1 q2 qn
Let V be the value of the game.
To find SA
The expected gain to player A when player B selects strategies B1,B2,...Bn respectively Since player A is gainer player and he
expects at least V, therefore we have a11p1+a21p2+......+am1pm>=V
a12p1+a22p2+....+am2pm>=V
......
a1np1+a2np2+....+amnpm>=V
To find the values of pi's , above inequalities are considered as equations and are then solved for given unknowns.
To find SB
The expected loss to player B when player A selects strategies A1,A2,...am respectively Since player B is loser player , therefore we
have
a11q1+a12q2+......+a1nqn<=V
a21q1+a22q2+....+a2nqn<=V
......
an1q1+an2q2+....+anmqn<=V
To find the values of qi's , above inequalities are considered as equations and are then solved for given unknowns.
By substituting the values of ai 's and qi's in any one of the above equation give the value of the game.
 Two – Person Zero Sum Game
The 2-person 0-sum game is a basic model in
game theory. There are two players, each with an
associated set of strategies. While one player aims
to maximize her payoff, the other player attempts
to take an action to minimize this payoff. In fact, the
gain of a player is the loss of another.
 Key elements of a 2-person game:

Each 2-person game consists of

➢ 2 players;
➢ Strategies available to each player;
➢ Payoffs for each player;
Oh, great! I
• the payoff is the amount of benefit or loss that a
love games.
player derives if a particular outcome happens.
• the payoff of each player depends on her
choice, and depends on the choice of the
other player.

39
 2-person 0-sum Games:

In 2-person 0-sum games the payoff function f can be represented

as follows.

If Player 1 chooses strategy s1 and Player 2 selects strategy s2, then

Player 1 will get f(s1,s2) and Player 2 will get -f (s1,s2). We will
refer to f(s1,s2) as the value of the game. Player 1 aims to
maximize f(s1,s2), while Player 2 attempts to minimize this value.

40
 2-person 0-sum games
Here is another
example of a
game.

Coin Matching Problem (Even-Odd Game)

➢ There are two players: Player 1 (the row player)
and Player 2 (the column player);
➢ Each player simultaneously shows a coin.
➢ If both coins are showing are heads, then Player
1 wins $2 (paid by Player 2). If both coins are
tails, then Player 1 wins $4. If the coins do not
match, then Player 1 loses $3.

41
 Describing a game
Is each game completely
described bythe payoff
matrix?

That’sright! Here is a more formal

description.

Normal-form isa simple wayto describe a 2-person 0-sumgame byusing a so-

called payoff matrix:
➢ Each row (column) of the matrix corresponds to a strategy available to
Player 1 (Player 2). In thiscase,we refer to Player 1 as the row player (or
simply R) and Player 2 asthe column player (or simply C).
➢ The i-j element of the matrix gives the payoff to the row playerif she
chooses i-th rowand the columnplayer selectsj-th column.Thematrix is
called a payoff matrix.
42
 A payoff matrix

Tom
Here is a payoff matrix
1 2 for the Even-Odd game.

1 2 -3
Chaty
2 -3 4
It is a good way
to view all the
basic elements
of a game.

43
 A payoff matrix
Here is one more example. Each player has three
strategies:
Player C
•Player R chooses a row: either row 1, or
row 2, or row 3;
-2 1 2 •Player C chooses a column: either column
Playe
2 -1 0 1, or column 2, or column 3.
r R We will later refer to these as pure strategies,
1 0 -2 for reasons that will become apparent when we
describe mixed strategies

This matrix is the payoff matrix for Player R, and Player C gets
the negative).

How much do R and C get if R chooses 1 and C selects 2?

How much do R and C get if R chooses 3 and C selects 3?

44
 A payoff matrix
Here is one more example. Each player has three
strategies:
Player C
•Player R chooses a row: either row 1, or
row 2, or row 3;
-2 1 2 •Player C chooses a column: either column
Playe
2 -1 0 1, or column 2, or column 3.
r R We will later refer to these as pure strategies,
1 0 -2 for reasons that will become apparent when we
describe mixed strategies

This matrix is the payoff matrix for Player R, and Player C gets
the negative). For example,
• If R chooses 1 and C selects 2, then R gets +1 and C get -1
• If R chooses 3 and C selects 3, then R gets -2 and C get +2.

45
 A guaranteed payoff for the Row Player
Who goes In games, two playersmake decision at the same
first? time.
Player C

-2 1 2
Player
R
2 -1 0
1 0 -2
But for the purpose of thisexample,suppose that Player R were forced to announce a
row before Player C makes her decision. If Player R announces
• Row 1, then the player’sC best response is Column1 and R will get -2;
• Row 2, then the player’sC best response is Column2 and R will get -1;
• Row 3, then the player’sC best response isColumn3 and R will get -2;
Player R wishes to maximize her payoff and her best pure choice is to announceRow 2.
In fact, she takes amaximin strategy to maximize her minimum payoff. This gurantees a
payoff of at least -1 to Player R, regardlessof the player’sC strategy.
46
 A guaranteed maximum payoff to the Row Player

If Player C announces
• Column1, then R’s best responseis Row2 and R gets 2.
But what if the
column player • Column2, then R’s best responseis Row1 and R gets 1.
announced her • Column3, then R’s best responseis Row1 and R gets 2.
strategy first? Player C wantsto minimize the payoff of Player R, and thusher
best pure strategy (if she went first) is to announce Column2. This
strategy is called a minimaxpure strategy. It minimizes the
maximum payofffrom Player C. This showsthat the value of the
game for the Row Player can alwaysbe limited to at most 1.

Player C

-2 1 2
Player R 2 -1 0
1 0 -2
47
 If one player chooses prior to the other.

Good point. And it implies an important mathematical result.

If Player R chooses a strategy before Player C, R can guarantee
It seems that a payoff of at least
goingfirst is
always a If Player C chooses a stategy before Player R, then C can
disadvantage. guarentee that R receives at most

This implies that

48
 Saddle-point

Yes! It may be the case that the lower bound and the upper
Can the bound on the value of the game coincide. In this case, there
equalityhold in are strategies such that
some games?

The pair is called a saddle point of the game. It is

also called a pure Nash equilibrium since no player has an
intensive to change her strategy.

Player C
In this example, the
-1 -2 -1 pure Nash equilibrium
Player occurswhen Player R
R 2 2 1 chooses2 and C selects
-1 -1 0 3.

49
 Mixed strategies What you said is a mixed (also called randomized)
strategy since R assigns a probability to eachrow and
selects arow accordingly.This plays akey role in game
theory. In this case,R might do pretty well evenif she
Since R and C go at the same
(stupidly) announced her strategy in advance,so long as
time, it would seem pretty
C couldn’t see the result of the coin flip. Let’s see what is
dumb for R to announcein
she Player’s C best response. If C choosesColumn
advance what she will choose.
• 1, then R gets -2 with probability 0.5 or 2 with
And she needs to mix it up.
probability 0.5; So R’s expected payoffis 0.
What would happen if she used
• 2, then R gets 1 with probability 0.5 or 1 with
a coin to decide whether to
probability 0.5; So R’s expected payoffis 0.
select Row 1 or 2?
• 3, then R gets 0 with probability 0.5 or 2 with
probability 0.5; So R’s expected payoffis 1.
Since C aims to minimize the player’s R payoff,shewill
chooseColumn1 or Column 2.Thus, R canguarantee an
expected payoffof at least 0, which is much better than
Prob Player Cshe could guarantee before.

0.5 -2 1 2
Player
R
0.5 2 -1 0
0 1 0 -2
50
 Optimal
Yes. Here is the wayto model the problemof finding her best strategy.
mixed For each row i, let the decisionvariablexi be the probabilityof selecting
strategies row i. If C chooses
• Column 1, then R’sexpected value is P1:=(-2)x1+2x2+1x3=-
2x1+2x2+x3;
Great!
• Column 2, then R’sexpected value is
Can she P2:= 1x1+(-1)x2+2(0)x3=x1-x2;
do even • Column 3, then R’sexpected value is
better? P3:= 2x1+(0)x2+(-2)x3=2x1-2x3.
Thus Player R’s expected value is at least
min{P1, P2, P3}.
Player R will assign the probabilities x1,x2 and x3 in such awayto
maximize min{P1, P2, P3} in order to determine her best mixed
strategy.
Prob Player C

x1 -2 1 2
Player
R
x2 2 -1 0
x3 1 0 -2
51
 Yes it is. Here is the optimization problem:
max min{P1,P2,P3}
I see that
P1=-2x1+2x2+x 3,
computing the best
P2= x1-x2,
mixed strategy for
P3=x2+2x3,
Player R is an
x1+x2+x3=1,
optimization x1,x2,x3≥0.
problem. Is it a
Notice that probabilities must sum to 1, since PlayerR is obligated to
linear program?
choosea row. In addition, probabilities can neverbe negative! These are
our constraints.
Introduce a new variable z to be min={P1,P2,P3}.
Then, we canexpress the above problem as a linear program.
max z
z≤-2x1+2x2+x 3,
z≤x1-x2,
z≤x2+2x3,
x1+x 2+x 3=1,
x1,x2,x3 ≥0.

The optimal solution is x1= 7/18, x2 =5/18,x3 =1/3 with

optimal value Z= 1 /9 .
So,with a mixed strategy R guaranteesobtainingat least 1/9.
52
 How canwe obtain an upper As we have already observed an upper
bound for R when she is boundfor R (or equivalentlya lower
permitted to choose a mixed boundfor C) can be computed if Player R
strategy? is in a positionto take her strategy after
hearingthe Player’sC strategy.
Player C

Prob y1 y2 y3

-2 1 2
Player
R 2 -1 0
1 0 -2
Let yj be the probabilityof selectingcolumn j, for j=1,2,3. If R chooses
• Row 1, then R’s expected payoffis P1:= (-2)y1+y2+(2)y3=-2y1+y2+2y3;
• Row 2, then R’s expected payoffis P2:= 2y1+(-1)y2+(0)y3= 2y1-y2 ;
• Row 3, then R’s expected payoffis P3:= (1)y1+(0)y2+(-2)y3=y1-2y3.
Player R wantsto maximize her expected payoff, so Player R max expected payoff is
max{P1, P2, P3}.
Therefore, Player C must assign the probabilities y1,y2 and y3 in such awayto minimize
max{P1, P2, P3} in order to determine her best mixed strategy.
53
 Thanks! I think we can write a linear
problem to determine an optimal
mixed strategy for Player C in the same
manner.

Exactly! Here is the linear program:

min w
w ≥-2y1+y2+ 2y3;
w ≥2y1-y2 ;
w ≥y1-2y3,
y1+y2+y3 = 1,
y1,y2,y3 ≥0.

The optimal solution is y1= 1/ 3, y2= 5/ 9, y3= 1/ 9 with

optimal value w=1/ 9.
So, with thisrandomstrategy R gets only1 /9.

54
 Wait a moment! I see that the payofffor
player R is the same, whether Player R
announces her strategy first or Player C. Is
that a coincidence?

It’s no coincidencethat the optimal average payoff to the game is 1/9,

assuming that both players playoptimally,and it doesnot matter who goes
first. This result holdsfor 2-person 0-sumgames in general:
For 2-person 0-sum games, the maximum payoff that R can guarantee
by choosing a random strategy is the minimum payoff to R that Ccan
guarantee by choosinga randomstrategy.

55
 2-person 0-sum games in general
• Let x denote a randomstrategyfor R, with value z(x) and let y denote a random
strategy for C with value w(y). Then
z(x)  w(y) for all x, y.
• The optimum x* can be obtained bysolving an LP. Socan the optimum y*. In addition,
z(x*) = w(y*).
• In other words, the maximum payoff that R can guarantee bychoosing a random
strategy is the minimum payoffto R that C can guarantee bychoosing a mixed strategy.

• Notice that z(x*) is an upper boundon the payoff of Player R and w(y*) is a lower
boundon the payoffof Player C. Player R wishes to maximize her payoff, while Player C
attemptsto minimize her payoff. Since z(x*) = w(y*), neither playercan benefit by a
unilateralchange in strategy,even when eachplayer is aware of the other player’s
strategy.In this case,the pair (x*,y*) is calledamixed Nash equilibrium.

56
 A 2-dimensional view of game theory
Notice that
In the class, I heard we • if R goes first and decides on a strategy
can easily to solve 2- of choosing row 1 with probability p
person 0-sum game and row 2 with probability 1-p, then
graphically theory
when there are two the strategy for C is easily determined.
strategies per player. • so R can determine the payoff as a
How does it work?
function of p, and then choose p to
maximize the payoff.
Followme in the next slides to illustrate this
method with the Even-or-Odd game.

Thanks! Learningfrom examples is my

favorite way of learning. It is way
more fun than learning from mistakes.

57
 I want to minimize the payoff.What We graph the payoff as a function of
would my optimal strategy be? the probabilityp given that I select
Row 1.
I’ll choose column 1 with
probability p and column 2
with probability 1-p.

4 4
3 3
2 2
Payoff for Row
1 1
payoff 1.
0 0
Tom
1 2 -1 -1
-2 -2
Cathy
1 -2 3
-3 -3
2 3 -4 -4 -4
0 probability of selecting no. 1 by Tom 1
58
 We graph the payoff for Row 2 asp
goes from 0 to 1.

Here is the payoff if you choose

Row 2.

4 4
3 3
2 2
Payoff for Row
payoff 1 2. 1
0 0
Tom
1 2 -1 -1
-2 -2
1 -2 3
Cathy -3 -3
2 3 -4 -4 -4
0 probability of selecting no. 1 by Tom 1
59
 I want to maximize the payoff to me. So here is my
So, what strategy as a function of p:
column • if p<7 /12, my best response is Row 1;
should I • If p>7 /12, my best response will be Row 2;
pick? Since you want to minimize my payoff, your best strategy
is to set p=7/12. This guarantees that you can limit my
expected winnings to at most 1 /12.

4 4
3 3
2 2

payoff 1 1
0 0
Tom
7/12
1 2 -1 -1
-2 -2
1 -2 3
Cathy -3 -3
2 3 -4 -4 -4
0 probability of selecting no. 1 by Tom 1
60
 It now my turn to choose an optimal
strategy. I’ll let q denote the probability
But what’s the best that
that I select Row 1. I need to figure out
you cando?
the best choice of q.
Here is my payoff if you select Column 1.

4 4
3 3
2 2
Payoff for Column 1.
payoff 1 1
0 0
Tom
1 2 -1 -1
-2 -2
1 -2 3
Cathy -3 -3
2 3 -4 -4 -4
0 q = Prob(Cathy selects Row 1) 1
61
 Here is my payoff if you call out 2.

I see!You take a similar Remember that your strategy is minimax,

approach. but mine is maximin.

4 4
3 3
2 2
Payoff for Column 2.
payoff 1 1
0 0
Tom
1 2 -1 -1
-2 -2
1 -2 3
Cathy -3 -3
2 3 -4 -4 -4
0 probability of selecting no. 1 by Cathy 1
62
 I can tell you now what is your best strategy:
I want to minimize the payoff. So here is my strategy as a
function of q:
• if q<7/12, my best response is Column 1;
• If q>7/12, my best response will be Column 2;
Since you want to maximize the payoff, the best strategy is to
set q=7/12. This guarantees you can get at least 1/12.

4 4
3 Payoff for Column 1. 3
Payoff for Column 2.
2 2
payoff 1 1
0 0
Tom 7/12
-1 -1
1 2 -2 -2

Cathy
1 -2 3 -3 -3
-4 -4
63
2 3 -4 0 probability of selecting no. 1 by Cathy 1
 Did I do a good job?
Tom, you always do a good job.

If we were playing for

real, I wouldn’t like this
game becauseI would
lose on average.

That’strue. If I choose my strategy optimality, I can

guarantee aminimumpayoff 1/12.The best you can do
is to choose your optimumstrategy as well and
guarantee that I get no more than 1/12 on average. If
we had an equalchance of winning, it wouldhave been
called a fair game. But this game wasn’t fair.
64
 Constant Sum and Non-Constant Sum Games
• In a constant sum game, the sum of all players' payoffs is the same for any
outcome. Hence, a gain for one participant is always at the expense of
another, such as in most sporting events. Given the conflicting interests,
the equilibrium of such games is often in mixed strategies. Since payoffs
can always be normalized, constant sum games may be represented as
(and are equivalent to) zero sum game in which the sum of all players'
payoffs is always zero.

• In game theory, nonzero-sum games (more precisely known as

nonconstant-sum games) include many examples in which the sum of the
payoffs to the players varies according to the strategies chosen. These
cases are often more relevant to issues in social science and public policy
than are zero-sum (and more generally constant-sum) games.
Nash Equilibrium