Chapter 14

Game Theory
Introduction
• Life is full of conflict and competition.

• Numerous examples involving adversaries in conflict include parlor games, military

battles, political campaigns, advertising and marketing campaigns by competing business
firms, and so forth.

• A basic feature in many of these situations is that the final outcome depends primarily
upon the combination of strategies selected by the adversaries.

• Game theory is a mathematical theory that deals with the general features of competitive
situations like these in a formal, abstract way. It places particular emphasis on the
decision-making processes of the adversaries.

9/19/2023 1405-324 (IE 411): Operations Research II 2

Introduction
• The focus in this chapter is on the simplest case, called two-person,
zero-sum games.

• As the name implies, these games involve only two adversaries or

players (who may be armies, teams, firms, and so on).

• They are called zero-sum games because one player wins whatever the
other one loses, so that the sum of their net winnings is zero.

9/19/2023 1405-324 (IE 411): Operations Research II 3

The Formulation Of Two-person, Zero-sum Games

Consider the game called odds and evens consists simply of each player
simultaneously showing either one finger or two fingers. If the number
of fingers matches, so that the total number for both players is even,
then the player taking evens (say, player 1) wins the bet (say, $1) from
the player taking odds (player 2). If the number does not match, player 1
pays $1 to player 2. Thus, each player has two strategies: to show either
one finger or two fingers.

9/19/2023 1405-324 (IE 411): Operations Research II 4

 Payoff Table For The Odds And Evens
Game
• In general, a two-person game is
characterized by:
1. The strategies of player 1.
2. The strategies of player 2.
3. The payoff table.

• Before the game begins, each player knows the strategies he or she has available, the ones the
opponent has available, and the payoff table.

• The actual play of the game consists of each player simultaneously choosing a strategy without
knowing the opponent’s choice.
9/19/2023 1405-324 (IE 411): Operations Research II 5
The Formulation Of Two-person, Zero-sum Games

• A strategy is a predetermined rule that specifies completely how one

intends to respond to each possible circumstance at each stage of the game.

• The payoff table shows the gain (positive or negative) for player 1 that
would result from each combination of strategies for the two players.

• It is given only for player 1 because the table for player 2 is just the
negative of this one, due to the zero-sum nature of the game.

9/19/2023 1405-324 (IE 411): Operations Research II 6

The Formulation Of Two-person, Zero-sum Games

• A primary objective of game theory is the development of rational criteria

for selecting a strategy. Two key assumptions are made:
1. Both players are rational.
2. Both players choose their strategies solely to promote their own welfare (no
compassion for the opponent).

• Game theory contrasts with decision analysis, where the assumption is that
the decision maker is playing a game with a passive opponent—nature—
which chooses its strategies in some random fashion.

9/19/2023 1405-324 (IE 411): Operations Research II 7

Solving Simple Games—A Prototype Example
• Two politicians are running against each other for the U.S. Senate. Campaign plans must now be made
for the final two days, which are expected to be crucial because of the closeness of the race. Therefore,
both politicians want to spend these days campaigning in two key cities, Bigtown and Megalopolis.

• To avoid wasting campaign time, they plan to travel at night and spend either one full day in each city or
two full days in just one of the cities. However, since the necessary arrangements must be made in
advance, neither politician will learn his (or her) opponent’s campaign schedule until after he has
finalized his own.

• Therefore, each politician has asked his campaign manager in each of these cities to assess what the
impact would be (in terms of votes won or lost) from the various possible combinations of days spent
there by himself and by his opponent. He then wishes to use this information to choose his best strategy
on how to use these two days.
9/19/2023 1405-324 (IE 411): Operations Research II 8
Formulation as a Two-Person, Zero-Sum Game
• To formulate this problem as a two-person, zero-sum game, we must identify the two
players, the strategies for each player, and the payoff table.
• Obviously the two players are the politicians.

• Each player has the following three strategies:

• Strategy 1 = spend one day in each city.
• Strategy 2 = spend both days in Bigtown.
• Strategy 3 = spend both days in Megalopolis.

• The strategies would be more complicated in a different situation where each politician
learns where his opponent will spend the first day before he finalizes his own plans for his
second day.

