Operation Research: Chapter (2)

Chapter Tow

GAME THEORY

51
Operation Research: Chapter (2)

52
Operation Research: Chapter (2)

Chapter Two

GAME THEORY

2.1 INTRODUCTION:

Game theory deals with decision situations in which

two intelligent opponents with conflicting objectives are
trying to outdo one another. Typically examples for
competing products and planning strategies for warring
armies.

In a game conflict, two opponents, known as players,

will each have a (finite or infinite) number of alternatives or
strategies. Associated with each pair of strategies is a payoff
that one player receives from the other. Such games are
known as two-person zero-sum games because a gain by one
player signifies an equal loss to the other. It surfaces, then, to
summarize the game in terms of the payoff to one player.
Designating the two players as A and B with n and m
strategies, respectively, the game is usually represented by the
payoff matrix to player A as:

Player B
a11 a12 a13………..a1m
a21 a22 a23…… …..a2m
Player A ……………………..
…………………...
an1 an2 an3…… …..anm

53
Operation Research: Chapter (2)

The representation indicates that if A uses strategy i and

B uses strategy j, the payoff to is aij .

Game theory applications have been developed for

situations in which the competing players are teams,
companies, political candidates, and contract bidders
.
2.2 TWO-PERSON ZERO-SUM GAMES

In this section, we describe two-person, zero-sum

games. Two-person means that two players participate in the
game. Zero-sum means that the gain (or loss) for one player is
equal to the loss (or gain) for the other player. As a result, the
gain and loss balance out (resulting in a zero-sum) for the
game. What one player wins, the other player loses. Let us
demonstrate a two-person, zero-sum game and its solution by
considering two companies competing for market share.

Suppose that two companies are the only manufacturers

of a particular product; they compete against each other for
market share. In planning a marketing strategy for the coming
year, each company will select one of three strategies
designed to take market share from the other company. The
three strategies, which are assumed the same for both
companies, are as follows:
Strategy 1: Increase advertising.
Strategy 2: Provide quantity discounts.
Strategy 3: Extend warranty.

54
Operation Research: Chapter (2)

TABLE 1
PAYOFF TABLE SHOWING THE PERCENTAGE GAIN IN MARKET
SHARE FOR COMPANY A

Company B
Increase Quantity Extend
Advertising Discounts Warranty
b1 b2 b3
a1 4 3 2
Company A a2 -1 4 1
a3 5 -2 0

A payoff table showing the percentage gain in the market

share for Company A for each combination of strategies is shown
in Table 1. Because it is a zero-sum game, any gain in market
share for Company A is a loss in market share for Company B.

In interpreting the entries in the table, we see that if

Company A increases advertising (a1) and Company B
increases advertising (b1), Company A will come out ahead
with an increase in market share of 4%, while Company B
will have a decrease in market share of 4%. On the other
hand, if Company A provides quantity discounts (a2) and
Company B increases advertising (b1), Company A will lose
1% of market share, while Company B will gain 1% of
market share. Therefore, Company A wants to maximize the
payoff that is its increase in market share. Company B wants
to minimize the payoff because the increase in market share
for Company A is the decrease in market share for Company
B.

55
Operation Research: Chapter (2)

This market-share game meets the requirements of a

two-person, zero-sum game. The two companies are the two
players, and the zero-sum occurs because the gain (or loss) in
market share for Company A is the same as the loss (or gain)
in market share for Company B. Each company will select
one of its three alternative strategies. Because of the planning
horizon, each company will have to select its strategy before
knowing the other company’s strategy. What is the optimal
strategy for each company?

The logic of game theory assumes that each player has

the same information and will select a strategy that provides
the best possible payoff from its point of view. Suppose
Company A selects strategy a1. Market share increases of 4%,
3%, or 2% are possible depending upon Company B’s
strategy. At this point, Company A assumes that Company B
will select the strategy that is best for it. Thus, if Company A
selects strategy a1, Company A assumes Company B will
select its best strategy b3, which will limit Company A’s
increase in market share to 2%. Continuing with this logic,
Company A analyzes the game by protecting itself against the
strategy that may be taken by Company B. Doing so,
Company A identifies the minimum payoff for each of its
strategies, which is the minimum value in each row of the
payoff table. These row minimums are shown in Table 2.

Considering the entries in the Row Minimum column,

we see that Company A can be guaranteed an increase in
market share of at least 2% by selecting strategy a1. Strategy
a2 could result in a decrease in market share of 1% and

56
Operation Research: Chapter (2)

strategy a3 could result in a decrease in market share of 2%.

After comparing the row minimum values, Company A
selects the strategy that provides the maximum of the row
minimum values. This is called a maxim in strategy. Thus,
Company A selects strategy a1 as its optimal strategy; an
increase in market share of at least 2% is guaranteed.

Let us now look at the payoff table from the point of

view of the other player, Company B. The entries in the
payoff table represent gains in market share for Company A.

TABLE 2
PAYOFF TABLE WITH ROW MINIMUMS
Company B
b1 b2 b3 Minimum
a1 4 3 2 2 Maximum
Company A a2 - 1 4 1 -1
a3 5 -2 0 -2

Correspond to losses in market share for Company B.

Consider what happens if Company B selects strategy b1.
Company B market share decreases of 4%, –1%, and 5% are
possible. Under the assumption that Company A will select the
strategy that is best for it, Company B assumes Company A will
select strategy a3, resulting in a gain in market share of 5% for
Company A and a loss in market share of 5% for Company B. At
this point, Company B analyzes the game by protecting itself
against the strategy taken by Company A. Doing so, Company B
identifies the maximum payoff to Company A for each of its
strategies b1, b2, and b3. This payoff value is the maximum value
in each column of the payoff table. These column maximums are
shown in Table 3.

57
Operation Research: Chapter (2)

Considering the entries in the Column Maximum row,

Company B can be guaranteed a decrease in market share of
no more than 2% by selecting the strategy b3. Strategy b1
could result in a decrease in market share of 5% and strategy
b2 could result in a decrease in market share of 4%. After
comparing the column maximum values, Company B selects
the strategy that provides the minimum of the column
maximum values. This is called a minimax strategy. Thus,
Company B selects b3 as its optimal strategy. Company B has
guaranteed. That Company A cannot gain more than 2% in
market share.

2.3 IDENTIFYING A PURE STRATEGY SOLUTION

If it is optimal for both players to select one strategy and

stay with that strategy regardless of what the other player
does, the game has a pure strategy solution. Whenever the
maximum of the row minimums equals the minimum of the
column maximums, the players cannot improve their payoff
by changing to a different strategy. The game is said to have a
pure strategy solution.

TABLE 3 PAYOFF TABLE WITH COLUMN MAXIMUMS

Company B
b1 b2 b3 Minimum Row
a1 4 3 2 2 Maximum
Company A a2 - 1 4 1 -1
a3 5 -2 5 2
Maximum Column 5 4 2 Minimum

58
Operation Research: Chapter (2)

Underline point, or an equilibrium point. Thus, a pure

strategy is the optimal strategy for the players. The requirement
for a pure strategy solution is as follows:

A Game Has a Pure Strategy Solution If:

Maximum (Row minimums) = Minimum (Column maximums)

Because this equality is the case in our example, the

solution to the game is for Company A to increase advertising
(strategy a1) and for Company B to extend the warranty (strategy
b3). Company A’s market share will increase by 2% and Company
B’s market share will decrease by 2%.

With Company A selecting its pure strategy a1, let us see

what happens if Company B tries to change from its pure strategy
b3. Company A’s market share will increase 4% if b1 is selected
or will increase 3% if b2 is selected. Company B must stay with its
pure strategy b3 to limit Company A to a 2% increase in market
share. Similarly, with Company B selecting its pure strategy b3,
let us see what happens if Company A tries to change from its
pure strategy a1. Company A’s market share will increase only
1% if a2 is selected or will not increase at all if a3 is selected.
Company A must stay with its pure strategy a1 in order to keep its
2% increase in market share. Thus, even if one of the companies
discovers its opponent’s pure strategy in advance, neither
company can gain any advantage by switching from its pure
strategy.

If a pure strategy solution exists, it is the optimal solution to

the game. The following steps can be used to determine when a
game has a pure strategy solution and to identify the optimal pure
strategy for each player:

59
Operation Research: Chapter (2)

