    \documentstyle[12pt,epsf]{msart}   


   \textheight 9in 


\begin{large}
         \begin{document}   




   
\section*{ 5 REPUTATION AND  REPEATED GAMES  WITH SYMMETRIC INFORMATION} 

\noindent
June 26, 1993 
 February 5, 1996

   \newpage
 
    
  \noindent
 {\bf Grim Strategy}\\
  {\it (1) Start by choosing {\it Deny}.\\ 
   (2) Continue to choose {\it Deny} unless some player  has chosen
 $Confess$, in which case choose $Confess$ forever.}
   
 
 \noindent
 {\bf Tit-for-Tat}\\
  {\it (1) Start by choosing {\it Deny}.\\ 
   (2) Thereafter, in period $n$ choose the action that the other
player chose in period $(n-1)$.} 

     Tit-for-tat, unlike the grim strategy,
cannot enforce cooperation.   See Problem 5.5 for   elaboration of this point.  

 
   \newpage

  \noindent
 {\bf Theorem 5.1 (The Folk Theorem)}\\
  {\it In an infinitely repeated n-person game with finite action
sets at each repetition, any  combination of actions observed in any
finite number of repetitions is the unique outcome of some subgame
perfect equilibrium given \\
  {\bf Condition 1:} The rate of time preference is zero, or positive
and sufficiently small; \\
 {\bf Condition 2:} The probability that the game ends at any
repetition is zero, or positive and sufficiently small; and\\
  {\bf Condition 3:} The set of payoff profiles
that strictly Pareto-dominate the minimax payoff profiles in the
mixed extension of the one-shot game is n-dimensional.}

 What the Folk Theorem tells us is that claiming that particular
behaviour arises in a perfect equilibrium is meaningless in an
infinitely repeated game. This applies to any game that meets
Conditions 1 to 3, not just ``The   Prisoner's Dilemma''. If an infinite
amount of time always remains in the game, a way can always be found
to make one player willing to punish another for the sake of a better
future, even if the punishment currently hurts the punisher as well
as the punished.  Any finite interval of time is insignificant
compared to eternity, so the threat of future reprisal makes the
players willing to carry out the punishments needed. 

 
 
\newpage
 
\noindent
 {\bf Minimax and Maximin}

In discussions of strategies which enforce cooperation,  the question of  the maximum severity of punishment strategies frequently arises. The idea of the minimax strategy is useful for this: the minimax strategy is defined as the most severe sanction 
possible if the offender does not cooperate in his own punishment. The corresponding strategy for the offender, trying to protect himself from punishment, is the maximin strategy: 

 {\it The strategy $s_i^*$ is a {\bf maximin strategy} for player
$i$ if, given that the other players pick strategies to make his
payoff as low as possible, $s_i^*$ gives him the highest possible
payoff. In our notation, $s_i^*$ solves} 
 \begin{equation} \label{e5.9}
  \stackrel{Maximize}{s_i}\;\; \stackrel{Minimum}{s_{-i}}
\pi_i(s_i,s_{-i}). 
 \end{equation}
   

 The following shows how to calculate the  minimax and maximin strategies for    a two-player game with player 1 as $i$.
\begin{center} \begin{tabular}{llll}
 Maximin:& $Maximum$& $Minimum$ & $\pi_1$.\\
          & $s_1$ &$s_2$&    \\
 Minimax:& $Minimum$& $Maximum$ & $\pi_1$.\\
          & $s_2$ &$s_1$&    \\
\end{tabular}
\end{center}


 In ``The   Prisoner's Dilemma'', the minimax and maximin strategies are
both {\it Confess}.  Although ``The   Welfare Game'' (Table 3.1) has only a
mixed strategy Nash equilibrium, if we restrict ourselves to the pure
strategies the pauper's maximin strategy is {\it Try to Work}, which
guarantees him at least 1, and his strategy for minimaxing the
government is {\it Be Idle}, which prevents the government from
getting more than 0.

   Under minimax, player 2 is purely malicious but must move first
(at least in choosing a mixing probability) in his attempt to cause
player 1 the maximum pain. Under maximin, player 1 moves first, in
the belief that player 2 is out to get him.  In non-zero-sum games,
minimax is for sadists and maximin for paranoids. In zero-sum games,
the players are merely neurotic: minimax is for optimists and maximin
for pessimists.
 
 The maximin strategy need not be unique, and it can be in mixed
strategies.  Since maximin behavior can also be viewed as minimizing
the maximum loss that might be suffered, decision theorists refer to
such a policy as a {\bf minimax criterion,} a catchier phrase (Luce
\& Raiffa [1957] p.  279).


\newpage
 
 