9/19/2023 1405-324 (IE 411): Operations Research II 9

Formulation as a Two-Person, Zero-Sum Game
• Each entry in the payoff table for player 1 represents the utility to player 1 (or the
negative utility to player 2) of the outcome resulting from the corresponding
strategies used by the two players.

• From the politician’s viewpoint, the objective is to win votes, and each additional
vote (before he learns the outcome of the election) is of equal value to him.

• Therefore, the appropriate entries for the payoff table for politician 1 are the total
net votes won from the opponent (i.e., the sum of the net vote changes in the two
cities) resulting from these two days of campaigning.

9/19/2023 1405-324 (IE 411): Operations Research II 10

Form of the payoff table for politician 1 for the
political campaign problem
• Using units of 1,000 votes, this formulation is summarized in the Table

• Game theory assumes that both players are using the same formulation (including the
same payoffs for player 1) for choosing their strategies.

• However, this payoff table would not be appropriate if additional information were
available to the politicians.

• Using the form given in the Table, we give three alternative sets of data for the
payoff table to illustrate how to solve three different kinds of games.
9/19/2023 1405-324 (IE 411): Operations Research II 11
 Payoff table for player 1 for variation 1 of the political
campaign problem (dominated strategies)

• A strategy is dominated by a second strategy if the second strategy is always at

least as good (and sometimes better) regardless of what the opponent does. A
dominated strategy can be eliminated immediately from further consideration.
Player 2 Player 2
Strategy All the data in first row better than the data in row three Strategy Strategy 3
1 2 3 1 2 3
for player 1
1 1 2 4 1 1 2 4
is dominated
Player 1 2 1 0 5 Player 1 2 1 0 5
by strategy 1
3 0 1 -1 Thus, eliminating strategy 3 3 0 1 -1

Strategy Strategy
As a result, both players should select their strategy 1. Player 1 then will receive a 1 ---- 3 2 ---- 3
payoff of 1 from player 2 (that is, politician 1 will gain 1,000 votes from politician 2). 1
1
<
<
4
5
2
0
<
<
4
5

Player 2 Player 2 Player 2 Strategy 3

Strategy Strategy 2 Strategy Strategy 2 Strategy
1 2 3 1 2 3 1 2 3 for player 2
for player 2 for player 1
1 1 2 4 1 1 2 4 1 1 2 4 is dominated
is dominated is dominated
Player 1 2 1 0 5 Player 1 2 1 0 5 Player 1 2 1 0 5 by strategy
by strategy 1 by strategy 1
3 0 1 -1 3 0 1 -1 3 0 1 -1 1&2

9/19/2023 1405-324 (IE 411): Operations Research II 12

Payoff table for player 1 for variation 1 of the political
campaign problem (dominated strategies)
Player 2
Strategy
1 2 3
1 1 2 4 1. Strategy 3 of player 1 is dominated by strategy 1.
Player 1 2 1 0 5
3 0 1 -1

Player 2
Strategy
1 2 3 2. Strategy 3 of player 2 is dominated by strategies 1 and 2.
1 1 2 4
Player 1
2 1 0 5

Player 2
Strategy
1 2
1 1 2 3. Strategy 2 of player 1 is dominated by strategy 1.
Player 1
2 1 0

Player 2
Strategy
1 2 4. Strategies 2 of player 2 is dominated by strategy 1.
Player 1 1 1 2

Player 2
Strategy
1
5. Therefore, the optimal strategy is strategy 1 for each player and the resulting
Player 1 1 1 payoff is 1 (1000 votes) to player 1.

9/19/2023 1405-324 (IE 411): Operations Research II 13

 Payoff table for player 1 for Variation 2 of the
Example (minimax criterion)
• Minimax criterion is a standard criterion proposed by game theory for selecting a
strategy (a way as to minimize a player maximum losses whenever the resulting choice of
strategy cannot be exploited by the opponent to then improve his position).

• This criterion says to select a strategy that would be best even if the selection were being
announced to the opponent before the opponent chooses a strategy.

Minimax – The smallest of the maximim