Step 1. Compute the minimum payoff for each row (Player A

Step 2. For Player A, select the strategy that provides the

maximum of the row minimums.

Step3. Compute the maximum payoff for each column (Player B).

Step 4. For Player B, select the strategy that provides the

minimum of the column maximums.

Step 5. If the maximum of the row minimums is equal to the

minimum of the column maximums, this value is the value
of the game and a pure strategy solution exists. The
optimal pure strategy for Player A is identified in Step 2,
and the optimal pure strategy for Player B is identified in
Step 4.

60
Operation Research: Chapter (2)

2.4 A MIXED STRATEGY GRAPHICAL SOLUTION

If the maximum of the row minimums does not equal the

minimum of the column maximums, a pure strategy solution does
not exist. In this case, a mixed strategy solution becomes optimal.
In the following discussion, we define a mixed strategy solution
and show how linear programming can be used to identify the
optimal mixed strategy for each player.

Let us continue with the two-company market-share game

and consider a slight modification in the payoff table as shown in
Table 4. Only one payoff has changed. If both Company A and
Company B choose the extended warranty strategy, the payoff to
Company A is now a 5% increase in market share rather than the
previous 0%. The row minimums do not change, but the column
maximums do. Note that the column maximum for strategy b3 is
5% instead of the previous 2%.

TABLE 4
MODIFIED PAYOFF TABLE SHOWING THE PERCENTAGE GAIN IN
MARKET SHARE FOR COMPANY A

Company B
b1 b2 b3 Minimum Row
a1 4 3 2 2 Maximum
Company A a2 - 1 4 1 -1
a3 5 -2 5 -2
Column Maximum 5 4 Minimum 5

In analyzing the game to determine whether a pure

strategy solution exists, we find that the maximum of the row
minimums is 2% while the minimum of the row maximums is
4%. Because these values are not equal, a pure strategy

61
Operation Research: Chapter (2)

solution does not exist. In this case, it is not optimal for each
company to be predictable and select a pure strategy
regardless of what the other company does. The optimal
solution is for both players to adopt a mixed strategy.

EXAMPLE 1:
Consider the following 2x3 game. The payoff is for
player A:
Player B
b1 b2 b3 Minimum row
a1 1 3 5 1 Maximum
Player A
a2 5 0 -2 -2
Column Maximum 5 3 5
Minimum

Minimum max ≠ Maximum min, then pure strategy solution

does not exist. So each player selects mixed strategies as
follows:

Suppose the time of the game is T, he will play part of time

say t1 with strategy a1 and will play the rest of the time say t2
with strategy a2. that is:

T = t1 + t2
A mixed strategy solution will be:
Maximize his gain (g)
s.t
1t1 + 5 t2 > g,
3 t1 + 0 t2 > g,
5 t1 - 2 t2 > g,

62
Operation Research: Chapter (2)

Change the inequalities to equality:

1t1 + 5 t2 = g,
3 t1 + 0 t2 = g,
5 t1 - 2 t2 = g,

5 5

4 4

3 C 3
Minimax
2 2

1 Feasible region 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 t1

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 t2
-1 -1

-2 -2

Point C is the solution that means A will play 0.27 of the time
of game using strategy a1 and 0.73 the time of game using
strategy a2. His total gain will be 1.7

63
Operation Research: Chapter (2)

2.5 A MIXED STRATEGY MATHEMATICAL

SOLUTION

The Basics of Game Theory

The focus of game theory is the game, which serves as a

model of an interactive situation among rational players. The
key to game theory is that one player's payoff is contingent on
the strategy implemented by the other player. The game
identifies the players' identities, preferences, and available
strategies and how these strategies affect the outcome.
Depending on the model, various other requirements or
assumptions may be necessary.

Game theory has a wide range of applications, including

psychology, evolutionary biology, war, politics, economics,
and business. Despite its many advances, game theory is still
a young and developing science.

Game Theory Definitions

Any time we have a situation with two or more players that
involve known payouts or quantifiable consequences, we can
use game theory to help determine the most likely outcomes.
Let's start out by defining a few terms commonly used in the
study of game theory:

 Game: Any set of circumstances that has a result

dependent on the actions of two or more decision-
makers (players)
 Players: A strategic decision-maker within the context
of the game

64
Operation Research: Chapter (2)

 Strategy: A complete plan of action a player will take

given the set of circumstances that might arise within
the game
 Payoff: The payout a player receives from arriving at a
particular outcome (The payout can be in any
quantifiable form, from dollars to utility.)
 Information set: The information available at a given
point in the game (The term information set is most
usually applied when the game has a sequential
component.)
 Equilibrium: The point in a game where both players
have made their decisions and an outcome is reached

The Nash Equilibrium

Nash Equilibrium is an outcome reached that, once achieved,
means no player can increase payoff by changing decisions
unilaterally. It can also be thought of as "no regrets," in the
sense that once a decision is made, the player will have no
regrets concerning decisions considering the consequences.

The Nash Equilibrium is reached over time, in most cases.

However, once the Nash Equilibrium is reached, it will not be
deviated from. After we learn how to find the Nash
Equilibrium, take a look at how a unilateral move would
affect the situation. Does it make any sense? It shouldn't, and
that's why the Nash Equilibrium is described as "no regrets."
Generally, there can be more than one equilibrium in a game.

However, this usually occurs in games with more complex

elements than two choices by two players. In simultaneous
games that are repeated over time, one of these multiple

65
Operation Research: Chapter (2)

equilibrium is reached after some trial and error. This scenario

of different choices overtime before reaching equilibrium is
the most often played out in the business world when two
firms are determining prices for highly interchangeable
products, such as airfare or soft drinks.

Impact on Economics and Business

Game theory brought about a revolution in economics by
addressing crucial problems in prior mathematical economic
models. For instance, neoclassical economics struggled to
understand entrepreneurial anticipation and could not handle
the imperfect competition. Game theory turned attention away
from steady-state equilibrium toward the market process.

In business, game theory is beneficial for modeling competing

behaviors between economic agents. Businesses often have
several strategic choices that affect their ability to realize
economic gain. For example, businesses may face dilemmas
such as whether to retire existing products or develop new
ones, lower prices relative to the competition, or employ new
marketing strategies. Economists often use game theory to
understand oligopoly firm behavior. It helps to predict likely
outcomes when firms engage in certain behaviors, such as
price-fixing and collusion.

Types of Game Theory

Although there are many types (e.g., symmetric/asymmetric,

simultaneous/sequential, et al.) of game theories, cooperative
and non-cooperative game theories are the

66
Operation Research: Chapter (2)

mostcommon. Cooperative game theory deals with how

coalitions, or cooperative groups, interact when only the
payoffs are known. It is a game between coalitions of players
rather than between individuals, and it questions how groups
form and how they allocate the payoff among players.

Non-cooperative game theory deals with how rational

economic agents deal with each other to achieve their own
goals. The most common non-cooperative game is the
strategic game, in which only the available strategies and the
outcomes that result from a combination of choices are
listed. A simplistic example of a real-world non-cooperative
game is Rock-Paper-Scissors.

Examples of Game Theory

There are several "games" that game theory analyzes. Below,

we will just briefly describe a few of these.

The Prisoner's Dilemma

The Prisoner's Dilemma is the most well-known example of
game theory. Consider the example of two criminals arrested
for a crime. Prosecutors have no hard evidence to convict
them. However, to gain a confession, officials remove the
prisoners from their solitary cells and question each one in
separate chambers. Neither prisoner has the means to
communicate with each other. Officials present four deals,
often displayed as a 2 x 2 box.

1. If both confess, they will each receive a five-year prison

sentence.

67
Operation Research: Chapter (2)

2. If Prisoner 1 confesses, but Prisoner 2 does not, Prisoner

1 will get three years and Prisoner 2 will get nine years.
3. If Prisoner 2 confesses, but Prisoner 1 does not, Prisoner
1 will get 10 years, and Prisoner 2 will get two years.
4. If neither confesses, each will serve two years in
prison.

The most favorable strategy is to not confess. However,

neither is aware of the other's strategy and without certainty
that one will not confess, both will likely confess and receive
a five-year prison sentence. The Nash equilibrium suggests
that in a prisoner's dilemma, both players will make the move
that is best for them individually but worse for them
collectively.

The expression "tit for tat" has been determined to be the

optimal strategy for optimizing a prisoner's dilemma. Tit for
tat was introduced by Anatol Rapoport, who developed a
strategy in which each participant in an iterated prisoner's
dilemma follows a course of action consistent with his
opponent's previous turn. For example, if provoked, a player
subsequently responds with retaliation; if unprovoked, the
player cooperates.

Dictator Game

This is a simple game in which Player A must decide how to

split a cash prize with Player B, who has no input into Player
A’s decision. While this is not a game theory strategy per se,
it does provide some interesting insights into people’s
behavior. Experiments reveal about 50% keep all the money

68
Operation Research: Chapter (2)

to themselves, 5% split it equally, and the other 45% give the

other participant a smaller share.

The dictator game is closely related to the ultimatum game, in

which Player A is given a set amount of money, part of which
has to be given to Player B, who can accept or reject the
amount given. The catch is if the second player rejects the
amount offered, both A and B get nothing. The dictator and
ultimatum games hold important lessons for issues such as
charitable giving and philanthropy.

Volunteer’s Dilemma

In a volunteer’s dilemma, someone has to undertake a chore

or job for the common good. The worst possible outcome is
realized if nobody volunteers. For example, consider a
company in which accounting fraud is rampant, though top
management is unaware of it. Some junior employees in the
accounting department are aware of the fraud but hesitate to
tell top management because it would result in the employees
involved in the fraud being fired and most likely prosecuted.

Being labeled as a whistleblower may also have some

repercussions down the line. But if nobody volunteers, the
large-scale fraud may result in the company’s
eventual bankruptcy and the loss of everyone’s jobs.

The Centipede Game

The centipede game is an extensive-form game in game

theory in which two players alternately get a chance to take

69
Operation Research: Chapter (2)

the larger share of a slowly increasing money stash. It is

arranged so that if a player passes the stash to his opponent
who then takes the stash, the player receives a smaller amount
than if he had taken the pot.

The centipede game concludes as soon as a player takes the

stash, with that player getting the larger portion and the other
player getting the smaller portion. The game has a pre-defined
total number of rounds, which are known to each player in
advance.

Limitations of Game Theory

The biggest issue with game theory is that, like most other
economic models, it relies on the assumption that people are
rational actors that are self-interested and utility-maximizing.
Of course, we are social beings who do cooperate and do care
about the welfare of others, often at our own expense. Game
theory cannot account for the fact that in some situations we
may fall into a Nash equilibrium, and other times not,
depending on the social context and who the players are.

Backward Induction

In game theory, backward induction is the process of

deducing backward from the end of a problem or scenario to
infer a sequence of optimal actions.

70
Operation Research: Chapter (2)

Zero-Sum Game

A situation in which one person’s gain is equivalent to

another’s loss, so that the net change in wealth or benefit is
zero. A zero-sum game may have as few as two players, or
millions of participants.

Nash Equilibrium

The Nash Equilibrium is a concept within game theory where

the optimal outcome of a game is where there is no incentive
to deviate from their initial strategy.

Tit for Tat Definition

Tit for tat is a game-theory strategy in which a player chooses the

action that the opposing player chose in the previous round of
play.

Centipede Game Definition

The centipede game in game theory involves two players

alternately getting a chance to take the larger share of an
increasing money stash.

Traveler's Dilemma Definition

The traveler's dilemma demonstrates the paradox of

rationality—that making decisions illogically often produces a
better payoff in game theory.

71
Operation Research: Chapter (2)

How Game Theory Strategy Improves Decision Making

Game theory, the study of strategic decision-making, brings

together disparate disciplines such as mathematics,
psychology, and philosophy. Game theory was invented by
John von Neumann and Oskar Morgenstern in 1944 and has
come a long way since then. The importance of game theory
to modern analysis and decision-making can be gauged by the
fact that since 1970, as many as 12 leading economists and
scientists have been awarded the Nobel Prize in Economic
Sciences for their contributions to game theory.

Game theory is applied in a number of fields, including

business, finance, economics, political science, and
psychology. Understanding game theory strategies—both the
popular ones and some of the relatively lesser-known
stratagems—is important to enhance one’s reasoning
and decision-making skills in a complex world.

Prisoner’s Dilemma

One of the most popular and basic game theory strategies is

the prisoner's dilemma. This concept explores the decision-
making strategy taken by two individuals who, by acting in
their own individual best interest, end up with worse
outcomes than if they had cooperated with each other in the
first place.

In the prisoner’s dilemma, two suspects apprehended for a

crime are held in separate rooms and cannot communicate
with each other. The prosecutor informs both Suspect 1 and

72
Operation Research: Chapter (2)

Suspect 2 individually that if he confesses and testifies against

the other, he can go free, but if he does not cooperate and the
other suspect does, he will be sentenced to three years in
prison. If both confess, they will get a two-year sentence, and
if neither confesses, they will be sentenced to one year in
prison.

While cooperation is the best strategy for the two suspects,

when confronted with such a dilemma, research shows most
rational people prefer to confess and testify against the other
person than stay silent and take the chance the other party
confesses.

Game Theory Strategie

s
The prisoner's dilemma lays the foundation for advanced
game theory strategies, of which the popular ones include:

Matching Pennies

This is a zero-sum game that involves two players (call them

Player A and Player B) simultaneously placing a penny on the
table, with the payoff depending on whether the pennies
match. If both pennies are heads or tails, Player A wins and
keeps Player B’s penny. If they do not match, Player B wins
and keeps Player A’s penny.

Deadlock

This is a social dilemma scenario like the prisoner’s

dilemma in that two players can either cooperate or defect

73
Operation Research: Chapter (2)

(i.e. not cooperate). In a deadlock, if Player A and Player B

both cooperate, they each get a payoff of 1, and if they both
defect, they each get a payoff of 2. But if Player A cooperates
and Player B defects, then A gets a payoff of 0 and B gets a
payoff of 3. In the payoff diagram below, the first numeral in
the cells (a) through (d) represents Player A’s payoff, and the
second numeral is that of Player B:

Deadlock Payoff Matrix

Player B
Cooperate Defect
Player A Cooperate (a) 1, 1 (b) 0, 3
Defect (c) 3, 0 (d) 2, 2

Deadlock differs from prisoner’s dilemma in that the action of

greatest mutual benefit (i.e. both defect) is also the dominant
strategy. A dominant strategy for a player is defined as one
that produces the highest payoff of any available strategy,
regardless of the strategies employed by the other players.

A commonly cited example of deadlock is that of two nuclear

powers trying to reach an agreement to eliminate their
arsenals of nuclear bombs. In this case, cooperation implies
adhering to the agreement, while defection means secretly
reneging on the agreement and retaining the nuclear arsenal.
The best outcome for either nation, unfortunately, is to renege
on the agreement and retain the nuclear option while the other
nation eliminates its arsenal since this will give the former a
tremendous hidden advantage over the latter if war ever
breaks out between the two. The second-best option is for

74
Operation Research: Chapter (2)

both to defect or not cooperate since this retains their status as

nuclear powers.

Cournot Competition

This model is also conceptually similar to prisoner’s dilemma

and is named after French mathematician Augustin Cournot,
who introduced it in 1838. The most common application of
the Cournot model is in describing a duopoly or two main
producers in a market.

For example, assume companies A and B produce an identical

product and can produce high or low quantities. If they both
cooperate and agree to produce at low levels, then
limited supply will translate into a high price for the product
on the market and substantial profits for both companies. On
the other hand, if they defect and produce at high levels, the
market will be swamped and result in a low price for the
product and consequently lower profits for both. But if one
cooperates (i.e. produces at low levels) and the other defects
(i.e. surreptitiously produces at high levels), then the former
just break even while the latter earns a higher profit than if
they both cooperate.

The payoff matrix for companies A and B is shown (figures

represent profit in millions of dollars). Thus, if A cooperates
and produces at low levels while B defects and produces at
high levels, the payoff is as shown in the cell (b)—break-even
for company A and $7 million in profits for company B.

75
Operation Research: Chapter (2)

Cournot Payoff Matrix

Company B
Cooperate Defect
Company A Cooperate (a) 4, 4 (b) 0, 7
Defect (c) 7, 0 (d) 2, 2

Coordination

In coordination, players earn higher payoffs when they select

the same course of action.

As an example, consider two technology giants who are

deciding between introducing a radical new technology in
memory chips that could earn them hundreds of millions in
profits, or a revised version of an older technology that would
earn them much less. If only one company decides to go
ahead with the new technology, rate of adoption by
consumers would be significantly lower, and as a result, it
would earn less than if both companies decide on the same
course of action. The payoff matrix is shown below (figures
represent profit in millions of dollars).

Thus, if both companies decide to introduce the new

technology, they would earn $600 million apiece, while
introducing a revised version of the older technology would
earn them $300 million each, as shown in the cell (d). But if
Company A decides alone to introduce the new technology, it
would only earn $150 million, even though Company B
would earn $0 (presumably because consumers may not be
willing to pay for its now-obsolete technology). In this case, it

76
Operation Research: Chapter (2)

makes sense for both companies to work together rather than

on their own.
Coordination Playoff Matrix
Company B
New Technology Old Technology
New
Company A (a) 600, 600 (b) 0, 150
Technology
Old
(c) 150, 0 (d) 300, 300
Technology

Centipede Game

This is an extensive-form game in which two players

alternately get a chance to take the larger share of a slowly
increasing money stash. The centipede game is sequential
since the players make their moves one after another rather
than simultaneously; each player also knows the strategies
chosen by the players who played before them. The game
concludes as soon as a player takes the stash, with that player
getting the larger portion and the other player getting the
smaller portion.

As an example, assume Player A goes first and has to decide

if he should “take” or “pass” the stash, which currently
amounts to $2. If he takes, then A and B get $1 each, but if A
passes, the decision to take or pass now has to be made by
Player B. If B takes, she gets $3 (i.e. the previous stash of $2
+ $1) and A gets $0. But if B passes, A now gets to decide
whether to take or pass, and so on. If both players always
choose to pass, they each receive a payoff of $100 at the end
of the game.

77
Operation Research: Chapter (2)

The point of the game is if A and B both cooperate and

continue to pass until the end of the game, they get the
maximum payout of $100 each. But if they distrust the other
player and expect them to “take” at the first opportunity, Nash
equilibrium predicts the players will take the lowest possible
claim ($1 in this case). Experimental studies have shown,
however, this “rational” behavior (as predicted by game
theory) is seldom exhibited in real life. This is not intuitively
surprising given the tiny size of the initial payout in relation to
the final one. Similar behavior by experimental subjects has
also been exhibited in the traveler’s dilemma.

Traveler’s Dilemma

This non-zero sum game, in which both players attempt to

maximize their own payout without regard to the other, was
devised by economist Kaushik Basu in 1994. For example,
in the traveler’s dilemma, an airline agrees to pay two
travelers compensation for damages to identical items.
However, the two travelers are separately required to estimate
the value of the item, with a minimum of $2 and a maximum
of $100. If both write down the same value, the airline will
reimburse each of them that amount. But if the values differ,
the airline will pay them the lower value, with a bonus of $2
for the traveler who wrote down this lower value and a
penalty of $2 for the traveler who wrote down the higher
value.

The Nash equilibrium level, based on backward induction, is

$2 in this scenario. But as in the centipede game, laboratory
experiments consistently demonstrate most

78
Operation Research: Chapter (2)

participants, naively or otherwise, pick a number much higher

than $2.

Traveler’s dilemma can be applied to analyze a variety of

real-life situations. The process of backward induction, for
example, can help explain how two companies engaged in a
cutthroat competition can steadily ratchet product prices lower
in a bid to gain market share, which may result in them
incurring increasingly greater losses in the process.

Battle of the Sexes

This is another form of the coordination game described

earlier, but with some payoff asymmetries. It essentially
involves a couple trying to coordinate their evening out.
While they had agreed to meet at either the ball game (the
man’s preference) or at a play (the woman’s preference), they
have forgotten what they decided, and to compound, the
problem, cannot communicate with one another. Where
should they go? The payoff matrix is shown below with the
numerals in the cells representing the relative degree of
enjoyment of the event for the woman and man, respectively.
For example, cell (a) represents the payoff (in terms of
enjoyment levels) for the woman and man at the play (she
enjoys it much more than he does). Cell (d) is the payoff if
both make it to the ball game (he enjoys it more than she
does). Cell (c) represents the dissatisfaction if both go not
only to the wrong location but also to the event they enjoy
least—the woman to the ball game and the man to the play.

79
Operation Research: Chapter (2)

Battle of the Sexes Payoff Matrix

Man
Play Ball Game
Woman Play (a) 6, 3 (b) 2, 2
Ball Game (c) 0, 0 (d) 3, 6

Dictator Game

This is a simple game in which Player A must decide how to

split a cash prize with Player B, who has no input into Player
A’s decision. While this is not a game theory strategy per se,
it does provide some interesting insights into people’s
behavior. Experiments reveal about 50% keep all the money
to themselves, 5% split it equally and the other 45% give the
other participant a smaller share. The dictator game is closely
related to the ultimatum game, in which Player A is given a
set amount of money, part of which has to be given to Player
B, who can accept or reject the amount given. The catch is if
the second player rejects the amount offered, both A and B
get nothing. The dictator and ultimatum games hold important
lessons for issues such as charitable giving and philanthropy.

Peace-War

This is a variation of the prisoner’s dilemma in which the

“cooperate or defect” decisions are replaced by “peace or
war.” An analogy could be two companies engaged in a price
war. If both refrain from price cutting, they enjoy relative
prosperity (cell a), but a price war would reduce payoffs
dramatically (cell d). However, if A engages in price cutting
(war) but B does not, A would have a higher payoff of 4 since

80
Operation Research: Chapter (2)

it may be able to capture substantial market share, and this

higher volume would offset lower product prices.
Peace-War Payoff Matrix
Company B
Peace War
Company A Peace (a) 3, 3 (b) 0, 4
War (c) 4, 0 (d) 1, 1

Volunteer’s Dilemma

In a volunteer’s dilemma, someone has to undertake a chore

or job for the common good. The worst possible outcome is
realized if nobody volunteers. For example, consider a
company where accounting fraud is rampant but top
management is unaware of it. Some junior employees in the
accounting department are aware of the fraud but hesitate to
tell top management because it would result in the employees
involved in the fraud being fired and most likely prosecuted.

Being labeled as a whistleblower may also have some

repercussions down the line. But if nobody volunteers, the
large-scale fraud may result in the company’s
eventual bankruptcy and the loss of everyone’s jobs.

The Bottom Line

Game theory can be used very effectively as a tool for

decision-making whether in an economical, business or
personal setting.

81
Operation Research: Chapter (2)

The Prisoner’s Dilemma in Business and the Economy

The prisoner’s dilemma, one of the most famous game

theories, was conceptualized by Merrill Flood and Melvin
Dresher at the Rand Corporation in 1950. It was later
formalized and named by Princeton mathematician, Albert
William Tucker.

The prisoner’s dilemma basically provides a framework for

understanding how to strike a balance between cooperation
and competition and is a useful tool for strategic decision-
making.

As a result, it finds application in diverse areas ranging from

business, finance, economics, and political science to
philosophy, psychology, biology, and sociology.

KEY TAKEAWAYS

 A prisoner's dilemma describes a situation where,

according to game theory, two players acting
strategically will ultimately result in a suboptimal
choice for both.
 In business, understanding the structure of certain
decisions as prisoner's dilemmas can result in more
favorable outcomes.
 This set-up allows one to balance both competition and
cooperation for mutual benefit.

82
Operation Research: Chapter (2)

Prisoner’s Dilemma Basics

The prisoner’s dilemma scenario works as follows: Two

suspects have been apprehended for a crime and are now in
separate rooms in a police station, with no means of
communicating with each other. The prosecutor has
separately told them the following:

 If you confess and agree to testify against the other

suspect, who does not confess, the charges against you
will be dropped and you will go scot-free.
 If you do not confess but the other suspect does, you
will be convicted and the prosecution will seek the
maximum sentence of three years.
 If both of you confess, you will both be sentenced to
two years in prison.
 If neither of you confesses, you will both be charged
with misdemeanors and will be sentenced to one year in
prison.

What should the suspects do? This is the essence of the

prisoner’s dilemma.

Evaluating Best Course of Action

Let’s begin by constructing a payoff matrix as shown in the

table below. The “payoff” here is shown in terms of the length
of a prison sentence (as symbolized by the negative sign; the
higher the number the better). The terms “cooperate” and
“defect” refer to the suspects cooperating with each other (as
for example, if neither of them confesses) or defecting (i.e.,

83
Operation Research: Chapter (2)

not cooperating with the other player, which is the case where
one suspect confesses, but the other does not). The first
numeral in cells (a) through (d) shows the payoff for Suspect
A, while the second numeral shows it for Suspect B.
Prisoner’s Dilemma – Payoff Matrix Suspect B
Cooperate Defect

Suspect A (a) -1, -1 (c) -3, 0

Cooperate

(b) 0, -3 (d) -2, -2

Defect

The dominant strategy for a player is one that produces the best
payoff for that player regardless of the strategies employed by
other players. The dominant strategy here is for each player to
defect (i.e., confess) since confessing would minimize the average
length of time spent in prison. Here are the possible outcomes:

 If A and B cooperate and stay mum, both get one year in

prison—as shown in the cell (a).
 If A confesses but B does not, A goes free and B gets three
years—represented in the cell (b).
 If A does not confess but B confesses, A gets three years
and B goes free—see cell (c).
 If A and B both confess, both get two years in prison—as
the cell (d) shows.

So if A confesses, they either go free or get two years in prison.

But if they do not confess, they either get one year or three years
in prison. B faces exactly the same dilemma. Clearly, the best
strategy is to confess, regardless of what the other suspect does.

84
Operation Research: Chapter (2)

Implications of Prisoner’s Dilemma

The prisoner’s dilemma elegantly shows when each individual

pursues their own self-interest, the outcome is worse than if they
had both cooperated. In the above example, cooperation—wherein
A and B both stay silent and do not confess—would get the two
suspects a total prison sentence of two years. All other outcomes
would result in a combined sentence for the two of either three
years or four years.

In reality, a rational person who is only interested in getting the

maximum benefit for themselves would generally prefer to defect,
rather than cooperate. If both choose to defect assuming the other
won't, instead of ending up in the cell (b) or (c) option—like each
of them hoped for—they would end up in the cell (d) position and
each earn two years in prison.

In the prisoner’s example, cooperating with the other suspect

fetches an unavoidable sentence of one year, whereas confessing
would in the best case result in being set free, or at worst fetch a
sentence of two years. However, not confessing carries the risk of
incurring the maximum sentence of three years, if say A’s
confidence that B will also stay mum proves to be misplaced and
B actually confesses (and vice versa).

This dilemma, where the incentive to defect (not cooperate) is so

strong even though cooperation may yield the best results, plays
out in numerous ways in business and the economy, as discussed
below.

85
Operation Research: Chapter (2)

Applications to Business

A classic example of the prisoner’s dilemma in the real world is

encountered when two competitors are battling it out in the
marketplace. Often, many sectors of the economy have two main
rivals. In the U.S., for example, there is a fierce rivalry between
Coca-Cola (KO) and PepsiCo (PEP) in soft drinks and Home
Depot (HD) versus Lowe’s (LOW) in building supplies. This
competition has given rise to numerous case studies in business
schools.2 3 Other fierce rivalries include Starbucks (SBUX) versus
Tim Horton’s (THI) in Canada and Apple (AAPL) versus
Samsung in the global mobile phone sector.

Consider the case of Coca-Cola versus PepsiCo, and assume the

former is thinking of cutting the price of its iconic soda. If it does
so, Pepsi may have no choice but to follow suit for its cola to
retain its market share. This may result in a significant drop in
profits for both companies.

A price drop by either company may thus be construed as

defecting since it breaks an implicit agreement to keep prices high
and maximize profits. Thus, if Coca-Cola drops its price but Pepsi
continues to keep prices high, the former is defecting, while the
latter is cooperating (by sticking to the spirit of the implicit
agreement). In this scenario, Coca-Cola may win market share and
earn incremental profits by selling more colas.

Payoff Matrix

Let’s assume that the incremental profits that accrue to Coca-Cola

and Pepsi are as follows:

86
Operation Research: Chapter (2)

 If both keep prices high, profits for each company

increase by $500 million (because of normal growth
in demand).
 If one drops prices (i.e., defects) but the other does not
(cooperates), profits increase by $750 million for the former
because of greater market share and are unchanged for the
latter.
 If both companies reduce prices, the increase in soft drink
consumption offsets the lower price, and profits for each
company increase by $250 million.

The payoff matrix looks like this (the numbers represent

incremental dollar profits in hundreds of millions):

Coca-Cola vs. PepsiCo –Payoff

Matrix PepsiCo

Cooperate Defect

Coca-Cola Cooperate 500, 500 0, 750

750, 0
Defect 250, 250

Other oft-cited prisoner’s dilemma examples are in areas such

as new product or technology development or advertising and
marketing expenditures by companies.

For example, if two firms have an implicit agreement to

leave advertising budgets unchanged in a given year, their net
income may stay at relatively high levels. But if one defects
and raises its advertising budget, it may earn greater profits at

87
Operation Research: Chapter (2)

the expense of the other company, as higher sales offset the

increased advertising expenses. However, if both companies
boost their advertising budgets, the increased advertising
efforts may offset each other and prove ineffective, resulting
in lower profits—due to the higher advertising expenses—
than would have been the case if the ad budgets were left
unchanged.

Applications to the Economy

The U.S. debt deadlock between the Democrats and

Republicans that springs up from time to time is a classic
example of a prisoner’s dilemma.

Let’s say the utility or benefit of resolving the U.S. debt issue
would be electoral gains for the parties in the next election.
Cooperation in this instance refers to the willingness of both
parties to work to maintain the status quo with regard to the
spiraling U.S. budget deficit. Defecting implies backing away
from this implicit agreement and taking the steps required to
bring the deficit under control.

If both parties cooperate and keep the economy running

smoothly, some electoral gains are assured. But if Party A
tries to resolve the debt issue in a proactive manner, while
Party B does not cooperate, this recalcitrance may cost B
votes in the next election, which may go to A.

However, if both parties back away from cooperation and

play hardball in an attempt to resolve the debt issue, the
consequent economic turmoil (sliding markets, a possible

88
Operation Research: Chapter (2)

credit downgrade, and government shutdown) may result in

lower electoral gains for both parties.

How Can You Use It?

The prisoner’s dilemma can be used to aid decision-making in

a number of areas in one’s personal life, such as buying a car,
salary negotiations and so on.

For example, assume you are in the market for a new car and
you walk into a car dealership. The utility or payoff, in this
case, is a non-numerical attribute (i.e., satisfaction with the
deal). You want to get the best possible deal in terms of price,
car features, etc., while the car salesman wants to get the
highest possible price to maximize his commission.

Cooperation in this context means no haggling; you walk in,

pay the sticker price (much to the salesman’s delight), and
leave with a new car. On the other hand, defecting means
bargaining. You want a lower price, while the salesman wants
a higher price. Assigning numerical values to the levels of
satisfaction, where 10 means fully satisfied with the deal and
0 implies no satisfaction, the payoff matrix is as shown below:
Car Buyer vs. Salesman –Payoff Matrix
Salesman

Cooperate Defect
Buyer
Cooperate (a) 7, 7 (c) 0,10

Defect (b) 10, 0 (d) 3, 3

89
Operation Research: Chapter (2)

What does this matrix tell us? If you drive a hard bargain and
get a substantial reduction in the car price, you are likely to be
fully satisfied with the deal, but the salesman is likely to be
unsatisfied because of the loss of commission (as can be seen
in cell b).

Conversely, if the salesman sticks to his guns and does not

budge on price, you are likely to be unsatisfied with the deal
while the salesman would be fully satisfied (cell c).

Your satisfaction level may be less if you simply walked in

and paid full sticker price (cell a). The salesman in this
situation is also likely to be less than fully satisfied, since
your willingness to pay full price may leave him wondering if
he could have “steered” you to a more expensive model, or
added some more bells and whistles to gain
more commission.

Cell (d) shows a much lower degree of satisfaction for both

buyer and seller, since prolonged haggling may have
eventually led to a reluctant compromise on the price paid for
the car.

Likewise, with salary negotiations, you may be ill-advised to

take the first offer that a potential employer makes to you
(assuming you know that you’re worth more).

Cooperating by taking the first offer may seem like an easy

solution in a difficult job market, but it may result in you
leaving some money on the table. Defecting (i.e., negotiating)
for a higher salary may indeed fetch you a fatter pay package.

90
Operation Research: Chapter (2)

Conversely, if the employer is not willing to pay more, you

may be dissatisfied with the final offer.

Hopefully, the salary negotiations do not turn acrimonious,

since that may result in a lower level of satisfaction for you
and the employer. The buyer-salesman payoff matrix shown
earlier can be easily extended to show the satisfaction level
for the job seeker versus the employer.

The Bottom Line

The prisoner’s dilemma shows us that mere cooperation is not

always in one’s best interests. In fact, when shopping for a
big-ticket item such as a car, bargaining is the preferred
course of action from the consumers' point of view.
Otherwise, the car dealership may adopt a policy of
inflexibility in price negotiations, maximizing its profits but
resulting in consumers overpaying for their vehicles.

Dominant Strategy Solution vs. Nash Equilibrium

Solution: An Overview

Game theory is the science of strategic decision making in

situations that involve more than one actor. These can include
actual games, or real-life situations like military battles,
business interactions, or managerial decisions. According
to game theory, the best strategy for an individual may or may
not be the same depending on the stakes of the game and
given the likely move of the other player involved.

91
Operation Research: Chapter (2)

Sometimes, the best strategy will be the same no matter how

other players act. This is known as the dominant strategy. On
the other hand, there exists the so-called Nash equilibrium,
which does not describe a particular strategy per se, but rather
a sort of mutual understanding-- each player understands the
other player's optimal strategies and takes those into
consideration when optimizing his own strategy.

 According to game theory, the dominant strategy is the

optimal move for an individual regardless of how other
players act.
 A Nash equilibrium describes the optimal state of the
game where both players make optimal moves but now
consider the moves of their opponent.
 A well-known example of where the Nash equilibrium
plays out in game theory is the prisoner's dilemma.

Dominant Strategy Solution

It's possible that a dominant strategy solution is also in Nash

equilibrium, although the underlying principles of a dominant
strategy render Nash analysis somewhat superfluous. In other
words, the cost and benefit incentives don't change based on
other actors.

In the dominant strategy, each player's best strategy is

unaffected by the actions of other players. This renders the
critical assumption of the Nash equilibrium—that each actor
knows the optimal strategy of the other players—possible but
almost pointless.

92
Operation Research: Chapter (2)

Game theory is the science of strategy in situations that

involve more than one actor. This can include actual games,
military battles, business interactions, or managerial
economics.

Nash Equilibrium Solution

The Nash equilibrium is named after John Forbes Nash, Jr.,

who authored a one-page article in 1950 (and a longer follow-
up in 1951) describing a stable-state equilibrium in a multi-
person situation where no participant gains by a change in his
strategy as long as the other participants also remain
unchanged.

In other words, Nash equilibrium takes place when each

player remains in the same position as long as no other player
would take a different action. Each player would be worse off
and, therefore, chooses not to move.

The most famous example of Nash equilibrium is

the prisoner's dilemma. In the prisoner's dilemma, two
criminals are captured and interrogated separately. Even
though each would be best off by not cooperating with police,
each expects the other criminal to confess and reach a plea
deal. Thus, there is a conflict between group rationality and
individual rationality, and each criminal is likely to rat out the
other.

This example has caused some confusion about the Nash

equilibrium. The theory is not used exclusively for situations
where there is a defecting party; the Nash equilibrium can

93
Operation Research: Chapter (2)

exist where all members of a group cooperate or where none

do. In fact, many games can have multiple Nash equilibrium.

In game theory, two or more decision makers, called

players, compete against each other. Each player selects one
of several strategies without knowing in advance the strategy
selected by the other player or players. The combination of
the competing strategies provides the value of the game to the
players. Game theory applications have been developed for
situations in which the competing players are teams,
companies, political candidates, and contract bidders.

In this section, we describe two-person, zero-sum games.

Two-person means that two players participate in the game.
Zero-sum means that the gain (or loss) for one player is equal
to the loss (or gain) for the other player. As a result, the gain
and loss balance out (resulting in a zero-sum) for the game.
What one player wins, the other player loses. Let us
demonstrate a two-person, zero-sum game and its solution by
considering two companies competing for market share.

Competing for Market Share

Suppose that two companies are the only manufacturers of a

particular product; they compete against each other for market
share. In planning a marketing strategy for the coming year,
each company will select one of three strategies designed to
take market share from the other company. The three
strategies, which are assumed to be the same for both
companies, are as follows:
Strategy 1: Increase advertising.

94
Operation Research: Chapter (2)

Strategy 2: Provide quantity discounts.

Strategy 3: Extend warranty.

TABLE 1
PAYOFF TABLE SHOWING THE PERCENTAGE GAIN
IN MARKET SHARE
FOR COMPANY A
Company B
Increase Quantity Extend
Advertising Discounts Warranty
b1 b2 b3
a1 4 3 2
CompanyA a2 -1 4 1
a3 5 -2 0

A payoff table showing the percentage gain in the

market share for Company A for each combination of
strategies is shown in Table 1. Because it is a zero-sum game,
any gain in market share for Company A is a loss in market
share for Company B.

In interpreting the entries in the table, we see that if

Company A increases advertising (a1) and Company B
increases advertising (b1), Company A will come out ahead
with an increase in market share of 4%, while Company B
will have a decrease in market share of 4%. On the other
hand, if Company A provides quantity discounts (a2) and
Company B increases advertising (b1), Company A will lose
1% of market share, while Company B will gain 1% of
market share. Therefore, Company A wants to maximize the
payoff that is its increase in market share. Company B wants
to minimize the payoff because the increase in market share

95
Operation Research: Chapter (2)

for Company A is the decrease in market share for Company

B.

This market-share game meets the requirements of a

two-person, zero-sum game. The two companies are the two
players, and the zero-sum occurs because the gain (or loss) in
market share for Company A is the same as the loss (or gain)
in market share for Company B. Each company will select
one of its three alternative strategies. Because of the planning
horizon, each company will have to select its strategy before
knowing the other company’s strategy. What is the optimal
strategy for each company?

The logic of game theory assumes that each player has

the same information and will select a strategy that provides
the best possible payoff from its point of view. Suppose
Company A selects strategy a1. Market share increases of 4%,
3%, or 2% are possible depending upon Company B’s
strategy. At this point, Company A assumes that Company B
will select the strategy that is best for it. Thus, if Company A
selects strategy a1, Company A assumes Company B will
select its best strategy b3, which will limit Company A’s
increase in market share to 2%. Continuing with this logic,
Company A analyzes the game by protecting itself against the
strategy that may be taken by Company B. Doing so,
Company A identifies the minimum payoff for each of its
strategies, which is the minimum value in each row of the
payoff table. These row minimums are shown in Table 2.

96
Operation Research: Chapter (2)

Considering the entries in the Row Minimum column,

we see that Company A can be guaranteed an increase in
market share of at least 2% by selecting strategy a1. Strategy
a2 could result in a decrease in market share of 1% and
strategy a3 could result in a decrease in market share of 2%.
After comparing the row minimum values, Company A
selects the strategy that provides the maximum of the row
minimum values. This is called a maxim in strategy. Thus,
Company A selects strategy a1 as its optimal strategy; an
increase in market share of at least 2% is guaranteed.

Let us now look at the payoff table from the point of

view of the other player, Company B. The entries in the
payoff table represent gains in market share for Company A,
which

TABLE 2
PAYOFF TABLE WITH ROW MINIMUMS

Company B
b1 b2 b3 Minimum
a1 4 3 2 2 Maximum
Company A a2 - 1 4 1 -1
a3 5 -2 0 -2

correspond to losses in market share for Company B.

Consider what happens if Company B selects strategy b1.
Company B market share decreases of 4%, –1%, and 5% are
possible. Under the assumption that Company A will select
the strategy that is best for it, Company B assumes Company
A will select strategy a3, resulting in a gain in market share of

97
Operation Research: Chapter (2)

5% for Company A and a loss in market share of 5% for

Company B. At this point, Company B analyzes the game by
protecting itself against the strategy taken by Company
[Link] so, Company B identifies the maximum payoff to
Company A for each of its strategies b1, b2, and b3. This
payoff value is the maximum value in each column of the
payoff table. These column maximums are shown in Table 3 a

Considering the entries in the Column Maximum row,

Company B can be guaranteed a decrease in market share of
no more than 2% by selecting the strategy b3. Strategy b1
could result in a decrease in market share of 5% and strategy
b2 could result in a decrease in market share of 4%. After
comparing the column maximum values, Company B selects
the strategy that provides the minimum of the column
maximum values. This is called a minimax strategy. Thus,
Company B selects b3 as its optimal strategy. Company B has
guaranteed that Company A cannot gain more than 2% in
market share.

Identifying a Pure Strategy Solution

If it is optimal for both players to select one strategy and

stay with that strategy regardless of what the other player
does, the game has a pure strategy solution. Whenever the
maximum of the row minimums equals the minimum of the
column maximums, the players cannot improve their payoff
by changing to a different strategy. The game is said to have a

TABLE 3 PAYOFF TABLE WITH COLUMN MAXIMUMS

98
Operation Research: Chapter (2)

Company B
b1 b2 b3 Minimum Row
a1 4 3 2 2 Maximum
CompanyA a2 -1 4 1 -1
a3 5 -2 5 -2
Maximum Column 5 4 2 Minimum

underline point, or an equilibrium point. Thus, a pure strategy

is the optimal strategy for the players. The requirement for a
pure strategy solution is as follows:

A Game Has a Pure Strategy Solution If:

Maximum (Row minimums) = Minimum (Column

maximums)

Because this equality is the case in our example, the

solution to the game is for Company A to increase advertising
(strategy a1) and for Company B to extend the warranty
(strategy b3). Company A’s market share will increase by 2%
and Company B’s market share will decrease by 2%.

With Company A selecting its pure strategy a1, let us

see what happens if Company B tries to change from its pure
strategy b3. Company A’s market share will increase 4% if b1
is selected or will increase 3% if b2 is selected. Company B
must stay with its pure strategy b3 to limit Company A to a
2% increase in market share. Similarly, with Company B
selecting its pure strategy b3, let us see what happens if
Company A tries to change from its pure strategy a1.
Company A’s market share will increase only 1% if a2 is
selected or will not increase at all if a3 is selected. Company

99
Operation Research: Chapter (2)

A must stay with its pure strategy a1 in order to keep its 2%

increase in market share. Thus, even if one of the companies
discovers its opponent’s pure strategy in advance, neither
company can gain any advantage by switching from its pure
strategy.

If a pure strategy solution exists, it is the optimal

solution to the game. The following steps can be used to
determine when a game has a pure strategy solution and to
identify the optimal pure strategy for each player:

Step 1. Compute the minimum payoff for each row (Player

A).
Step 2. For Player A, select the strategy that provides the
maximum of the row minimums.
Step3. Compute the maximum payoff for each column (Player
B).
Step 4. For Player B, select the strategy that provides the
minimum of the column maximums.
Step 5. If the maximum of the row minimums is equal
to the minimum of the column maximums, this value
is the value of the game and a pure strategy solution
exists. The optimal pure strategy for Player A is
identified in Step 2, and the optimal pure strategy for
Player B is identified in Step 4.

If the maximum of the row minimums does not equal

the minimum of the column maximums, a pure strategy
solution does not exist. In this case, a mixed strategy solution
becomes optimal. In the following discussion, we define a

100
Operation Research: Chapter (2)

mixed strategy solution and show how linear programming

can be used to identify the optimal mixed strategy for each
player.

Identifying a Mixed Strategy Solution

Let us continue with the two-company market-share game and

consider a slight modification in the payoff table as shown in
Table 4. Only one payoff has changed. If both Company A
and Company B choose the extended warranty strategy, the
payoff to Company A is now a 5% increase in market share
rather than the previous 0%. The row minimums donot
change, but the column maximums do. Note that the column
maximum for strategy b3 is 5% instead of the previous 2%.
TABLE 4
MODIFIED PAYOFF TABLE SHOWING THE PERCENTAGE GAIN IN
MARKET SHARE FOR COMPANY A

Company B
b1 b2 b3 Minimum Row
a1 4 3 2 2 Maximum
Company A a2 - 1 4 1 -1
a3 5 -2 5 -2
Column Maximum 5 4 Minimum 5

In analyzing the game to determine whether a pure

strategy solution exists, we find that the maximum of the row
minimums is 2% while the minimum of the row maximums is
4%. Because these values are not equal, a pure strategy
solution does not exist. In this case, it is not optimal for each
company to be predictable and select a pure strategy

101
Operation Research: Chapter (2)

regardless of what the other company does. The optimal

solution is for both players to adopt a mixed strategy.

With a mixed strategy, each player selects its strategy

according to a probability distribution. In the market share
example, each company will first determine an optimal
probability distribution for selecting whether to increase
advertising, provide quantity discounts, or extend warranty.
Then, when the game is played, each company will use its
probability distribution to randomly select one of its three
strategies.

First, consider the game from the point of view of

Company A. Company A will select one of its three strategies
based on the following probabilities:

PA= the probability that Company A selects strategy a1

PA2 = the probability that Company A selects strategy a2
PA3 = the probability that Company A selects strategy a3

Using these probabilities for Company A’s mixed

strategy, what happens if Company B selects strategy b1?
Using the payoffs in the b1 column of Table 5.8, we see
Company A will experience an increase in market share of
4% with probability PA1, a decrease in market share of 1%
with probability PA2, and an increase in market share of 5%
with probability PA3. Weighting each payoff by its
probability and summing provides the expected value of the
increase in market share for Company A. If Company B
selects strategy b1, this expected value, referred to as the
expected gain if strategy b1 is selected, can be written

102
Operation Research: Chapter (2)

as follows:

EG(b1) = 4PA1 – 1PA2 = 5PA3

The expression for the expected gain in market share for

Company A for each Company B strategy is provided in
Table 5.
TABLE 5
EXPECTED GAIN IN MARKET SHARE FOR COMPANY A FOR EACH
COMPANY B STRATEGY

Company B Strategy Expected Gain for Company A

b1 EG(b1) = 4PA1 - 1PA2 + 5PA3
b2 EG(b2) = 3PA1 + 4PA2 - 2PA3
b3 EG(b3) =2PA1 + 1PA2 +5PA3

EG(b1) = 4PA1 - 1PA2 ) + 5PA3 = 4(1⁄₃) - 1(1⁄₃) + 5(1⁄₃) = ⁸⁄₃

