First Class On Game Theory

Introduction: Noncooperative Games Dominant
and Dominated Strategies
Carlos Hurtado
Department of Economics
University of Illinois at Urbana-Champaign
[email protected]
Jun 20th, 2017
C. Hurtado (UIUC - Economics) Game Theory

On the Agenda
1 What do we do in Economic?
2 What is Game Theory?
3 A Brief History of Game Theory
4 The Theory of Rational Choice
5 The Extensive Form Representation of a Game
6 Strategies and the Normal Form Representation of a Game
7 The Rational Choice Paradigm
8 Exercises
9 Formalizing the Game
10 Dominant and Dominated Strategies
11 Iterated Delation of Strictly Dominated Strategies
12 Iterated Delation of Dominated Strategies
13 Exercises
What do we do in Economic?
On the Agenda
8 Exercises
13 Exercises
I What makes a theoretical model economics is that the concepts we are

analyzing are taken from real life.
I Through the investigation of these concepts, we indeed try to understand reality

better, and the models provide a language that enables us to think about
economic interactions in a systematic way.
I We do not view economic models as an attempt to describe exactly the world, or

to provide tools for predicting the future.
I Although we will be studying formal concepts and models, they will always be
given an interpretation. An economic model differs substantially from a purely
mathematical model in that it is a combination of a mathematical model and its
interpretation.
C. Hurtado (UIUC - Economics) Game Theory 1 / 66

I The word model sounds more scientific than fable or fairy tale, but there is
not much difference between them. The author of a fable draws a parallel to a
situation in real life and has some moral he wishes to impart to the reader.
I The fable is an imaginary situation that is somewhere between fantasy and reality.
Any fable can be dismissed as being unrealistic or simplistic, but this is also the
fables advantage.
I Being something between fantasy and reality, a fable is free of extraneous details
and annoying diversions. In this unencumbered state, we can clearly discern what
cannot always be seen from the real world.
I On our return to reality, we are in possession of some sound advice or a relevant
argument that can be used in the real world. We do exactly the same thing in
economic theory.
I Thus, a good model in economic theory, like a good fable, identifies a number of
themes and elucidates them. We perform thought exercises that are only loosely
connected to reality and have been stripped of most of their real-life characteristics.
I However, in a good model, as in a good fable, something significant remains.

As if Rationality
I Rationality forms the basis of decision-making in the neoclassical school.
I Decision-makers are optimizers, given the constraints they find themselves in.
I Rationality assumes that decision-makers maximize things that give them

happiness and minimize things that give them pain.
I Implications:
- Narrows down the set of possible outcomes.

- Rational man is a clever individual.
- Rationality helps to predict the outcome of an economic system.
- Once economic agents have optimized their utility and reached a situation
where they do not want deviate, the economic system reaches a stable
outcome: equilibrium.

Perfect Competition is a Benchmark
I Assumes the existence of many buyers and many sellers.
I Decision making is made independently and individually.
- Decisions are not made in coalitions (together/jointly)
- Decisions are not inter-dependent: Decision of one agent is neither

influenced by another agent, nor does it influence that of another agent.
I Independent and individual decision-making under perfect competition implies each

decision-maker tries to do the best they can irrespective of what other
decision-makers are doing. (really?)
I Perfect competition is a theoretical extreme. Like the ideal human body

temperature of 98.4 degrees Fahrenheit it almost never exists. It is used as a
benchmark to explain deviations from this perfect world.

What is Game Theory?
On the Agenda
8 Exercises
13 Exercises
I Branch of applied mathematics and economics that studies strategic situations

where there are several players, with different goals, whose actions can affect one
another.
I A game is any situation where multiple players can affect the outcome, a player is
a stakeholder, a move or option is an action a player can take and, at the end of
the game, the payoff for each player is the outcome.
I The value of game theory lies in understanding the interactions and likely
outcomes when the end result is dependent on the actions of others who have
potentially conflicting motives.
I Game theory is mainly used in economics, political science, and psychology, as well
as logic, computer science, and biology.
I The subject first addressed zero-sum games, such that one persons gains exactly
equal net losses of the other participant or participants. Today, game theory
applies to a wide range of behavioral relations: the study of decision science,
including both humans and non-humans.

Lets play a game!
I Each person writes a number between 0 and 100.
I The winner is the one who wrote the closest number to half the average of all
numbers, including his or her own number.

A Brief History of Game Theory
On the Agenda
8 Exercises
13 Exercises