Maximin – The largest of the minimum
payoff in each column of a payoff matrix.
payoff in each row of a payoff matrix.

9/19/2023 1405-324 (IE 411): Operations Research II 14

Payoff table for player 1 for Variation 2 of the
Example (minimax criterion)
• Notice the interesting fact that the same entry in this payoff table yields
both the maximin and minimax values.
• The reason is that this entry is both the minimum in its row and the
maximum of its column. The position of any such entry is called a saddle
point (the payoff that results when the maximin and the minimax are the
same, which is the value of the game).
• The saddle point has the shape of a saddle-shaped surface.
• The middle point on a horse saddle is simultaneously the lowest point along the spine
of the horse and the highest point between the rider’s legs.

9/19/2023 1405-324 (IE 411): Operations Research II 15

Payoff table for player 1 for Variation 2 of the
Example (minimax criterion)

• Equilibrium solution or stable solution results from a situation where

neither player has any motive to consider changing strategies, either to
take advantage of his opponent or to prevent the opponent from taking
advantage of him.

• In this case, players 1 and 2 should exclusively use their maximin and
minimax strategies, respectively.

9/19/2023 1405-324 (IE 411): Operations Research II 16

Payoff table for player 1 for Variation 3 of the
Example (minimax criterion)

• The result shows that there is no saddle point.

• Thus, the suggested solution (player 1 to play strategy 1 and player 2 to play strategy 3) is an
unstable solution.

• The key fact seems to be that whenever one player’s strategy is predictable, the opponent can take
advantage of this information to improve his position. Therefore, an essential feature of a rational
plan for playing a game such as this one is that neither player should be able to deduce which
strategy the other will use.
9/19/2023 1405-324 (IE 411): Operations Research II 17
Games With Mixed Strategies
• Whenever a game does not possess a saddle point, game theory advises
each player to assign a probability distribution over her set of strategies.
𝑥𝑖 = probability that player 1 will use strategy 𝑖 𝑖 = 1, 2, . . . , 𝑚
𝑦𝑖 = probability that player 2 will use strategy 𝑗 𝑗 = 1, 2, . . . , 𝑛
where m and n are the respective numbers of available strategies.
• These plans (𝑥1 , 𝑥2 , ⋯ , 𝑥𝑚 ) and (𝑦1 , 𝑦2 , ⋯ , 𝑦𝑛 ) are usually referred to as
mixed strategies, and the original strategies are then called pure strategies.

• Note: σ𝑛𝑖=1 𝑥𝑖 = 1 and σ𝑚

𝑗=1 𝑦𝑗 = 1

9/19/2023 1405-324 (IE 411): Operations Research II 18

Games With Mixed Strategies
• Although no completely satisfactory measure of performance is available for
evaluating mixed strategies, a very useful one is the expected payoff.

• By applying the probability theory definition of expected value, this quantity is

𝑚 𝑛

Expected payoff for player 1 = ෍ ෍ 𝑝𝑖𝑗 𝑥𝑖 𝑦𝑗

𝑖=1 𝑗=1

Where 𝑝𝑖𝑗 is the payoff if player 1 uses pure strategy 𝑖 and player 2 uses pure
strategy 𝑗.

9/19/2023 1405-324 (IE 411): Operations Research II 19

Games With Mixed Strategies
• Suppose that players 1 and 2 in variation 3 of the political campaign
11
problem select the mixed strategies (𝑥1 , 𝑥2 , 𝑥3 ) = ( , , 0) and (𝑦1 , 𝑦2 , 𝑦3 ) =
22
1 1
(0, , ) respectively.
2 2

• This selection would say that player 1 is giving an equal chance (probability
1
of ) of choosing either (pure) strategy 1 or 2, but he is discarding strategy 3
2
entirely. Similarly, player 2 is randomly choosing between his last two pure
strategies.

9/19/2023 1405-324 (IE 411): Operations Research II 20

Games With Mixed Strategies
Player 2
Strategy
1 2 3
1 0 -2 2
Player 1 2 5 4 -3
3 2 3 -4

Expected payoff for player 1 = σ𝑚 𝑛 3 3

