## Randomization, Communication, and Efficiency in Repeated Games with Imperfect Public Monitoring

by
Michihiro Kandori

Citation

Title:

Randomization, Communication, and Efficiency in Repeated Games with Imperfect Public Monitoring

Author:

Michihiro Kandori

Year:

2003

Publication:

Econometrica

Volume:

71

Issue:

1

Start Page:

345

End Page:

353

Publisher:

Language:

English

URL:

Select license:

Select License

DOI:

PMID:

ISSN:

**Updated:**November 22nd, 2012

Abstract:

Econometricn, Vol. 71, No. 1 (January, 2003), 345-353

NOTES AND COMMENTS

RANDOMIZATION, COMMUNICATION, AND EFFICIENCY IN REPEATED

GAMES WITH IMPERFECT PUBLIC MONITORING1

1. INTRODUCTION

THEPRESENT PAPER shows that the Folk Theorem under imperfect (public) informa- tion (Fudenberg, Levine, and Maskin (1994), FLM hereafter) can be obtained under a much weaker set of assumptions, if we allow communication among players. The FLM Folk Theorem considers long-term relationships, where players can publicly observe some signal, whose probability distribution is affected by their unobservable actions. The FLM Folk Theorem shows that in such a situation, any feasible and individually rational out- comes can be sustained when the signal takes on suficiently many values relative to the number of available actions. In particular, in generic symmetric games with K actions for each player and L different values for the signal, the FLM Folk Theorem obtains when 2K-15L.

While this condition covers a wide range of applications with "rich" signal spaces, it fails when only coarse information is available. For example, the FLM Folk Theorem fails when the outcome (of the signal) is either success or failure (L =2). What is perhaps more troubling, however, is the fact that we may not have a precise idea of the number of possible signal outcomes and actions in any given application. Therefore, it would be valuable to know if the Folk Theorem also holds for the case when the number of possible outcomes is rather small. In the present paper, we show that the Folk Theorem also holds for the case with a small signal space, once we let players communicate.

In particular, we show that for generic symmetric games with at least four players, we can drop the FLM condition on the number of actions and signals altogether and prove the folk theorem under the same condition as in the perfect monitoring case. We mentioned the symmetric case as it provides a clean sufficient condition, but the symmetry is not essential; our condition for the Folk Theorem (condition (1) in Section 3) can also be satisfied for a wide class of (asymmetric) games, even when the signal is binary (success or failure) so that the available information is minimal.

Our equilibrium has the following features. At the end of each period, each player announces which action he has just taken. Players can tell a lie but we will construct

' The original paper was entitled, "Check Your Partners' Behavior by Randomization" (Kandori (1999)). The present paper is mainly based on Section 4 of the original paper, while Section 3 (on private equilibria) is incorporated in Kandori and Obara (2000).

This project was originated in a stimulating conversation with Tadashi Sekiguchi. I would also like to thank A. Matsui, V Bhaskar, J. Moore, the Editor, and three anonymous referees for helpful comments and discussion. Financial aids from CIRJE at University of Tokyo and The Japan Economic Research Foundation are gratefully acknowledged.

equilibria where they voluntarily reveal the true action^.^ Thus the players' future payoffs can depend both on the signal and actions, and a rich class of information can be gener- ated when players randomize. The basic logic is similar to the random sampling technique for quality control. A factory manager randomly picks up one of the products assembled by workers and examines its quality. Even though the outcome of the test is only binary (pass or failure), it can discipline a large number of workers. Note well that, to provide incentives for the workers, their compensation should depend not only on the test result (the value of the signal) but also on whose product was examined (the action of the man- ager). Similarly in repeated games, if players randomize over different actions and the future payoffs can depend both on the realized signal and actions, rich information can be generated to discipline the players.4

A similar idea can be embodied in games without communication. Even without com- munication, it is possible to construct an equilibrium where players randomize over dif- ferent actions and the future payoffs depend both on the realized signal and actions. Such an equilibrium is called aprivate equilibrium, which is ignored by the majority of the exist- ing work, including FLM and Abreu, Pearce, and Stacchetti (1990). A companion paper by Kandori and Obara (2000) explores this issue and shows that such an equilibrium can provide significant welfare improvements.

