prj
代写project 这个项目是project代写的代写题目
Game Theory
Supermodular Games
Ruitian Lang
ANU
General idea
Finding all the Nash equilibria is usually a very challenging exercise.
Can we say something about the set of Nash equilibria without
actually computing all of them?
Can we do comparative statics for games: are Nash equilibrium
strategies increasing or decreasing in some parameters?
We can for a special class of strategic form games: supermodular
games.
Table of contents
1 Topkiss Theorem
2 Rationalizability
3 Supermodular games
Increasing differences
Can we do comparative statics without invoking the Implicit Function
Theorem, for example when our Objective function is not differentiable?
Definition
Let I 1 and I 2 be two intervals. A function f : I 1 I 2 R is said to have
increasing differencesif for all x , x
I 1 , y , y
I 2 with x
> x and y
> y,
f ( x
, y
) f ( x , y
) f ( x
, y ) f ( x , y ).
If the strict inequality always holds, the function f is said to havestrictly
increasing differences.
Assume that f ( x ,)has increasing differences and for everythere is a
unique maximum x
()of f (,). Then x
()is non-decreasing in.
Necessary generalizations
In a two-player game, if S 1 and S 2 are intervals and u 1 ( s 1 , s 2 )has
increasing differences, then BR 1 ( s 2 )is non-decreasing in s 2.
What if there are more than two players? Can we still say something
useful?
What if BR 1 is not a function (ie there are more than one best
responses)?
Partial order of vectors
Definition
For two n-dimensional vectors x =( x 1 ,…, xn ) and y =( y 1 ,…, yn ) , we write
x yif xi yifor i = 1 ,…, n andx > yif x y and x = y.
There are vectors x , y such that x y and y x are both false;
therefore, this defined above is not an order in that not every
pair of vectors are comparable.
That x > y does not mean that xi > yi for i = 1 ,…, n.
Thisis transitive: if x y and y z , then x z , with strict
inequality if x > y or y > z.
Examples from microeconomics
Consumer theoryA consumers utility function u is called monotonic if
u ( x
) u ( x )whenever x
x. Being monotonic means that
the consumer prefers more to less.
General equilibriumLet N be the set of consumers in an economy with ui
being the utility function of consumer i N. An allocation x
is said to be Pareto dominated by x
if
( u 1 ( x
),…, un ( x
))>( u 1 ( x ),…, un ( x )).
The definition of increasing differences remain the same with I 1 and I 2
replaced with subsets ofR
n
, as long asis understood to be the partial
order.
Comparative statics
Theorem
(Topkis) Let I be an ordered space, T be a subset of R
n
and f : I T R
be a function with increasing differences. Assume that for some t 1 , t 2 T
with t 1 t 2 , x 1 is a (global) maximum of f (, t 1 ) and x 2 is a (global)
maximum of f (, t 2 ). If x 1 x 2 , then x 2 is also a maximum of f (, t 1 ) and
x 1 is also a maximum of f (, t 2 ).
It is easier to visualize the theorem in the special case where the set of
maxima for each t T is an interval; the theorem says that x 1 and x 2
must be in the overlap part (intersection) of the intervals corresponding to
t 1 and t 2.
Compact ordered space I (optional)
Definition
A compact ordered space is an ordered set equipped with its order
topology such that the set is a compact space.
In the topology defined by the order, a set is open if and only if it is a
union of open intervals.
Compact ordered space II (required)
Two examples:
(^1) A bounded and closed interval. (^2) A finite set equipped with any order. Every function on a finite set is
continuous.
Two properties:
(^1) Every closed subset of a compact ordered space has a greatest
element and a smallest element.
(^2) Every monotone sequence in a compact ordered space has a limit.
Topkiss Theorem for compact ordered spaces
Theorem
Let I be a compact ordered space, T be a subset of R
n
, and f : I T R
be a function with increasing differences. In addition, assume that f ( x ,)
is continuous in x for every T. Then the following are true.
(^1) For every T, f (,) has a maximum; in fact, the set of maxima of
f (,) has a largest element x () and a smallest element x ().
(^2) For , T with , x () x () and x () x ().
Increasing differences and derivatives
Proposition
Let I be an interval T be a convex open subset of R
n
, and f : I T R
be a continuous function that is differentiable in the interior of the domain.
Denote by f 1 jthe mixed second order partial derivative of f with respect to
its first variable and its jth variable, for j = 2 ,…, n + 1. If f 1 j ( x , t ) 0 for
every x in the interior of I and t T, then f has increasing differences.
Interior means not at the boundary of I in case I is not an open interval.
Example: the producers problem
Assume that the cost for producing q units is c ( q )for q 0.
A competitive producer solves the problemmax q 0 pq c ( q ), where p
is the market price of its product.
The objective function has increasing differences in( q , p )without any
assumption on c. What can we say about the optimal quantity?
Table of contents
1 Topkiss Theorem
2 Rationalizability
3 Supermodular games
Rational players
A player of a strategic form game is calledrationalif he plays a best
response to some probability distribution over the opponents strategy
profiles.
Some probability distribution is not the same as a mixed strategy
profile, as correlations among different players are allowed.
What can we say about a rational players behavior without knowing
the probability distribution he plays for?
Strictly dominated strategies I
Definition
Fix a strategic form game and a player i. A strategy si Siis called
strictly dominatedif there exists a mixed strategy iof Player i such that
ui ( si , s i )< ui ( i , s i ) , for every s i S i.
No matter what the opponents play, si is strictly worse than i.
In searching for a strategy that strictly dominates si , we include mixed
strategies.
Strictly dominated strategies II
Theorem
Fix a strategic form game and a player i. If a strategy si Siis strictly
dominated, then it is not a best response to any probability distribution
over the opponents strategies.
This means that a rational player never plays a strictly dominated
strategy.
The converse of the theorem is also true for finite games (and some
generalizations): if a strategy is never a best response, it is strictly
dominated. The proof of this assertion is much more diicult.
Knowledge of rationality
Assume that Player i is rational himself and knows that the other
players are rational. What can we say about Player i s play?
Let S
( 1 )
j be the set of Player j s strategies that are not strictly
dominated. Player i knows that Player j will only choose from S
( 1 )
j.
Let S
( 1 )
i be the set of strategy profiles of Player i s opponents such
that each j plays a strategy from S
( 1 )
j.
Player i plays a best response to some probability distribution over
S
( 1 )
i
. The proof of the theorem implies that Player i will not play a
strictly dominated strategy with the opponents strategies restricted to
S
( 1 )
i.
Common knowledge
Informally, something is a common knowledge if
(^1) Everybody knows it. (^2) Everybody knows that everybody knows it. (^3) Everybody knows that everybody knows that everybody knows it. (^4) …
If it is common knowledge that every player is rational, then the
elimination procedure can continue indefinitely.
Rationalizable strategies
Definition
Let S
( 0 )
i = Sifor every Player i. Recursively, call a strategy si Si
eliminated by Round n + 1 if there exist a mixed strategy of Player i such
that
ui ( si , s i )< ui ( i , s i ) , for every s i S
( n )
i ,
and define S
( n + 1 )
i as the set of Player is strategies that are not eliminated
by Round n + 1. Put S
()
i =
T
n = 1 S
( n )
i. A strategy in S
()
i is called
rationalizable.
Nash equilibrium strategies are rationalizable
Theorem
Assume that is a Nash equilibrium of a strategic form game in mixed
strategy. Then for every Player i and strategy siin the support of i, siis
rationalizable.
Definition
If in a strategic form game, every player has only one rationalizable
strategy, such a game is calledsolvable by rationalizability.
Remark. A game that is solvable by rationalizability needs not have a
Nash equilibrium.
Guessing 2/3 of the average
There are n players, each choosing a real number si [ 0 , 100 ].
Player i s payoff is
(^) s
i
2
3
s
(^) , where s = n ^1
P n
i = 1 si.
This game is solvable by rationalizability.
Table of contents
1 Topkiss Theorem
2 Rationalizability
3 Supermodular games
Definition
Definition
A strategic form game with finitely many players is called supermodular if
for every player i, Siis a compact ordered space, uiis continuous and
ui ( si , s i ) has increasing differences in siand s i.
The statement on compactness and continuity encompasses the
following two cases:
(^1) Si is a bounded and closed interval and ui is continuous. (^2) Si is a finite set.
A compact ordered space always has a largest element and a smallest
element.
To obtain nice result in the end, the definition also requires that
ui ( si , s i )is continuous in s i.
Examples
The investment game.
Battle of sexes.
Bank run.
Two-player Cournot competition after relabeling one firms strategies.
The main theorem
Theorem
The following is true for a supermodular game.
(^1) For every player i N, there exists a smallest rationalizable strategy s
i
and a greatest rationalizable strategy si.
(^2) sand s are Nash equilibria.