𝑖=1 σ𝑗=1 𝑝𝑖𝑗 𝑥𝑖 𝑦𝑗 = σ𝑖=1 σ𝑗=1 𝑝𝑖𝑗 𝑥𝑖 𝑦𝑗

= 0 𝑥1 𝑦1 + −2 𝑥1 𝑦2 + 2 𝑥1 𝑦3 + 5 𝑥2 𝑦1 + 4 𝑥2 𝑦2 + −3 𝑥2 𝑦3 + 2 𝑥3 𝑦1 + 3 𝑥3 𝑦2 + −4 𝑥3 𝑦3
= −2 𝑥1 𝑦2 + 2 𝑥1 𝑦3 + 5 𝑥2 𝑦1 + 4 𝑥2 𝑦2 + −3 𝑥2 𝑦3 + 2 𝑥3 𝑦1 + 3 𝑥3 𝑦2 + −4 𝑥3 𝑦3
= −2𝑥1 𝑦2 + 2𝑥1 𝑦3 + 5𝑥2 𝑦1 + 4𝑥2 𝑦2 − 3𝑥2 𝑦3 + 2𝑥3 𝑦1 + 3𝑥3 𝑦2 − 4𝑥3 𝑦3
= 2𝑥1 𝑦3 + 5𝑥2 𝑦1 + 4𝑥2 𝑦2 + 2𝑥3 𝑦1 + 3𝑥3 𝑦2 − (2𝑥1 𝑦2 + 3𝑥2 𝑦3 + 4𝑥3 𝑦3 )

1 1 1 1 1 1 1 1 1 1 3
=2 +4 − 2 +3 = +1−( + )
2 2 2 2 2 2 2 2 2 2 4

2+4− 2+3 1
= =
4 4

• This measure of performance does not disclose anything about the risks involved in playing the
game, but it does indicate what the average payoff will tend to be if the game is played many times.

9/19/2023 1405-324 (IE 411): Operations Research II 21

Games With Mixed Strategies

9/19/2023 1405-324 (IE 411): Operations Research II 22

Games With Mixed Strategies

• There are several methods to find the optimal mixed strategy for each player.

• One is a graphical procedure that may be used whenever one of the players has
only two (undominated) pure strategies.

• When larger games are involved, the usual method is to transform the problem to a
linear programming problem that then can be solved by the simplex method on a
computer.

9/19/2023 1405-324 (IE 411): Operations Research II 23

Graphical Solution Procedure
• To illustrate this procedure, consider variation 3 of the political campaign problem,
Player 2
Strategy
1 2 3
1 0 -2 2
Player 1 2 5 4 -3
3 2 3 -4

Notice that the third pure strategy for player 1 is dominated by her second (values of the
second strategy are better than the third strategy), so the payoff table can be reduced to,

9/19/2023 1405-324 (IE 411): Operations Research II 24

Graphical Solution Procedure
• Therefore, for each of the pure strategies available to player 2, the expected payoff for
player 1 will be (note, σ𝑛𝑖=1 𝑥𝑖 = 1 ⟹ 𝑥1 + 𝑥2 = 1 ⟹ 𝑥1 = 1 − 𝑥2):

• Now plot these expected-payoff lines on a graph, for any given values of 𝑥1 and (𝑦1 , 𝑦2 ,
𝑦3 ), the expected payoff will be the appropriate weighted average of the corresponding
points on these three lines.

9/19/2023 1405-324 (IE 411): Operations Research II 25

 Graphical Solution Procedure
• Given 𝑥1 , player 2 can minimize this expected payoff by
choosing the pure strategy that corresponds to the
“bottom” line for that 𝑥1 (either −3 + 5𝑥1 or 4 − 6𝑥1 , but
never 5 − 5𝑥1 ).

• According to the minimax criterion, player 1 wants to

maximize this minimum expected payoff

• Thus, player 1 should select the value of 𝑥1 where the

bottom line peaks, i.e., where the (−3 + 5𝑥1 ) and (4
− 6𝑥1 ) lines intersect, which yields an expected payoff of Lower envelope