1713
In a letter dated 13 November 1713 Francis Waldegrave provided the first known,
minimax mixed strategy solution to a two-person game. Waldegrave wrote the
letter, about a two-person version of a card game, to Pierre-Remond de Montmort
who in turn wrote to Nicolas Bernoulli, including in his letter a discussion of the
Waldegrave solution.
1838
The French economist Antoine Augustine Cournot discussed a duopoly where the
two duopolists set their output based on residual demand.
1871
In the first edition of his book The Descent of Man, and Selection in Relation to
Sex Charles Darwin gives the first (implicitly) game theoretic argument in
evolutionary biology: If births of females are less common than males, females can
expect to have more offspring. Thus parents genetically disposed to produce
females tend to have more than the average numbers of grandchildren, hence,
female births become more common. As the 1:1 sex ratio is approached, the
advantage associated with producing females dies away.

Intellectual debate between the French Mathematician Emile Borel (1871-1956)

and the Hungarian Mathematician John Von Neumann (1903-1957):
Do zero-sum games have a solution?
1921
Emile Borel published four notes on strategic games and an erratum to one of
them. Borel gave the first modern formulation of a mixed strategy along with
finding the minimax solution for two-person games with three or five possible
strategies. Initially he maintained that games with more possible strategies would
not have minimax solutions, but by 1927, he considered this an open question as
he had been unable to find a counterexample.
1928
John von Neumann proved the minimax theorem. It states that every two-person
zero-sum game with finitely many pure strategies for each player is determined, ie:
when mixed strategies are admitted, this variety of game has precisely one
individually rational payoff vector.

1934
R.A. Fisher independently discovers Waldegraves solution to the card game. Fisher
reported his work in the paper Randomisation and an Old Enigma of Card Play.
Intellectual debate between Hungarian Mathematician John Von Neumann

(1903-1957) and he Austrian economist Oskar Morgenstern (1902-1977):
Can utility be quantified?
1944
Theory of Games and Economic Behavior by John von Neumann and Oskar
Morgenstern is published. As well as expounding two-person zero sum theory this
book is the seminal work in areas of game theory such as the notion of a
cooperative game, with transferable utility (TU), its coalitional form and its von
Neumann-Morgenstern stable sets. It was also the account of axiomatic utility
theory given here that led to its wide spread adoption within economics.

Von Neumann and Morgenstern formally laid the foundations of Game Theory as a
branch of applied mathematics. However, their effort failed to generate stir for two
reasons.
1. The Theory of Games and Economic Behavior was based on the notion of
zero-sum games. These are known as Games of Conflict or Non-Cooperative
Games. Most games in social sciences are non-zero-sum games.
2. It did not establish how equilibrium in games of interdependent decision-making

would arise. The world did not have to wait too long for this solution.

1950
Contributions to the Theory of Games I, H. W. Kuhn and A. W. Tucker eds.,
published.
1950
In January 1950 Melvin Dresher and Merrill Flood identified a game where it is in
the best interest for players to cooperate, but individual self-interest invokes them
to not cooperate. The game reaches a bad equilibrium that is inferior to a superior
outcome that could have been reached and was available. This phenomenon was
canonized by Albert Tucker.
In the summer of 1950 Tucker was at Stanford University. He was working on a
problem in his room when a graduate student of psychology knocked and asked
what he was doing. The answer was short: game theory. Why dont you explain
to us in a seminar? Tucker used his now famous example of two thieves who were
put into separate cells and asked the same question by the judge. Tucker
christened the phenomenon as The Prisoners Dilemma.

1953
Extensive form games allow the modeler to specify the exact order in which players
have to make their decisions and to formulate the assumptions about the
information possessed by the players in all stages of the game. In two papers,
Extensive Games (1950) and Extensive Games and the Problem of Information
(1953), H. W. Kuhn included the formulation of extensive form games which is
currently used, and also some basic theorems pertaining to this class of games.
1953
In four papers between 1950 and 1953 John Nash (1928 - 2015) made seminal
contributions to both non-cooperative game theory and to bargaining theory.

Note: Nash arrived at Princeton in the Fall of 1948 to start a PhD. He came to
Princeton with one of the shortest reference letters. His professor Richard Duffin
(1909-1996) wrote just one sentence: He is a mathematical genius.
Just eighteen months later, Nash submitted a 28 page doctoral dissertation. The
number 28 went on to become a superstitious number at Princeton. Von
Neumann solved the mini-max theorem in 1928. Nash was born in 1928. Nashs
doctoral dissertation was 28 pages.