= 2.67
EG(b2) = 3PA1 + 4PA2 - 2PA3 = 3(1⁄₃) + 4(1⁄₃) – 2(1⁄₃) = ⁵⁄₃ =
1.67
EG(b3) = 2PA1 - 1PA2 + 5PA3 = 2(1⁄₃) +1(1⁄₃) + 5(1⁄₃) = ⁸⁄₃
= 2.67

The logic of game theory assumes that if Company A

uses a mixed strategy, Company B will select the strategy that
will minimize Company A’s expected gain. Using these
results, Company A assumes Company B will select strategy
b2 and limit Company A’s expected gain in market share to
1.67%. Because Company A’s pure strategy a1 provides a 2%
increase in market share, the mixed strategy with equal

103
Operation Research: Chapter (2)

probabilities, PA1 = 1⁄3, PA2 = 1⁄3, and PA3 = 1⁄3, is not the
optimal strategy for Company A.
Let us show how Company A can use linear
programming to find its optimal mixed strategy. Our goal is to
find probabilities, PA1, PA2, and PA3, that maximize the
expected gain in market share for Company A regardless of
the strategy selected by Company B. In effect, Company A
will protect itself against any strategy selected by Company B
by being sure its expected gain in market share is as large as
possible even if Company B selects its own optimal strategy.