𝑣 = 𝑣 = max min ( − 3 + 5𝑥1 ), (4 − 6𝑥1 )

0≤𝑥1 ≤1

9/19/2023 1405-324 (IE 411): Operations Research II 26

Graphical Solution Procedure

9/19/2023 1405-324 (IE 411): Operations Research II 27

Graphical Solution Procedure
• To find the corresponding optimal mixed strategy for player 2,

Expected payoff for player 1 ≤ 𝑣 = 𝑣

2
𝑦1∗ 5 − 5𝑥1 + 𝑦2∗ 4 − 6𝑥1 + 𝑦3∗ −3 + 5𝑥1 ≤
11
7
• When player 1 is playing optimally (𝑥1 = 11), this inequality will be an equality (by the minimax theorem), so that

20 ∗ 2 2 2
⟹ 𝑦1 + 𝑦2∗ + 𝑦3∗ = 𝑣 = 𝑒𝑞(1)
11 11 11 11

• Because (𝑦1 , 𝑦2 , 𝑦3 ) is a probability distribution, it is also known that 𝑦1∗ + 𝑦2∗ + 𝑦3∗ = 1.

7
• Therefore, 𝑦1∗ = 0 because 𝑦1∗ > 0 would violate 𝑒𝑞(1); i.e., the expected payoff on the graph at 𝑥1 = 11 would be
above the maximin point.

In general, any line that does not pass through the maximin point must be given a zero weight to avoid increasing the
expected payoff above this point.
9/19/2023 1405-324 (IE 411): Operations Research II 28
Graphical Solution Procedure

2 7 2
• Because the ordinate of this line must equal 11 at 𝑥1 = 11 and because it must never exceed 11, the line necessarily is
horizontal. (This conclusion is always true unless the optimal value of 𝑥1 is either 0 or 1, in which case player 2 also
should use a single pure strategy.) Therefore,
2
𝑦2∗ 4 − 6𝑥1 + 𝑦3∗ −3 + 5𝑥1 = for 0 ≤ 𝑥1 ≤ 1
11
• To solve for 𝑦2∗ and 𝑦3∗ , select two values of 𝑥1 (say, 0 and 1), and solve the resulting two simultaneous equations.
Thus,
2
4𝑦2∗ − 3𝑦3∗ = when 𝑥1 = 0
11
2
−2𝑦2∗ + 2𝑦3∗ = when 𝑥1 = 1
11
5 6
which has a simultaneous solution of 𝑦2∗ = 11 and 𝑦3∗ = 11. Therefore, the optimal mixed strategy for player 2 is
5 6
(𝑦1 , 𝑦2 , 𝑦3 ) = 0, , .
11 11

9/19/2023 1405-324 (IE 411): Operations Research II 29

Extra Examples for Finding Lower/Upper Envelope

9/19/2023 1405-324 (IE 411): Operations Research II 30

Solving by Linear Programming

• Solution method for mixed strategy games

• Transform the problem to a linear programming problem
• By applying the minimax theorem and using the definitions of minimax and maximin

• Expected payoff for player 1

𝑚 𝑛

෍ ෍ 𝑝𝑖𝑗 𝑥𝑖 𝑦𝑗
𝑖=1 𝑗=1

9/19/2023 1405-324 (IE 411): Operations Research II 31

Solving by Linear Programming

• Strategy (x1,x2,…xm) is optimal if

𝑚 𝑛

෍ ෍ 𝑝𝑖𝑗 𝑥𝑖 𝑦𝑗 ≥ 𝑣 = 𝑣
𝑖=1 𝑗=1

• For all opposing strategies (y1,y2,…yn)

9/19/2023 1405-324 (IE 411): Operations Research II 32

Solving by Linear Programming

• Optimal mixed strategy for player 1 given by solution to:

9/19/2023 1405-324 (IE 411): Operations Research II 33

Solving by Linear Programming

• Optimal mixed strategy for player 2 given by solution to:

9/19/2023 1405-324 (IE 411): Operations Research II 34

Solving by Linear Programming

• The two formulations are duals of each other

• Implies optimal mixed strategies for both players can be found by solving only
one linear programming problem
• Because dual solution is an automatic by-product

