\documentclass[12pt,epsf]{article}
\usepackage{verbatim}
\newcommand{\comments}[1]{}
\renewcommand\floatpagefraction{.9}
\renewcommand\topfraction{.9}
\renewcommand\bottomfraction{.9}
\renewcommand\textfraction{.1}
\setcounter{totalnumber}{50}
\setcounter{topnumber}{50}
\setcounter{bottomnumber}{50}
\usepackage{hyperref} \hypersetup{breaklinks=true, pagecolor=white,
colorlinks=
true, linkcolor=black, hyperfootnotes= false, urlcolor=blue } \urlstyle{
rm}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\reversemarginpar
\topmargin -.3in
\oddsidemargin -.1in
\textheight 8.5in
\textwidth 7in
\baselineskip 16pt
\begin{document}
\titlepage
\parindent 24pt
\parskip 10pt
\vspace*{12pt}
\begin{center}
\begin{Large}
{\bf Incomplete Information in Repeated Coordination Games }
\\
\end{Large}
\bigskip
2 November 2007 \\
\bigskip
Eric Rasmusen \\
\bigskip
{\it Abstract}
\end{center}
\vspace*{-12pt}
Asymmetric information can help achieve a good equilibrium in
repeated coordination games. If there is a small probability that one
player can play only one of a continuum of moves, that player can
pretend
to be of the constrained type, and other players will coordinate with
him.
\bigskip
\begin{small}
\noindent
\hspace*{20pt} Dan R. and Catherine M. Dalton Professor, Department of
Business
Economics and Public Policy, Kelley School of
Business, Indiana University. Visitor (2007-2008), Nuffield College,
Oxford
University. Office: 011-44-1865 554-163 or (01865) 554-163. Nuffield
College,
Room C3, New Road, Oxford, England, OX1 1NF.
Erasmuse@indiana.edu. \url{http://www.rasmusen.org}. This paper:
\url{Http://www.rasmusen.org/papers/goodtype-rasmusen.pdf}.
\noindent
I thank the Indiana Business Economics Brown Bag Lunch and Michael
Baye for
helpful comments.
\end{small}
\newpage
\noindent
{\bf 1.Introduction}
It is well
known that coordination games have multiple equilibria, depending on
player expectations, even if one equilibrium is pareto superior and
players can communicate. This multiplicity is present even in the one-
shot game, and just gets worse when the game is repeated. Few of the
refinements of Nash equilibrium that have been suggested in the context
of other kinds of games help with coordination games, and none has
gained more than minimal acceptance.
The problem of multiple equilibria in coordination games has attracted
attention from various authors. One way to try to predict which
equilibrium is played out is to use the behavioral idea of ``focal
points'' from Thomas Schelling (1960): that a human's attention is drawn
to
certain equilibria because they look ``different''. Thus, if a game's
equilibria had payoffs of (1,1), (2,2), and (100,100), the focal point
would be (100,100). This is a difficult notion to formalize, though: if
the alternatives were (1,1), (99,99), and (100,100) would we predict
that that the players would end up at (1,1) because it is the most
distinctive?
Clearly, the idea of the focal point is important. Philosopher David
Lewis (1965) divides the idea of the salience of a choice into two
parts. The choice has ``primary salience'' to a player if he believes it
is salient to he himself; it has ``secondary salience'' if he believes
it has salience to other players. Judith Mehta, Chris Starmer \&
Robert Sugden (1994, p. 661) add ``Schelling salience'' to primary and
secondary salience, as a choice that ``seems obvious or natural to
people who are looking for ways of solving
coordination problems.'' In their article they report results of
experiments trying to distinguish between primary salience-- the answers
subjects gave to questions when there was no reward for coordination--
and secondary or Schelling salience-- the answers when subjects were
rewarded for successful coordination. They found that subjects indeed
were picking with an eye towards what other subjects would pick; for
example when asked to write down any day of the year, only 6\% of the
first set of subjects answered December 25, but 44\% did when they were
rewarded for successful cooperation.
A second approach tries to use derive the unique equilibrium from
rationality. Gauthier (1975, p. 201) defines the ``Principle of
Coordination'' as that ``in a situation with one and only one outcome
which is both optimal and a best equilibrium, if each person takes every
other person to be rational and to share a common conception of the
situation, it is rational for each person to perform that action which
has the best equilibrium as one of the possible outcomes.'' Bacharach (
1993) Harsanyi \& Selten (1988) and Janssen (2000, 2001) have pursued
this approach, trying to add axioms for rational behavior that require
players to avoid dominated equilibria.
Repeating the game does not reduce the number of equilibria, but it does
introduce a new angle: finding the optimal way to play a game starting
without a convention as to the equilibria. What is the optimal strategy
for the two players if they must first grope their ways towards
coordination by guessing what the other player will do before they end
up at the same action and use it thereafter? That is the project in
Crawford\& Haller (1990), who find a learning procedure that converges
in
finite time.
A third approach is to look at evolution in games. Glenn Ellison
(1993),
Michihiro Kandori, George J. Mailath \& Rafael Rob (1993), and Peyton
Young (1993) take this approach. Start with a population of pairwise-
interacting players with different strategies. They play coordination
games, and increase or diminish in frequency depending on their
payoffs. In such settings, ``risk-dominant strategies'' emerge as
equilibria. In a symmetric two-player setting, this is the strategy a
player would choose if he thought there was a 50\% probability of the
other player choosing each strategy. The risk-dominant strategy is not
necessarily the one with the highest payoff; it balances that against
the loss if discoordination does occur.
Risk-dominant equilibria also arise in the single-repetition ``global
games'' of Morris \&
Shin (2003). They ask what happens if players have some small
uncertainty over what game they are playing out. It turns out that
iterated deletion of interim-dominated strategies can then make the
risk-dominant equilibrium the unique equilibrium.
I will show below that adding incomplete information changes the
repeated game
drastically. Kreps, Milgrom, Roberts \& Weber (1982) show that adding
a
small amount of carefully chosen incomplete information to the model can
result in cooperation in the finitely repeated prisoners' dilemma.
Fudenberg \& Maskin (1986) show more generally that adding incomplete
information can generate any of a wide range of average payoffs in
finite repeated games by getting around the backwards induction of the
Chainstore Paradox. Their theorem does not apply to many coordination
games, since it depends on a ``dimensionality condition'' that requires
payoffs to vary enough between players to allow equilibria to be
supported by punishment phases in which one player is able to punish
another without hurting himself. Benoit \& Krishna (1985), however, show
that if a game has multiple equilibria, as a coordination game does,
then a wide range of equilibria can be obtained if the game is repeated
enough times by using the threat of punishment phase in an inferior
equilibrium to enforce the desired behavior.
I will not be be able to reduce the number of equilibria in the
one-
shot game, but I will
show that with a small amount of
incomplete information and enough repetitions any perfect bayesian
equilibrim of even a finitely repeated two-player game will achieve
arbitrarily close to the optimal average payoff.
The results will not depend on careful
specification of the incomplete information, and it is
robust to out-of-equilibrium beliefs. There will be no assumption that
``Players are either of type $x=0$ or type $x=100$ (with small
probability), but never any other value of $x$.'' Nor will I specify
anything like, ``Out of equilibrium, the deviating player is believed
to be of type $x \in [0, 34]$.''
Rather, the intuition is that in coordination games, no
player has an incentive to hurt other players, so any attempt to
``fool'' other players by pretending to be of a particular type
will be eagerly accepted by them. This intuition is partly present in
the intuition behind the Gang of Four Theorem of
Kreps, Milgrom, Roberts \& Weber (1982); here, it applies better and so
the result is easier to achieve.
\bigskip
\bigskip
\noindent
{\bf 2. The Repeated Complete-Information Coordination Game with Two
Players }
Consider a ranked coordination game with $n = 2$ players indexed by
$i$ who simultaneously choose actions $x_1,x_2$ from the interval [0,
100]. The per-period payoff to player $i$ is $\pi(x_i, x_{-i})$
with:
\begin{equation}
\begin{array}{l}
(a) \forall x, \; \frac{ \partial \pi (x,x)}{\partial x} >0\;\;\;\; (b)
\pi (0,0) > \pi (x_i, x_{-i} ) \; if\; x_i \neq x_{-i}
\end{array}
\end{equation}
Assumption (a) says that a player's payoff rises if he chooses a higher
action and the other player chooses the same action as he does.
Assumption (b) says that if the player's choose different actions, their
payoffs are lower than if they coordinated on (0,0).
We will normalize to $\pi (0,0) =0$ and $\pi (100,100) =100$, which is
to say the per-period payoff is 0 when both players choose $x=0$ and
100 when they pick $x=100$. The assumptions then imply that
coordination on $x>0$ yields positive payoffs and discoordination
yields negative payoffs.
If the game is unrepeated and $T=1$, it has a continuum of pure
strategy equilibria, with $x$ on the continuum from 0 to 100, as well as
mixed strategy equilibria. All players prefer the equilibrium in which
$x=100$.
Which equilibrium will be played out, depends on player expectations.
A reasonable prediction is $x=100$ because it is pareto superior to
all other equilibria, a focal point. An equally special equilibrium,
however, is $x=0$. It is easy to imagine how the players could be
caught in any equilibrium--- if the game were preceded by a cheap talk
announcement by a malicious outsider that he expected them all to choose
$x=1$, for example, or after these players or others they knew about
had a history of playing $x=5$ for many periods.
Let the game be repeated a possibly infinite number $T$ times, with
the players observing each other's strategies after each round and
with no discounting.
If $T \geq 2$, equilibrium outcomes and strategies both become more
numerous. Let us classify them as follows:
In a {\bf time-dependent equilibrium}, some player's strategy in a
round depends on which round number it is. If the strategies are the
same in each round, the equilibrium is {\bf time-independent}.
In a {\bf history-dependent equilibrium}, some player's strategy in a
round depends on the history of play up to that point. If the
strategies do not depend on past play, the equilibrium is {\bf history-
independent}.
The following examples illustrate the definitions.
\begin{small}
\begin{tabular}{ll|cc}
& & \multicolumn{2}{|c|}{\bf Time}\\
& & & \\
& & Independent & Dependent\\
& & & \\
\hline
& & & \\
& Independent &Play 10 in each round. &\begin{tabular}{l|} Play 20 in
the first round\\
and 25 in the second.\\ \\ \\ \end{tabular} \\
{\bf History} & \multicolumn{3}{c}{\hrulefill}\\
& Dependent & \begin{tabular}{l|}Play 30 in each round unless \\someone
deviates, in which case \\
play 30 in the second round. \end{tabular} &
\begin{tabular}{l} For the first 50 rounds, player 1 \\
picks 2 and the
other players pick 14.\\
For the last 10,000 rounds \\everyone picks
100 unless someone \\
deviates. If someone deviates, all pick 0 \\for
the remainder of the game.
\end{tabular}\\
& & & \\
\hline
\end{tabular}
\end{small}
\begin{center}
{\bf Table 2: Two Dimensions}
\end{center}
Note that the history-dependent equilibria expand the number of
possible outcomes beyond coordination on some number between 0 and 100
in each period to allow many periods of equilibrium discoordination.
Benoit \& Krishna (1985) show that a wide array of outcomes might be
observed in equilibrium, supported by punishment strategies similar to
example (4)'s. The players choose any pattern of actions the modeller
may wish in the first $S$ periods, because in equilibrium they all play
$x=100$ in the last ($T-S$) rounds, but if anybody deviates earlier they
all play $x=2$. The observed actions, for example, might be (10, 2), (
7, 7), (8, 3), and then (100,100) for the last 200 rounds. As the
example shows,
repetition of the game does not solve the problem of multiple
equilibria, and in fact, even more outcomes become possible. The
average payoff could even be negative, if the equilibrium has many
periods of discoordination, so long as the average payoff is not below
the discoordination payoff.
\bigskip
\noindent
{\bf 3. The Incomplete-Information Coordination Game: A One-Action
Player }
Let us modify the game in the spirit of Kreps at al. (1982), by adding
a small amount of incomplete information. Players are of two types. With
some arbitrarily small probability $p>0$, a player $i$ is
``constrained'' to play $x_i = z_i$, in every round of the game,
where $z_i$ is chosen from [0, 100] using a atomless density
$f(z_i)$ such that $f(100)>0$. If player $i$
is not constrained, he is ``free''.
What is essential is that there be some possibility that a player will
choose $x=100$ and stick with it. This might be because he is truly
constrained, or because he misunderstands the rules of the game, because
he is irrational and thinks all players will make the same choice as he
does, because he wishfully thinks that the equilibrium will be the
pareto-optimal one (perhaps having read some of the references above) or
because he thinks, for whatever reason, that if he starts with
$x=100$ the other players will join him.
In the modified game, some equilibria disappear, as Example 1 shows.
\bigskip
\noindent
{\bf Example 1. } Suppose $T=20$ and the payoff from discoordination
is $-500$. Is it an equilibrium for a free
player to follow the strategy $x=5$ in every period and for a
constrained player of type $z$ to play $x=z$? No.
Consider what happens if player 1, although free, deviates to $x=100$
in the first round. Is it a best response for player 2, if free, to
play $x=5$ in the second round? That depends on player 2's
beliefs,which are generated by Bayes's Rule:
\begin{equation} \label{bayes}
\begin{array}{l}
Prob(z_1=100 |x_1=100)
= \frac{ Prob( x_1=100|z_1=100)* Density(z_1=100)}{ Prob( x_1=100|z_1=
100)* Density(z_1=100) + Prob( x_1=100|z_1= free)* Prob(z_1= free )} \\
\end{array}
\end{equation}
The priors tell us that $Prob(player \; 2 \; is \;free)=1-p$ and
$Density(z_1=100)=f(100)p$.
In the proposed equilibrium, $Prob( x_1=100|z_1=100) =1$ and
$Prob( x_1=100|z_1= free) =0$. Thus, equation (\ref{bayes}) becomes
\begin{equation} \label{bayes1}
Prob(z_1=100 |x_1=100) = \frac{ (1)* f(100)p}{ (1)* f(100)p+ (0)* (1-p)}
=1.
\end{equation}
After the first round, Player 2 therefore believes that Player 1's
type is $z_1=100$, so he concludes that $x_1=100$ for all future
rounds. Player 2's best response is not $x=5$, but to imitate Player
1's action, deviating to $x_2=100$. If both players then stick with
$x=100$, their payoffs are $(-500+ 19(100), -500+ 19(100))$ compared to
the $(20(5), 20(5))$ they would have gotten in equilibrium. Thus,
Player 1's deviation has been profitable.
It is not true, however, that the only equilibrium will be for a free
player to start with $x=100$ and to choose in the second and
succeeding periods whatever the other player chose in the first period.
If $x=99.9$, it is not worth bearing the initial cost of $-500$ to
deviate. Rather, what we can say is that for large enough $w$ a time-
independent equilibrium strategy must have a player beginning with $x=w$
and then choosing in the second and succeeding periods whatever the
other player chose in the first period. In such an equilibrium, the
equilibrium payoff is $(20w, 20w)$. The optimal deviation is to
$x=100$, which generates a deviation payoff of
$(-500+ 19(100), -500+ 19(100))$. There is no incentive to deviate from
equilibrium if and only if $ w \geq 92.5$.
Example 1 is the essence of this paper. If information is incomplete,
then a player can break out of a bad equilibrium at some cost by
pretending to be of an unusual type. If the game is repeated long
enough, it is worthwhile to bear that cost.
In fact, if $T$ is large enough, the game has a much smaller interval
of equilibria and the average payoff becomes arbitrarily close to 100.
\bigskip
\noindent
{\bf Proposition 1:} {\it For any $\epsilon$, there exists $T$ large
enough that in all pure-strategy equilibria the average payoff
approaches within
$\epsilon$ of the
optimum:}
\begin{equation}
\forall \epsilon>0, \exists T: \frac{ \sum_{t=1}^T \pi_{it} }{T}> 100-
\epsilon.
\end{equation}
\bigskip
\noindent
{\bf Proof.} The probability that a player is constrained is an
arbitrarily small $p$, so we the effect that the presence of truly
constrained players have on the average equilibrium payoffs will be less
than $\epsilon$.
Let the equilibrium with the lowest average payoff call for the
players
to first choose $(a,b)$ with $a$ or $b$ or both not equal to 100 in
round $t_1$. Without loss of generality, suppose that player 1 chooses
$a \neq 100$.
The minimum bound on the payoff is set by player 1 having the
deviation option to choose $x=100$ in that period and convince player
2 that player 1 is constrained of type $z=100$. Both players would
choose $x=100$ for every succeeding round. This would generate a
payoff of $ \pi(100, b) + 100(T-1)$, where $\pi(100, b)$ is the
discoordination payoff that arises from that particular deviation, since
there would be one period of discoordination and all other periods will
have per-period payoffs of 100. This strategy will have an average
payoff of
\begin{equation}
\frac{\pi(100, b)}{T} + \frac{100(T-1)}{T}= 100 + \frac{\pi(100,
b)}{T} - \frac{100 }{T}.
\end{equation}
If $T$ is large enough, the last two terms, which are both negative,
shrink to less than whatever small amount
$\epsilon$ we might choose.
Q.E.D.
\bigskip
The equilibria will be in actions with an average payoff in the
interval $[100-\epsilon, 100]$ for some $\epsilon$ that depends on $T$.
This set of equilibria does not depend heavily on the out-of-equilibrium
payoffs--just for one period of discoordination loss-- and therefore it
is not necessarily the same as the set of risk-dominant equilibria. It
could be, for example, that for $x$ in [0,50] the discoordination payoff
if the other player chooses a different $x$ is $-1$, but for $x$ in (50,
100] it is $-5000$, in which case the risk-dominant equilibrium would be
(50,50), not (100,100).
\bigskip
\noindent
{\bf 1. The Incomplete-Information Coordination Game: A Tit-for-Tat
Player }
\noindent
{\it With small probability $p$, player 1 is ``constrained'' to play
tit-for-tat: in equilibrium he begins with whatever $x_1=z$ maximizes
his equilibrium payoff, but thereafter he plays the action $y$ that is
played by the most other players in $(t-1)$, randomizing among the
possibilities if there is a tie for action $y$. }
Equilibrium is very much as earlier. We can get cooperation except in
the first, and last periods, I think. Maybe not, though-- this is
tricky.
Suppose 20 every time is the eq. One person deviates to 100 in the first
period. A second person then will deviate to 1 in the second period.
Then everybody will deviate to 100 in the third period.
\bigskip
\noindent
{\bf 4. The Repeated Complete-Information Coordination Game with More
than Two Players
}
Now let us allow for more than two players.
Consider a ranked coordination game with $n \geq 2$ players indexed
by $i$ who simultaneously choose actions $x_1, ..., x_n$ from the
interval [0,100]. If $\#x_i$ players choose the same action $x_i$,
the per-period payoff to player $i$ is $\pi_i(x_i,x_{-i}, \#x_i)$,
with:
\begin{equation}
\begin{array}{l}
(a') \frac{ \partial \pi_i(x_i, x_{-i},\#x_i)}{\partial x_i} \geq 0\;\;
\;\; \\
(b') \frac{ \Delta \pi_i(x_i, x_{-i},\#x_i)}{\Delta \#x_i} >0,\;\;
\;\;\\
(c) \frac{ \partial^2 \pi_i(x_i, x_{-i},\#x_i)}{\partial x_i \partial
x_j} =0\\
\\
(d) \pi_i(0, x_{-i},n) > \pi_i(100, x_{-i},n-1),\;\;\;\; \\
(e) \pi_i(w,
x_{-i},l) > \pi_i(w', x_{-i},l-1) \forall l, w, w'\neq x\\
\end{array}
\end{equation}
Assumption (a') says that the payoff to player $i$ rises or stays the
same as the magnitude of the group action $x_i$ rises-- from 88, say,
to 89. Assumption (b') says that the payoff to choosing action $x_i$
rises from being in a bigger group.
Assumption (c) says that the payoff
to player $i$ from choices made by players who choose discoordinating
actions does not depend on which actions they choose. I might not need
this one.
Assumption (d) says
that group size matters more than action size: the payoff to $i$ from
choosing $x_i=0$ in a group of $n$ is bigger than from choosing
$x_i=100$ in a group of size $n-1$. Assumption (e) is a more general
version of (d), saying that a larger group always gets a bigger payoff,
no matter what the size of the action. I probably do not need these for
my $N=3$ case.
An example (for which I thank Michael Rauh and Michael Baye) is:
\begin{equation}\begin{array}{l}
\pi_i(x_i, x_{-i},\#x_i) = [\#x_i(1+ \frac{x_i}{1000}) -n] (100/1.1n)
\end{array}
\end{equation}
or, without our normalization of $\pi_i(0, x_{-i},n) =0$ and
$\pi_i(100, x_{-i},n) =100$,
\begin{equation}
\pi_i(x_i, x_{-i},m) = \#x_i(1+ \frac{x_i}{1000})
\end{equation}
\noindent
{\bf Example 2.} Let there be four players, and consider the
equilibrium (5, 5, 5, 5). Suppose player 1 deviates to $x_1=10$ in the
first period. Even believing that player 1 is of type $z=10$, a
unilateral switch by one of the other three players from 5 to 10
would be unprofitable if $\pi_i(x=5, m=3) > \pi_i(x=10, m=2)$. Thus,
this would be an equilibrium outcome. (not quite an equilbirium, since 5
is not a best rsponse to $(10, 10, 10) $ in the first period).
\noindent
{\it Three Players }
With three players and these assumptions, we do get near-optimal
coordination.
\noindent
{\it Four or More Players }
With three players and these assumptions, we do NOT get near-optimal
coordination.
\bigskip
\noindent
{\it Dropping Assumption (b)
$\frac{ \delta \pi_i(x_i,m)}{\delta m} >0$ }
Everything works the same if $n=2$, of course, since assumption (b) is
redundant for that case.
The intuition is similar when we move from two to three players, but
a complication arises. If Player 1 deviates from an inefficient
equilibrium by choosing $x_1=100$, Player 2 cannot unilaterally create
coordination by switching to $x_2=100$, because Player 3 must switch
too.
That is why there are discoordination equilibria too, as mentioned but
not explained earlier. Two examples will illustrate:
(1) Let $p_i=-1$, $N=4$. A Nash equilibrium in the one-shot game is
$(0, 0, 80, 80)$.
(2) Let $N=3$. $\pi(0, 20, 80) = (-1, -1, -1)$. Let $w$ be any
number
on $[0,1]$ except 0, 20, and 80. $\pi(w, 20, 100) = (-10, -2, -2)$.
$\pi(0, w, 80) = (-2, -10, -2)$. $\pi(0, 20, w) = (-2, -2, -10)$.
$p=-20$
for any other discoordination permutation.
A Nash equilibrium in the one-shot game is $(0, 20, 100)$.
The difference between these two examples is that in Example 1 players
1 and 2 would be no worse off if each switched unilaterally to $x=100$,
so the discoordination equilibrium is less plausible.
Because action by a single player cannot restore full coordination,
incomplete information will not be as general a solution to the
coordination problem now as it was in the two-player games. Consider how
the possibility of a player constrained to play $x=1$ would affect the
discoordination equilibrium in Example 2. If the first-period choices
were $(1, .2, .8)$, Players 2 and 3 would each conclude that player 1
would play $x_1=1$ in the second period. But in that case, if either
switches unilaterally to $x=1$, their payoffs will fall from -2 to -20.
Nonetheless, there are two ways the incomplete information argument
can be adapted to multi-player games, by applying a dominance argument
in an important special case, and by changing the kind of
incompleteness.
First, let us apply the dominance argument. We will now confine
ourselves to a special case, the case in Example 1, in which $p_i=-v$
for some number $v$. This means that the discoordination payoff is the
same regardless of how many players choose the same $x$, so long as even
one of them diverges, and that payoff does not change with the size of
the divergence. Being discoordinated is like being pregnant: the
players are either coordinated or discoordinated.
WAIT: WHY WILL THIS WORK? .1 is a best response if all the other
players choose it.
Let us define strategy $s_i$ to be ``weakly dominated'' if its payoff
for player $i$ is (a) no higher than that of any other strategy
regardless of the strategies other players choose and (b) is lower for
some other strategies they might choose:
$\pi_i(s_i, s_{-i}) \leq \pi_i(s_i', s_{-i}) \forall s_i', s_{-i}$ and
$\pi_i(s_i, s_{-i}) < \pi_i(s_i'', s_{-i}'')$ for at least one
$s_i'', s_{-i}''$.
\noindent
{\it The Weak Dominance Refinement: Strategy combination $S_1$ is not
an equilibrium if it includes a weakly dominated strategy and there
exists a Nash equilibrium strategy combination $S_2$ that does not. }
The weak dominance refinement does not involve any iteration and
it applies to equilibrium strategies off the equilibrium path as well as
on it.
Though weak, this is not an obviously correct refinement, since some
equilibria economists generally accept are in weakly dominated
strategies. Notably, the unique equilibrium in a Bertrand game of
charging price equal to marginal cost is weakly dominated by choosing a
higher price. The weak dominance refinement would not rule out that
equilibrium, since it is unique, but I mention it as a caution not to
accept the refinement blindly. Instead, consider my applications below
and decide if you think it rules out plausible equilibria in any of
them.
In the
complete-information coordination game, the weak dominance refinement
rules out some (but not all) equilibrium strategies with a zero
payoff, but no positive equilibrium payoffs.
The weak dominance refinement rules out the coordination equilibrium
with $x=0$.
It also rules out any equilibrium in which some player mixes over a
continuum. Doing so yields an expected payoff of zero in any strategy
combination, because two players choosing the same $x$ has infinitesimal
probability. If a player chose $x=z>0$ instead, and so did all the
other players, his payoff would rise to $z$.
On the other hand, the
weak dominance refinement does not rule out mixed strategy equilibria
that do not mix over a continuum, e.g., each player mixing between .2
and .7.
Nor does it rule out
all zero-payoff equilibria. Nash equilibria in which more than two
players choose different values of $x$ as pure strategies survive. The
equilibrium in Example 1 is an example.\footnote{These will disappear in
the incomplete information game. Someone would deviate to x=1 and the
rest would follow. If it were
(.2, .5, 1), the player choosing x=.2 would deviate to 1.} For example,
(.2, .5, .9) is a Nash equilibrium because no single player's
deviation would raise the payoff above zero. The strategies are
undominated because each of them is a best response to itself; e.g.,
.2, would be the strictly best response if the other players were to
also choose .2.
Now apply incomplete information.
All free players continuing to choose $x$ in the succeeding rounds is
still a Nash equilibrium if $n>2$. They expect to have
discoordination in all $T-1$ of those rounds, but if a single player $j$
unilaterally deviates to $x_j=1$ to try to match the believed-to-be-
constrained player $i$, he cannot prevent discoordination from
continuing, so his deviation will not raise his payoff above zero.
Continuing to choose $x$ is a weakly dominated strategy for player
$j$, however, because a deviation to $x_j=1$ either keeps his payoff at
zero, or, if all $n-2$ other players also choose $x_k=1$, it raises his
payoff to 1. Hence, if we rule out weakly dominated strategies, player
$j$ must choose $x_j=1$ in the second round, and so must all the other
players. But then, a deviation by free player $i$ to $x_i=1$ in round 1
may be profitable for him. This eliminates many stationary
equilibria, except for ones with $x=1$ and ones with $x$ close to 1.
The second approach to the multi-player game is to keep the game
general, but to change the way incomplete information enters. Suppose
that *each period* a player might be transformed into a one-move player.
Then we can use backwards induction. It is possible that in period 1,
player 1 will change, in period 2 player 2 changes, etc. But if that is
so, they will pretend to change too.
Suppose all but one player has chosen $x=1$. The last player will
deduce that the others are one-move players, and will change to $x=1$.
Suppose all but two players have chosen $x=1$. The next-to-last player
will deduce that the earlier players are one-move players and will
continue to pick $x=1$. He knows that if he picks $x=1$ too, the last
player will pick $x=1$. So he does.
Suppose all but $m$ players have chosen $x=1$. The last-but $m-1$
player will deduce that the earlier players are one-move players and
will continue to pick $x=1$. He knows that if he picks $x=1$ too, the
next player will pick $x=1$. So he does.
This induction proceeds player by player, so if there are $N$ players
and they begin with the expectation of not playing $x=1$ then it will
take $N$ periods of discoordination before periods of coordination at
$x=1$ begin. The number of repetitions $T$ must be great enough for
every player in the sequence to be willing to do his part. The ordering
of hte players in the sequence may help, because it can be the player
who suffers least during the discoordination who makes the first
deviation, the one who suffers second-most who makes the second
deviation, and so forth. I will not try to prove all that. But what is
easy to see is that if $T$ is big enough, the induction deviation will
work, in which case coordination at $x=1$ will be immediate.
\bigskip
\noindent
{\bf 6. Mixed Coordination-Conflict Games
}
Incomplete information can actually hurt in mixed coordination-
conflict
games, by destroying the possibility of pure-strategy equilibria.
I will show this in the example of the finitely repeated battle of the
sexes. First, we will need to look at the game with complete
information.
\begin{center}
{\bf Table 2: The Battle of the Sexes }
\begin{tabular}{lllccc}
& & &\multicolumn{3}{c}{\bf Woman}\\
& & & {\it Fight} & & {\it Ballet} \\
& & {\it Fight} & {\bf A,B} & & 0,0 \\
& {\bf Man} && & & \\
& & {\it Ballet} & 0,0 & & {\bf B,A} \\
& && & & \\
\multicolumn{6}{l}{\it Payoffs to: (Man, Woman). $A>B$. }
\end{tabular}
\end{center}
The one-shot game of Table 2 has two
pure strategy equilibria, $(fight, fight)$ and $(ballet, ballet)$, and a
mixed strategy equilibrium.
in which the man plays $fight$ with
probability $m=A/(A+B)$ and the woman with probability $w=B/(A+B)$.
The repeated game has many equilibria, but let us focus on four of them.
Three are time-independent equilibria in which the three one-shot
equilibria are repeated. The total payoffs of the pure-strategy
equilibria are $(TA, TB)$ and $(TB, TA)$.
For comparison later, it will
be useful to lay out the total payoffs of the mixed-strategy equilibrium
for at least one player. The man's expected payoff $V_m(fight,t)$ if he
plays $fight$ is made up of the $w$ he receives if the woman also
plays $fight$, plus the 0 he receives if she plays $ballet$, plus the
continuation value $V_m(fight,t+1)$ of the game:
\begin{equation}
V_m(fight,t) = w A+ (1-w) (0) + V_m(fight,t+1).
\end{equation}
If the man chooses $ballet$, his expected payoff is made up of the
$0$ he receives if the woman plays $fight$, plus the $B$ he receives
if she plays $ballet$, plus the continuation value $V_m(ballet,t+1)$ of
the game:
\begin{equation} \label{ballet1}
V_m(ballet,t) = w (0)+ (1-w) (B) + V_m(ballet,t+1).
\end{equation}
In a mixed-strategy equilibrium the payoffs from the two pure strategies
must be equal, so $V_m(fight,t) =V_m(ballet,t)$ and
$V_m(fight,t+1) =V_m(ballet,t+1)$. Solving $wA = (1-w)B$ is what yields
the woman's mixing probability $w=B/(A+B)$. The man's one-shot expected
payoff is then $AB/(A+B)$, which is less than $B$ since $B p_1,
\end{equation}
and in general if the man has always chosen $fight$ up to $t$ then
\begin{equation}
p_t = \frac{1 * p_{t-1}}{1*p_{t-1} + m_{t-1}*(1-p_{t-1})} >
p_{t-1}.
\end{equation}
Thus, $p_t$ is increasing in $t$ so long as the man always plays
$fight$.
The woman's expected payoffs are
\begin{equation}
Woman's payoff (fight) = p_t B + (1-p_t) [m_t B + (1-m_t)0]
\end{equation}
and
\begin{equation}
Woman's payoff (ballet) = p_t 0 + (1-p_t) [m_t 0 + (1-m_t)A]
\end{equation}
Equating these,
\begin{equation} \label{e20}
p_t B + (1-p_t) m_t B =
(1-p_t) (1-m_t)A
\end{equation}
and
\begin{equation}
m_t = \frac{p_tB + (1-p_t)A}{(1-p_t) (A+B)}.
\end{equation}
This value of $m_t$ would be the same as for the complete-information
game if $p=0$. Otherwise, it is less, and it is decreasing in $p_t$.
Oddly enough, the unconstrained man plays $fight$ with lower probability
the greater the woman's belief that he is constrained and must play
$fight$. That is because the man's mixing probability must make the
woman indifferent between $fight$ and $ballet$ as pure strategies, and
for this to happen when she believes he is more likely to play $fight$
as a constrained player he must be less likely to play $fight$ as
unconstrained.
Since $p_t$ increases with $t$ if the man always chooses $fight$,
$m_t$ falls. As a consequence, $p_t$ not only rises, but it does not
approach any asymptote less than 1, as it might if $m_t$ fell as $t$
rose. For large enough $p_t$, the woman's payoff from $fight$ is equal
to that from $ballet$ even if $m_t=0$, as equation (\ref{e20}) becomes:
\begin{equation}
p_t B =
(1-p_t) A
\end{equation}
This occurs if $p_t$ rises to $\frac{A}{A+B}$. Let us denote the period
in which that occurs as period $S$. In period $s$ and after, if the man
has played $ballet$ throughout, the mixed-strategy equilibrium must
break down and the woman will play $fight$.
Consider, however, the man's incentive in period $(S-1)$. He knows that
if he plays $fight$ for just one period, the two players will play
$(fight, fight)$ for the remaining $(T-S)$ periods, whereas if he plays
$ballet$ they will revert to the complete-information mixed-strategy
equilibrium. An upper bound on his total remaining-game payoff if he
chooses $ballet$ is
\begin{equation}
man's payoff (ballet) = B + (T-S) \frac{AB}{A+B}
\end{equation}
A lower bound on his total remaining-game payoff if he chooses
$ballet$ is
\begin{equation}
man's payoff (fight) = 0 + (T-S) A
\end{equation}
The value of $S$ is independent of the $T$, the total length of the
game. If the game is long enough, $(T-S)$ will be great enough that
$fight$ dominates $ballet$ whatever mixing probability the woman may use
in period $S-1$.
\footnote{xxx But could there be a Benoit-Krishna eq. in which there is
arbitrary behavior and then punishment? That is one without mixing in
every period, though. Even then, my statements hold
true. Periods in which there is no mixing-- just $Fight$ as a pure
strategy-- would have no chnge in $p_t$, though. }
Conjectured mixed-strategy equilibrium: they mix for S periods, then go
to fight, fight if the man has never chosen ballet.
Disproof: Consider period S-1. The man has a strong interest in choosing
Fight then, because he will be the victor. So if (T-S) is big enough,
he will choose Fight in S-1. But then the woman will choose fight in S-1
also. That means he has an even stronger incentive to choose Fight in S-
2. We can induct backwards to FF.
What about two-sided uncertainty? I can show that no mixed-strat. eq.
exists. It would have to give one or the other of them an incentive to
go to S periods to become victor, adn that would make the other back
down. The fact that BOTH would back down is not relevant. The eq. makes
no sense. There CAN be a pure-strategy eq. now-- if either player
backs down and makes the other the victor immediately. But what kind of
out-of-eq behavior si needed?
3. Attrition equilibrium. Conjecture: they mix, and if they go the full
S periods, the man becomes the victor.
Disproof: as in the mixed-strat. eq., the man would persist at S, and
the woman would give up early.
What about two-sided uncertainty? It seems it rules out the attrition
equilibrium also.
[the repeated BS is like repeated bargaining,but simpler.]
J Kennan, R Wilson
Bargaining with Private Information
Journal of economic literature [0022-0515] Kennan yr:1993 vol:31
iss:1 pg:45
Suppose there is probability $p$ that
the man is constrained to choose $fight$. What
happens to the $(ballet, ballet)$ time-independent equilibrium? The
strategy combination
$(ballet, ballet)$ in each period is no longer an equilibrium outcome,
because the woman's best response to the man's choice of $fight$
would be to herself choose $fight$.
The closest to that equilibrium would be for the woman to start by
choosing $prizefight$ with probability $w(t)$ and the man with
probability $m(t)$, each probability depending on $t$, the number of
periods that have elapsed with the man choosing $prizefight$. If the man
ever chooses $ballet$, then the fact that he is free is revealed, and
both players choose $ballet$ thenceforth. If the woman ever chooses
$prizefight$, she continues to do so to the end of the game. Thus, we
have a war of attrition.
Let the expected payoff from the rest of the game to the man be
$V_m(t). $
On the other hand, the period-by-period mixed-strategy equilibrium
also changes. Now, the more the man picks $prizefight$, the more likely
he is to be constrained. This means the woman will eventually come to
believe he is constrained, and will choose $prizefight$ thereafter.
This gives the man more incentive to choose $prizefight$ than he
previously had...
If the man ever chooses $Ballet$, let them revert to the
mixed-strategy equilibrium. If the woman chooses The payoff to the man
must be equal from
each pure
strategy, so
\begin{equation}
\pi_m(prizefight,t) = w(t)A + V_m(t) = \pi_m(prizefight,t) =
\end{equation}
The idea that there is uncertainty associated with a game thus lends
support to the idea that the equilibrium in the battle of the sexes will
be a mixed-strategy one--- though it points to the war of attrition
equilibrium rather than the period-by-period mixed-strategy equilibrium.
\bigskip
\noindent
{\bf Closing Remarks}
This could be tested against the Focal Optimality Theory, whether by
introspection or experimentally, with the following modification of the
game.
The constrained strategies are limited to $z<80$. The Incomplete info
explanation predicts $x=80$, but the Focal Optimality Theory continues
to predict $x=100$. Of course, we have a new focal point too, so the
test is not pure.
\newpage
\noindent
{\bf References}
M Bacharach (1993) ``Variable Universe Games,''
{\it Frontiers of Game Theory}, 1993
Benoit, Jean-Pierre \& Vijay Krishna (1985) ``Finitely Repeated
Games,'' {\it Econometrica,} 53(4): 905-922 (July 1985).
Carlsson, Hans \& Eric van Damme (1994) ``Global Games and Equilibrium
Selection Hans Carlsson,'' {\it Econometrica}, 61(5): 989-1018 (
September 1993).
Crawford, Vincent P. \& Hans Haller (1990) ``Learning How to
Cooperate: Optimal Play in Repeated Coordination Games,'' {\it
Econometrica,} 58(3): 571-595 (May, 1990).
Binmore, Ken \& Larry Samuelson (2005) ``The Evolution of Focal
Points,'' Wisconsin working paper, March 15, 2005. \url{
http://www.ssc.wisc.edu/~larrysam/publications/focal903.pdf}.
Glenn Ellison (1993) ``Learning, Local Interaction, and
Coordination,''
Econometrica, Vol. 61, No. 5. (Sep., 1993), pp. 1047-1071.
Fudenberg, Drew \& Eric Maskin (1986) ``The Folk Theorem in Repeated
Games with Discounting or with Incomplete Information,'' {\it
Econometrica}, 54(3): 533-554 (May 1986).
Goyal, Sanjeev \& Maarten C. W. Janssen (1996) ``Can We Rationally
Learn to Coordinate?'' {\it Theory and Decision,} 40: 29-49.
Goyal, Sanjeev \& Maarten C. W. Janssen (1997) ``Non-Exclusive
Conventions and Social Coordination,'' {\it Journal of Economic
Theory}, 77: 34--57 (1997).
Janssen, Maarten C. W. (2001) ``On the Principle of Coordination,''
{\it Economics and Philosophy} 17(2): 221-234.
Janssen, Maarten C. W. (2001) ``Rationalizing Focal Points,'' {\it
Theory and Decision,} 50: 119-148.
Learning, Mutation, and Long Run Equilibria in Games
Michihiro Kandori; George J. Mailath; Rafael Rob
Econometrica, Vol. 61, No. 1. (Jan., 1993), pp. 29-56.
Kreps, David, Paul Milgrom, John Roberts, \& Robert Wilson (1982)
``Rational Cooperation in the Finitely Repeated Prisoners' Dilemma,'' {
\it Journal of Economic Theory}, 27: 245-252 (August 1982).
Lewis, David (1969) {\it Convention,} Harvard University Press,
Cambridge, Mass.
Morris, Stephen \& Hyun Song Shin (2003) ``Global Games: Theory and
Applications,''
in {\it Advances in Economics and Econometrics (Proceedings of the
Eighth World Congress of the Econometric Society)}, edited by M.
Dewatripont, L. Hansen and S. Turnovsky. Cambridge, England: Cambridge
University Press (2003).
Sugden, Robert (1995) ``A Theory of Focal Points,'' {\it The
Economic Journal,} 105(430): 533-550 (May 1995).
H. Peyton Young The Evolution of Conventions
Econometrica, Vol. 61, No. 1. (Jan., 1993), pp. 57-84.
WHAT NEEDS TO BE DONE:
1. Do the N=3 and N=4 cases.
2. Finish the comlpete info Battles of the Sexes analysis. In
particular: How do the total payoffs compare?
3. Do the incomlpete info Battle of the Sexes analysis.
\end{document}