Given the probabilities PA1, PA2, and PA3 and the

expected gain expressions in Table 5.9, game theory assumes
that Company B will select a strategy that provides the
minimum expected gain for Company A. Thus, Company B
will select b1, b2, or b3 based on

Min {EG(b1), EG(b2), EG(b3)}

When Company B selects its strategy, the value of

the game will be the minimum expected gain. This
strategy will minimize Company A’s expected gain in
market share.

Company A will select its optimal mixed strategy using a

maxim in strategy, which will maximize the minimum
expected gain. This objective is written as follows :

104
Operation Research: Chapter (2)

Max [Min {EG(b1) , EG(b2), EG(b3)}]

Company A seeks to maximize the

minimum EG Company B can obtain
Company B will select a strategy
to minimize the EG for Company A

Define GAINA to be the optimal expected gain in

market share for Company A. Because Company B will select
a strategy that minimizes this expected gain, we know GAINA
is equal to Min {EG(b1), EG(b2), EG(b3)}. Thus, the
individual expected gains, EG(b1), EG(b2), and EG(b3), must
all be greater than or equal to GAINA. If Company B selects
strategy b1, we know

EG(b1) > GAINA

Using the probabilities PA1, PA2, and PA3 and the

expected gain expression in Table 5.9, this condition can be
written as follows :