9/19/2023 1405-324 (IE 411): Operations Research II 35

Solving by Linear Programming
• Deal with 𝑥𝑚+1 and 𝑦𝑛+1 being unrestricted in sign in the linear programming
formulations, as follows,
1. If it is clear 𝑣 ≥ 0 so that the optimal values of 𝑥𝑚+1 and 𝑦𝑛+1 are nonnegative, then
introduce nonnegativity constraints for these variables.
2. If 𝑣 < 0, then apply one of the following options,
a. replace 𝑥𝑚+1 or 𝑦𝑛+1 by the difference of two nonnegative variables (see section 4.6).
b. reverse players 1 and 2 so that the payoff table would be rewritten as the payoff to the original
player 2.
c. add a sufficiently large fixed constant to all the entries in the payoff table that the new value of
the game will be positive. (For example, setting this constant equal to the absolute value of the
largest negative entry will suffice.)

9/19/2023 1405-324 (IE 411): Operations Research II 36

Solving by Linear Programming: Application to Variation 3 of the
Political Campaign Problem

𝑥2

• The linear programming model for player 1 for this example is

9/19/2023 1405-324 (IE 411): Operations Research II 37

Solving by Linear Programming: Application to Variation 3 of the
Political Campaign Problem

• Prepare the model for Simplex Tableau, first adjust each constraint

Subject to
5𝑥2 − 𝑥3 − 𝑦1 + 𝐴1 = 0 𝐸𝑞. (1)
−2𝑥1 + 4𝑥2 − 𝑥3 − 𝑦2 + 𝐴2 = 0 𝐸𝑞. (2)
2𝑥1 − 3𝑥2 − 𝑥3 − 𝑦3 + 𝐴3 = 0 𝐸𝑞. (3)
𝑥1 + 𝑥2 + 𝐴4 = 1 𝐸𝑞. (4)

and
𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 , 𝐴1 , 𝐴2 , 𝐴3 , 𝐴4 ≥ 0

9/19/2023 1405-324 (IE 411): Operations Research II 38

 Solving by Linear Programming: Application to Variation 3 of the
Political Campaign Problem
• Second, adjust the objective function
Maximize 𝑍 = 𝑥3 − 𝑀𝐴1 − 𝑀𝐴2 − 𝑀𝐴3 − 𝑀𝐴4 𝐸𝑞. (0)

Subject to
5𝑥2 − 𝑥3 − 𝑦1 + 𝐴1 = 0 𝐸𝑞. (1)
−2𝑥1 + 4𝑥2 − 𝑥3 − 𝑦2 + 𝐴2 = 0 𝐸𝑞. (2)
2𝑥1 − 3𝑥2 − 𝑥3 − 𝑦3 + 𝐴3 = 0 𝐸𝑞. (3)
𝑥1 + 𝑥2 + 𝐴4 = 1 𝐸𝑞. (4)

and
𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 , 𝐴1 , 𝐴2 , 𝐴3 , 𝐴4 ≥ 0
𝐸𝑞. (0)
−𝑀 × 𝐸𝑞. (1)
Objective function −𝑀 × 𝐸𝑞. (2)
−𝑀 × 𝐸𝑞. (3)
−𝑀 × 𝐸𝑞. (4)
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

9/19/2023 1405-324 (IE 411): Operations Research II 39

Solving by Linear Programming: Application to Variation 3 of the
Political Campaign Problem
𝐸𝑞. (0)
−𝑀 × 𝐸𝑞. (1)
−𝑀 × 𝐸𝑞. (2)
−𝑀 × 𝐸𝑞. (3)
−𝑀 × 𝐸𝑞. (4)
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒

• The linear programming model for player 1 for this example is

Maximize 𝑍 = 𝑀𝑥1 + 7𝑀𝑥2 − 3𝑀 − 1 𝑥3 − 𝑀𝑦1 − 𝑀𝑦2 − 𝑀𝑦3 − 𝑀

