Transcript CHT. 5 DATABASE MANAGEMENT

Chapter 12 & Module E
Decision Theory
&
Game Theory
Decision Making
A
decision is made for a future action.
 A decision making process is a process
of “selection” : Selecting one from
many options (alternatives) as the
decision.
Decision Theory
 Decision
theory deals with following type
of decision making problems:
– The outcome for an decision alternative is not
certain, which is affected by some factors that
are not controlled by the decision maker.
– Example: Selecting a stock for investment.
Components of Decision
Making (D.M.)
 Decision
alternatives - for managers to
choose from.
 States of nature - that may actually occur
in the future regardless of the decision.
 Payoff - outcome of a decision alternative
under a state of nature.
The components are given in Payoff Tables.
A Decision Table
Investment
decision
alternatives
Apartment
Office
Warehouse

States of Nature
Economy
Economy
good
bad
0.6
0.4
$ 50,000
$ 30,000
100,000
- 40,000
30,000
10,000
Criterion:Expected Payoff
 Select
the alternative that has the largest
expected value of payoffs.
 Expected payoff of an alternative:
n
  Vi * Pi
i 1
n=number of states of nature
Pi=probability of the i-th state of nature
Vi=payoff of the alternative under the i-th state of
nature
Example
Econ
Good
0.6
Econ
Bad
0.4
Apartment 50,000
30,000
Decision
Alt’s
Office
100,000 -40,000
Warehouse 30,000
10,000
Expected payoff
Expected Value of Perfect
Information (EVPI)
 It
is a measure of the value of
additional information on states of
nature.
 It tells up to how much you would pay
for additional information.
An Example
If a consulting firm offers to provide “perfect
information about the future with $5,000, would
you take the offer?
States of Nature
Investment
Economy
Economy
decision
good
bad
alternatives
0.6
0.4
Apartment
$ 50,000
$ 30,000
Office
100,000
- 40,000
Warehouse
30,000
10,000
Calculating EVPI
 EVPI

= EVwPI – EVw/oPI
= (Exp. payoff with perfect information) –
(Exp. payoff without perfect information)
Expected payoff with Perfect
Information
 EVwPI

n
h
i
Pi
i 1
where n=number of states of nature
hi=highest payoff of i-th state of nature
Pi=probability of i-th state of nature
Example for Expected payoff with
Perfect Information
Investment
decision
alternatives
Apartment
Office
Warehouse
hi
States of Nature
Economy
Economy
good
bad
0.6
0.4
$ 50,000
$ 30,000
100,000
- 40,000
30,000
10,000
100,000
30,000
Expected payoff with perfect information
= 100,000*0.6+30,000*0.4 = 72,000
Expected payoff without
Perfect Information
Expected
payoff of the best
alternative selected without using
additional information. i.e.,
EVw/oPI = Max Exp. Payoff
Example for Expected payoff without
Perfect Information
Decision
Alt’s
Econ
Good
0.6
Apartment 50,000
*Office
Econ
Bad
0.4
30,000
100,000 -40,000
Warehouse 30,000
10,000
Expected payoff
42,000
*44,000
22,000
Expected Value of Perfect Information
(EVPI) in above Example
 EVPI
= EVwPI – EVw/oPI
= 72,000 - 44,000
= $28,000
EVPI is a Benchmark in Bargain
 EVPI
is the maximum $ amount the
decision maker would pay to
purchase perfect information.
Value of Imperfect Information
Expected value of imperfect information
= (discounted EVwPI) – EVw/oPI
= (EVwPI * (% of perfection)) – EVw/oPI
Game Theory
 Game
theory is for decision making
with two decision makers of
conflicting interests in competition.
 In decision theory: Human vs. God.
 In game theory: Human vs. Human.
Two-Person Zero-Sum Game
 Two
decision makers’ benefits are
completely opposite
i.e., one person’s gain is another person’s loss
 Payoff/penalty
table (zero-sum table):
– shows “offensive” strategies (in rows) versus
“defensive” strategies (in columns);
– gives the gain of row player (loss of column
player), of each possible strategy encounter.
Example 1 (payoff/penalty table)
Athlete
Strategies
(row strat.)
1
2
A
Manager’s Strategies
(Column Strategies)
B
C
$50,000
$60,000
$35,000
$40,000
$30,000
$20,000
Two-Person Constant-Sum
Game
 For
any strategy encounter, the row
player’s payoff and the column player’s
payoff add up to a constant C.
 It can be converted to a two-person zerosum game by subtracting half of the
constant (i.e. 0.5C) from each payoff.
Example 2 (2-person, constantsum)
During the 8-9pm time slot, two
broadcasting networks are vying for an
audience of 100 million viewers, who
would watch either of the two networks.
Payoffs of nw1 for the constantsum of 100(million)
Network 1
western
soap
comedy
Network 2
western Soap
Comedy
35
45
38
15
58
14
60
50
70
An equivalent zero-sum table
Network 1
western
soap
comedy
Network 2
western Soap
Comedy
-15
- 5
-12
-35
8
-36
10
0
20
Equilibrium Point
 In
a two-person zero-sum game, if there
is a payoff value P such that
P
=
max{row minimums}
=
min{column maximums}
then P is called the equilibrium point, or
saddle point, of the game.
Example 3 (equilibrium point)
Athlete
Strategies
(row strat.)
1
2
A
Manager’s Strategies
(Column Strategies)
B
C
$50,000
$60,000
$35,000
$40,000
$30,000
$20,000
Game with an Equilibrium
Point: Pure Strategy
 The