4PA1 – 1PA2 + 5PA3 > GAINA

Similarly, for Company B strategies b2 and b3, the fact

that both EG(b2) > GAINA and EG(b3) > GAINA provides the
following two expressions:

3PA1 + 4PA2 – 2PA3 = GAINA

2PA1 + 1PA2 + 5PA3 = GAINA

105
Operation Research: Chapter (2)

In addition, we know that the sum of the Company A’s mixed

strategy probabilities must equal 1.
PA1 + PA2 + PA3 = 1

Finally, realizing that the objective of Company A is to

maximize its expected gain, GAINA, we have the following
linear programming model. Solving this linear program will
provide Company A’s optimal mixed strategy.

Max GAINA
s.t. Company B strategy

2PA1 + 1PA2 + 5PA3 ‫ ع‬GAINA > (Strategy b1)

3PA1 + 4PA2 - 2PA3 ‫ ع‬GAINA > (Strategy b2)
4PA1 - 1PA2 + 5PA3 ‫ ع‬GAINA > (Strategy b3)
PA1 + PA2 + PA3 =1
PA1, PA2, PA3, GAINA > 0

The solution of Company A’s linear program is shown in

Figure 5.8.

From Figure 4, we see Company A’s optimal mixed

strategy is to increase advertising (a1) with a probability of
0.875 and extend warranty (a3) with a probability of 0.125.
Company A should never provide quantity discounts (a2)
because PA2 = 0. The expected value of this mixed strategy is
a 2.375% increase in market share for Company A.