2. THE MODEL

A group of players i = 1,2. . . ,N repeatedly plays a stage game over an infinite time horizon, t =0, 1,. . . . The stage game payoff function for player i is given by u,(a,, w), where a, E A, is player i's action and w E f2 is a publicly observable signal. Each player's action is not observable to other players. Given an action profile a E A =A, x . . . x A,v, the probability of w is denoted by p(w I a). (We assume that f2 and A are finite sets.) Player i's expected stage game payoff is defined by g,(a) = Em,,u,(a,, w)p(w I a). The average payoff of player i in the repeated game is given by (1 -6)Ez,S1g,(a(t)),where a(t) refers to the action profile in period t and 6 E (0,l) is the discount factor. We denote a mixed strategy profile by a E A =A, x . . . x A,, and abuse the notation to represent the corresponding expected payoff and signal distribution by g,(a) and p(w I a). Finally, we define the stage game payoff profile by g = (g,,.. . ,g,).

Let us now introduce communication in the model. In each period, each player i takes an action, observes w, and then5 (simultaneously with other players) announces a message m,. As we examine the case where the players reveal their action, we assume m, E A,. The players can tell a lie but we will construct equilibria where they voluntarily tell the truth, as we will see in the next section.

-? Communication has been introduced in repeated games with imperfect private monitoring, where each player privately receives a different signal about the past actions (Ben-Porath and Kahneman (1996), Compte (1998), and Kandori and Matsushima (1998)). The main role of communication in those works, which mainly look at pure strategies, is to coordinate the players' actions, rather than to generate more information.

A more detailed explanation can be found in Section 3 (see the discussion regarding panel (b) of Table I).

%ternatively, we can assume that the players communicate before the realization of w. Our results show that the players truthfully reveal their actions after each realization of w. Then, under the same arrangements the players have incentives for truth-telling before observing w, and our results hold for either specification.

3. THE FOLK THEOREM WITH COMMUNICATION

Our equilibrium has the property that each player's future payoff is independent of what he announces. (Therefore, he has a weak incentive to tell the tr~th.~)

At the same time, we need to avoid punishing players simultaneously, as it entails welfare loss (see the explanation below). To put these ideas together, we employ the following construction; for any given pair of players, say 1 and 2, we transfer some of 1's future payoff to 2, when 1's cheating is suspected (and vice versa). Compared to the case where 1 and 2 are punished simultaneously, the transfer entails negligible welfare loss. This is one of the essential ideas employed by the FLM folk theorem. The transfer between 1 and 2 is based partly on the publicly observable signal w, as in FLM, but partly on the announced actions of other7 players (i =3,4, . . . ,N), which is the key to the improved efficiency obtained in the present paper. The transfer scheme to provide the right incentives can be constructed whenever player 1's actions are statistically distinguished from player 2's, so that we can tell which player is suspected of deviation (the precise conditions will be presented shortly). Note also that it needs at least three players, which will be assumed throughout the paper.

First let us introduce some notation. For a given pair of players i and j, we denote their opponents' action profile by a_,. E A_,, = nk,,, ,A,, and their mixed action profile a_,,E A-i, is defined similarly. For any given mixed strategy profile a, let Ri be the matrix whose rows and columns are indexed by a, and (w,a-,,) respectively, with its (ai, (w, a-,.))-element given by

Roughly speaking, R, summarizes the observability of various actions of player i. Each row in Ri represents the distribution of (w, a-ij) given each action of player i, and recall that (w, a_,,) is the relevant information to determine the transfer between i and j. As this matrix depends on who else is in the given pair (i.e., player j) and other players' mixed action profile aq, we denote Ri =Ri(j, aq). Now define Qij(a) by "stacking" R, on Rj;

