Games and Economic Behavior 51 (2005) 264–295 www.elsevier.com/locate/geb
Asymptotic expected number of Nash equilibria of two-player normal form games Andrew McLennan a,∗ , Johannes Berg b a Department of Economics, University of Minnesota, 271 19th Avenue South, Minneapolis, MN 55455, USA b Universität zu Köln, Zülpicher Strasse 77, Institut for Theoretische Physik, D-50937 Köln, Germany
Received 14 November 2003 Available online 10 December 2004
Abstract The formula given by McLennan [The mean number of real roots of a multihomogeneous system of polynomial equations, Amer. J. Math. 124 (2002) 49–73] is applied to the mean number of Nash equilibria of random two-player normal form games in which the two players have M and N pure strategies respectively. Holding M √ fixed while N → ∞, the expected number of Nash equilibria is √ approximately ( π log N /2)M−1 / M. Letting M = N → ∞, the expected number of Nash equilibria is exp(N M + O(log N )), where M ≈ 0.281644 is a constant, and almost all equilibria have each player assigning positive probability to approximately 31.5915 percent of her pure strategies. 2004 Elsevier Inc. All rights reserved. JEL classification: C72 Keywords: Random games; Nash equilibrium; Two-player games; Normal form games; Computational complexity; Statistical mechanics; Disordered systems
* Corresponding author.
E-mail addresses:
[email protected] (A. McLennan),
[email protected] (J. Berg). URLs: http://www.econ.umn.edu/~mclennan, http://www.thp.uni-koeln.de/~berg/. 0899-8256/$ – see front matter 2004 Elsevier Inc. All rights reserved. doi:10.1016/j.geb.2004.10.008
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
265
1. Introduction Few game theorists would disagree with the assertion that, at least subjectively, Nash equilibrium is a complex concept. For certain particular classes of games it is possible to analyze the set of Nash equilibria without undue difficulty, but even seemingly quite minor modifications of a game from such a class typically render equilibrium analysis intractable. For general extensive or normal form games, only quite small examples can be solved by hand. New software has significantly extended the range of games for which equilibrium analysis is possible,1 but it is still easy to bump up against the limitations stemming from computational complexity. Results concerning the number of Nash equilibria provide lower bounds on the computational complexity of various computations. One of the earliest papers discussing the number of mixed equilibria, McKelvey and McLennan (1997), gave a combinatoric characterization of the maximal number of totally mixed Nash equilibria associated with payoffs for a given normal form. Their result implies that in various cases the maximal number of totally mixed equilibria, and a fortiori the worst case complexity of computing these equilibria, grows exponentially with the size of the game. Here we continue this line of research, studying the mean number of Nash equilibria of all sorts—pure, partially mixed, and totally mixed—of random two-player normal form games. Suppose that S1 and S2 are nonempty finite sets of pure strategies for agents 1 and 2. The set of pure strategy profiles S := S1 × S2 . A payoff for either agent is an assignment of a numerical utility to each pure strategy profile. Our model of a random game is that the two agents’ payoffs are independently distributed, and each payoff is a uniformly distributed point in the unit sphere centered at the origin in RS . Equivalently (due to the invariance of Nash equilibrium under positive affine rescalings of the payoffs) we could assume that the agents’ payoffs at the various pure strategy profiles are i.i.d. normal random variables. Let M := |S1 | and N := |S2 | be the number of pure strategies possessed by the two agents. Let ν˜ M,N be the number of Nash equilibria of the random M × N game, and let EM,N be the mean of ν˜ M,N , that is, the expected number of Nash equilibria of a random game, given this distribution on payoffs. Much of the analysis is concerned with the case M = N ; let ν˜ N := ν˜ N,N and EN := EN,N . The support of a Nash equilibrium is the pair (T1 , T2 ) whose components are the sets of pure strategies that are assigned positive probability. At an equilibrium with support (T1 , T2 ) the first (second) agent’s mixed strategy satisfies a linear system of equations expressing the equality of the expected utilities, for the second (first) agent, of the pure strategies in T2 (T1 ). If T1 and T2 have different numbers of elements, then one of these two systems of linear equations will have more equations than degrees of freedom, and will consequently have no solutions when the utilities lie in a generic set that has probability one under our model of a random game. Thus, with probability one all equilibria have supports in which |T1 | = |T2 |. Since the distribution of games is symmetric with respect to interchange of pure strategies, the expected number of equilibria with support (T1 , T2 ) depends q only on this number. For q = 1, . . . , min{M, N } let ν˜ M,N be the number of Nash equilibria 1 E.g., Gambit (http://econweb.tamu.edu/gambit/).
266
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
of the random M × N game with supports containing q pure strategies for both players. q q q q q q Let EM,N be the expectation of ν˜ M,N , and let ν˜ N := ν˜ N,N and EN := EN,N . Let Φ be the cumulative distribution function of the standard normal distribution N(0, 1). Our first main result involves a function f : (0, 1) × R × R → R given by the formula x2ρ y2ρ − − 2 ρ log ρ + (1 − ρ) log(1 − ρ) + ρ log 2 2 2 + (1 − ρ) log Φ(x) + log Φ(y) .
f (ρ, x, y) := −
Here the variable ρ represents the fraction q/N of the pure strategies receiving positive probability in an equilibrium, while x and y are variables of integration. Since lim ρ log ρ = lim eτ τ = 0, τ →−∞
ρ→0
(1)
there is a unique continuous extension of f to [0, 1] × R × R, and we will regard it as being defined on this domain. √ 2 Let ϕ(x) := e−x /2 / 2π be the density of the normal distribution N (0, 1) with mean t zero and unit variance, and let Dx := ϕ(x) dx. (That is, Φ(t) = −∞ Dx.) The central idea in the proof of Theorem 1 below is that EN is well approximated by ∞ ∞ N 1 Dx Dy exp Nf (q/N, x, y) . N q=1
−∞
−∞
Let A := arg max f be the set of points where f attains its maximum, and let U be any open neighborhood of A. In view of the properties of the exponential function, it is natural to expect (and not so hard to show) that U dρDxDy exp(Nf (ρ, x, y)) → 1 as N → ∞. ∞ N 1 ∞ q=1 N −∞ Dx −∞ Dy exp(Nf (q/N, x, y)) In this way we obtain rather precise statements concerning both the asymptotic rate of growth of EN and (insofar as q represents the number of elements in the support of an equilibrium) the size of the supports of the preponderance of equilibria. Theorem 1. Let M be the maximum of f in [0, 1] × R × R. Then EN = exp MN + O(log N ) . (That is, there is a constant C > 0 such that N −C exp(MN ) < EN < N C exp(MN ) for all N .) For ε > 0 let Rε be the ε-neighborhood of the convex hull of the projection of A onto the first coordinate, so R is the set of ρ such that there are numbers x and y such that f (ρ, x, y) = M. Then for any ε > 0 it is the case for sufficiently large N that the fraction of equilibria with supports using a fraction of pure strategies in Rε is at least 1 − ε: q q/N ∈Rε EN lim = 1. N →∞ EN
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
267
Numerical calculations2 strongly suggest that f has a single maximizer (ρ ∗ , x ∗ , y ∗ ) ≈ (0.315915, 0.797883, 0.797883), at which point the value of f is approximately 0.281644. The results of numerical computation of the ratio EN +1 /EN out to N = 294 are consistent with a asymptotic ratio of e0.281644 = 1.325307. If, in fact, (ρ ∗ , x ∗ , y ∗ ) is the unique maximizer of f , then, asymptotically, all Nash equilibria of a random N × N game have supports for each agent containing ρ ∗ ≈ 31.6% of the pure strategies. The distribution of support sizes has some bearing on a literature investigating the distribution of the number of pure equilibria, as we now explain. Motivated by the feeling that pure equilibria are, in various ways, preferable to mixed equilibria, Dresher (1970) investigates the probability that an N × N game has a pure equilibrium, showing that it converges to 1 − 1/e as N → ∞. Extending this analysis, Powers (1990) and Stanford (1995) show that asymptotically the number of pure equilibria has a Poisson distribution with mean one. (This result is not restricted to two-player games.) Our result can be viewed as a comment on this literature by virtue of showing that the fraction of equilibria that are pure diminishes at an exponential rate. A more substantive point concerns the method of analysis. For pure strategy pairs (s, t) and (s , t ) with s = s and t = t , the events that (s, t) and (s , t ) are pure Nash equilibria are statistically independent, since no payoff enters both sets of equilibrium conditions. Similarly, if it were the case that, as the game became large, the size of the support of almost all Nash equilibria became small relative to N 1/2 , the relevant events, namely that supports of the relevant size had mixed equilibria, would become, for the most part, independent, and one might hope to use this to show that the distribution of the number of equilibria became Poisson in the limit.3 But since we show that, for large N , most equilibria assign positive probability to more than 31% of the agents’ pure strategies, this approach is infeasible. (Nonetheless, the conjecture that the distribution of the number of equilibria is asymptotically Poisson seems intuitively reasonable, and it is not refuted by any computational experience that we know of.) Our second main result shows that a dramatically different rate of growth obtains when the number of pure strategies of one of the players is held fixed while the number for the other player becomes large. Theorem 2. For any fixed positive integer M, treating EM,N as a function of N , we have
√
π log N M−1 1 1 EM,N = 1 + O √ . √ 2 log N M For any ε > 0 it is the case for sufficiently large N that the fraction of equilibria with supports with M pure strategies for both agents is at least 1 − ε: M lim EM,N /EM,N = 1.
N →∞
2 Specifically, the calculations were done using a feature of Mathematica that uses hill climbing methods to find local maxima, without a guarantee of global optimality. 3 Since, among other things, the number of equilibria is odd with probability one (Harsanyi, 1973), this notion would need to be formulated carefully.
268
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
Thus, for fixed M, EM,N diverges as N → ∞, but very slowly, and equilibria with large supports are asymptotically dominant. Some additional related literature is as follows. McLennan (1996) characterizes the maximal number of pure equilibria of a normal form game with generic payoffs, and the maximal number of regular totally mixed Nash equilibria of a normal form game is characterized by McKelvey and McLennan (1997), but it is difficult to pass from these results to a characterization of the maximal number of regular equilibria of all sorts. The maximal number of equilibria of a two-player normal form game has been studied by Quint and Shubik (1997), Keiding (1995), McLennan and Park (1999), and von Stengel (1999), but is not completely understood. An important application of our results is to the determination of the computational complexity of the problem of determining all equilibria of a two-player normal form game. As these issues are studied in computer science, the standard classification is crude (polynomial, NP, exponential, etc.) because this classification is largely independent of the features of particular machines that might be used to perform the calculations. (Hopcroft and Uhlman, 1979 and Papadimitriou, 1994 are standard introductions to the relevant concepts from the theory of computational complexity.) Worst case running time is more commonly studied than mean running time, but not because it is thought of as more relevant or interesting. Rather, it is usually more tractable. A fortiori, Theorem 1 implies that the mean running time of an algorithm for computing all equilibria of an N × N game grows at an exponential (or greater) rate with N . Of course one can infer from this that the worst case running time of such an algorithm must also grow at an exponential rate or worse. On the other hand, by considering the crude algorithm that simply checks every possible support, one may show that the worst case running time is, at worst, exponential. Thus these results give the exact mean and worst case complexity classes, according to the standard classification in theoretical computer science, of the problem of computing all equilibria of a two person normal form game. They suggest that it might be interesting to study equilibrium enumeration procedures from the point of view of bounds on computational complexity that are output-sensitive, i.e., functions of the size of the output as well as the size of the input. Literature on equilibrium enumeration for two person games is surveyed in Section 2.7 of von Stengel (2002). The remainder of the paper has the following structure. In the next section we discuss the “typical” number of equilibria of a random game. Section 3 states the formula from McLennan (2004) giving the mean number of Nash equilibria, with a particular support, for a normal form with arbitrarily many players, and we specialize this formula to the case of two players, obtaining the Key Formula. Section 4 presents some numerical evaluations of the Key Formula, and describes various conjectures that are suggested by the computations. Section 5 presents the proof of Theorem 1. The proof of Theorem 2 is contained in Sections 6–9. Section 10 presents some concluding remarks.
2. Typical games Our results cannot be interpreted as characterizing the “typical” number of equilibria of a random game since, among other things, the mean may be strongly affected by a small set
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
269
of games that have many equilibria. Similarly, Theorem 1’s characterization of the support size of most equilibria does not necessarily correspond to the support sizes of the equilibria of typical games. This section discusses these issues, giving some indication of the state of existing literature on this topic. There are many types of information that could be regarded as giving an indication of the typical number of equilibria. In addition to means, medians, and modes, one could hope to finding limiting distributions of various sorts, but these may not exist. For examthe variables x˜1 , . . . , x˜N ple, consider a quantity of the form SN = exp( N i=1 x˜ i ) where N 2 are i.i.d. N (m, σ ) normal random variables, so that XN := i=1 x˜i is a N (N m, N σ 2 ) variable and the distribution of SN is log-normal. The density of the distribution of N ) is given by αN : (0, ∞) → R++ where SN = exp(X
(ln s − N m)2 1 1 . · · exp − αN (s) := √ 2N σ 2 2πNσ 2 s By solving for the point at which the derivative of the density vanishes, one finds that the mode of the distribution of SN is exp(N (m − σ 2 )). The mean of SN may be calculated by straightforward integration:
∞ X 1 (XN − N m)2 N XN dXN E SN = E e =√ e · exp − 2N σ 2 2πNσ 2 −∞ = exp N m + σ 2 /2 . Of course the median of the distribution is exp{N m}. Thus the ratios of mean to median and median to mode are, respectively, exp{N σ 2 /2} and exp{N σ 2 }. In particular, the median and average of the distribution of SN do not coincide, and in fact their ratio grows exponentially. A natural technique for attempting to construct a limiting distribution is to rescale by dividing SN by its median, since the rescaled distribution has half its mass in (0, 1) and the N := SN / exp(N m) has other half in (1, ∞). It is easily computed that the distribution of U density βN : (0, ∞) → R++ where
1 (ln u)2 1 1 1 √ · · exp − · . βN (u) := √ 2 2 2 2N σ 2πNσ u 2πNσ u Note that for each t ∈ (0, ∞), limN →∞ βN (t) = 0. Roughly, half the mass is being compressed into smaller and smaller neighborhoods of 0, while the other half is being spread “ever more thinly” over the interval (1, ∞). Evidently there is no limitingdistribution. SN = N1 N On the other hand, as N → ∞ the variance of A˜ N ≡ N1 log i=1 x˜ i vanishes like 1/N . In this sense there exists a typical value of A˜ N = N1 E(log SN ) = m which is realized with a probability tending to 1 as N → ∞. In statistical physics a quantity such as A˜ N is said to be self-averaging (in the limit as N → ∞) because the limiting average value that is realized, with probability one, is E(A˜ 1 ). The realizations of the random variables {x˜i } resulting in a given neighborhood of the typical value of A˜ N may be termed typical configurations of the random variables. The probability of an atypical configuration decays exponentially with N , yet, as we have seen
270
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
above, atypical configurations contribute to the average value of SN . In this sense the average value of SN fails to describe typical realizations of the random variables. In this example the existence of a typical value of A˜ N follows from the central limit theorem by construction. The scenario of a random variable with its average growing exponentially with the number of independent random variables is realized in less contrived circumstances in the statistical mechanics of disordered systems. Examples are models of so-called spin glasses, i.e., elementary magnets with random interactions between them, or neural networks learning random patterns (Mézard et al., 1987). In spin glasses, the state of an elementary magnet i is modeled by a binary variable s˜i = ±1, with random interacspin i and j drawn from some distribution. The energy of the system is tions Jij between defined as i,j Jij s˜i s˜j . The number of spin states with a given energy is found to grow exponentially with the number of spins N . One finds that the logarithm of the number of states (termed the entropy) is a self-averaging quantity: In order to find the behavior of this model for typical cases of the random disorder, the logarithm of the number of states has to be averaged over the random interactions. This framework may be brought to bear on random games: In games the number of Nash equilibria averaged over the payoff matrices need not coincide with the number found in typical realizations of the payoff matrices (if they exist), even though typical realizations occur with a probability tending to one as N → ∞. They reason is that, as in the above toy example, atypical realizations of the payoff matrices (occurring with a probability vanishing exponentially with N ) may have an (exponentially) larger number of equilibria than typical realizations, and thus contribute to the average properties. The same holds then for other properties of the Nash equilibria, such as the size of the support (discussed above), or the expected payoffs. Using techniques from the statistical mechanics of disordered systems, the statistical properties of Nash equilibria for typical realizations of the payoff matrices have been calculated by Berg and Engel (1998), Berg and Weigt (1999), and Berg (2000), and the results have been checked numerically. One obtains that for typical realizations of the payoff matrices, the number of Nash equilibria grows asymptotically like exp(N M ), where M ≈ 0.2773 < M, and almost all equilibria of typical payoff matrices have each player assigning positive probability to approximately 30.35 percent (which is less than ρ ∗ ) of her pure strategies. One also finds that for independently and identically distributed entries of the payoff matrices, these results only depend on the first two moments of this distribution (provided the second moment exists and is non-zero). In other words, the results derived for a Gaussian distribution of the payoffs hold for a very generic class of random games. These results are based on a method, the so-called replica trick, which has been successfully applied to a number of problems (Mézard et al., 1987), but is distinctly non-rigorous. For certain models of neural networks, some results first obtained using the replica trick have since been proven rigorously by Talagrand (1998). Here we would like to point to the mathematical challenge of providing a rigorous analysis of the typical properties of equilibria of games with random payoffs. 3. The fundamental formula The basis of our work is a formula from McLennan (2004) for the mean (relative to a natural model of a random game) number of Nash equilibria of a normal form game,
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
271
with any number of players, that have a particular support. This section states that formula. Consider an n agent normal form given by nonempty finite sets S1 , . . . , Sn of pure strategies. Let S := S1 × · · · × Sn be the set of pure strategy profiles. For each agent the space of possible payoffs is RS . The means studied here are defined relative to the model of a random game in which the agents’ payoffs are statistically independent, with each agent’s payoff uniformly distributed in the unit sphere in RS . We call this the spherical model. As with the case n = 2, an equivalent model is given by supposing that the payoffs of the agents at the various pure strategy profiles are i.i.d. random variables whose common distribution is normal. The support of a Nash equilibrium is the n-tuple (T1 , . . . , Tn ) whose components Ti ⊂ Si (i = 1, . . . , n) are the sets of pure strategies that are assigned positive probability. The basis of our work here is a formula established in McLennan (2004) that characterizes the expected (relative to the spherical model) number of Nash equilibria with support (T1 , . . . , Tn ). In preparation for the statement of this formula we define the objects it refers to. The expectation of the absolute value of the determinant of a certain random matrix is the most complicated term of the formula. For i = 1, . . . , n let pi := |Ti | − 1 be the dimension of the simplex of mixed strategies with support Ti , let p := (p1 , . . . , pn ) be the vector of these dimensions, and let p := p1 + · · · + pn . Let D(p) be the p × n matrix with entries 0 if p1 + · · · + pi−1 < k p1 + · · · + pi , Dki (p) = 1 otherwise. For example,
0 0 D(2, 3) = 1 1 1
1 1 0. 0 0
p whose rows are indexed by the The random matrix of interest is the p × p matrix Z integers k = 1, . . . , p, whose columns are indexed by the pairs ij for i = 1, . . . , n and ij j = 1, . . . , pi , and whose entries z˜ k are independently distributed normal random variables p is a p × p matrix of centered normal with mean zero and variance Dki (p). That is, Z random variables with variance matrix D(p)C(p) where 1...1 0...0 ... 0...0 0...0 1...1 ... 0...0 C(p) := .. .. ... . . 0...0 0...0 ...
1...1
272
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
is an n × p column-copying matrix that has exactly p1 1s in the first row, p2 1s in the second row, . . . , pn 1s in the nth row. Continuing the example above, 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 = 1 1 0 0 0. D(2, 3)C(2, 3) = 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 √ For integers a, b 0 let r(a, b) be the probability that 0 / a + 1 is greater than each of 1 , . . . b when 0 , 1 , . . . , b are i.i.d. normal random variables with mean zero. This function will be the central concern of the analysis in Sections ∞ 5–9. Let : (0, ∞) → (0, ∞) be Euler’s function: (s) ≡ 0 exp(−x)x s−1 dx. General Formula (McLennan, 2004). The expected number of Nash equilibria with support (T1 , . . . , Tn ) is n n ( 1 ) −3p/2 2 p | . · r pi , |Si \ Ti | · (2) 2 · E | det Z pi +1 ( ) i=1 i=1 2 From this point forward we consider only the case n = 2. This formula implies a fact we derived earlier from elementary considerations: the expected number of equilibria is zero if has a square block of zeros that is |T1 | = |T2 |, as in the example above, since in that case Z large enough to guarantee that its determinant is zero. Consider the case |T1 | = |T2 | =: q. consists of four q × q blocks. The two diagonal blocks are identically zero, In this case Z while the entries of the off diagonal blocks are i.i.d. N (0, 1) random variables. The absolute is the product of the absolute values of the determinants of the value of the determinant of Z off diagonal blocks. Since these two determinants are statistically independent, the expec is the square of the expectation of the tation of the absolute value of the determinant of Z absolute value of the determinant of a q × q random matrix whose entries are i.i.d. N (0, 1) random variables. The determinant of a q × q matrix is the product of the norms of its rows times the determinant of the matrix obtained by multiplying each row by the constant that makes it a unit vector. In the case of a q × q random matrix whose entries are N (0, 1) random variables, the norms of the rows and the determinant of the normalized matrix are statistically independent. Therefore the expectation of the absolute value of the determinant is the qth power of the expectation of the norm of a random vector in Rq whose components are independent N (0, 1) random variables times the expectation of the absolute value of the determinant of an q × q random matrix whose rows are independently distributed vectors that are uniformly distributed in the unit sphere S q−1 in Rq . The computation of these expectations requires some work, but is not conceptually difficult. The result is the following specialization of the result above to the case of two agents. Key Formula. The expected number of Nash equilibria with support (T1 , T2 ) is zero if |T1 | = |T2 |, and when q := |T1 | = |T2 | it is 22(1−q) r q − 1, |S1 | − q r q − 1, |S2 | − q .
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
273
The simplification of (2) that results in the Key Formula may be understood directly, rather than as a matter of computation. First, the sets S1 and S2 enter the formula only through the factor r |T1 | − 1, |S1 \ T1 | r |T2 | − 1, |S2 \ T2 | . Now consider the case of totally mixed Nash equilibrium: T1 = S1 and T2 = S2 , so that all pure strategies are assigned positive probability. Note that r(a, 0) = 1 for all a. Algebraically, the definition of totally mixed Nash equilibrium consists of: (a) a system of equations stating that agent 2’s mixed strategy is such that all of agent 1’s pure strategies have the same expected payoff for agent 1, (b) a similar system of equations expressing agent 2’s indifference between all of her pure strategies, (c) the two equations asserting that the sums of the probabilities in each agents mixed strategy is one, and (d) the inequalities requiring all probabilities to be positive. The polynomials set to zero in (a) and (b) are homogeneous of degree one, and their solution sets are linear subspaces of the spaces RS1 and RS2 . The conditions in (c) and (d) describe the interiors of the unit simplices in RS1 and RS2 . When |S1 | = |S2 | the subspaces determined by (a) and (b) are both generically one dimensional, and the expected number of totally mixed Nash equilibria can be thought of as the probability that both of these subspaces intersect the interiors of the respective unit simplices. Since the two agents’ payoffs are distributed independently, this probability is the square of the probability that one of them intersects the simplex. The distribution of coefficient vectors in the system of equations (a) is invariant under orthogonal (inner product preserving) transformations of the space of variables, so one should expect the distribution induced by (a) on the space of one dimensional subspaces of RS2 to be uniform in the natural sense; for more details see McLennan (2004). The probability that a uniformly distributed random one dimensional subspace of RS2 intersects the positive orthant is 21−|S2 | . Thus we obtain the Key Formula. There is a temptation to regard r(q − 1, |S1 | − q) as the “probability” that a Nash equilibrium of the truncated game obtained by eliminating all strategies in S1 \ T1 and S2 \ T2 remains an equilibrium when we restore these strategies. There is a sense in which this is true, namely that the probability is the same, independent of the mixed strategy profile. (This follows from the Main Theorem in McLennan, 2004.) But the conditional probability that agent 1 does not want to deviate to a strategy in S1 \ T1 is affected by any additional information one might have about agent 1’s payoff. In our applications of the Key Formula we typically sum over all supports of a particular size. Counting the number of possible supports for each agent, we obtain q
EM,N :=
M N 2−2q 2 r(q − 1, M − q)r(q − 1, N − q) q q
(3)
274
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
and EM,N :=
M
q EM,N
q=1
M
M N 2−2q 2 = r(q − 1, M − q)r(q − 1, N − q). q q
(4)
q=1
4. Numerical evaluation of the mean number of equilibria Since the function r can easily be evaluated by numerical integration, the right-hand side of (4) is easily computed. The results of this computation for 2 M 30 and 2 N 8 are shown in Table 1. Looking down any column, one sees that, for fixed M, EM,N increases with N , but at a slow and decelerating rate. As one goes out the diagonal the ratios EN +1 /EN are 1.3, 1.291, 1.282, 1.277, 1.274, 1.273 for N = 2, . . . , 6 respectively. In fact the ratio for N = 7 is a local minimum, after which the ratio increases steadily, reaching
Table 1 Expected numbers of Nash equilibria of all sorts Numbers of strategies
2
3
4
5
6
7
8
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1.250 1.375 1.456 1.515 1.562 1.599 1.631 1.658 1.682 1.703 1.722 1.739 1.755 1.769 1.783 1.795 1.806 1.817 1.828 1.837 1.846 1.855 1.863 1.871 1.878 1.885 1.892 1.899 1.905
1.375 1.625 1.809 1.954 2.074 2.175 2.264 2.341 2.411 2.474 2.531 2.584 2.633 2.679 2.721 2.761 2.799 2.834 2.868 2.900 2.930 2.959 2.987 3.014 3.040 3.064 3.088 3.111 3.133
1.456 1.809 2.098 2.342 2.554 2.741 2.909 3.062 3.201 3.330 3.450 3.561 3.666 3.765 3.858 3.947 4.031 4.112 4.189 4.262 4.333 4.401 4.466 4.530 4.591 4.650 4.707 4.762 4.816
1.515 1.954 2.342 2.690 3.007 3.297 3.566 3.817 4.052 4.273 4.482 4.680 4.869 5.050 5.222 5.388 5.547 5.700 5.848 5.991 6.129 6.263 6.393 6.519 6.641 6.760 6.876 6.989 7.100
1.562 2.074 2.554 3.007 3.436 3.843 4.232 4.603 4.959 5.300 5.629 5.946 6.252 6.548 6.835 7.113 7.384 7.647 7.903 8.152 8.395 8.632 8.864 9.091 9.313 9.530 9.742 9.950 10.155
1.599 2.175 2.741 3.297 3.843 4.378 4.902 5.415 5.916 6.408 6.888 7.359 7.820 8.273 8.716 9.151 9.578 9.997 10.409 10.814 11.212 11.604 11.989 12.368 12.742 13.110 13.472 13.830 14.182
1.631 2.264 2.909 3.566 4.232 4.902 5.575 6.248 6.920 7.590 8.257 8.920 9.579 10.233 10.882 11.525 12.164 12.797 13.425 14.048 14.665 15.277 15.883 16.485 17.081 17.672 18.258 18.839 19.415
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
275
1.322916 for N = 294.4 These regularities are substantiated theoretically by Theorems 1 and 2. A number of other regularities are apparent in this table, and are not contradicted by any other computations performed by the authors. We describe these now, but it should be stressed that, although each is buttressed by extensive computational experience, and seems to generalize to games with more than two agents, none of these properties of the computed numbers have been proved to hold in general, and consequently they constitute a collection of plausible and challenging conjectures. The most obvious feature of Table 1, and perhaps the most important, is the observation that EM,N is an increasing function of M and N . There is a striking contrast between the simplicity and fundamental character of this property of the data, on the one hand, and the apparent difficulty of extracting enough information from the formula above to be able to prove that this is true in general. Examining second differences, in all computations performed to date it is the case that (EM+2,N − EM+1,N ) − (EM+1,N − EM,N ) < 0. That is, if the number of strategies for one player is held fixed while the number for the other increases, the expected number of equilibria increases at a decreasing rate. Theorem 2 shows that, asymptotically, this must be true on average. For the ‘mixed’ second difference, all experience to date is consistent with the conjecture that (EM+1,N +1 − EM,N +1 ) − (EM+1,N − EM,N ) 0. That is, the rate at which the number of equilibria increases with M is an increasing function of N . Table 1 suggests that the second diagonal difference (EM+2,N +2 − EM+1,N +1 ) − (EM+1,N +1 − EM,N ) is always positive. That is, as one increases the numbers of strategies for both agents, the expected number of equilibria increases at an increasing rate. Theorem 1 shows that, asymptotically, this holds on average as one goes out the main diagonal M = N . This analysis generalizes in a straightforward way to show that this is true along any diagonal of the form N = M + k. All computations to date are consistent with the conjecture that, for all j , the differences EM+1,N − EM,N +1 along diagonals M + N = k are positive if and only if M < N − 1. This means that for any total number of pure strategies for the two agents, the expected number of equilibria will be greater if the strategies are divided more equally between the two agents. 4 At this point the results given by our software diverge from those given by theory, and for this reason we are
inclined to doubt the accuracy of the calculations for large N . Continuing from N = 294, the calculated values of the ratio decline steadily, eventually reaching 1.180734 when N = 1199.
276
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
5. Proof of Theorem 1 The proofs of Theorems 1 and 2 are independent, and are based, respectively, on two quite distinct approaches. Both proofs involve rather lengthy computations. In this section we consider the asymptotic rate of growth of EN , leading to the proof of Theorem 1. We begin by developing an approximation to the right-hand side of (4) that is valid in general. Subsequently we specialize to the case M = N , then reformulate the approximation in a way that allows us to find a portion of the integral that is dominant. Clearly, in view of the Key Formula, any progress in understanding the means of interest must be derived from improved understanding of the function √ r(a, b). Viewing r(a, b) as the probability that a N (0, 1) random variable divided by a + 1 is greater than b other independent N (0, 1) random variables, we may write
b t r(a, b) = DtΦ √ . a+1 In view of the formula Dt = √
ϕ(t) dt ϕ(x) dx Dx,
the change of variables x =
√t a+1
gives
Dx e−ax /2 Φ(x)b
1 1 2 = Dx exp log(a + 1) − ax + b log Φ(x) . 2 2
r(a, b) =
2
a+1
In particular, r(q − 1, M − q) =
1 1 2 log q − (q − 1)x + (M − q) log Φ(x) . Dx exp 2 2
Therefore
M 1−q 2 r(q − 1, M − q) = Dx exp J (M, q, x) q where J (M, q, x) := log
1 1 M + (1 − q) log 2 + log q − (q − 1)x 2 2 2 q
+ (M − q) log Φ(x). Substituting this in (4) yields EM,N =
M
Dx exp J (M, q, x)
Dy exp J (N, q, y)
q=1
M 1 Dx Dy exp log N + J (M, q, x) + J (N, q, y) . = N q=1
(5)
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
277
We now analyze the function J (N, q, x) by separating it into terms that are small in relation to N and ones that grow in proportion to N . Sterling’s formula (e.g., Billingsley (1986, pp. 245–246)) is applied in the form
√ 1 1 log N! = N + log N − N + log 2π + O , 2 N yielding5
1 1 N 1 log N − q + log q − N − q + log(N − q) + O(1) log = N+ 2 2 2 q
N −q q − (N − q) log + O(log N ). = −q log N N
Introducing the variable ρ := q/N ,
N log = −N ρ log ρ + (1 − ρ) log(1 − ρ) + O(log N ). q Substituting into the definition of J and rearranging, 1 J (N, Nρ, x) = N −ρ log ρ − (1 − ρ) log(1 − ρ) − ρ log 2 − ρx 2 2 1 2 + (1 − ρ) log Φ(x) + x + O(log N ). 2 Specializing to the case M = N , then substituting this result into (5) and simplifying (in 2 particular, Dx ex /2 = √1 dx) leads to 2π
EN =
N 1 N
exp Nf (q/N, x, y) + O(log N ) dx dy,
(6)
q=1
where x2ρ y2ρ − − 2 ρ log ρ + (1 − ρ) log(1 − ρ) + ρ log 2 2 2 + (1 − ρ) log Φ(x) + log Φ(y)
f (ρ, x, y) := −
is the function defined in the introduction. We need to show that the right-hand side of (6) is bounded both above and below by exp(MN + O(log N )). We first show that this quantity is an upper bound. Let P := f −1 ([0, ∞)) and Q := f −1 ((−∞, 0)). In general, if S is any set, 1S will denote the indicator function of that set. Let C := sup −2 ρ log ρ + (1 − ρ) log(1 − ρ) + ρ log 2 . 0 2 log ρ + (1 − ρ) log(1 − ρ)/ρ + log 2 , 2 this follows from d log ρ + (1 − ρ) log(1 − ρ)/ρ + log 2 = − log(1 − ρ)/ρ 2 > 0. dρ −
(7)
Therefore ∞ ∞ N 1 · exp(MN ). 1P (q/N, x, y) · exp Nf (q/N, x, y) dx dy vol P N q=1
−∞ −∞
) < ∞, so the various facts developed above combine to Below we will show that vol(P give N 1 O(log N ) EN = e 1P (q/N, x, y) + 1Q (q/N, x, y) N q=1 × exp Nf (q/N, x, y) dx dy e
O(log N )
N 1 O(log N ) + 1P (q/N, x, y) N q=1
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
× exp Nf (q/N, x, y) dx dy
279
· exp(MN ) = exp MN + O(log N ) . eO(log N ) O(log N ) + vol P is This upper bound on EN will be established once we show that the volume of P if and finite. Taking the exponential of (7), then simplifying, we find that (ρ, x, y) ∈ P only if 2(1−ρ) π ϕ(x)ϕ(y) > ρ 2 · (1 − ρ)1/ρ . 2 Let µ := inf0 0, the calculation of ϕ(x)ϕ(y) whenever (ρ, x, y) ∈ P so that ρ < 2µ ∞ −αx 2 /2 √ √ = 2π/α follows quickly from the change of variable t := αx. Thus −∞ e < vol P
∞ ∞
−∞ −∞
1 π ϕ(x)ϕ(y) dx dy = √ 2µ 2 µ
2
∞ e
−x 2 /4
dx
−∞
2π = √ < ∞. µ
Turning now to the other bound, let (ρ, ˜ x, ˜ y) ˜ be an element of A. For each N let
1 1 1 1 1 1 × x˜ − , x˜ + × y˜ − , y˜ + RN := ρ˜ − , ρ˜ + N N N N N N be the cube of side length 2/N centered at (ρ, ˜ x, ˜ y). ˜ For each N there will be precisely ˜ y) ˜ it two integers q with ρ˜ − N1 q/N < ρ˜ + N1 , so for any positive number α < ϕ(x)ϕ( is the case, for large N , that 1 α < N N3 N
q=1
∞
∞ Dx
−∞
Dy1RN (q/N, x, y).
−∞
Since f is C 2 , there is a number β > 0 such that for sufficiently large N , f (ρ, x, y) > M − β/N 2 for all (ρ, x, y) ∈ RN . Therefore (6) implies that EN
N 1 1RN · exp Nf (q/N, x, y) + O(log N ) dx dy N q=1
α exp MN − β/N − O(log N ) 3 N = exp MN + log α − 3 log N − β/N − O(log N ) = exp MN − O(log N ) .
280
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
The remaining claim of Theorem 1 is that the right-hand side of (6) is asymptotically dominated by the part of the domain lying in arbitrarily small neighborhoods of A. Let U ⊂ [0, 1] × R × R be a neighborhood of A. It is not hard to show that lim sup f (ρr , xr , yr ) 0 whenever {(ρr , xr , yr )} is a sequence with (xr , yr ) → ∞. Since M > 0, it follows that f −1 ((M − ε, M]) ⊂ U for sufficiently small ε > 0. With obvious modifications, the argument used to establish the upper bound can also be employed to obtain the following inequality: 1 Dx Dy1f −1 ((−∞,M−ε]) N q=1,...,N
1 × exp Nf (q/N, x, y) + x 2 + y 2 + O(log N ) 2 exp (M − ε)N + O(log N ) . This completes the proof of Theorem 1, since we have shown that for any δ > 0 it is the case, for all sufficiently large N , that
1 1 2 2 Dx Dy1U · exp Nf (q/N, x, y) + x + y + O(log N ) N 2 q=1,...,N
(1 − δ)EN .
6. Proof of Theorem 2 The proof of Theorem 2 has been broken down into smaller chunks as follows. In this section we explain how the next result, which is useful for studying the mean number of equilibria with small supports, implies Theorem 2. In turn, Proposition 1 will be shown (in Section 7) to follow, after some calculation, from two more technical results, which will in turn be reduced to smaller pieces. Proposition 1. For any fixed integer a 0 and ε > 0, √ √
a π log b a ε−1 2 a! a + 1 r(a, b) = 1 + O (log b) . b b
(8)
The passage from Proposition 1 to Theorem 2 involves only manipulations of orders of magnitudes. To begin with observe that for fixed q we have
N N (N − 1) · · · (N − q + 1) /(N − q)q = q q!(N − q)q
q 1 1 1 1+ ··· 1 + = 1 + O(1/N ) . (9) = q! N −q N −q q! Substituting a = q − 1 and b = N − q in (8), multiplying by ( Nq )21−q , and then applying this fact, we obtain
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
281
N 1−q 2 r(q − 1, N − q) q
√ N (q − 1)! q π log(N − q) q−1 ε−1 = 1 + O (log N ) N −q N −q q q−1 1 = 1 + O (log N )ε−1 √ π log(N − q) 2 . q To simplify further observe that log(N − q) is well approximated by log N − q/N because N log N = log(N − q) + N −q 1t dt. Combining this with (3), we find that for given integers M q > 0 and any ε > 0,
M 1−q q−1 1 q ε−1 EM,N = 1 + O (log N ) 2 r(q − 1, M − q) √ (π log N ) 2 . q q Since r(a, 0) = 1 for any a, this formula simplifies nicely in the special case q = M to 1 M−1 M EM,N = 1 + O (log N )ε−1 √ (π log N/4) 2 . M √ q q−1 For given M and q = 2, . . . , M, the ratio of EM,N to log N EM,N will converge to some M−1 M 1 constant as N → ∞. In particular, EM,N will dominate EM,N , . . . , EM,N asymptotically, and the order of magnitude of the error in the approximation will be given by the ratio of M−1 M . This completes the proof of Theorem 2. to EM,N EM,N 7. Proof of Proposition 1 The main idea in the proof of Proposition 1 is to exploit the theory of the limiting distribution of the top order statistic Xb:b := max{ 1 , . . . , b } of a collection of b i.i.d. standard normal random variables, which is the Gumbel distribution given by the cumulative distribution function G(x) := exp −e−x . More precisely, if we set log 4π + log log b and σb := (2 log b)−1/2 , 2(2 log b)1/2 then (e.g., Reiss, 1989, p. 160 or Kendall et al., 1994, Chapter 14) the distribution of (Xb:b − µb )/σb converges weakly to the Gumbel distribution, with a particular rate of convergence:
Xb:b − µb (log log b)2 . ∈ B − G(B) = O sup P σ log b µb := (2 log b)1/2 −
B
b
(Here the supremum is over all Borel sets B ⊂ R.) It turns out that the notational burden is diminished if we replace b with b − 1 on the left-hand side of the desired equation. That is, we will prove that, for any given a and ε, √ √
a π log b a ε−1 2 a! a + 1 r(a, b − 1) = 1 + O (log b) . (10) b b
282
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
Analyzing the ratio of the right-hand side to its value with b − 1 in place of b, this is easily seen to be equivalent to Proposition 1. √ Recall that r(a, b) is the probability that 0 / a + 1 is greater than the maximum of 1 , . . . , b where 0 , . . . , b are standard normal random variables. The cumulative distribution function for the maximum of b − 1 i.i.d. N (0, 1) random variables is Φ b−1 , and the density of this distribution is (b − 1)Φ b−2 ϕ. Using integration by parts we compute that ∞ r(a, b − 1) = −∞
√ d Φ(t)b−1 dt 1 − Φ a + 1t dt
∞ =− −∞
√ d 1 − Φ a + 1 t Φ(t)b−1 dt dt
√ ∞ √ a+1 ϕ( a + 1 t) = bΦ(t)b−1 ϕ(t) dt b ϕ(t) −∞
√ ∞ a+1 d 2 = Φ(t)b dt. e−at /2 b dt
(11)
−∞
For s ∈ R let ab (s) := µb + σb s = (2 log b)1/2 −
log 4π + log log b 1 + s, 2(2 log b)1/2 (2 log b)1/2
and let 1 1 log 4π + log log b s+ s2. kb (s) := µb σb s + σb2 s 2 = s − 2 8 log b 2 log b
(12)
The change of variables t = ab (s) results, after a little computation, in ∞ e −∞
−at 2 /2
d 2 Φ(t)b dt = e−aµb /2 dt
∞
−∞
e−akb (s)
b d Φ ab (s) ds. ds
(13)
In the result described above the difference between the density g(s) := e−s G(s) of the Gumbel distribution and the density of the rescaled distribution of Xb:b is given equal weight everywhere in R. Unfortunately, this is not the weighting relevant to our work here, so the result cannot be applied directly. The following two facts will be proved in the next two sections. Proposition 2. For fixed a and ε > 0, ∞ e −∞
−akb (s)
b d Φ ab (s) ds = 1 + O (log b)ε−1 ds
∞
−∞
e−akb (s) g(s) ds.
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
283
Proposition 3. For fixed a, ∞ e
−akb (s)
−∞
(log log b)2 g(s) ds = 1 + O log b
∞
e−as g(s) ds.
−∞
Taking these as given, we now complete the proof of Proposition 1. The definition of µb gives
√ 4π log b (log 4π + log log b)2 −µ2b /2 e · = exp − 16 log b b
√ 2 4π log b (log log b) . (14) = 1+O log b b Combining (11), (13), Propositions 2 and 3, and (14), we have √ √
∞ a a + 1 π log b a ε−1 2 r(a, b − 1) = 1 + O (log b) e−as g(s) ds, b b −∞
∞
so (10) will follow once we show that for any integer a 0, −∞ e−as g(s) ds = a!. The case a = 0 follows simply from the fact that g is the density of a probability distribution, so this follows from induction, with the induction step given by the following computation: ∞ e
−as
∞ g(s) ds = e−as exp −e−s s=−∞ −
−∞
∞
−∞
∞ =a
e
−∞
−as
d −as e exp −e−s ds ds
s −s ee exp −e−s ds = a
∞
e−(a−1)s g(s) ds.
−∞
8. Proof of Proposition 3 The proofs of Propositions 2 and 3 both break R into a central interval where the integrands are close and two tails that are shown to be insignificant. Since it is simpler, we give the proof of Proposition 3 first, taking up the proof of Proposition 2 in the next section. The following three lemmas establish approximations for the integral on the left-hand side in Proposition 3 on the three relevant intervals. The first lemma will be applied in the proofs of both Proposition 2 and Proposition 3 (where the case β = 1 is relevant). Lemma 1. For fixed a and 0 < β 1, let s b := −β log log b. Then s b e −∞
−akb (s)
s b g(s) ds < −∞
β e−as g(s) ds = O e−(log b) (log b)aβ .
284
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
Proof. The inequality follows from the fact that kb (s) s whenever s 0. We will show that s b
e−as g(s) ds = e−(log b)
β
a a! i=0
−∞
(log b)iβ .
i!
The assertion follows from this formula in view of the fact that, as b → ∞, the sum on the right is dominated by the summand corresponding to i = a. The formula is proved by sb β induction on a. For the case a = 0 we have −∞ g(s) ds = G(s b ) = e−(log b) . Recalling that g(s) = e−s G(s), the induction step follows from integration by parts: s b e
−as
s b g(s) ds = e−as G(s) −∞ −
−∞
s b
d −as e G(s) ds ds
−∞
=e
−(log b)β
s b aβ
(log b)
+a
e−(a−1)s g(s) ds.
2
−∞
Lemma 2. For fixed a,
log log b
e
−akb (s)
log log b
g(s) ds −
− log log b
Proof. Since
− log log b
∞
−∞ e
log log b
e
−as g(s) ds
−akb (s)
(log log b)2 . g(s) ds = O log b
= a! and et − 1 > 1 − e−t when t > 0, we have log log b
g(s) ds −
− log log b
e
−as
− log log b
e−as g(s) ds
max
max
" a|k (s)−s| e b − 1 a!.
− log log bslog log b
! − log log bslog log b
−ak (s) e b − e−as g(s) ds
− log log b
" −a(k (s)−s) b e − 1
!
log log b
log log b
e−as g(s) ds
− log log b
In view of (12), 2 kb (s) − s log 4π + log log b log log b + log log b 8 log b 2 log b − log log bslog log b
2 (log log b) . =O log b
max
The assertion follows from the fact that |e|t| − 1| = (1 + o(1))|t| in the limit as t → 0.
2
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
285
Lemma 3. For fixed a, ∞
e−as g(s) ds = O (log b)−(a+1) ,
log log b
and for sufficiently large b, ∞ e
−akb (s)
∞ g(s) ds <
log log b
e−as g(s) ds.
log log b
Proof. Since g(s) := e−s exp(−e−s ) < e−s , ∞ e
−as
∞ g(s) ds <
log log b
e−(a+1)s ds =
log log b
e−(a+1) log log b = O (log b)−(a+1) . a+1
For sufficiently large b we have log log b > (log 4π + log log b)/4, which implies that kb (s) s whenever s log log b. This establishes the inequality. 2 Proof of Proposition 3. The following calculation applies the three Lemmas above: ∞ ∞ −akb (s) −as e g(s) ds − e g(s) ds −∞
−∞
e−akb (s) g(s) ds +
− log log b −∞
+
log log b
− log log b
e
−akb (s)
e−as g(s) ds
− log log b −∞
log log b
g(s) ds −
e
− log log b
−as
g(s) ds
∞ ∞ −akb (s) −as + e g(s) ds + e g(s) ds log log b
log log b
(log b)a (log log b)2 O +O + O (log b)−(a+1) b log b
(log log b)2 . 2 =O log b
286
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
9. Proof of Proposition 2 The proof of Proposition 2 also bounds the difference of interest by a sum of terms, then applies five inequalities. One of these, Lemma 1, has already been developed, and the other four are given by the next result. Throughout this section, to simplify notation we set s b := −β log log b. Lemma 4. For a fixed integer a and sufficiently small numbers β, γ > 0: s b
e−akb (s)
(a) −∞
(b)
b d β Φ ab (s) ds = O e−(log b) ; ds
γ (log
b) b −akb (s) d −akb (s) e Φ ab (s) − e g(s) ds = O (log b)β+3γ −1 ; ds
sb
∞
e−akb (s)
(c) (log b)γ
∞
b d γ Φ ab (s) ds = O e−a(log b) ; ds
e−akb (s) g(s) ds < e−a(1+o(1))(log b) . γ
(d) (log b)γ
Proof of Proposition 2. Choose β, γ > 0 with β + 3γ = ε. In the second relation below we apply (a), Lemma 1, (b), (c), and (d), in that order: ∞ ∞ d b Φ ab (s) ds − e−akb (s) e−akb (s) g(s) ds ds −∞
−∞
s b s b b −akb (s) d −akb (s) Φ ab (s) ds + e e g(s) ds ds −∞
−∞
γ γ (log (log b) b) b −akb (s) d −akb (s) + Φ ab (s) ds − e e g(s) ds ds
sb
sb
∞ ∞ b −akb (s) d −akb (s) + Φ ab (s) ds + e e g(s) ds ds (log b)γ
(log b)γ
β β = O e−(log b) + O (log b)aβ e−(log b) + O e−(1−β−3γ ) log log b γ γ + O e−a(log b) + e−a(1+o(1))(log b) 2 = O e−(1−β−3γ ) log log b = O (log b)−(1−ε) .
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
287
The remainder is devoted to the proof of Lemma 4. Since they are simpler, we prove (c) and (d) first. Proof of (c). Using elementary calculus one may easily compute that the minimum of kb (s) − s is attained at s = 18 (log 4π + log log b), at which point kb (s) − s = − Therefore ∞ (log b)γ
s whenever s < 0, integration by parts, the inequality above, another integration by parts, and the definitions of Fb , ab , and s b , we compute as follows:
288
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
s b e −∞
−akb (s)
b d Φ ab (s) ds < ds
s b
e−as
−∞
=e
−as b
b d Φ ab (s) ds ds s b
b Φ ab (s b ) +
b ae−as Φ ab (s) ds
−∞
0:
1 1 1 1− 2 ϕ(t) < 1 − Φ(t) < ϕ(t). (16) t t t =
We have log 4π + (1 + 2β) log log b ab (s b ) = (2 log b)1/2 − 2(2 log b)1/2
log log b (2 log b)1/2 = 1+O log b and
ab (s b )2 = 2 log b − log 4π − (1 + 2β) log log b + O
(log log b)2 . log b
The first of these implies that ab (s b ) > 0, so
φ(ab (s b )) 1 . Φ ab (s b ) = 1 − 1 + O ab (s b ) ab (s b )2 Using the formula for ab (s b )2 to evaluate the normal density at ab (s b ) gives
√ 1 2(log b) 2 +β (log log b)2 , ϕ ab (s b ) = 1 + O log b b
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
289
so that
ϕ(ab (s b )) (log log b)2 (log b)β = 1+O . ab (s b ) log b b
Combining these results with the approximation of Φ(ab (s b )) above yields
(log b)β (log log b)2 1 1 + O Φ ab (s b ) = 1 − 1 + O log b b (log b)2
2 β (log log b) (log b) =1− 1+O . log b b In turn, these approximations of ϕ(ab (s b )) and Φ(ab (s b )) give
√ 1 (log b)β (log log b)2 2(log b) 2 +β ϕ(ab (s b )) cb = = 1+O 1+O Φ(ab (s b )) b log b b √
1 2(log b) 2 +β (log log b)2 . = 1+O log b b Since σb = (2 log b)−1/2 , we have
(log log b)2 bcb σb = 1 + O (log b)β log b bcb σb = 1 + O (log b)−β . bcb σb − a
and (17)
Next, we approximate Φ(ab (s b ))b . The expansion log(1 − x) = − j =1 x j /j (which 1 = − j =0 x j ) implies that 1 + log(1 − x)/x = may be obtained by integrating − 1−x
− 12 x − 13 x 2 − · · ·, and this implies that (1 − x)1/x = e−1− 2 x+O(x ) . More generally, 1
1 1− x b
b
=
1 1− x b
b x x
= e−x e− 2 x
1 2 /b
eO(x
2
3 /b2 )
.
(18)
2
log b) β Applying this with x = b(1 − Φ(ab (s b ))) = (1 + O( (loglog b ))(log b) gives log b)2 b −(1+O( (loglog ))(log b)β b Φ ab (s b ) = e .
The claim follows from (15), (17), and this equation. It remains to show that Fb (ab (s)) Φ(ab (s)) when s s b . Let s b := −2µb /σb + s b = −4 log b + log 4π + (1 + β) log log b be the number such that ab (s b ) = −ab (s b ), and observe that fb ab (s) < fb ab (s b ) = ϕ ab (s b ) < ϕ ab (s) for all s ∈ (s b , s b ). Since Fb (ab (s b )) = Φb (ab (s b )), this inequality implies that Fb (ab (s)) > Φ(ab (s)) whenever s b s < s b .
290
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
For t < 0 (16) gives Φ(t) = 1 − Φ(−t) < ϕ(t)/(−t), so that tΦ(t) + ϕ(t) > 0. In particular, for t < 0 we have d ϕ(t) ϕ (t)Φ(t) − ϕ(t)2 −ϕ(t)(tΦ(t) + ϕ(t)) = = < 0. (19) dt Φ(t) Φ(t)2 Φ(t)2 Since ϕ(−t) = ϕ(t) for all t, we have ϕ(ab (s b )) ϕ(ab (s b )) Φ(ab (s b )) ϕ(ab (s b )) fb (ab (s b )) = · > = . Φ(ab (s b )) Φ(ab (s b )) Φ(ab (s b )) Φ(ab (s b )) Fb (ab (s b )) Combining (19) with the fact that fb (t)/Fb (t) ≡ cb is constant, we see that
fb (ab (s)) Fb (ab (s)) d ϕ(ab (s)) log = σb Φ(ab (s)) for all s < s b .
2
Proof of (b). As we pointed out in the proof of (c), kb (s) s −
3(log 4π + log log b)2 64 log b
for all s, so γ (log b)
e−akb (s) g(s) ds O(1)
sb
γ (log b)
e−as g(s) ds
sb
∞ < O(1)
e−as g(s) ds = O(1)a! = O(1).
−∞
Therefore (b) follows if we can prove that γ (log b)
e
−akb (s)
d b Φ(µb + σb s) − g(s) ds ds
sb
= O (log b)β+3γ −1
γ (log b)
e−akb (s) g(s) ds.
(20)
sb
The result mentioned in Section 7 concerning the asymptotic distribution of the top order statistic of b i.i.d. standard normal random variables is the assertion that the appropriately rescaled distribution, which has c.d.f. Φ(ab (s))b , converges (weakly, with a particular rate of convergence) to the Gumbel distribution. For the proof of Proposition 2 we develop something stronger than a related result, namely that the associated density function b b−1 d Φ ab (s) = bΦ ab (s) ϕ ab (s) σb ds
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
291
converges, uniformly on compact intervals, at a certain rate, to the density function g(s) := e−s exp(−e−s ) of the Gumbel distribution. Since, for large b, |s b | = β log log b is small relative to (log b)γ , (20) follows from: Lemma 5. For any β, γ > 0 with β + 2γ < 1, b−1 max γ bΦ ab (s) ϕ ab (s) σb − g(s) = O (log b)β+2γ −1 . s b s(log b)
Proof. Noting that ab (s) > 0 for all s > s b (at least if b is sufficiently large) define
ϕ(ab (s)) 1 and εb (s) := Φ ab (s) − 1 − Db (s)e−s . Db (s) := bes ab (s) b The key idea is that (16) will imply that |εb (s)| is small, which allows the development of an accurate approximation of Φ(ab (s))b−1 based on applying (18) to the numerator of the right-hand side of b−1 (1 − b1 Db (s)e−s + εb (s))b Φ ab (s) = . 1 − b1 Db (s)e−s + εb (s)
(21)
To simplify notation set νb := µb − (2 log b)1/2 = − so that ab (s) =
(log 4π + log log b) , 2(2 log b)1/2
2 log b + νb + σb s.
Recalling that σb := (2 log b)−1/2 , a brief computation yields ab (s)2 = 2 log b − log 4π − log log b + 2s + (νb + σb s)2 , whence √ 2 log b −s 1 −ab (s)2 /2 − 12 (νb +σb s)2 e . =e · ϕ ab (s) = √ e b 2π Substituting into the definition of Db gives
# νb + σb s − 12 (νb +σb s)2 1+ √ . Db (s) = e 2 log b The rest of the proof is a sequence of asymptotic approximations that are valid provided that s lies in the range s b := −β log log b s (log b)γ . First of all, for s in this range we have |νb + σb s| = O((log b)γ −1/2 ). This gives 1 νb + σb s 2 = 1 + O (log b)γ −1 and e− 2 (νb +σb s) = 1 + O (log b)2γ −1 , 1+ √ 2 log b so that
Db (s) = 1 + O (log b)2γ −1 .
292
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
In addition,
ab (s) = (2 log b)1/2 + νb + σb s = (2 log b)1/2 1 + O (log b)γ −1 .
In view of these calculations and the fact that e−s (log b)β when s s b , (16) gives
1
−s
ϕ(ab (s)) ϕ(ab (s)) b Db (s)e = O =O εb (s) = Φ ab (s) − 1 − ab (s) ab (s)3 ab (s)2
1 (log b)β−1 . =O b We now develop approximations of the terms that will appear in our application of (18). In particular, e−Db (s)e
−s +bε (s) b
−s
β+2γ −1
)+O((log b) ) = e−e +O((log b) = 1 + O (log b)β+2γ −1 exp(−e−s ). β−1
(22)
For s s b we have
Db (s)e−s − bεb (s) = e−s + O (log b)β+2γ −1 + O (log b)β−1 = O (log b)β ,
so e
− 12 (Db (s)e−s −bεb (s))2 /b
1 (log b)2β =1+O b
and eO((Db (s)e
−s −bε (s))3 /b2 ) b
=1+O
(23)
1 3β . (log b) b2
(24)
(25)
Applying (18) with x = Db (s)e−s + bεb (s), using (22), (24), and (25) to approximate the three factors, we obtain
b 1 −s 1 − Db (s)e + εb (s) = 1 + O (log b)β+2γ −1 exp −e−s . b Since
1 1 1 1 − Db (s)e−s + εb (s) = 1 + O (log b)β+2γ −1 + O (log b)β−1 , b b b combining this with (21) results in b−1 Φ ab (s) = 1 + O (log b)β+2γ −1 exp −e−s . Recalling again that σb := (2 log b)−1/2 , (21) and the subsequent approximation yield 1 2 bϕ ab (s) σb = e− 2 (νb +σb s) · e−s = 1 + O (log b)2γ −1 · e−s . Combining this with the result above yields bΦ ab (s) b−1 ϕ ab (s) σb − g(s) = O (log b)β+2γ −1 g(s). Since g is continuous with lims→−∞ g(s) = lims→∞ g(s) = 0, this establishes the claim. 2
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
293
10. Conclusion Theorem 1 characterizes the asymptotics of the mean number of Nash equilibria of a two-player normal form game in which both players have the same number of pure strategies. Since the mean is shown to grow exponentially, and algorithms with exponential worst case running times are known, the problem of finding all equilibria of an N × N game has exponential mean and worst case computational complexity. The relative merits of exponential time algorithms for computing all equilibria of such games must therefore be assessed using more subtle measures of computational efficiency. One possibility is to investigate measures of computational cost that are output sensitive, meaning roughly that they measure the use of resources (time and memory) in relation to the number of equilibria. In this connection a result of Gilboa and Zemel (1989) (see also Connitzer and Sandholm, 2003) is important: determining whether a two-player game has more than one Nash equilibrium is already an NP-hard problem. It seems likely that our methods can be extended to show that the mean number of equilibria is exponential in Mk along sequences {(Mk , Nk )} with Mk → ∞ and Mk /Nk → α > 0. In view of the monotonicity exhibited by Table 1, Theorem 1 leads one to expect the mean number of equilibria to be exponential in Mk along any sequence with Mk Nk and Mk → ∞, but that result is not established here. On the other hand, Theorem 2 shows that for fixed M, EM,N → ∞ as N → ∞, but very slowly. As we stress in Section 2, our results cannot be interpreted as characterizing the asymptotics of the typical number of equilibria, or of the typical support size of equilibria of typical games. These questions have been studied using methods of statistical physics, with results suggesting that the typical number of equilibria grows exponentially, at a lower rate than the mean. Based on these results, it seems likely that the asymptotic distribution of the fraction of pure strategies involved in typical equilibria of typical games is degenerate, with a limiting value that is less than the corresponding fraction for all equilibria. The methods used to arrive at these results are not rigorous, but in one case results first derived using these techniques were later established rigorously. Many other issues await resolution. In addition to the conjectures mentioned in Section 4, one expects that similar results hold for games with three (or more) players, but such results do not follow in a straightforward way from Theorems 1 and 2. The key to p |) in equation (2). such results would seem to be useful estimates of the term E(| det Z Some results along these lines are given in McLennan (2002). One of the general lessons of this line of research is that it encourages interest in highly structured classes of games, since all but the smallest random games are (most often) intractable. For example, economists often study games that are symmetric with respect to interchange of players, in which case it is natural to focus on symmetric equilibria. Insofar as the methods underlying the results presented here depend heavily on symmetry, this seems like a promising direction. Games of pure cooperation (i.e., all players have the same payoff function) could also be investigated. Two-player zero sum games have a single connected component of Nash equilibria, so a different set of questions arises; these are being investigated by Roberts (2004).
294
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
Acknowledgments We are indebted to Robin Pemantle for suggestions that led to the development of Theorem 2, and to Jeroen Swinkels for a very helpful conversation. We have benefitted from the comments of seminar participants at the University of Iowa, the University of Wisconsin, the AMS meetings in Hoboken in April 2001, Northwestern University, the University of Chicago, Waseda University, Universiteit Maastricht, and Games 2002. McLennan gratefully acknowledges the hospitality of the Abdus Salam International Center for Theoretical Physics and the Institute for Social and Economic Research. We benefitted from the suggestions of the editor and two referees.
References Berg, J., 2000. Statistical mechanics of random two-player games. Phys. Rev. E 61 (3), 2327–2339. Berg, J., Engel, A., 1998. Matrix games, mixed strategies, and statistical mechanics. Phys. Rev. Lett. 81, 4999– 5002. Berg, J., Weigt, M., 1999. Entropy and typical properties of Nash equilibria in two-player Games. Europhys. Lett. 48 (2), 129–135. Billingsley, P., 1986. Probability and Measure, second ed. Wiley, New York. Connitzer, V., Sandholm, T., 2003. Complexity results about Nash equilibria. In: Proceedings of The 18th International Joint Conference on Artificial Intelligence, pp. 765–771. Dresher, M., 1970. Probability of a pure equilibrium point in n-person games. J. Combin. Theory 8, 134–145. Gilboa, I., Zemel, E., 1989. Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. 1, 80–89. Harsanyi, J.C., 1973. Oddness of the number of equilibrium points: a new proof. Int. J. Game Theory 2, 235–250. Hopcroft, J.E., Uhlman, J.D., 1979. Introduction to Automata Theory, Languages, and Computation. Addison– Wesley, Reading, MA. Keiding, H., 1995. On the maximal number of Nash equilibria in a bimatrix game. Games Econ. Behav. 21, 148–160. Kendall, M., Stuart, A., Ord, K., 1994. The Advanced Theory of Statistics, vol. I, sixth ed. Oxford Univ. Press, New York. McKelvey, R.D., McLennan, A., 1997. The maximal number of regular totally mixed Nash equilibria. J. Econ. Theory 72, 411–425. McLennan, A., 1996. The maximal generic number of pure Nash equilibria. J. Econ. Theory 72, 408–410. McLennan, A., 2002. The mean number of real roots of a multihomogeneous system of polynomial equations. Amer. J. Math. 124, 49–73. McLennan, A., 2004. The expected number of Nash equilibria of a normal form game. Econometrica. In press. McLennan, A., Park, I.-U., 1999. Generic 4 × 4 games have at most 15 Nash equilibria. Games Econ. Behav. 26 (1), 111–130. Mézard, M., Parisi, G., Virasoro, M., 1987. Spin Glass Theory and Beyond. World Scientific, Singapore. Papadimitriou, C.H., 1994. Computational Complexity. Addison–Wesley, Reading, MA. Powers, I., 1990. Limiting distributions of the number of pure strategy Nash equilibria. Int. J. Game Theory 19, 277–286. Quint, T., Shubik, M., 1997. A theorem on the number of Nash equilibria in a bimatrix game. Int. J. Game Theory 26, 353–360. Reiss, R.-D., 1989. Approximate Distributions of Order Statistics. Springer-Verlag, New York. Roberts, D.P., 2004. Kernel sizes for random matrix games. Mimeo. University of Minnesota. Stanford, W., 1995. A note on the probability of k pure Nash equilibria in matrix games. Games Econ. Behav. 9, 238–246. von Stengel, B., 1999. New maximal numbers of equilibria in bimatrix games. Discrete Comput. Geom. 21, 557–568.
A. McLennan, J. Berg / Games and Economic Behavior 51 (2005) 264–295
295
von Stengel, B., 2002. Computing equilibria for two-person games. In: Aumann, R., Hart, S. (Eds.), Handbook of Game Theory, vol. 3. North-Holland, Amsterdam, pp. 1723–1759. Talagrand, M., 1998. Rigorous results for the Hopfield model with many patterns. Probability Theory Related Fields 110, 177–276.