106
Operation Research: Chapter (2)

Let us show what happens to the expected gain if

Company A uses this optimal mixed strategy. Company A’s
expected gain for each Company B strategy follows:

EG(b1)
= 4PA1- 1PA2 + 5PA3 = 4(0.875) - 1(0) + 5(0.125)
= 4.125
EG(b2)
= 3PA1 + 4PA2 - 2PA3 = 3(0.875) + 4(0) - 2(0.125) =2.375
EG(b3)
= 2PA1 + 1PA2 + 5PA3 = 2(0.875) + 1(0) + 5(0.125)
= 2.375
Company B will minimize Company A’s expected gain by
selecting either strategy b2 or b3. However, Company A has
selected its optimal mixed strategy by maximizing this:
FIGURE 6
THE SOLUTION FOR COMPANY A’S OPTIMAL MIXED STRATEGY

Optimal ObjectiveValue = 2.37500

Variable Value Reduced Costs
-------------- --------------- -----------------
PA1 0.87500 0.00000
PA2 0.00000 -0.25000
PA3 0.12500 0.00000
GAINA 2.37500 0.00000

Constraint Slack/Surplus Dual Value

-------------- --------------- -----------------
1 1.75000 0.00000
2 0.00000 -0.37500
3 0.00000 -0.62500
4 0.00000 2.37500