If Qij(a) has the maximum row rank, we can statistically distinguish what i does from what j does, by looking at (w, a_,-), and it is possible to construct the efficient punishment (transfer) discussed above. This is basically the painvise full rank condition of FLM, except that we utilize both w and a-ij to police players i and j, while FLM utilize only w. The crux of the matter here is that lettingplayers randomize and supplementing the signal w with realized actions a-,, provide more information.

It is possible to provide a strict incentive for truth telling by modifying our equilibrium construc- tion. Kandori and Matsushima (1998) show that when players privately observe random variables that are not independent, we can provide strict incentive to tell the truth. Hence it is not obvious that mixed actions, which are by definition independent, can also be revealed with strict incentives. The crux of the matter is that, conditional on w, the mixed actions are in fact not independent. The details can be found in the discussion paper version of the present paper (Kandori (1999)).

'This induces truth-telling: players i = 3,4,. . . ,N have a (weak) incentive to tell the truth, as their future payoffs are not affected by what they say.

(b)

The crude intuition for this can be obtained by the random sampling analogy discussed in the introduction, but let us provide a more detailed explanation here. Suppose we have a joint production problem with three players, where each player's (unobservable) effort level is either H (high) or L (low). The observable signal w takes on two values, S (success) or F (failure). Assume now a (possibly mixed) action profile a is being played. Without communication, we must determine the transfer between players 1 and 2 solely on the basis of w. This is the traditional approach taken by FLM. The probability distribution of w is given by the matrix represented as panel (a) of Table Is (the counterpart of our matrix Q,,(a)). For example, the first row represents the distribution of w, when a, =H, given that other players are mixing according to a_,. To distinguish 1and 2's behavior, we need that those rows are "distinct" in the sense of linear independence. As there is one linear constraint9 for the rows, the distinguishability holds when the matrix has the maximum possible row rank 3. This is the FLMpainvisefill rank condition. This condition, however, cannot possibly be satisfied in this example, as the matrix has only two columns. In other words, the binary signal w = S,F cannot possibly distinguish two player's actions.

Suppose, in contrast, that we let players randomize and introduce communication, to use both w and a, (the truthfully announced action by player 3) to determine the trans- fer between player 1 and 2. The distribution of (w, a,) changes according to 1 and 2's actions, and it is summarized by our matrix Q,,(a), represented as panel (b) of Table I. Now that we have more columns,"' it is possible that the matrix has the maximum row rank 3 (for a generic choice of entries1'). In other words, with the richer information (w, a,), we can now distinguish players 1 and 2's actions. To understand why this is the case, the following consideration may help. When player 1 reduces his effort, it may always increase the chance of failure (F), but the magnitude of this effect depends on (among other things) player 3's effort level. For example, if there is a strong complementarity between 1 and 3's efforts, the reduction of 1's effort sharply increases the chance of failure,

The entries are left blank, as they are not essential for the argument here. a, (H) x (the first row) +a,(L) x (the second row) represents the distribution of w under a, which is also equal to a,(H) x (the third row) +a2(L)x (the fourth row). "' Note, however, that there is one linear dependence for the columns, as the first two columns add up to a,(H)(1, 1,1, I)', which is proportional to the sum of the last two columns a,(L)(1, 1,1,1)'.

"It is not completely obvious that we can suitably perturb the entries by slightly changing the information structure p(w / a), as they also depend on the mixed strategy profile under consideration. Note that we have to consider various mixed strategy profiles to obtain the Folk Theorem. Lemma 2 formally addresses this issue.

when 3 is working hard (while the effect may be minute when 3's effort is low, as 1's effort is rather useless without the help of 3). When the complementarity is not so strong between 3 and 2's efforts, in contrast, the reduction of 2's effort has somewhat different effects on the relative likelihood of (w, a,). Hence we may statistically distinguish 1 and 2's effort levels by looking at (w, a,).

This is why letting 3 randomize and reveal his action through communication may be useful. Although 3's action itself does not contain any information, the informativeness of the signal w (concerning 1 and 2's actions) does in general depend on 3's action.