equilibrium point is the only rational
outcome of this game; and its
corresponding strategies for the two sides
are their best choices, called pure strategy.
 The value at the equilibrium point is called
the value of the game.
 At the equilibrium point, neither side can
benefit from a unilateral change in strategy.
Pure Strategy of Example 3
Athlete
Strategies
(row strat.)
1
2
A
Manager’s Strategies
(Column Strategies)
B
C
$50,000
$60,000
$35,000
$40,000
$30,000
$20,000
Example 4 (2-person, 0-sum)
Row
Players
Strategies
1
2
3
Column Player Strategies
1
2
3
4
4
10
2
3
1
6
5
7
Mixed Strategy
If
a game does not have an
equilibrium, the best strategy
would be a mixed strategy.
Game without an Equilibrium
Point
A
player may benefit from unilateral
change for any pure strategy. Therefore,
the game would get into a loop.
 To break loop, a mixed strategy is
applied.
Example:
Company I
Strategies
2
3
Company II Strategies
B
C
8
4
1
7
Mixed Strategy
A
mixed strategy for a player is a set of
probabilities each for an alternative of
the player.
 The expected payoff of row player (or
the expected loss of column player) is
called the value of the game.
Example:
Company I
Company II Strategies
Strategies
B
C
2
8
4
3
1
7
Let mixed strategy for company I be
{0.6, 0.4}; and for Company II be
{0.3, 0.7}.
Equilibrium Mixed Strategy
 An
equilibrium mixed strategy
makes expected values of any
player’s individual strategies
identical.
 Every game contains one
equilibrium mixed strategy.
 The equilibrium mixed strategy is
the best strategy.
How to Find Equilibrium Mixed
Strategy
By linear programming (as introduced
in book)
 By QM for Windows, – we use this
approach.

Both Are Better Off at
Equilibrium
 At
equilibrium, both players are
better off, compared to maximin
strategy for row player and minimax
strategy for column player.
 No player would benefit from
unilaterally changing the strategy.
A Care-Free Strategy
 The
row player’s expected gain remains
constant as far as he stays with his mixed
strategy (no matter what strategy the
column player uses).
 The column player’s expected loss
remains constant as far as he stays with
his mixed strategy (no matter what
strategy the row player uses).
Unilateral Change from
Equilibrium by Column Player
probability
0.6
0.4
Strat 2
Strat 3
0.1
B
8
1
0.9
C
4
7
Unilateral Change from
Equilibrium by Column Player
probability
0.6
0.4
Strat 2
Strat 3
1.0
B
8
1
0
C
4
7
Unilateral Change from
Equilibrium by Row Player
probability
0.2
0.8
Strat 2
Strat 3
0.3
B
8
1
0.7
C
4
7
A Double-Secure Strategy
 At
the equilibrium, the expected gain
or loss will not change unless both
players give up their equilibrium
strategies.
– Note: Expected gain of row player is always
equal to expected loss of column player,
even not at the equilibrium, since 0-sum)
Both Leave Their Equilibrium
Strategies
probability
0.5
0.5
Strat 2
Strat 3
0.8
B
8
1
0.2
C
4
7
Both Leave Their Equilibrium
Strategies
probability
0.2
0.8
Strat 2
Strat 3
0
B
8
1
1
C
4
7
Penalty for Leaving
Equilibrium
 It
is equilibrium because it discourages
any unilateral change.
 If a player unilaterally leaves the
equilibrium strategy, then
– his expected gain or loss would not change,
and
– once the change is identified by the
competitor, the competitor can easily beat
the non-equilibrium strategy.
Find the Equilibrium Mixed
Strategy
 Method
1: As on p.573-574 of our text
book. The method is limited to 2X2 payoff
tables.
 Method 2: Linear programming. A general
method.
 Method we use: Software QM.
Implementation of a Mixed
Strategy
 Applied
in the situations where the mixed
strategy would be used many times.
 Randomly select a strategy each time
according to the probabilities in the
strategy.
 If you had good information about the
payoff table, you could figure out not only
your best strategy, but also the best strategy
of your competitor (!).
Dominating Strategy vs.
Dominated Strategy
 For
row strategies A and B: If A has a
better (larger) payoff than B for any column
strategy, then B is dominated by A.
 For column strategies X and Y: if X has a
better (smaller) payoff than Y for any row
strategy, then Y is dominated by X.
 A dominated decision can be removed from
the payoff table to simplify the problem.
Example:
Company I
Strategies
1
2
3
Company II Strategies
A
B
C
9
7
2
11
8
4
4
1
7
Find the Optimal Mixed
Strategy in 2X2 Table
 Suppose
row player has two strategies, 1
and 2, and column player has two
strategies, A and B.
For row player:
 Let
p be probability of selecting row
strategy 1. Then the probability of
selecting row strategy 2 is (1-p).
 Represent EA and EB by p, where EA (EB)
is the expected payoff of the row player if
the column player chose column strategy
A (B).
 Set EA = EB , and solve p from the
equation.
For column player:
 Let
p be probability of selecting column
strategy A. Then the probability of
selecting column strategy B is (1-p).
 Represent E1 and E2 by p, where E1 (E2)
is the expected payoff of the row player if
the column player chose column strategy
A (B).
 Set E1 = E2 , and solve p from the
equation.