107
Operation Research: Chapter (2)

minimum expected gain. Thus, Company A obtains an

expected gain in market share of 2.375% regardless of the
strategy selected by Company B. The mixed strategy with
PA1 = 0.875, PA2 = 0.0, and PA3 = 0.125 is the optimal
strategy for Company A. The expected gain of 2.375% is
better than Company A’s best pure strategy (a1), which
provides a 2% increase in market share.

Now consider the game from the point of view of

Company B. Company B will select one of its strategies based
on the following probabilities:

PB1 = the probability that Company B selects strategy b1

PB2 = the probability that Company B selects strategy b2
PB3 = the probability that Company B selects strategy b3

Based on these probabilities for Company B’s mixed

strategy, what happens if Company A selects strategy a1?
Using the payoffs in the a1 row of Table 5.8, Company B will
experience a decrease in market share of 4% with probability
PB1, a decrease in market share of 3% with probability PB2,
and a decrease in market share of 2% with probability PB3. If
Company A selects strategy a1, the expected value, referred
to as Company B’s expected loss if strategy a1 is selected, can
be written as follows:

EL(a1) = 4PB1 + 3PB2 +2PB3

The expression for the expected loss in market share for

Company B for each Company A strategy is provided in
Table 6.

108
Operation Research: Chapter (2)

Let us show how Company B can use linear

programming to find its optimal mixed strategy. Our goal is to
find the probabilities, PB1, PB2, and PB3, that minimize the
expected loss in market share to Company B regardless of the
strategy selected by Company A. In effect, Company B will
protect itself from any strategy selected by Company A by
being sure its expected loss in market share is as small as
possible even if Company A selects its own optimal strategy.
TABLE 6
EXPECTED LOSS IN MARKET SHARE FOR COMPANY B FOR EACH
COMPANY A STRATEGY

Company A Strategy Expected Loss for Company B

a1 4PB1 + 3PB2 + 2PB3
a2 -1PB1 + 4PB2 + 1PB3
a3 5PB1 - 2PB2 + 5PB3