Let us now generalize the observations obtained in the above example. We are going to derive a necessary condition under which Q,-(a) has the maximum row rank. (The condition turns out to be sufficient in generic games, thanks to Lemma 2 below.) Let q,(ak) (k = i, j) and q,,(w, a_,,) be the akth row and the (w, a-,,)th column of matrix QLj(a). The simple case presented in panel (b) of Table I would be useful to understand the (unavoidably) heavy notation. The number of the columns is 101x IA-,,I, but as we have seen in panel (b) of Table I (see footnote lo), the identity C,Pr,(w,a-ijlak) = a-,,(a-,,) for k =i, j imposes some linear dependence among them. Namely, we have

for each a_,,, and this implies that we have I A_,,I -1 linear constraints for the col~mns.'~ (Note that those constraints do not exist in FLM (see panel (a) of Table I).) Therefore, at most (101 x IA-,I) -(IA_,,I -1) = (101-1)nki,,Ak +1columns can be independent. The number of rows are I A, I +I A, 1, but as in the above example (see footnote 9), there is one linear constraint among them. Namely, we have I,,q,,(a,)a,(a,) =C,, q,(a,)a,(a,) as both sides are equal to the probability distribution of (w, a_,,) under mixed strategy profile a. Hence at most I A,I + I A, I -1 rows can be independent. (Note that the same constraint also appears in FLM.) Therefore, a necessary condition for Q,,(a) to have the maximum row rank is (101 -1) nk,,,, Ak + 1 ? IAII+ IA,I -1, or

This is a necessary condition for the matrix Qi,(a) to have the maximum row rank IA,I + 1 Aj1 -1. Lemma 2 in the Appendix shows that it is also generically sufficient: for a generic choice of the underlying information structure p(w I a), Qi,(a) has the maximum row rank whenever condition (1) is satisfied. This leads us to the following folk theorem. Let yi be player i's minimax value gi = maxaL mine-, gi(ai, ci). Define the set of feasible and individually rational payoffs by V* = {v E co[g(A)] / Vi v;2 yi), where co[g(A)] is the convex hull of pure strategy stage payoffs.

PROPOSITION (Folk Theorem with Communication): Suppose N 2 3 and V*has non- empty interior. Under (I), for a generic choice of the signal distribution, any feasible and

l2Fix any a!,,. For each a-, fa",, we have

individually rational payoff profile can be approximately achieved by a sequential equilibrium with communication, if the discount factor is sufjiciently close to unity.

A sketch of the proof is presented in the Appendix, and the full proof can be found in the discussion paper version, Kandori (1999). Condition (1) is weaker than the FLM condition,