1953
In two papers, Equilibrium Points in N-Person Games (1950) and Non-cooperative
Games (1951), Nash proved the existence of a strategic equilibrium for
non-cooperative games -the Nash equilibrium- and proposed the Nash program,
in which he suggested approaching the study of cooperative games via their
reduction to non-cooperative form.
- This was the missing link to Von Neumann and Morgensterns magnum opus!!
- He established equilibrium where all players calculate their best strategy based on
what they assume is the best strategy of the other players.
- Every finite game must have at least one solution such that once reached, no
player within the game will have an incentive to deviate.
- If all rational economic agents in a system are trying to do the best they can, the
economic system must be in equilibrium such that no single agent will want to
unilaterally deviate from their position.
- A Nash equilibrium does not necessarily imply that a game will reach a solution
that is the best possible solution for all players in the game.

Why was John Nashs 1950 Game Theory paper such a big deal?
I In 1928, Hungarian mathematician John von Neumann, launched the field of game
theory with a study of two-player zero-sum games, in which the players have
completely opposite interests
I von Neumann dealt with the case n = 2, and it was by no means obvious how to
extend the concept of equilibrium for the general case and prove that it always
exists.
I Nash is very clear about this in his 1951 Annals paper:

The notion of an equilibrium point is the basic ingredient in our theory. This
notion yields a generalization of the concept of the solution of a two-person
zero-sum game. It turns out that the set of equilibrium points of a two-person
zero-sum game is simply the set of all pairs of opposing good strategies.
I The solution concept was very innovative. For example, Arrow and Debrew (1954)
generalized Nashs theorem on the existence of equilibrium points for games to
proof the existence of an equilibrium for a competitive economy.

1953
The notion of the Core as a general solution concept was developed by L. S.
Shapley (Rand Corporation research memorandum, Notes on the N-Person Game
III: Some Variants of the von-Neumann-Morgenstern Definition of Solution, RM-
817, 1952) and D. B. Gillies (Some Theorems on N-Person Games, Ph.D. thesis,
Department of Mathematics, Princeton University, 1953). The core is the set of
allocations that cannot be improved upon by any coalition.
50s
Near the end of this decade came the first studies of repeated games. The main
result to appear at this time was the Folk Theorem. This states that the
equilibrium outcomes in an infinitely repeated game coincide with the feasible and
strongly individually rational outcomes of the one-shot game on which it is based.
Authorship of the theorem is obscure.

I Identification and formalization of the Prisoners Dilemma by Flood, Dresher and

Tucker had important implications in economic theory and the social sciences.
- It provided a rigorous explanation to why intervention into markets can be
justified in the presence of public goods that are jointly consumed once
provided, but almost impossible to finance through voluntary contribution.
I This phenomenon formed the basis to why players in a game find a mutual interest
to cooperate if a Prisoners Dilemma game is played more than once. This lead to
what is known as Trigger Strategies.
- Anatol Rapoport (1911-2007) proposed a simple strategy called Tit For Tat
in a repeated Prisoners Dilemma tournament.
- Rapoport proposed, each player cooperates with the other player in a
repeated Prisoners Dilemma as long as the other player does the same. If
one player defects in one round, the game ends with the other player
applying the Trigger of Tit For Tat by no cooperation and ending the game.

I Refinement of the Nash Equilibrium: The development of Game Theory from the
1950s was based on the limitations of the Nash Equilibrium.
- The Nash Equilibrium argued that a game can have multiple equilibria
(solutions). It did not provide how to identify the set of multiple equilibria
and which one to choose as the more probable equilibrium.
I Thomas Schelling introduced two terms Focal Point (the logical outcome from
information from outside a game) and Credible Commitment (sending a signal that
a player will commit to a certain actions).
- The Focal Point provided a basis for behavioural sciences why players prefer
one set of equilibrium to another. It also helped narrow down probable
solutions from a larger set.
- The Credible Commitment (Threat) gave an added edge to explain previous
models like the Stackelberg model in a sequential game setting.

I A further development in the Nash Equilibrium came through the works of the
Hungarian-American Game Theorist John Harsanyi.
I The Nash equilibrium was based on games of complete information. In economic

theory, this is known as games under symmetric information when all players in a
game make decisions based on having the same set of information.
I By the 1970s, economists like George Akerlof, Michael Spence and Joseph Stiglitz
started analyzing decision-making under asymmetric information or games under
incomplete information.
I Harsanyi had by that time refined the Nash Equilibrium under Bayesian
Probability. This enabled the analysis of games where different players have
different sets of information about themselves.
I Harsanyis refinement was a blessing for economists who were battling with
asymmetric information.

Goodbye to Rationality:
I By the 1960s and the 1970s, psychologists studying decision-making, started to

challenge the rationality assumption upon which the neoclassical school of
economic theory and Game Theory was based.
I One of the pioneers was Herbert Simon (1916- 2001). He introduced the notion of
Bounded Rationality.
I When individuals make decisions they posses limited information, limited cognitive
ability, and limited time within which to make decisions.
I With the development of bounded rationality, economic theory slowly started to