Given the probabilities PB1, PB2, and PB3 and the

expected loss expressions in Table 5.10, game theory assumes
that Company A will select a strategy that provides the
maximum expected loss for Company B. Thus, Company A
will select a1, a2, or a3 based on

Max {EL(a1), EL(a2), EL(a3)}

When Company A selects its strategy, the value of the

game will be the expected loss, which will maximize
Company B’s expected loss in market share.

109
Operation Research: Chapter (2)

Company B will select its optimal mixed strategy using a

minimax strategy to minimize the maximum expected loss.
This objective is written as follows :

Min [Max {EL(a1), EL(a2), EL(a3)}]

Company B seeks to maximize the

minimum EL Company A can obtain
Company A will select a strategy
to minimize the EL for Company B

Define LOSSB to be the optimal expected loss in market

share for Company B. Because Company A will select a
strategy that maximizes this expected loss, we know
LOSSB is equal to Max {EL(a1), EL(a2), EL(a3)}. Thus,
the individual expected losses, EL(a1), EL(a2), and EL(a3),
must all be less than or equal to LOSSB. If Company A
selects strategy, a1, we know

EL(a1) < LOSSB

Using the probabilities PB1, PB2, and PB3 and the

expected loss expression for EL(a1) in Table 5.10, this
condition can be written as follows :

4PB1+ 3PB2 + 2PB3< LOSSB

Similarly, for Company A strategies a2 and a3, the fact
that both EL(a2) < LOSSB and EL(a3) < LOSSB provides the
following two expressions:

110
Operation Research: Chapter (2)

– 1PB1 + 4PB2 + 1PB3 < LOSSB

5PB1 – 2PB2 + 5PB3 < LOSSB
In addition, we know that the sum of the Company B’s
mixed strategy probabilities must equal 1.

PB1 + PB2 + PB3 = 1

FIGURE 7
THE SOLUTION FOR COMPANY B’S OPTIMAL MIXED STRATEGY

Optimal Objective Value = 2.37500

Variable Value Reduced Cost
-------------- --------------- -----------------
PB1 0.00000 1.75000
PB2 0.37500 0.00000
PB3 0.62500 0.00000
LOSSB 2.37500 0.00000

Constraint Slack/Surplus Dual Value

-------------- --------------- -----------------
1 0.00000 2.37500
2 0.00000 -0.87500
3 0.25000 0.00000
4 0.00000 -0.12500

Finally, realizing that the objective of Company B is to

minimize its expected loss, LOSSB, we have the following
linear programming model. Solving this linear program will
provide Company B’s optimal mixed strategy.

Min LOSSB
s.t. Company A strategy
4PB1 + 3PB2 + 2PB3 < LOSSB (Strategy a1)

111
Operation Research: Chapter (2)

-1PB1 + 4PB2 + 1PB3 < LOSSB (Strategy a2)

5PB1 - 2PB2 + 5PB3 < LOSSB (Strategy a3)
PB1 + PB2 + PB3 =1
PB1, PB2, PB3, LOSSB > 0

The solution of Company B’s linear program is shown in

Figure 7.
From Figure 8, we see Company B’s optimal mixed
strategy is to provide quantity discounts (b2) with a
probability of 0.375 and extend warranty (b3) with a
probability of 0.625. Company B should not increase
advertising (b1), because PB1 = 0. The expected value or
expected loss of this mixed strategy is 2.375%. Note that the
expected loss of 2.375% of the market share for Company B
is the same as the expected gain in market share for Company
A. The mixed strategy solution shows the zero-sum for the
expected payoffs.

Let us show what happens to the expected loss if

Company B uses this optimal mixed strategy. Company B’s
expected loss for each Company A strategy follows:

EL(a1)
= 4PB1 + 3PB2 + 2PB3 = 4(0) + 3(0.375) + 2(0.625) = 2.375
EL(a2)
= -1PB1 + 4PB2 + 1PB3 = -1(0) + 4(0.375) + 1(0.625) = 2.125
EL(a3)
= 5PB1 - 2PB2 + 5PB3 = 5(0) - 2(0.375) + 5(0.625) =2.375

Company A will maximize Company B’s expected loss by

selecting either strategy a1 or a3. However, Company B has

112
Operation Research: Chapter (2)

selected its optimal mixed strategy by minimizing this

maximum expected loss. Thus, Company B obtains an
expected loss in market share of 2.375% regardless of the
strategy selected by Company A. The mixed strategy with
PB1 = 0.0, PB2 = 0.375, and PB3 = 0.625 is the optimal
strategy for Company B. The expected loss of 2.375% is
better than Company B’s best pure strategy (b2), which
provides a 4% loss in market share.

The optimal mixed strategy solution with a value of

2.375% is an equilibrium solution. Given Company A’s
mixed strategy probabilities, Company B cannot improve the
value of the game by changing PB1, PB2, or PB3. Likewise,
given Company B’s mixed strategy probabilities, Company A
cannot improve the value of the game by changing PA1, PA2,
or PA3. In general, the solution to the linear program will
provide an equilibrium optimal mixed strategy solution for the
game.

Let us conclude this linear programming application by

making some observations and suggestions about using linear
programming to solve mixed strategy two-person, zero-sum
games. First of all, consider the dual value for constraint 2 in
the solution of the Company A linear program in Figure 5.8.
This dual value is =0.375. Recall that constraint
2 provides Company A’s expected gain if Company B selects
strategy b2. The absolute value of the dual value is Company
B’s optimal probability for this strategy. Thus, we know PB2
=0.375 without having to solve the Company B linear
program. Using the absolute value of the dual values for the

113
Operation Research: Chapter (2)

Company A linear program in Figure 5.8, we know that the

optimal mixed strategy solution for Company B is PB1 = 0.0,
PB2 = 0.375, and PB3= 0.625. Therefore, when a two-person,
zero-sum game has a mixed strategy, we only need to solve
the linear program for one of the players. The optimal mixed
strategy for the other player can be found by using the
absolute value of the dual values.

Finally, note that a nonnegativity constraint in the linear

program for Company A requires the value of the game,
GAINA, to be greater than or equal to 0. A similar
nonnegativity constraint in the linear program for Company B
requires the value of the game, LOSSB, to be greater than or
equal to 0. Because the value of the game in our example was
2.375%, we met these nonnegativity requirements. However,
consider a two-person, zero sum game where the payoff table
contains several negative payoffs for player A. It may turn out
that when player A selects an optimal mixed strategy, a
negative value of the game is the best the player can do. In
this case GAINA and LOSSB would be negative, which causes
the linear program to have an infeasible solution.

If this condition exists or may exist, the following

strategy can be used to modify the game and ensure that the
linear program has a feasible solution. Define a constant c as
follows:

If this condition exists or may exist, the following

strategy can be used to modify the game and ensure that the

114
Operation Research: Chapter (2)

linear program has a feasible solution. Define a constant c as

follows:

c = the absolute value of the largest negative payoff for player

A

A revised payoff table can be created by adding c to

each payoff, turning it into an equivalent two-person, zero-
sum game. Because the revised payoff table contains no
negative payoffs, the nonnegativity constraint for the value of
the game will be satisfied and a feasible solution will exist for
the linear program. More importantly, the optimal mixed
strategy using the revised payoffs will be the same as the
optimal mixed strategy for the original game. By subtracting c
from the optimal objective function value for the game with
the revised payoffs, you will obtain the objective function
value for the original game.

1. The analysis of a two-person, zero-sum game

begins with checking to see whether a pure strategy solution
exists. If the maximum of the row minimums for player A,
VA, is not equal to the minimum the column maximums for
player B, VB, a pure strategy solution does not exist. At this
point, we can also conclude that a mixed strategy solution is
optimal and that the value of the game will be between VA
and VB. For example, in our mixed strategy market-share
game, the maximum of the row minimums was 2% and the
minimum of the column maximums was 4%. Thus, we can
conclude that a mixed strategy solution exists and that the

115
Operation Research: Chapter (2)

value of the game is between 2% and 4%. We would know

this result before solving the mixed strategy linear program.

If the maximum of the row minimums, VA, is positive

and the minimum of the column maximums, VB, is positive,
we know that the value of the mixed strategy game will be
positive. In this case, it is not necessary to revise the payoff
table by the constant c to obtain a feasible linear programming
solution. However, if one or both VA and VB are negative, the
value of the mixed strategy game can be negative. In this case,
it is desirable to revise the payoff table by adding the constant
c to all payoffs prior to solving the linear program.

2. The linear programming formulation presented in

this section used nonnegativity constraints GAINA > 0 and
LOSSB > 0 so that the two persons, mixed strategy game
could be solved with traditional linear programming software.
If you are using software such as LINGO or Excel, these
variables do not have to be nonnegative. In this case,
eliminate the nonnegative requirements and make GAINA and
LOSSB unrestricted in sign. This treatment guarantees that the
linear program will have a feasible solution and eliminates the
need to add a constant to the payoffs in situations where
GAINA and LOSSB may be negative.

116