A Computationally Efficient Characterization of Pure Strategy Nash Equilibria in Large Entry Games

Finance and Economics Discussion Series Divisions of Research & Statistics and Monetary Affairs Federal Reserve Board, Washington, D.C. A Computationally Efficient Characterization of Pure Strategy Nash Equilibria Entry Games Andrew Cohen 2005-37 NOTE: Staff working papers in the Finance and Economics Discussion Series (FEDS) are preliminary materials circulated to stimulate discussion and critical comment. The analysis and conclusions set forth are those of the authors and do not indicate concurrence by other members of the research staff or the Board of Governors. References in publications to the Finance and Economics Discussion Series (other than acknowledgement) should be cleared with the author(s) to protect the tentative character of these papers.

A Computationally Efficient Characterization of Pure Strategy Nash Equilibria in Large Entry Games Andrew Cohen* Federal Reserve Board December 2004 Abstract: This note presents a simple algorithm for characterizing the set of pure strategy Nash equilibria in a broad class of entry games. The algorithm alleviates much of the computational burden associated with recently developed econometric techniques for estimating payoff functions inferred from entry games with multiple equlibria. *The opinions expressed are those of the author and do not necessarily reflect the opinion of Board of Governors or its staff. Contact information: Federal Reserve Board, Washington, D.C., 20551. (202)-452-2612.

I. Introduction There has been increasing interest in the estimation of payoff functions inferred from games in which agents choose from a discrete set of strategies that yield an observable profile of agents’ decisions, Y, which is assumed to be generated according to a particular equilibrium concept. Several researchers have employed this type of model to infer the effect of competition on firms’ profits by assuming that observed market structures are pure strategy Nash equilibria, (“PSNE”), of an entry game. If the game admits multiple PSNE, however, the empirical model is “incomplete” since a given parameter vector may map into more than one entry profile. Dating back at least to the work of Bresnahan and Reiss (1990) and Berry (1992), researchers have used different approaches to estimate entry models that admit multiple PSNE. Tamer (2003) forms an estimator that does not require one to “select” a particular PSNE by bounding the likelihood of a given Y by the probability that Y is the unique PSNE (lower bound) and the probability that Y is a PSNE (upper bound). Ciliberto and Tamer (2004, “CT”), and Andrews, Berry and Jia (2004, “ABJ”), have proposed similar estimators for multi-player games. These estimators are computationally intensive because they require one to recover the set of PSNE. I show that when the effect of entry on firms’ profits depends only on the number of entrants, the NxN matrix of best replies to each possible number of entrants can be manipulated to fully and succinctly characterize the set of PSNE. The method is feasible for a large number of potential entrants because it requires operating only on an NxN matrix, as opposed to operating on the Nx2N matrix of all possible entry profiles. The algorithm is applicable only when the argument of each firm’s profit function is the number of competing entrants, though the profit function is permitted to differ across firms. Whether or not such an

assumption is valid will depend upon the application. Section 2 discusses recently developed estimators for which a computationally efficient way of characterizing the set of PSNE in the entry game is of practical value. Section 3 presents some theoretical results that underlie the computational algorithm presented in section 4. Section 5 concludes. II. Estimation of Games with Multiple PSNE Tamer (2003) considers a bivariate simultaneous move entry game. The profits of each firm are: Π =[X β+ yδ+ε]y 1 1 2 1 1 (1) Π =[X β+ yδ+ε]y 2 2 1 2 2 where X and X are vectors of exogenous variables, y =1 if firm i enters and zero 1 2 i otherwise, ε is the unobservable component of i’s profit, and β and δ are parameters. A i PSNE of this game is a pair of entry decisions, ( y*,y*) , satisfying: 1 2 y* =1⇔ X β+ y*δ+ε ≥0 and 1 1 2 1 (2) y* =1⇔ X β+ y*δ+ε ≥0 2 2 2 1 Bresnahan and Reiss (1991) show that this game admits multiple PSNE if the error structure is sufficiently rich. In particular, for certain values of the parameters and unobservables, either firm may enter as a monopolist, but not both. Tamer (2003) bounds the likelihoods of both monopoly outcomes by applying different hypothetical “selection rules” when the model predicts multiple PSNE. The lower bound,P(1,0), is the probability that (1,0) is the unique PSNE; i.e., that (1,0) would never obtain in the region in which both (1,0) and (0,1) are PSNE. The upper bound, P(1,0), is the probability that (1,0) is simply a PSNE; 2