whenever N >3. Recall that our equilibrium with communication works only when N 2 3, and we are assuming JA,I r 1 (otherwise player k has nothing to choose). Let us now examine when (1) is likely to be satisfied. Note that (1) is most difficult to hold when I Ail and I A, I are large and I A, Iis small (k #i,j). However, even in such a strongly asymmetric case, (1) can be satisfied if there are many players. As we may assume that 101>1(otherwise no information is available) and each player has something to choose, the left side of (1) is at least 2"-2. This quickly becomes a large number as N increases, so we conclude that our Folk Theorem is likely to hold when there are many players. If players have similar numbers of actions, in contrast, our Folk Theorem quite generally holds. A clean statement is obtained when players have the same number of available actions, such as in (the finite version of) the Green-Porter oligopoly model (1984), where A, =(0, 1.2,. ..:H) is the set of possible outputs. Let K =H +1 be the number of available actions. Then, condition (1) reduces to (101 -l)KN-* 2 2K -2, and this is always satisfied13 when N >4. In other words, we can drop the FLM conditions altogether for generic games in this class.

COROLLARY 1': Consider a game where the players have an equal number of actions, and suppose N r 4 and V*has nonempty interior. Then, for a generic choice of the signal distribution, the Folk Theorem under imperfect public information holds with communication.

A similar result also holds for symmetric games. As some restrictions are imposed by the symmetry of p(w I a), we have to check if the generic full rank properties (Lemma 2 in the Appendix) also hold for symmetric games. The answer turns out to be positive, and we obtain the following result (see the discussion paper version, Kandori (1999), for the proof).

COROLLARY 2': Consider symmetric games, and suppose N 2 4 and V*has nonempty interior. Then, for a generic choice of the (symmetric) signal distribution, the Folk Theorem under imperfect public information holds with communication.

REMARK: AS d7Aspremont and Gerard-Varet (1998) note, the contract problem in the Appendix with h =(1,. ..,1) can be interpreted as the static contract (moral hazard) problem for joint production with risk neutral players. Our proof shows that efficiency can generically be achieved with communication in such a problem, under a quite weak condition (1). In particular, players in a joint production problem may well have the same

l3 As we exclude the case where there is no information, we have 10112. Then N 14implies

(~(~)l-1)K~1-2-(2K-2)~K2-2K+2=(K-1)2+l>0.

number of available actions, and our Corollaries show that we can generically achieve efficiency with at least four players, when the compensation scheme depends not only on the outcome obut also on verifiable messages of players.

Faculty of Economics, University of Tokyo, 7-3-1 Hongo, Bunkyo City, Tokyo 113-0033, Japan; kandori@e.u-tokyo.ac.jp

Manuscript received June, 1999; final revision received June, 2002.

APPENDIX

Here we present a sketch of proof of our Folk Theorem (Proposition). The proof utilizes the Fudenberg and Levine (1994) (FL hereafter) algorithm, which allows us to determine the limit (6 + 1) equilibrium payoff set in the repeated game by means of a set of associated static contract problems. Let us present the modified version of the FL algorithm to fit our model with commu- nication. Let m, = c,(a,, w) be player i's communication strategy in the stage game (i.e., player i announces that m, =c,(a,, w) E A, is the action he has taken, when he actually chose a, and the real- ized signal is w). Let x(w, m) = (x,(w, m), . . . ,x,(w, m)) represent the "transfer" to each player, given w and announced action profile m. For a given welfare weight A = (A,, . . . ,A,) # 0,we define the "maximized welfare" (or, following FL, maximum "score") k(A) by

sup A. (g(a) +E[x I a, c]) subject to

a. C. X

where E[x I a, c] is the expected value of x(o, m) under (a, c). This could be interpreted as a static contract problem, where the social planner tries to maximize the social welfare by means of the side payment scheme x. This is closely related to the incentive constraints for the repeated game, where x corresponds to the variation of continuation payoffs in the repeated game.I4 This is a rough intuition for why the above programming problem is useful in calculating the equilibrium payoff set in the repeated game. Define D(A) = {v E 9LN I Av 5 k(A)} and let VC(6) be the set of perfect semipublic equilibrium payoffs in the game with communication under discount factor 6. (A perfect semipublic equilibrium is a sequential equilibrium where each player's action at time t depends only on the past history of signal and messages (~(s), m(s)), s < t.) Then we have the f~llowing.'~

LEMMA1 (The FL Algorithm with Communication):

lim Vc (6) 3 nD(A),

6-1

APO

if the right hand side has nonempty interior.16

l4Condition (B), which may be interpreted as the budget constraint in terms of the contract problem interpretation, stipulates that the payoff variations cannot go beyond the boundary of the equilibrium payoff set, whose tangent vector is given by A.

Is This is the modification of the FL algorithm by means of communication, obtained by Compte

(1998) and Kandori and Matsushima (1998).

l6If we used mixed communication strategies in the definition of kc(A), we would have equality

rather than set inclusion 3.For our purpose this weaker version suffices.

The proof of the Proposition is obtained by showing that the maximum possible welfare can be attained for each A f 0 in the above programming problem so that we have n,,, D(A) 1V'. Lemma 2 below, which corresponds to the painvise and individual full rank conditions of FLM, plays a key role in designing incentive compatible side payment schemes that entail no welfare loss (A. E[x I a, c] = 0). An informal description of such transfer schemes is given at the beginning of Section 3, and the formal construction can be found in the discussion paper version (Kandori (1999)).

LEMMA 2 (Generic Full Rank Conditions with Communication): Under (I), the following state- ments are true for a generic choice of signal distribution p(o 1 a).

- (1)
- For any E > 0 and any pure strategy profile a, there is a mixed stratem profile a such that Ig(a) -g(a)l iE and Q,,(a) has the maximum row rank for any pair i, j.
- (ii)
- Take any E > 0 and any profile (a,, a-,) where a, is a best response against a-,. Then there is a profile (a;, a',) such that l\g,(a,, a-,)-g!(a:, n',)ll < E, a; is a best response against a',, and Rj(i, (a;, a:,)) has,full row rank for each j # i.

Remark: (i) and (ii) are generic versions of the painvise and individual full rank conditions of FLM, suitably modified to fit our model with communication. The individual full rank condition (ii) is necessary to support the point that gives player i his maximum or minimax payoff.

PROOF: (i) We first show that Q,,(a) has the maximum row rank under (1) for a parricular choice of a and p(w i a). Then we goon to show that the same is true for generic a and p(w I a). For each pair i, j, fix a profile a(;, j) = (a:, a;, a!,,), where is completely mixed." Thanks to the fact that players i and j are choosing pure actions, Q,,(a(ij)) has a simple structure. To see this, we first construct a matrix P(a_,), each row of which represents the probability distribution of w under a unilateral deviation by player i or j from the action profile (a:, a?, a_,,). Let p(a) be the 1 x fli vector representing the probability distribution of w given action profile a. Let n,(a ,,) be the IA, x 101matrix whose rows are p(a,, a;, a_,,), a, E A,, and similarly define the A, 1 x Rl matrix nj(a_,,). With this notation, we define P(a_,,) to be the (IA,l+All)x 1121 matrix obtained by stacking n,(a-,,) on IT,(a_,,). If we denote A_,, = {a!,,, . . . ,a!',,}, where M = IAJ, the structure of Q,,(a(ij)) is expressed as

Since we assumed that a!,,(a-,,) > 0 for all a-,,, we have

rank Q,,(a(ij)) = rank (P(a!,,), . . . , ~(a!',,))

Note that the matrix (P(a!,,), . . . ,P(a?,,)) has two identical rows. (This is because each P(a_,,) has two rows equal to p(af, a:, a_,,), as it appears in both n,(a ,,) and n,(a_,,).) Delete one of them, and denote the resulting matrix by (P (a!,]), . . . , P (a:,)). As the delet~on does not affect the rank,

(2) rank Q,](a(ij)) = rank (P'(a!,,), . . . , ~'(a:,))

Recall that each row in P'(a_,,) represents a probability distribution of w, and note that each element in the matrix (P'(a!,,), . . . , P'(a!,,)) is equal to p(w I a), with distinct (o, a) for each element. Hence, by changing p(w I a), we can freely perturb (P'(a!,,), . . . ,P'(af,,)) subject to the constraints (i) each element must be nonnegative, and (ii) the columns of each matrix P'(a_,,) must add up to (1, . . . , 1)'. The latter shows that at most (10 -1)n,,,,,

A, + 1 columns are linearly independent, as we have seen when we derived condition (1). Given that there is a priori no other restriction, it is rather obvious that there is an information structure p' for which (P'(a!,,), . . . ,P'(a.'',)) has full row rank, if the number of possibly independent columns exceeds the number of rows IA,I + IA, -1 (this is precisely our condition (1)). For completeness, I offer an example of p*in what follows.

I' We treat a(;, 1) as a mixed action profile, and its first two elements, af, and a;, are interpreted as the degenerate mixed actions that play a:, and a: with probability one.

From the matrix P'(a-,,), delete the last column, and denote the resulting (IA,I + A,I -I) x (101-1) matrix by P"(a_,,). Note that each element of this matrix is p(o I a) for some w and a, and therefore there is a priori no restriction of this matrix except (i) each element is nonnegative and (ii) the sum of the elements in each row is less than or equal to 1. Let P be the square matrix formed by the first IA, I + A, I -1 columns of matrix

We can choose p*(o I a) in such a way that P is an upper triangle matrix (matrix whose lower diagonal elements are 0) with diagonal elements all equal to 1. (This is possible because any row of P"(a-,,) can be equal to a zero vector.) Matrix P has full rank = IA,I + IA,I -1, as the determinant of P is nonzero (it is equal to 1, the product of its diagonal elements). Hence under information structure p*, matrix (P'(U!,~), . . . ,P'(a,yi1)) has full row rank A,I + IA,j -1, as its submatrix P achieves the same row rank. By (2), matrix Q,,(a(ij)) also has full row rank IA,I +IA, -1 under p*.

So far we have shown that ~,,(a) has the maximum row rank for a = a(;, j) and p(w I a) = p*(o I a). Now we show that the same is true for generic a and p(w I a). Take any (IA,I +IA, -1) x (IA, +I A, I -1) submatrix of Q,, (a(;, j)) that is nonsingular when p(w I a) =p*(w a), and denote its determinant by D,,. Since D,, is a polynomial in p(w I a) and nonzero for p*(o I a), we conclude that it is nonzero on an open and dense set, say P(i, j), in the space of all possible signal distributions. In other words, Q,,(a(i, j)) has the maximum row rank under (1) in an open and dense set, say P(i, j), in the space of all possible signal distributions p(. .). Thus in an open and dense set n,,,,,,, P(i, j), for each pair i, j, Q,,(a(i, j)) has the maximum row rank. Now fix a p(. I .) in this generic set. Since D,, is also a polynomial in a and nonzero for a = a(;, j), we conclude that it is nonzero on an open and dense set, say A(;, j), in the space of mixed strategy profiles. Thus, for a generic choice of the signal distribution, Q,,(a) has the maximum row rank for each i, j on an open and dense set n,,,,,+, A(;, j). Claim (i) then follows from the continuity of the stage payoff function g.

(ii) By a similar argument as above, we can show that for a generic choice of the signal distribu- tion, there is an open and dense set 4' such that for any pair i, j and any a;', the matrix R,(i, (a:', a",)) has full row rank if a" E 4'. Choose a' E A' so that a', is sufficiently close to the given profile &_,. Then, we have Ilg, (a,, a-,) -g,(a;, a',) 11 < F by Berge's Theorem (on the continuity of maximized value), and R,(i, (a:, a',,)) has full row rank for each j f i. Q. E. D.

REFERENCES

ABREU, D., D. PEARCE, AND E. STACCHETTI (1990): "Towards a Theory of Discounted Repeated Games with Imperfect Monitoring," Econometnca, 58, 1041-1064. BEN-PORATH,E., AND M. KAHNEMAN (1996): "Communication in Repeated Games with Private Monitoring," Journal of Economic Theoly, 70, 281-297. COMPTE,0. (1998): "Communication in Repeated Games with Imperfect Private Monitoring," Econometnca, 66, 597-626. D'ASPREMONT,C., AND L. GERARD-VARET (1998): "Linear Inequality Methods to Enforce Part- nerships under Uncertainty: An Overview," Games and Economic Behavior, 25, 311-336. FUDENBERG,D., AND D. LEVINE (1994): "Efficiency and Observability with Long-Run and Short- Run Players," Journal of Economic Theov, 62, 103-135. FUDENBERG, D., D. LEVINE, AND E. MASKIN (1994): "The Folk Theorem with Imperfect Public Information," Econometnca, 62, 997-1040. GREEN, E., AND R. PORTER (1984): "Noncooperative Collusion under Imperfect Price Information," Econometnca, 52, 87-100. KANDORI, M. (1999): "Check Your Partners' Behavior by Randomization," CIRJE Discussion Paper F-49, University of Tokyo; http://www.e.u-tokyo.ac.jp/cirje/research/dp/99list.htm . KANDORI, M., AND H. MATSUSHIMA(1998): "Private Observation, Communication and Collusion," Econornetnca, 66, 627-652. KANDORI, M., AND I. OBARA (2000): "Efficiency in Repeated Games Revisited: The Role of Private Strategies," The University of Tokyo and UCLA, mimeo.

Comments