Subject to
5𝑥2 − 𝑥3 − 𝑦1 + 𝐴1 = 0
−2𝑥1 + 4𝑥2 − 𝑥3 − 𝑦2 + 𝐴2 = 0
2𝑥1 − 3𝑥2 − 𝑥3 − 𝑦3 + 𝐴3 = 0
𝑥1 + 𝑥2 + 𝐴4 = 1

and
𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 , 𝐴1 , 𝐴2 , 𝐴3 , 𝐴4 ≥ 0

9/19/2023 1405-324 (IE 411): Operations Research II 40

Solving by Linear Programming: Application to Variation 3 of the
Political Campaign Problem
Basic Coefficient of: Right
Iteration Eq.
Variable Z x1 x2 x3 y1 y2 y3 A1 A2 A3 A4 Side
Z (0) 1 -M -7M 3M-1 M M M 0 0 0 0 -M
A1 (1) 0 0 5 -1 -1 0 0 1 0 0 0 0
0 A2 (2) 0 -2 4 -1 0 -1 0 0 1 0 0 0
A3 (3) 0 2 -3 -1 0 0 -1 0 0 1 0 0
A4 (4) 0 1 1 0 0 0 0 0 0 0 1 1
Z (0) 1 -4.5M 0 1.25M - 1 M -0.75M M 0 1.75M 0 0 -M
A1 (1) 0 2.5 0 0.25 -1 1.25 0 1 -1.25 0 0 0
1 x2 (2) 0 -0.5 1 -0.25 0 -0.25 0 0 0.25 0 0 0
A3 (3) 0 0.5 0 -1.75 0 -0.75 -1 0 0.75 1 0 0
A4 (4) 0 1.5 0 0.25 0 0.25 0 0 -0.25 0 1 1
Z (0) 1 0 0 -14.5M - 1 M -7.5M -8M -M 8.5M 9M 0 -M
A1 (1) 0 0 0 9 -1 5 5 1 -5 -5 0 0
2 x2 (2) 0 0 1 -2 0 -1 -1 0 1 1 0 0
x1 (3) 0 1 0 -3.5 0 -1.5 -2 0 1.5 2 0 0
A4 (4) 0 0 0 5.5 0 2.5 3 0 -2.5 -3 1 1
Z (0) 1 0 0 0 -0.611M - 0.111 0.556M + 0.556 0.0556M + 0.556 0.611M + 0.111 0.444M - 0.556 0.944M - 0.556 0 -M
x3 (1) 0 0 0 1 -0.111 0.556 0.556 0.111 -0.556 -0.556 0 0
3 x2 (2) 0 0 1 0 -0.222 0.111 0.111 0.222 -0.111 -0.111 0 0
x1 (3) 0 1 0 0 -0.389 0.444 -0.056 0.389 -0.444 0.056 0 0
A4 (4) 0 0 0 0 0.611 -0.556 -0.056 -0.611 0.556 0.056 1 1
Z (0) 1 0 0 0 0 0.454 0.545 0 M - 0.454 M - 0.545 M - 0.182 0.182
x3 (1) 0 0 0 1 0 0.455 0.545 0 -0.455 -0.545 0.182 0.182
4 x2 (2) 0 0 1 0 0 -0.091 0.091 0 0.091 -0.091 0.364 0.364
x1 (3) 0 1 0 0 0 0.091 -0.091 0 -0.091 0.091 0.636 0.636
y1 (4) 0 0 0 0 1 -0.909 -0.091 -1 0.909 0.091 1.636 1.636

The optimal mixed strategy for player 1 is (𝑥1 , 𝑥2 ) = 0.636, 0.364 and for player 2 is
(𝑦1 , 𝑦2 , 𝑦3 ) = 0,0.454, 0.545 and the value of the game 𝑥3 = 𝑣 = 𝑣 = 0.182.
9/19/2023 1405-324 (IE 411): Operations Research II 41
Extensions
• Game theory research extends to more complicated games than are covered here
• Two-person, constant-sum game
• n-person game
• Nonzero-sum game
• Noncooperative and cooperative games
• Defined by amount of pre-game communications

• Infinite games
• Decision variable is continuous

9/19/2023 1405-324 (IE 411): Operations Research II 42