i.e., that (1,0) would always obtain in the region in which both (1,0) and (0,1) are PSNE. CT extend this intuition to the multi-firm entry game using a modified minimum distance estimator in which the likelihood of Y is bounded by the probabilities that Y is the unique PSNE (lower bound) and that Y is any PSNE (upper bound). Simulation methods must be used to calculate these regions. The estimator is computationally burdensome because finding the PSNE entails checking N inequalities for each of the 2N possible outcomes at each draw from the distribution of the unobservables.1 The algorithm provided below can significantly reduce this burden. III. Theory Extending the specification in (1) to cover several potential entrants requires additional notation. Let A denote the set of all possible entry profiles with Y∈A being a particular entry profile, and y being the ith element of Y. Define Λ⊂ Α as the set of PSNE i profiles. Finally, i’s profits are: ⎡ ⎛ ⎞ ⎤ Π =⎢X β+ f ⎜ ∑y ⎟+ε⎥ y (3) i i i j i i ⎢⎣ ⎝ j≠i ⎠ ⎥⎦ where f (⋅) is assumed to be strictly decreasing in the number of entrants and f (n)=0 if i i n≤0. The model is slightly different from CT (and ABJ) in that the effect of entry on ⎛ ⎞ profits, f ⎜ ∑y ⎟, depends only on the number of other entrants and not their identities. CT i j ⎝ j≠i ⎠ can estimate different parameters capturing the effect of a particular firm’s entry on the 1 For this reason, CT and ABJ restrict the number of possible outcomes by consolidating similar types of firms into one. 3

profits of each of the other firms because they observe the same set of potential entrants across several markets. When the identities of the potential entrants vary across markets, however, estimating identity-specific shift parameters is infeasible. In this case, the specification in (3) would be more appropriate while still providing some flexibility since the number of entrants may affect each firm’s profits differently. All PSNE have in common that all entrants are profitable and no additional firm could profitably enter the market. That is: Y∈Λ⇔ ⎡y =1⇔Π ( y ,Y−i) ≥0⎤∀i=1…N (4) ⎣ i i i ⎦ where Y−i is the vector of entry decisions for all firms other than i. The assumption that f (⋅) is strictly decreasing implies that the number of entrants is unique in any PSNE. This i unique number of entrants, however, may correspond to multiple PSNE in terms of which firms actually enter. The uniqueness of the number of entrants across PSNE and the following three propositions form the basis of the computational algorithm. Define r (⋅) to be firm i’s best reply correspondence, mapping Y−i into {0,1}. That i is: ⎛ ⎞ r ( Y−i) =1⇔ X β+ f ⎜ ∑y ⎟+ε ≥0 (5) i i i j i ⎝ j≠i ⎠ Note that r ( Y−i) can be expressed as a function of the total number of entrants excluding i, i ⎛ ⎞ and that r ⎜ ∑y ⎟is weakly decreasing in ∑y . Proposition 1 provides necessary and i j j ⎝ j≠i ⎠ j≠i sufficient conditions for determining how many firms enter in every PSNE. 4

Proposition 1: N* is the PSNE number of entrants if and only if the following conditions hold: (1) It is a best reply for at least N* firms to enter, given entry by N*−1 competing firms, and (2) It is a best reply for no more than N* firms to enter, given entry by N* competing firms. Formally, ∑y = N*∀Y∈Λ⇔∑r ( N*−1 ) ≥ N* and ∑r ( N*) ≤N*. i i i i i i Proofs of all propositions are contained in the appendix. When ∑r ( N*−1 ) > N*, there are multiple PSNE, all with N* entrants. i i Characterizing the set of PSNE in this case requires segmenting firms according to whether they enter in: (a) every PSNE, (b) at least one PSNE, or (c) none of the PSNE. Proposition 2 provides a method to identify firms in (a), and proposition 3 provides a method to identify firms in (b) and (c). Proposition 2: When there are multiple PSNE with N*entrants, the vector of best replies to entry by N*competing firms captures the set of firms that enter in every PSNE.2 Formally, if ∑r ( N*−1 ) > N*, then r ( N*) =1⇔ y =1∀Y∈Λ i i i i Proposition 3: The vector of best replies to entry by N*−1 competing firms captures the set of firms that enter in at least one PSNE. Formally, r ( N*−1 ) =1⇔∃Y∈Λ: y =1 i i Propositions 1-3 imply that one can characterize the set of PSNE by computing the vector of best replies to a given number of entrants rather than verifying N different 2 Berry (1992) uses this fact as well. 5