become a behavioural science.

I Robert Rosenthal (b 1933) first introduced the Centipede Game in 1981.
I Two players take turns choosing either to take a slightly larger share of a slowly
increasing pot, or to pass the pot to the other player. Based on sub-game perfect
equilibrium and backward induction, the rational outcome of the game would be
for the player making the first decision to take the entire pot in the first round.
I However, empirical evidence suggested otherwise. Players tend to partially

cooperate so the pot becomes larger as the game proceeds. This empirical
outcome challenged the rationality assumption of Game Theory.

I The Ultimatum Game was introduced in 1982 by Werner Guth, Rolf

Schmittberger, and Bernd Schwarze.
I In the Ultimatum Game, two players decide how to divide a sum of money. The
first player proposes how to divide the sum between the two players. The second
player can either accept or reject this proposal. If the second player rejects, neither
player receives anything. If the second player accepts, the money is split according
to the proposal. The game is played only once.
I This game challenges the rationality assumption. Rationality would suggest the
proposer keeps all the money and does not offer anything to the other player.
I Empirical evidence suggests ethics and morality and evolutionary behaviour leads
to some degree of fairness in the splitting of the money.
I Extension of this is the Rubinstein Bargaining: Two players that alternate the
ultimatum game. The game keeps going until one player accepts an offer.
Rubinstein uses discount factors (every delay is costly). Rubinstein recovers a
unique solution.

The Theory of Rational Choice
On the Agenda
8 Exercises
13 Exercises
I A decision-maker chooses the best action according to her preferences, among all
the actions available to her.
I Her rationality lies in the consistency of her decisions when faced with different
sets of available actions, not in the nature of her likes and dislikes.
Actions:
- A set A consisting of all the actions that, under some circumstances, are
available to the decision-maker.
- In any given situation the decision-maker is faced with a subset of A, from
which she must choose a single element.
- The decision-maker knows this subset of available choices, and takes it as
given; in particular, the subset is not influenced by the decision-makers
preferences.
- The set A could, for example, be the set of bundles of goods that the
decision-maker can possibly consume; given her income at any time, she is
restricted to choose from the subset of A containing the bundles she can
afford.

Preferences and payoff functions:

- We assume that the decision-maker, when presented with any pair of actions,
knows which of the pair she prefers (Completeness), or knows that she
regards both actions as equally desirable (is indifferent between the
actions).
- Rational Choice (Transitivity): We assume further that these preferences are
consistent in the sense that if the decision-maker prefers the action a to the
action b, and the action b to the action c, then she prefers the action a to
the action c.
- Note that we do not rule out the possibility that a persons preferences are
altruistic in the sense that how much she likes an outcome depends on some
other persons welfare.
- We can represent the preferences by a payoff function, which associates a
number with each action in such a way that actions with higher numbers are
preferred1 .
a b u(a) < u(b)

1
Utility Representation: Refer to Ariel Rubinsteins Lecture Notes in Microeconomic Theory, Ch2. (Free on his web page!)
A Digression on Transitivity:
- Aggregation of considerations as a source of intransitivity.

a 1 b 1 c;b 2 c 2 a; c 3 a 3 b a b c a
- The use of similarities as an obstacle to transitivity.
An individual may express indifference in a comparison between two elements
that are too close to be distinguishable.
I The theory of rational choice is that in any given situation the decision-maker
chooses the member of the available subset of A that is best according to her
preferences.
I The action chosen by a decision-maker is at least as good, according to her

preferences, as every other available action.

The Extensive Form Representation of a Game
On the Agenda
8 Exercises
13 Exercises
What is a Game?
I From the noncooperative point of view, a game is a multi-person decision situation

defined by its structure, which includes:
- Players: Independent intelligent decision makers
- Rules: Which specify the order of players decisions, their feasible decisions
at each point they are called upon to make one, and the information they
have at such points.
- Actions: All the alternatives available to the players. We call A the set of
actions.
- Outcome: How players decisions jointly determine the physical outcome.
- Preferences: players preferences over outcomes.

Examples
I Matching Pennies (version A).

Players: There are two players, denoted 1 and 2.
Rules: Each player simultaneously puts a penny down, either heads up or tails up.
Actions: Ai = {H, T }
Outcomes: If the two pennies match, player 1 pays 1 dollar to player 2; otherwise,
player 2 pays 1 dollar to player 1.
I Matching Pennies (version B).
Rules: Player 1 puts a penny down, either heads up or tails up. Then, Player 2
puts a penny down, either heads up or tails up.