\newpage

 
 It is important to remember that  minimax and maximin strategies are not always pure strategies. In ``The Minimax Illustration Game'' of Table 5.1,   Row can guarantee himself a payoff of 0 by choosing $Down$, so that is his maximin strategy.   Column cannot hold Row's payoff down to 0, however, by using a pure  minimax   strategy. If Column chooses $Left$, Row can choose $Middle$ and get  a payoff of 1; if Column chooses $Right$, Row can choose $Up$ and get a payoff of 1. Column can, however hold Row's payoff down to 0 by choosing a mixed minimax strategy of {\it (Probability 0.5 of  Left, Probability 0.5 of  Right)}.  Row would then respond with $Down$, for a minimax payoff of 0, since either $Up$, $Middle$, or a mixture of the two would give him a payoff of $-0.5$ ($=0.5 (-2) + 0.5 (1))$.\footnote{ Column's  maximin and minimax strategies can also be computed. The  strategy for minimaxing  Column is {\it (Probability 0.5 of Up, Probability 0.5 of Middle)}, his maximin strategy is {\it (Probability 0.5 of Left, Probability 0.5 of Right)}, and his minimax payoff is 0.} 
 
  
\begin{center}
{\bf Table  5.1 ``The Minimax Illustration Game'' }\footnote{This example is   from p. 150 of  Fudenberg \& Tirole (1991).} 

 \begin{tabular}{lllccc}
  &       &             &\multicolumn{3}{c}{\bf Column}\\
  &       &             &    $Left$   &   &  $Right$      \\
  &   & $ Up $      &      $-2, \fbox{2} $ &    & $\fbox{1},-2$ \\
 & {\bf Row:} & $Middle$& $ \fbox{1}, -2$  & &  $-2, \fbox{2}$ \\
&  &         $Down$         &    $ 0, \fbox{1} $ &    &  $0,\fbox{1}$ \\  
\multicolumn{6}{l}{\it Payoffs to: (Row, Column).}
\end{tabular}                
\end{center}

 In  two-person zero-sum games,  minimax and maximin strategies are more directly useful, because when player 1 reduces player 2's payoff, he increases his own payoff. Punishing the other player is equivalent to rewarding yourself. This is the origin of the celebrated 
 {\bf Minimax Theorem} (von Neumann [1928]), which  says that a minimax
equilibrium exists in pure or mixed strategies for every two-person
zero-sum game  and is identical to the maximin equilibrium.  Unfortunately, the  games that  come up in   applications   are almost never zero-sum games, so the Minimax Theorem is inapplicable. 
 

\newpage


 
   \begin{center}
{\bf ``Product Quality''}\\
\end{center}
 {\bf Players}\\
  An infinite number of potential firms and a continuum of consumers.

 \noindent
  {\bf Order of Play}\\
 (1) An endogenous number $n$ of firms decide to  enter the
market at cost $F$.\\
 (2) A firm that has entered chooses its quality to be $High$ or
$Low$, incurring the constant marginal cost $c$ if it picks $High$
and zero if it picks $Low$.  The choice is unobserved by consumers.
The firm also picks a price $p$.\\
  (3) Consumers decide which firms (if any) to buy from, choosing
firms randomly if they are indifferent.  The amount bought from firm
$i$ is denoted $q_i$.  \\
 (4) All consumers observe the quality of all goods purchased in that period.\\
  (5) The game returns to (2) and repeats.

\noindent
 {\bf Payoffs}\\
 The   consumer benefit from a product of low quality
is zero, but consumers are willing to buy quantity $q(p) =
\sum_{i=1}^n q_i$ for a product believed to be high quality, where
$\frac{dq}{dp} < 0$.\\
  If a firm stays out of the market, its payoff is zero.\\
 If firm $i$ enters, it receives $-F$ immediately. Its current end-of-period
payoff is $q_ip$ if it produces $Low$ quality and $q_i(p-c)$ if it
produces $High$ quality.  The discount rate is $r \geq 0$.


\newpage
 
      Consider the following strategy
profile:

\noindent
 {\bf Firms.} $\tilde{n}$ firms enter. Each produces high quality and
sells at price $\tilde{p}$. If a firm ever deviates from this, it
thereafter produces low quality (and sells at  the same price $\tilde{p}$).  The
values of $\tilde{p}$ and $\tilde{n}$ are given by equations (5.\ref{e5.2})
and (5.\ref{e5.7}) below.

\noindent
  {\bf Buyers.} Buyers start by choosing randomly among the firms
charging $\tilde{p}$. Thereafter, they remain with their initial firm
unless it changes its price or  quality, in which case they switch
randomly to a firm that has not changed its price or quality.

\noindent
   This strategy profile is a perfect equilibrium.  The equilibrium must satisfy three constraints that
will be explained in more depth in Section 7.3: incentive
compatibility, competition, and market clearing. 

 The incentive compatibility constraint says that the individual firm
must be willing to produce high quality. 
  \begin{equation}\label{e5.2} 
 {\bf (incentive \; compatibility)}\;\;\;\;\;\;\;\;\;
\frac{q_i p}{1+r} \leq \frac{q_i(p-c)}{r}. 
 \end{equation}
 Inequality (5.\ref{e5.2}) determines a lower bound for the price, which must
satisfy
 \begin{equation}\label{e5.3} 
  \tilde{p} \geq  (1+r)c .
 \end{equation}
   Condition (5.\ref{e5.3})  will be satisfied as an  equality,    because any firm trying to charge a price higher than the
quality-guaranteeing $\tilde{p}$ would lose all its customers.
  
   The second constraint is that competition drives profits to zero,
so firms are indifferent between entering and staying out of the
market.
 \begin{equation}\label{e5.4}
 {\bf (competition) }\;\;\;\;\;\;\;\;\; \frac{q_i(p-c)}{r} = F.
  \end{equation}
 Treating (5.\ref{e5.2}) as an equation and using it to replace $p$ in
equation (5.\ref{e5.4}) gives
 \begin{equation}\label{e5.5}
q_i =  \frac{F }{c}.
\end{equation}
    We have now determined $p$ and $q_i$, and only $n$ remains, which
is determined by the equality of supply and demand.   
  \begin{equation}\label{e5.6} 
 {\bf (market \;\; clearing) }\;\;\;\;\;\;\;\;\; nq_i = q(p).
   \end{equation}
  Combining equations (5.\ref{e5.2}), (5.\ref{e5.5}), and (5.\ref{e5.6}) yields
  \begin{equation}\label{e5.7}
  \tilde{ n} = \frac{cq([1+r]c)}{F }.
  \end{equation}

  


\end{large}

\end{document}