inequalities for each of 2Npossible entry profiles. The algorithm for doing so proceeds in three steps: (1) calculate the NxN matrix of best replies to each possible number of competing entrants; (2) find the number of entrants common to all PSNE using Proposition 1; and (3) determine whether a given profile is the unique PSNE, a PSNE (unique or not), or not a PSNE using the appropriate columns of the best reply matrix. The last step may be repeated to check all possible outcomes without repeating the first two steps. IV. Computational Algorithm Step 1: Compute the matrix of best replies to the number of competing entrants. (cid:105) A. Calculate the NxN matrix of firms’ profits conditional on entering, Π, where: Π (cid:105) = X β+ f (t−1)+ε for i,t =1,...,N (6) i,t i i i B. Define the NxN matrix of firms’ best replies, R, where: (cid:105) R =1 if Π ≥0 i,t i,t (7) R =0 otherwise i,t Note that the tth column of R, denoted by R (t) , represents firms’ best replies to entry by t−1 competitors. Step 2: Find the equilibrium number of entrants,N*, using Proposition 1. A. N* =0 is the unique PSNE if ∑R =0 (8) i,1 i B. N* =t >0⇔∑R ≥t and ∑R ≤t (9) i,t i,t+1 i i Comment on Steps 1 and 2 When there are multiple PSNE: (1) firms that enter in every PSNE and firms that never enter in a PSNE will have values of one and zero, respectively, in the corresponding rows of both 6

( N*+1 ) ( N*) R and R ; and, (2) firms that enter in some but not all PSNE will have values of zero ( N*+1 ) ( N*) and one in the corresponding rows of R and R , respectively. That is, if the PSNE number of entrants is N*, then the set of PSNE is as follows: Λ = ⎧ ⎨Y | y =1 if R ( N*+1 ) =1,y =0 if R ( N*) =0,∑ N y = N* ⎫ ⎬ (10) i i j ⎩ j=1 ⎭ Example: ⎡1⎤ ⎡1⎤ ⎢ ⎥ ⎢ ⎥ 1 0 Suppose that R (2) = ⎢ ⎥ and R (3) =⎢ ⎥ so that N* =2. ⎢1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣0⎦ Any Y∈Λ must satisfy: (1) y =1 since R (2) = R (3) =1; (2)y =0 since 1 1 1 4 R (2) = R (3) =0; and (3) either y =1 or y =1 since R (2) = R (2) =1, R (3) = R (3) =0, 4 4 2 3 2 3 2 3 and N* =2. Step 3: Determine whether a desired profile of entry decisions, Y, is the unique PSNE, a PSNE, or not a PSNE. ( N*) A. Y is the unique PSNE if each element of Y is equal to the corresponding element of R . ( N*+1 ) B. Y is a PSNE if each element of Y is equal to the corresponding element of either R or R ( N*) , and Y involves entry by N* firms. The simulation estimator of the upper and lower bounds on the probability of observing the profile Y is computed by repeating steps 1-3 for each pseudo-random draw, d, (cid:75) from the distribution of ε. In particular, the simulation estimator of the lower bound on the probability of observing Y is: 7