Examples
I Matching Pennies (version C).
Rules: Player 1 puts a penny down, either heads up or tails up, without letting
player 2 know his decision. Player 2 puts a penny down, either heads up or tails up.
I Matching Pennies (version D).
Rules: Players flip a fair coin to decide who begins. The looser puts a penny down,
either heads up or tails up. Then, the winner puts a penny down, either heads up
or tails up.
Outcomes: If the two pennies match, the looser pays 1 dollar to player 2;
otherwise, the winner pays 1 dollar to player 1.

I Some games that are important in economics have simultaneous moves.
I Simultaneous means strategically simultaneous, in the sense that players

decisions are made without knowledge of others decisions.
I It need not mean literal synchronicity, although that is sufficient for strategic
simultaneity.
I But many important games have at least some sequential decisions, with some
later decisions made with knowledge of others earlier decisions.
I We need a way to describe and analyze both kinds of game.
I One way to describe either kind of game is via the extensive form or game tree,
which shows a games sequence of decisions, information, outcomes, and payoffs.

I A version of Matching Pennies with sequential decisions, in which Player 1 moves

first and player 2 observes 1s decision before 2 chooses his decision.

I We can represent the usual Matching Pennies with simultaneous decisions by

introducing an information set, which includes the decision nodes a player cannot
distinguish and at which he must therefore make the same decision, as in the
circled nodes.

I The order in which simultaneous decision nodes are listed has some flexibility, as in
previous case, where player 2 could have been at the top.
I For sequential decisions the order must respect the timing of information flows.
(Information about decisions already made, as opposed to predictions of future
decisions, has no reverse gear.)
I All decision nodes in an information set must belong to the same player and have
the same set of feasible decisions. (Why?)
I Players are normally assumed necessarily to have perfect recall of their own past
decisions (and other information). If so, the tree must reflect this.
Definition
A game is one of perfect information if each information set contains a single decision
node. Otherwhise, it is a game of imperfect information.


I This is an example of a game with simultaneous decision nodes and players with
perfect recall of their own past decisions.

I This is an example of a game with simultaneous decision nodes and players

without perfect recall of their own past decisions.

I This is another example of a game with simultaneous decision nodes and players
without perfect recall of their own past decisions.

Strategies and the Normal Form Representation of a Game
On the Agenda
8 Exercises
13 Exercises
I For sequential games it is important to distinguish strategies from decisions or

actions.
I A strategy is a complete contingent plan for playing the game, which specifies a
feasible decision for each of a players information sets in the game.
I Recall that his decision must be the same for each decision node in an information
set.
I A strategy is like a detailed manual of actions, not like a single decision or action.


I It is assumed that conditional on what a player observes, he can predict the

probability distributions of his own and others future decisions and their
consequences.
I If players have this kind of foresight, then their rational sequential decision-making
in real time should yield exactly the same distribution of decisions as
simultaneous choice of fully contingent strategies at the start of play.
I The player writes his own manual of actions. Then he will give you (a neutral
referee) the manual and let you play out the game. You will tell him who won.
I Because strategies are complete contingent plans, players must be thought of as

choosing them simultaneously (without observing others strategies),
independently, and irrevocably at the start of play.

Player 2 strategies:
I Strategy 1 (s1 ): Play H if player 1 plays H; Play H if player 1 plays T
I Strategy 2 (s2 ): Play H if player 1 plays H; Play T if player 1 plays T
I Strategy 3 (s3 ): Play T if player 1 plays H; Play H if player 1 plays T
I Strategy 4 (s4 ): Play T if player 1 plays H; Play T if player 1 plays T

I A game maps strategy profiles (one for each player) into payoffs (with outcomes
implicit).
I There is a one-to-one correspondence between actions and outcomes. Therefore

we can consider the preferences, and payoffs, to be over strategies.
I Specifying strategies make it possible to describe an extensive-form games

relationship between strategy profiles and payoffs by its (unique) normal form or
payoff matrix or (usually when strategies are continuously variable) payoff function.



I The mapping from the normal to the extensive form isnt univalent: the normal
form for Matching Pennies version B has possible extensive forms other than the
one depicted before:

Randomized Choices
I In game theory it is useful to extend the idea of strategy from the unrandomized
(pure) notion we have considered to allow mixed strategies (randomized strategy
choices).
I Example: Matching Pennies Version A has no appealing pure strategies, but there
is a convincingly appealing way to play using mixed strategies: randomizing 50-50.
(Why?)
I Our definitions apply to mixed as well as pure strategies, given that the
uncertainty about outcomes that mixed strategies cause is handled (just as for
other kinds of uncertainty) by assigning payoffs to outcomes so that rational
players maximize their expected payoffs.
I Mixed strategies will enable us to show that (reasonably well-behaved) games

