\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}