Introduction to
Game Theory
Yale Braunstein
Spring 2007
General approach
Brief History of Game Theory
Payoff Matrix
Types of Games
Basic Strategies
Evolutionary Concepts
Limitations and Problems
Brief History of Game Theory
1913 - E. Zermelo provides the first
theorem of game theory; asserts that
chess is strictly determined
1928 - John von Neumann proves the
minimax theorem
1944 - John von Neumann & Oskar
Morgenstern write "Theory of Games
and Economic Behavior
1950-1953 - John Nash describes Nash
equilibrium
Rationality
Assumptions:
humans are rational beings
humans always seek the best
alternative in a set of possible choices
Why assume rationality?
narrow down the range of possibilities
predictability
Utility Theory
Utility Theory based on:
rationality
maximization of utility
may not be a linear function of
income or wealth
It is a quantification of a person's
preferences with respect to certain
objects.
What is Game Theory?
Game theory is a study of how to
mathematically determine the best
strategy for given conditions in order
to optimize the outcome
Game Theory
Finding acceptable, if not optimal,
strategies in conflict situations.
Abstraction of real complex
situation
Game theory is highly mathematical
Game theory assumes all human
interactions can be understood and
navigated by presumptions.
Why is game theory important?
All intelligent beings make decisions all the
time.
AI needs to perform these tasks as a result.
Helps us to analyze situations more rationally
and formulate an acceptable alternative with
respect to circumstance.
Useful in modeling strategic decision-making
Games against opponents
Games against "nature
Provides structured insight into the value of
information
Types of Games
Sequential vs. Simultaneous
moves
Single Play vs. Iterated
Zero vs. non-zero sum
Perfect vs. Imperfect information
Cooperative vs. conflict
Zero-Sum Games
The sum of the payoffs remains
constant during the course of the
game.
Two sides in conflict
Being well informed always helps
a player
Non-zero Sum Game
The sum of payoffs is not constant
during the course of game play.
Players may co-operate or compete
Being well informed may harm a
player.
Games of Perfect Information
The information concerning an
opponents move is well known in
advance.
All sequential move games are of this
type.
Imperfect Information
Partial or no information concerning
the opponent is given in advance to
the players decision.
Imperfect information may be
diminished over time if the same
game with the same opponent is to
be repeated.
Key Area of Interest
chance
strategy
Matrix Notation
(Column) Player II
Strategy A Strategy B
Strategy A (P1, P2) (P1, P2)
(Row) Player I
Strategy B (P1, P2) (P1, P2)
Notes: Player I's strategy A may be different from
Player II's.
P2 can be omitted if zero-sum game
Prisoners Dilemma &
Other famous games
A sample of other games:
Marriage
Disarmament (my generals are
more irrational than yours)
Prisoners Dilemma
NCE
Notes: Higher payoffs (longer sentences) are bad.
Non-cooperative equilibrium Joint maximum
Jt.
max.
Institutionalized solutions (a la criminal organizations,
Games of Conflict
Two sides competing against each
other
Usually caused by complete lack of
information about the opponent or
the game
Characteristic of zero-sum games
Games of Co-operation
Players may improve payoff through
communicating
forming binding coalitions &
agreements
do not apply to zero-sum games
Prisoners Dilemma
with Cooperation
Prisoners Dilemma with Iteration
Infinite number of iterations
Fear of retaliation
Fixed number of iteration
Domino effect
Basic Strategies
1. Plan ahead and look back
2. Use a dominating strategy if
possible
3. Eliminate any dominated
strategies
4. Look for any equilibrium
5. Mix up the strategies
Plan ahead and look back
If you have a dominating
strategy,
use it
Use
strategy 1
Eliminate any dominated
strategy
Eliminate
strategy 2 as
its dominated
by strategy 1
Look for any
equilibrium
Dominating Equilibrium
Minimax Equilibrium
Nash Equilibrium
Maximin & Minimax Equilibrium
Minimax - to minimize the maximum
loss (defensive)
Maximin - to maximize the minimum
gain (offensive)
Minimax = Maximin
Maximin & Minimax
Equilibrium Strategies
Definition: Nash Equilibrium
If there is a set of strategies with the
property that no player can benefit
by changing her strategy while the
other players keep their strategies
unchanged, then that set of
strategies and the corresponding
payoffs constitute the Nash
Equilibrium.
Source: http://www.lebow.drexel.edu/economics/mccain/game/game.html
Is this a Nash Equilibrium?
Boxed Pigs Example
Cost to press When button is pressed,
button = 2 units food given = 10 units
Decisions, decisions...
Time for "real-life" decision
making
Holmes & Moriarity in "The Final Problem"
What would you do
If you were Holmes?
If you were Moriarity?
Possibly interesting digressions?
Why was Moriarity so evil?
What really happened?
What do we mean by reality?
What changed the reality?
Mixed Strategy
Mixed Strategy Solution
Probability
Value in of being Expected
Safe Guarded Loss
Safe 1 $ 10,000 1 / 11 $ 9,091
Safe 2 $ 100,000 10 / 11 $ 9,091
Both $ 110,000
The Payoff Matrix
for Holmes &Player
Moriarity
#2
Strategy #1 Strategy #2
P
l Strategy #1
a
Payoff (1,1) Payoff (1,2)
y
e
r
Strategy #2
# Payoff (2,1) Payoff (2,2)
1
Where is game theory
currently used?
Ecology
Networks
Economics
Limitations & Problems
Assumes players always maximize
their outcomes
Some outcomes are difficult to
provide a utility for
Not all of the payoffs can be
quantified
Not applicable to all problems
Summary
What is game theory?
Abstraction modeling multi-person
interactions
How is game theory applied?
Payoff matrix contains each persons
utilities for various strategies
Who uses game theory?
Economists, Ecologists, Network people,...
How is this related to AI?
Provides a method to simulate a thinking
agent
Sources
Much more available on the web.
These slides (with changes and additions)
adapted from:
http://pages.cpsc.ucalgary.ca/~jacob/Courses/Winter2000/CPSC533/Pa
ges/index.html
Three interesting classics:
John von Neumann & Oskar Morgenstern, Theory
of Games & Economic Behavior (Princeton, 1944).
John McDonald, Strategy in Poker, Business & War
(Norton, 1950)
Oskar Morgenstern, "The Theory of Games,"
Scientific American, May 1949; translated as
"Theorie des Spiels," Die Amerikanische
Rundschau, August 1949.