always have rational strategy combinations.

The Rational Choice Paradigm
On the Agenda
8 Exercises
13 Exercises
I The assumption that the player is rational lies at the foundation of what is known
as the rational choice paradigm.
Definition
Rational Choice Assumptions
The player fully understands the decision problem by knowing:
I The set of all possible actions A
I The payoffs associated whit the strategies R.
I Exactly how each strategy affects which outcome will materialize
I Her rational preferences over payoffs
Rational Player: A player facing a decision problem that will maximizes his payoff
over all possible strategies.

I A rational player chooses the action that brings her the highest payoff
I The rational player will have the most fun

Exercises
On the Agenda
8 Exercises
13 Exercises
Exercises
I Exercise 1. (Altruistic preferences) Person 1 cares both about her income and
about person 2s income. Precisely, the value she attaches to each unit of her own
income is the same as the value she attaches to any two units of person 2s
income. How do her preferences order the outcomes (1, 4), (2, 1), and (3, 0),
where the first component in each case is person 1s income and the second
component is person 2s income? Give a payoff function consistent with these
preferences. Is that payoff unique?
I Exercise 2. (Alternative representations of preferences) Adecision-makers

preferences over the set A = a, b, c are represented by the payoff function u
forwhich u(a) = 0, u(b) = 1, and u(c) = 4. Are they also represented by the
function v for which v(a) = -1, v(b) = 0, and v(c) = 2? How about the function
w for which w(a) = w(b) = 0 and w(c) = 8?
I Exercise 3. Deffine x y x y and y x . Denote the set of acctions by

X . Define I(x ) to be the set of all y in X for which y x . Show that the set (of
sets!) I(x )|x X is a partition of X . That is:
For all x and y , either I(x ) = I(y ) or I(x ) I(y ) = .
For every x X , there is y X such that x I(y ).

Exercises
I Exercise 4. In a game where player i has N information sets indexed n = 1, , N

and Mn possible actions at information set n, how many strategies does player i
have?
I Exercise 5. Depict the normal formm of Matching Pennies Version C.

Exercises
I Exercise 6. Consider the followign two-player (excluding payoffs):
a) What are player 1s possible strategies? player 2s?
b) Suppose that we change the game by merging the information set of player 1s
second round of moves (so that all the four nodes are now in a single information
set). Argue why the game is no longer one of perfect recall.

Formalizing the Game
On the Agenda
8 Exercises
13 Exercises
I Up to this point we defined game without been formal. Let me introduce some
Notation:
- set of players: I = {1, 2, , N}

- set of actions: i I, ai Ai , where each player i has a set of actions Ai .
- strategies for each player: i I, si Si , where each player i has a set of
pure strategies Si available to him. A strategy is a complete contingent plan
for playing the game, which specifies a feasible action of a players
information sets in the game.
QN
- profile of pure strategies: s = (s1 , s2 , , sN ) i=1
Si .
Note: let si = (s1 , s2 , , si1 , si+1 , , sN ) Si , we will denote
s = (si , si ) (Si , Si ).
QN
- Payoff function: ui : i=1
Si R, denoted by ui (si , si )

I Now we can denote game with pure strategies and complete information in normal
form by: N = {I, {Si }i , {ui }i }.
I What about the games with mix strategies?
I We have taken it that when a player acts at any information set, he
deterministically picks an action from the set of available actions. But there is no
fundamental reason why this has to be case.
Definition
A mixed strategy for player i is a function i : Si P [0, 1], which assigns a probability
i (si ) 0 to each pure strategy si Si , satisfying (s ) = 1.
si Si i i
I We denote the set of mixed strategies by (Si ).

I Note that a pure strategy can be viewed as a special case of a mixed strategy in
which the probability distribution over the elements of Si is degenerate.

Example
I Meeting in New York:

- Players: Two players, 1 and 2
- Rules: The two players can not communicate. They are suppose to meet in NYC
at noon to have lunch but they have not specify where. Each must decide where
to go (only one choice). Art Museum vs. Brooklyn Bridge for player 1. Art
Museum vs. Brooklyn Bridge vs. Central Park for player 2.
- Outcomes: If they meet each other, they enjoy others company. Otherwise, they
eat alone.
- Payoffs: They attach a monetary value of 100 USD to others company and 0
USD to eat alone.
player 2
A B C
A 100,100 0,0 0,0
player 1
B 0,0 100,100 0,0

Example
I Meeting in New York:
- set of players: I = {1, 2}
- set of actions: A1 = {A, B}, and A2 = {A, B, C }
- strategies for each player: S1 = A1 , and S2 = A2 (Why?)

Q2
- Payoff function: ui : i=1
Si R, denoted by ui (si , si )