P(Y)= 1 ∑ D I ⎜ ⎛ ∑ N I ⎛ ⎜y = R ( N*)⎞ ⎟= N ⎞ ⎟ (11) D ⎝ ⎝ i i,d ⎠ ⎠ d=1 i=1 and the upper bound is: P(Y)= D 1 ∑ d D =1 I ⎝ ⎜ ⎛ ⎢ ⎣ ⎡ ∑ i N =1 max ⎢ ⎣ ⎡ I ⎝ ⎛ ⎜y i = R i ( , N d *+1 ) ⎠ ⎞ ⎟,I ⎝ ⎛ ⎜y i = R i ( , N d *) ⎠ ⎞ ⎟ ⎥ ⎦ ⎤ = N ⎥ ⎦ ⎤ ⎟ ⎠ ⎞ •I ⎝ ⎛ ⎜ ∑ i N =1 y i = N* ⎠ ⎞ ⎟ (12) where I(⋅) is the indicator function. V. Conclusion This note provides an algorithm that significantly expands the settings in which one may feasibly estimate the payoff parameters from entry games with multiple PSNE. Under the commonly used assumption that the effect of entry on profits depends only on the number of entrants, the NxN matrix of firms’ best replies to entry by a given number of competitors fully characterizes the set of PSNE. In this case, one need not compute and operate on the Nx2N matrix of best replies to each possible configuration. References Andrews D, S. Berry and P. Jia, Confidence regions for parameters in discrete games with multiple equilibria, with an application to discount store location, Mimeo. Berry, S. Estimation of a model of entry in the airline industry, Econometrica 60, 889-917. Bresnahan, T. and P. Reiss. Entry in monopoly markets, Review of Economic Studies, 57(4), 531-553. Bresnahan, T. and P. Reiss. Empirical models of discrete games, Journal of Econometrics 48, 57-81. Ciliberto, F. and E. Tamer, Market structure and multiple equilibria in airline markets, Mimeo. 8

Tamer, E. Incomplete simultaneous discrete response model with multiple equilibria, Review of Economic Studies 70, 147-167. Appendix: Proofs of Propositions Proposition 1: ∑y = N*∀Y∈Λ⇔∑r ( N*−1 ) ≥ N* and ∑r ( N*) ≤N* i i i i i i Proof: Part I: There is only one value of N*that satisfies ∑r ( N*−1 ) ≥ N* and ∑r ( N*) ≤N* i i i i Suppose N*satisfies, ∑r ( N*−1 ) ≥ N* and ∑r ( N*) ≤N* i i i i Then anyN*+ > N* cannot satisfy the conditions above because: ∑r ( N*+ −1 ) ≤∑r ( N*) ≤ N* < N*+ i i i i and, any N*− < N* cannot satisfy the condition above because: ∑r ( N*−) ≥∑r ( N*−1 ) ≥ N* > N*− i i i i where the first inequality in both cases derives from the fact that r (⋅) is weakly decreasing. i Therefore, only one value of N*can satisfy the RHS of Proposition 1. Showing either the ⇒ or ⇐ direction of Proposition I will therefore suffice. Part II: ∑y = N*∀Y∈Λ⇒∑r ( N*−1 ) ≥ N* and ∑r ( N*) ≤N*follows from the i i i i i i definition of PSNE. QED. Proposition 2: If ∑r ( N*−1 ) > N*, then r ( N*) =1⇔ y =1∀Y∈Λ i i i i Proof: Part I: If ∑r ( N*−1 ) > N*, then r ( N*) =1⇒ y =1∀Y∈Λ follows from the definition of i i i i a best reply and the monotonicity of f (⋅). Part II: If ∑r ( N*−1 ) > N*, then y =1∀Y∈Λ⇒r ( N*) =1 can be proven by showing the i i i i 9

contrapositive to be true. If ∑r ( N*−1 ) > N*, then r ( N*) =0⇒ y =0 in some Y∈Λ is true by the definition of a i i i i PSNE. QED. Proposition 3: r ( N*−1 ) =1⇔∃Y∈Λs.t. y =1 i i Proof: Part I: r ( N*−1 ) =1⇒∃Y∈Λs.t.y =1 i i If Λis a singleton, then y =1 because r ( N*−1 ) =1. i i If there are multiple PSNE, note that there must be at least two firms with r ( N*−1 ) =r ( N*−1 ) =1 and r ( N*) =r ( N*) =0, and there must be at least one PSNE in i j i j whichy =0 and y =1. Construct Y by starting with an equilibrium profile Y′wherey′ =0 i j i and y ′ =1. Form Y by exchanging firm i for some firm j where y ′ =1 and r ( N*) =0 so j j j that y =1 and y =0. i j Part II: ∃Y∈Λ s.t. y =1⇒r ( N*−1 ) =1 follows from the definition of a PSNE. QED. i 10