100 if si = si
u(si , si ) =
0 6 si
if si =
I Player 2
- pure strategies: S2 = {A, B, C }. Player 2 has 3 pure strategies.
- mixed strategies: P3
(S2 ) = {(12 , 22 , 32 ) R3 |m
2
0m = 1, 2, 3 and 2 = 1}
m=1 m

Dominant and Dominated Strategies
On the Agenda
8 Exercises
13 Exercises

I Now we turn to the central question of game theory: What should be expected to
observe in a game played by rational agents who are fully knowledgeable about the
structure of the game and each others rationality?
I To keep matters simple we initially ignore the possibility that players might
randomize in their strategy choices.
I The prisoners dilemma:
* There are two thieves who are suspects in an armed robbery. Each thieve is in solitary
confinement with no means of speaking to or exchanging messages with the other.
* The prosecutors do not have enough evidence to convict the pair on the principal charge.
To nail the suspects for the robbery, the police need testimony from at least one of the
suspects.
* Simultaneously, the prosecutors offer each prisoner a deal that reduces the sentence he
will get if he confesses on his partner in crime.
* The alternative is for the suspect to say nothing to the investigators.
* Here is the offer:
- If both choose to remain silent, then both get 2 years in prison because the evidence
can support only the charge of petty theft.
- If player 1 remains silent while player 2 confesses, then player 1 gets 10 years in
prison while player 2 gets only 1 year for being cooperative and vice versa.
- If both confess then both get 9 years in prison.

I Let me put prisoners dilemma as a game of trust:
player 2
silent confess
silent -2,-2 -10,-1
player 1
confess -1,-10 -9,-9
I Observe that regardless of what her opponent does, player i is strictly better off
playing confess rather than silent. This is precisely what is meant by a strictly
dominant strategy.
- Player 2 plays silent. Player 1 knows that 1 > 2, better to confess.
- Player 2 plays confess. Player 1 knows that 9 > 10, better to confess.
- Regardless of the others strategies, it is always better to confess.
- Note that both would be better off if they both play silent.
Lesson self-interested behavior in games may not lead to socially optimal outcomes.

Definition
A strategy si Si is a strictly dominant strategy for player i if for all
si 6= si and all si Si , ui (si , si ) > ui (si , si ).
I A strictly dominant strategy for i uniquely maximizes her payoff for any strategy
profile of all other players.
I If such a strategy exists, it is highly reasonable to expect a player to play it. This
is a consequence of the Rational Choice Paradigm.

I What about if a strictly dominant strategy doesnt exist?
player 2
a b c
A 5,5 0,10 3,4
player 1
B 3,0 2,2 4,5
I You can easily convince yourself that there are no strictly dominant strategies here
for either player.
I Notice that regardless of whether Player 1 plays A or B, Player 2 does strictly

better by playing b rather than a.
I That is, a is strictly dominated by b.

Definition
A strategy si Si is strictly dominated for player i if there exists a
strategy si Si such that for all si Si , ui (si , si ) > ui (si , si ). In this
case, we say that si strictly dominates si .
I In words, si strictly dominates si if it yields a strictly higher payoff regardless of

what (pure) strategy rivals use.
I Note that the definition would also permits us to use mixed strategies.
I Using this terminology, we can restate the definition of strictly dominant: A

strategy si is strictly dominant if it strictly dominates all other strategies.
I It is reasonable that a player will not play a strictly dominated strategy, a

consequence of rationality, again.

Iterated Delation of Strictly Dominated Strategies
On the Agenda
8 Exercises
13 Exercises

player 2
a b c
A 5,5 0,10 3,4
player 1
B 3,0 2,2 4,5
I We argued that a is strictly dominated (by b) for Player 2; hence rationality of

Player 2 dictates she wont play it.
I We can push the logic further: if Player 1 knows that Player 2 is rational, he
should realize that Player 2 will not play strategy a.
I Notice that we are now moving from the rationality of each player to the mutual
knowledge of each players rationality.
I Once Player 1 realizes that 2 will not play a and deletes this strategy from the
strategy space, then strategy A becomes strictly dominated by strategy B for
Player 2.
I If we iterate the knowledge of rationality once again, then Player 2 realizes that 1
will not play A, and hence deletes A.
I Player 2 should play c. We have arrived at a solution.

Definition
A game is strict-dominance solvable if iterated deletion of strictly
dominated strategies results in a unique strategy profile.
I Since in principle we might have to iterate numerous times in order to solve a

strict-dominance solvable game, the process can effectively can only be justified by
common knowledge of rationality.
I As with strictly dominant strategies, it is also true that most games are not
strict-dominance solvable.
I You might worry whether the order in which we delete strategies iteratively
matters. Insofar as we are working with strictly dominated strategies so far, it does
not.

Iterated Delation of Dominated Strategies
On the Agenda
8 Exercises
13 Exercises
Definition
A strategy si Si is a weakly dominant strategy for player i if for all
si 6= si and all si Si , ui (si , si ) ui (si , si ), and for at least one
choice of si the inequality is strict.
Definition
A strategy si Si is weakly dominated for player i if there exists a strategy
si Si such that for all si Si , ui (si , si ) ui (si , si ), and for at least
one choice of si the inequality is strict. In this case, we say that si weakly
dominates si .
Definition
A game is weakly-dominance solvable if iterated deletion of weakly
dominated strategies results in a unique strategy profile.
I Using this terminology, we can restate the definition of weakly dominant: A

strategy si is weakly dominant if it weakly dominates all other strategies.
I You might worry whether the order in which we delete strategies iteratively
matters. Delation of dominated strategies could leave to different outcomes.
P2
L R
U 5,1 4,0
P1 M 6,0 3,1
D 6,4 4,4
P2 P2
L R L R
U 5,1 4,0 M 6,0 3,1
P1 P1
D 6,4 4,4 D 6,4 4,4

Exercises
On the Agenda
8 Exercises
13 Exercises
Exercises
Exercises
I Exercise 7. Prove that a player can have at most one strictly dominant strategy.
I Exercise 8. Apply the iterated elimination of strictly dominated strategies to the
following normal form games. Note that in some cases there may remain more
that one strategy for each player. Say exactly in what order you eliminated rows
and columns.
I Exercise 9. Apply the iterated elimination of dominated strategies to the following
normal form games. Note that in some cases there may remain more that one
strategy for each player. Say exactly in what order you eliminated rows and
columns.

Exercises
Exercises
I Exercise 8 and 9 (cont.).

Exercises
Exercises

Exercises
Exercises

First Class On Game Theory

Uploaded by

Copyright:

Available Formats

First Class On Game Theory

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

First Class On Game Theory

Uploaded by

Copyright:

Available Formats

Introduction: Noncooperative Games Dominant

and Dominated Strategies

Jun 20th, 2017

C. Hurtado (UIUC - Economics) Game Theory

I What makes a theoretical model economics is that the concepts we are

I Through the investigation of these concepts, we indeed try to understand reality

I We do not view economic models as an attempt to describe exactly the world, or

C. Hurtado (UIUC - Economics) Game Theory 1 / 66

C. Hurtado (UIUC - Economics) Game Theory 2 / 66

I Rationality forms the basis of decision-making in the neoclassical school.

I Rationality assumes that decision-makers maximize things that give them

- Narrows down the set of possible outcomes.

C. Hurtado (UIUC - Economics) Game Theory 3 / 66

Perfect Competition is a Benchmark

I Assumes the existence of many buyers and many sellers.

I Decision making is made independently and individually.

- Decisions are not made in coalitions (together/jointly)

- Decisions are not inter-dependent: Decision of one agent is neither

I Independent and individual decision-making under perfect competition implies each

I Perfect competition is a theoretical extreme. Like the ideal human body

C. Hurtado (UIUC - Economics) Game Theory 4 / 66

What is Game Theory?

I Branch of applied mathematics and economics that studies strategic situations

C. Hurtado (UIUC - Economics) Game Theory 5 / 66

What is Game Theory?

Lets play a game!

I Each person writes a number between 0 and 100.

C. Hurtado (UIUC - Economics) Game Theory 6 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 7 / 66

A Brief History of Game Theory

Intellectual debate between the French Mathematician Emile Borel (1871-1956)

C. Hurtado (UIUC - Economics) Game Theory 8 / 66

A Brief History of Game Theory

Intellectual debate between Hungarian Mathematician John Von Neumann

C. Hurtado (UIUC - Economics) Game Theory 9 / 66

A Brief History of Game Theory

2. It did not establish how equilibrium in games of interdependent decision-making

C. Hurtado (UIUC - Economics) Game Theory 10 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 11 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 12 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 13 / 66

C. Hurtado (UIUC - Economics) Game Theory 14 / 66

A Brief History of Game Theory

A Brief History of Game Theory

I Nash is very clear about this in his 1951 Annals paper:

C. Hurtado (UIUC - Economics) Game Theory 16 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 17 / 66

A Brief History of Game Theory

I Identification and formalization of the Prisoners Dilemma by Flood, Dresher and

C. Hurtado (UIUC - Economics) Game Theory 18 / 66

A Brief History of Game Theory

C. Hurtado (UIUC - Economics) Game Theory 19 / 66

A Brief History of Game Theory