Estimation and inference in games of incomplete information with unobserved heterogeneity and large state space

Fan, Yanqin; Jiang, Shuo; Shi, Xuetao Article Estimation and inference in games of incomplete information with unobserved heterogeneity and large state space Quantitative Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Fan, Yanqin; Jiang, Shuo; Shi, Xuetao (2024) : Estimation and inference in games of incomplete information with unobserved heterogeneity and large state space, Quantitative Economics, ISSN 1759-7331, The Econometric Society, New Haven, CT, Vol. 15, Iss. 4, pp. 893-938, https://doi.org/10.3982/QE2169 This Version is available at: https://hdl.handle.net/10419/320325 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Quantitative Economics 15 (2024), 893–938 1759-7331/20240893 Estimation and inference in games of incomplete information with unobserved heterogeneity and large state space Yanqin Fan Department of Economics, University of Washington Shuo Jiang MOE Key Lab of Econometrics, WISE, Department of Statistics and Data Science at School of Economics, Xiamen University Xuetao Shi School of Economics, University of Sydney Building on the sequential identification result of Aguirregabiria and Mira (2019), this paper develops estimation and inference procedures for static games of incomplete information with payoff-relevant unobserved heterogeneity and multiple equilibria. With payoff-relevant unobserved heterogeneity, sequential estimation and inference face two main challenges: the matching-types problem and a large number of matchings. We tackle the matching-types problem by constructing a new minimum-distance criterion for the correct matching and the payoff function with both correct and incorrect “moments.” To handle large numbers of matchings, we propose a novel and computationally fast multistep moment selection procedure. We show that asymptotically, it achieves a time complexity that is linear in the number of “moments” when the occurrence of multiple equilibria does not depend on the number of “moments.” Based on this procedure, we construct a consistent estimator of the payoff function, an asymptotically uniformly valid and easy-to-implement test for linear hypotheses on the payoff function, and a consistent method to group payoff functions according to the unobserved Yanqin Fan: [email protected] Shuo Jiang: [email protected] Xuetao Shi: [email protected] This paper is a revised version of the previously circulated paper “Estimation and inference in games of incomplete information with nonseparable unobserved heterogeneity,” dated September 17, 2020. We would like to thank a senior member of the editorial board and three anonymous referees for their insightful comments, which substantially improved this paper. We thank Aureo de Paula, Jin-Chuan Duan, Arnaud Maurel, Xun Tang, and Ruli Xiao, and participants of the 2018 Seattle-Vancouver Econometrics Conference, the 2019 North American Summer Econometrics Society Meetings, the 2021 Annual Conference of the International Association for Applied Econometrics, and 2023 Econometric Society Australasian Meeting for helpful discussions. This work was facilitated by Hyak supercomputer system and CSDE simulation cluster at the University of Washington. Shuo Jiang acknowledges the support of Fujian Key Lab of Statistics and the financial support from the Humanities and Social Sciences Foundation of the Ministry of Education of China [Grant 23YJC790053], Basic Scientific Center Project [Grant 71988101] of National Science Foundation of China, the 111 Project [Grant B13028], and National Natural Science Foundation of China [Grant 72373127]. ©2024 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at http://qeconomics.org.https://doi.org/10.3982/QE2169 894 Fan, Jiang, and Shi Quantitative Economics 15 (2024) heterogeneity. Extensive simulations demonstrate the finite sample efficacy of our procedures. Keywords. Matching-types problem, minimum-distance characterization, multistep moment selection procedure, time complexity. JEL classification. C12, C13, C57. 1. Introduction Motivation and main contributions The sequential approach to identification and estimation of discrete games of incomplete information is widely used in the literature; see Aguirregabiria and Mira (2007), Bajari, Benkard, and Levin (2007), and Pesendorfer and Schmidt-Dengler (2008)forseminal contributions and Bajari, Hong, and Nekipelov (2013)forasurvey.Inthefirststep, the equilibrium conditional choice probabilities (CCPs hereafter) at each observed state are identified and estimated from the data. In the second step, the payoff function is identified and estimated using variations in the observed state variable such as exclusion restrictions.1By avoiding the computation of equilibrium for every given state and parameter value, the sequential approach is computationally less costly than the allsolution or the joint method such as the nested fixed-point algorithm. However, the sequential approach relies critically on the assumption that there is no common knowledge payoff-relevant unobserved heterogeneity (unobserved heterogeneity hereafter) in the payoff function.2As discussed extensively in Aguirregabiria and Mira (2019), this assumption is very restrictive and often violated in the data, motivating them to study identification of a general class of games of incomplete information with payoff relevant unobserved heterogeneity and multiple equilibria. As pointed out in Aguirregabiria and Mira (2019), the presence of payoff relevant unobserved heterogeneity creates a major challenge in the sequential identification referred to as the matching-types problem, that is, the difficulty of correctly matching equilibrium CCPs for each unobserved state across different observed states. The matching-types problem arises because the first-step identification of equilibrium CCPs at each observed state is equivalent to the identification of a nonparametric finite mixture model, which is known to be identified only up to a label swapping of the mixing components. Despite this matching-types problem, Aguirregabiria and Mira (2019)establish a necessary and sufficient condition for the sequential identification of model primitives in games with unobserved heterogeneity of finite support and multiple equilibria. Building on their sequential identification result, this paper develops a sequential estimation approach for the class of games of incomplete information allowing for both unobserved heterogeneity of finite support and multiple equilibria.3 1Depending on the contexts/specifications, we will use payoff function, payoff vector, and payoff parameter interchangeably throughout this paper. 2In De Paula (2013), such unobserved heterogeneity is also called game-level heterogeneity or gamelevel shock. 3Although the joint identification does not suffer from the matching-types problem, estimators based on it for games with both unobserved heterogeneity and multiple equilibria have not been formally devel- Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 895 To tackle the matching-types problem, we construct a novel characterization of the correct matching and the true payoff vector via a minimum-distance criterion with both correct and incorrect “moments.” The set of correct moments corresponds to the correct matching; and the true payoff vector is uniquely determined through the correct matching. In the new minimum-distance criterion, the moment functions are linear in the unknown payoff vector with coefficients depending on the equilibrium CCPs identified in the first step. Estimation of the equilibrium CCPs is standard and can be done expeditiously using existing methods such as those in Bonhomme, Jochmans, and Robin (2016)andXiao (2018). Using the plug-in estimators of the coefficients, we obtain a vector of moment functions, based on which of the correct set of moments or the correct matching will be selected and the payoff vector will be estimated. Although this procedure falls within the general framework of Andrews (1999), the moment selection procedures in Andrews (1999) are computationally costly, and oftentimes infeasible even in games with moderately sized state spaces. The reason is that the number of matchings grows exponentially with the size of the state space. For example, in the Simple Game introduced in Section 2with medium numbers of players and observed and latent states, there can be thousands of trillions of matchings. To overcome this computational challenge, we propose a new and ingenious multistep moment selection (MMS) procedure for selecting the correct matching. It is based on the insight that in the minimum-distance criterion, a correct matching selects the same latent state across all observed states. As a result, a mismatch on any single observed state results in a wrong matching that needs not to be considered in the estimation. Exploiting this feature, in the new MMS procedure, we first eliminate matchings that are incorrect with high probability in multiple steps, then estimate the correct matching and the payoff vector using the remaining possible matchings. By carefully designing the steps involved, the new MMS procedure selects the correct matching with probability approaching one and is much faster to implement than the moment selection procedures in Andrews (1999) for games with large state spaces. Theoretically, we show that when there is no multiple equilibria or when the number of observed states with multiple equilibria does not increase with the number of moments, the new MMS procedure achieves a linear time complexity in the number of moments for large sample sizes.4 This is a significant improvement over the exponential time complexity of the moment selection procedures in Andrews (1999). Practically, the new MMS-based estimator of the payoff vector can be calculated within asecondwhen there are thousands of trillions of matchings; while the estimator in Andrews (1999)requiresthousands of seconds to computeevenwhenthereareonlymillions of matchings. When there are multiple equilibria played in the data, both multiple equilibria and unobserved heterogeneity contribute to the mixtures of CCPs. To estimate the cardinality of the support of the unobserved heterogeneity and the payoff vector on each latent state, we propose a method for grouping the payoff vectors by extending the k-means oped and are unexplored in practice. Additionally, they would carry the heavy computational burden of the existing nested fixed-point algorithm. 4The time complexity describes the amount of time it takes to run an algorithm. It is commonly estimated by counting the number of elementary operations performed by the algorithm. 896 Fan, Jiang, and Shi Quantitative Economics 15 (2024) method to penalize more clusters. The number of clusters estimate the number of latent states, and the payoffs on each latent state are estimated by the centers of each cluster. We show that our estimators consistently estimate the number of latent states and the payoff vector on each latent state. This method of separating multiple equilibria from unobserved heterogeneity is novel and can be used in other contexts such as the dynamic game with both multiple equilibria and unobserved heterogeneity studied in Luo, Xiao, and Xiao (2022). Lastly, we develop a fast-to-compute and asymptotically uniformly valid inference procedure for linear hypotheses on the payoff vector. Despite the difficulties in general post-selection inference, our test is asymptotically uniformly valid and is easy to implement with known critical values from the chi-squared distribution. Although we focus on the class of games with nonparametric payoff functions in Aguirregabiria and Mira (2019), we demonstrate that the novel minimum-distance characterization can be easily modified for games with parametric payoff functions commonly adopted in empirical work. As a result, the MMS procedure applies to these games as well. In the simulation section, we report the finite sample performance of the new MMS procedure, the estimators for the payoffs and the number of unobserved heterogeneity types, and the test when applied to four games with parametric payoffs. Based on the simulation results, we provide a rule-of-thumb for choosing the tuning parameters for implementation of the MMS procedure, and demonstrate its effectiveness using different designs constructed from the four games. Overall, the simulation results confirm the finite sample efficacy of both the estimation and inference procedures. Related literature Our paper connects with several strands of the literature. First, the paper is closely related to works on static games of incomplete information with/without unobserved heterogeneity. In the analysis of strategic timing incentives among radio stations, Sweeting (2009) estimates a parametric game of incomplete information that allows for multiple equilibria but no unobserved heterogeneity. He also states that “estimation of a game with many possible choices, multiple equilibria, and observed and possibly unobserved heterogeneity is well beyond the current literature.” Sweeting (2009) has sparked important research. De Paula and Tang (2012) propose a formal test for multiple equilibria when there is no unobserved heterogeneity. Grieco (2014) studies identification and estimation in a game with normally distributed private information, allowing both for the presence of multiple equilibria and for normally distributed unobserved heterogeneity. In Grieco (2014), the unobserved heterogeneity is of a nuisance nature; and the parameter of interest does not depend on unobserved heterogeneity. Xiao (2018)studies sequential identification and estimation in a game with multiple equilibria and no unobserved heterogeneity. She develops a new method based on eigendecomposition for identifying and estimating CCPs that come from multiple equilibria. Aguirregabiria and Mira (2019) present a general identification framework allowing for both unobserved heterogeneity and multiple equilibria, which nests the setup in Xiao (2018). In Aguirregabiria and Mira (2019), the payoff parameter of interest is allowed to depend on unobserved heterogeneity, which differs from the parameter of interest in Grieco (2014). Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 897 Luo, Xiao, and Xiao (2022) show that the matching-types problem in dynamic games of incomplete information could be resolved by making use of the special structure of Markov perfect equilibrium and the longitudinal variations of observed states. There is another strand of literature on the identification and estimation of complete information games such as Bajari, Hong, and Ryan (2010), in which all unobservables are common knowledge among players. A recent paper by Magnolfi and Roncoroni (2023)studies identification and estimation under the solution concept of the Bayesian correlated equilibrium, which is proposed by Bergemann and Morris (2013,2016). Magnolfi and Roncoroni (2023) allow for all information structures consistent with players knowing their own payoffs and the distribution of opponents’ payoffs. Their information structure nests both the complete and incomplete information settings.5 Our paper also contributes to the literature on moment selection and uniform inference. In a seminal paper, Andrews (1999) proposes several consistent moment selection procedures for the generalized method of moments estimation with valid and invalid moments. Andrews and Lu (2001) extend these procedures and apply them to dynamic panel data models. Two problems remain unsolved regarding the moment selection procedures. First, it is well known that executing the procedures in Andrews (1999)and Andrews and Lu (2001) can be computationally costly (see Liao (2013)).6Second, the built-in moment selection implies that the inference problem is a post-selection inference. Constructing an asymptotically uniformly valid inference method is challenging in this context (see Leeb and Pötscher (2005)andLeeb and Pötscher (2008)). In the paper, we solve both problems by fully exploiting the structure of our setup. First, a correct matching selects the same latent state for each observed state. As a result, we know the structure of the set of correct moments. This fact enables us to design a multistep algorithm that is fast to compute. Second, in our setting, the minimum number of correct moments is known. This allows us to construct an asymptotically uniformly valid and easy-to-implement inference method. Organization of the rest of this paper The rest of this paper is organized as follows. Section 2uses two games of incomplete information with unobserved heterogeneity to introduce our novel minimum-distance criterion of the payoff vector. The first game is a member of the class of games with nonparametric payoff functions studied in Aguirregabiria and Mira (2019) and is referred to as the Simple Game; and the second game is the same as the Simple Game except that its payoff function is parameterized. Section 3proposes the novel MMS procedure and the estimator of the payoff vector, proves its consistency, and shows the asymptotic linear time complexity of the procedure for the Simple Game. Section 4develops an asymptotically uniformly valid test for linear hypotheses on the payoff vector. Section 5extends the methods developed for the Simple Game to a game with a general number of players, 5Haile and Tamer (2003) and Aradillas-López, Gandhi, and Quint (2016) study identification and inference of auction models under weak assumptions that could allow for multiple equilibria. 6Unlike Liao (2013)orCheng and Liao (2015), a known set of valid moments that guarantee identification of the unknown parameter is not available in our setup. 898 Fan, Jiang, and Shi Quantitative Economics 15 (2024) actions, latent states, and most importantly multiple equilibria referred to as the General Game. We extend the MMS estimation procedure and the asymptotically uniformly valid test developed for the Simple Game to the General Game. In Section 6, we introduce variants of the Simple Game and General Game and investigate the finite sample performance of our estimation and inference methods via Monte Carlo simulation. Section 7concludes. Mathematical details of the results for the General Game are provided in Appendix A. Additional materials are collected in the Supplemental Appendix (Fan, Jiang, and Shi (2024)). Supplemental Appendix B contains proofs for the results in the paper. Supplemental Appendix C contains further details on Xiao (2018)’s CCP estimator and the identification in the General Game. Supplemental Appendix D contains additional details on the simulation. The codes for implementing the multistep estimation and inference procedures are available at https://github.com/FanJiangShi/MMSP. We close this section by introducing some notation used throughout this paper. For any q×1vectorE,letEdenote its Euclidean norm and E0denote its L0norm, that is, the number of nonzero elements in E.Forbeing some q×qmatrix, denote E2 ≡EE. For any finite set, |·|denotes its cardinality. For any given q-dimensional vector cof zeros and ones and some q×pmatrix A,letAcdenote the submatrix of A generated by deleting the rows in Acorresponding to zeros in c.LetIqbe a q×qidentity matrix. “wp →1” denotes “with probability approaching one.” 2. A minimum-distance characterization of the payoff vector In this section, we use two games of incomplete information with unobserved heterogeneity to introduce our novel minimum-distance characterization of the payoff vector. The first game is a member of the class of games with nonparametric payoff functions studied in Aguirregabiria and Mira (2019) and is referred to as the Simple Game. The second game is the same as the Simple Game except that its payoff function is parameterized. We introduce the Simple Game in Section 2.1 and review its sequential identification in Section 2.2.InSection2.3, we construct a novel characterization of the payoff function in the Simple Game via a minimum-distance criterion with both correct and incorrect moments. In Section 2.4, we introduce the payoff function of the second game and show how the minimum-distance characterization accommodates for the parametric structure of the payoff function of the second game. 2.1 The simple game In the Simple Game, there are three players, two actions, one exclusive observed state variable, and one dichotomous unobserved state variable.7Each player, denoted as i=1, 2, 3, chooses an action di∈{0, 1}. Before choosing his action, player idraws his private information i(di)for two actions di=0anddi=1 from a bivariate distribution. For i=1, 2, 3, denote zi∈Zias an observable exclusive state variable, which does 7It follows from Allman, Matias, and Rhodes (2009) and Aguirregabiria and Mira (2019) that when the number of mixing components is 2, the minimum number of players required for identifying CCPs up to a label swapping is 3. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 899 not enter the payoffs of other players, where Ziis a finite set with cardinality |Zi|.Let k∈K≡{A,B}be a common knowledge state variable that is known by all players but unobserved by the econometrician.8Player i’s payoff from choosing action diis given by πi(di,d−i,zi,k,i(di)), where the vector d−idenotes the joint actions of all the other players except i. Following Aguirregabiria and Mira (2019), we assume that player i’s payoff is additively separable in his private informationi(di)and can be written as πidi,d−i,zi,k,i(di)=πi(di,d−i,zi,k)−i(di), where πi(di,d−i,zi,k)captures how player i’s payoff for choosing dichanges with respect to his opponents’ actions and state variables.9Since the optimal action is invariant under monotonically increasing transformations of payoffs, we normalize the payoffs using πi(0, d−i,zi,k,˜i(0)) and define the normalized payoff for di=1as πi(1, d−i,zi,k)≡πi(1, d−i,zi,k)−πi(0, d−i,zi,k) sd , where sd denotes the standard deviation of i(1)−i(0). We refer to πi(di,d−i,zi,k)as the payoff function for player ihereafter. By normalization, πi(0, d−i,zi,k)=0. Define the normalized private information for player ias i≡1 sd (i(1)−i(0)).Let z≡(z1,z2,z3)∈Z≡Z1×Z2×Z3. We adopt the assumption in Aguirregabiria and Mira (2019)onistated below.10 Assumption 2.1. (i){i}3 i=1 i.i.d. ∼F(·),where F(·)is an absolutely continuous distribution function with a probability density function denoted as f(·)and is known to the econometrician.(ii)The support of f(·)is R.(iii)1,2,and 3are independent of the state variables (z,k). A(pure)strategyinthisgameisdefinedasfollows. Definition 2.1 (Strategy). For given zand k, a (pure) strategy for player iis a mapping σi(i,z,k):R×Z×K→{1, 0}. For notational compactness, we use σ≡(σ1(1,z,k),σ2(2,z,k),σ3(3,z,k))to denote a strategy profile given (z,k).Let1(·)denote the indicator function. Any given σis 8The assumption of a fixed and finite support for unobserved heterogeneity is not only used in Aguirregabiria and Mira (2019) (p. 1663), but also in single agent dynamic discrete choice models such as Kasahara and Shimotsu (2009). 9The additive separability of the private information is commonly assumed in the literature on the econometrics of games of incomplete information. Examples include Sweeting (2009), De Paula and Tang (2012), Bajari, Hong, and Nekipelov (2013), and Grieco (2014). 10Other papers that maintain such an assumption on private information include Zhu and Singh (2009), Li, Liu, and Deininger (2013), and Xiao (2018). Papers that allow for unknown distribution for private information include Aradillas-López (2010) and Lewbel and Tang (2015). Papers that allow for correlated private information among players include Wan and Xu (2014), Xu (2014), and Liu, Vuong, and Xu (2017). 900 Fan, Jiang, and Shi Quantitative Economics 15 (2024) completely characterized by the following CCPs: pi≡1σi(i,z,k)=1f(i)di,fori=1, 2, 3. Denote jand qas the two players other than player i.Theexpected payoff function for player iwith di=1forgiven(z,k)and σis computed as11 πi(1, z,k,σ)= dj,dq∈{0,1} pdj j(1−pj)1−djpdq q(1−pq)1−dqπi1, (dj,dq),zi,k. (2.1) Bayesian Nash Equilibrium (BNE) is then defined as follows. Definition 2.2 (Equilibrium). For any given (z,k), a BNE of the game is a strategy profile σ∗such that for any player iand for any i, σ∗ i(i,z,k)=arg max di∈{0,1}πidi,z,k,σ∗−i. In the Simple Game, we assume that the data are rationalized by a single equilibrium. This assumption will be discarded in Section 5. Assumption 2.2. A single equilibrium is played in the data for each (z,k)∈Z×K. Denote the equilibrium CCP of choosing action 1 for player ias pi(z,k)≡Pr(di= 1|z,k).Thenitholdsthat pi(z,k)=1σ∗ i(i,z,k)=1f(i)di. For any (z,k), the BNE of the game is equivalently characterized by the equilibrium CCP vector p(z,k)≡p1(z,k),p2(z,k),p3(z,k), (2.2) where pi(z,k)=Fπi1, z,k,σ∗ for i=1, 2, 3. Under Assumption 2.2, the equilibrium expected payoff function is unique and only depends on zand k. For brevity, we denote it as πi(1, z,k)≡πi(1, z,k,σ∗). Remark 2.1. For any given (z,k)and strategy profile σwith corresponding CCP vector (p1,p2,p3), the probability that choice 1 is optimal for player iin the Simple Game is given by F(πi(1, z,k,σ)) for i=1, 2, 3. This defines the best response mapping for players i=1, 2, 3 on (z,k)as follows: izkπi(1, z,k,σ)=Fπi(1, z,k,σ). (2.3) 11Because of the normalization, πi(0, z,k,σ)=0. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 907 where πzt=π11, zt,kt π11, zt,k tand zt=z1p2zt,kt+p3zt,kt z1p2zt,k t+p3zt,k t. The minimum-distance characterization of the payoff vector we constructed for the Simple Game in Section 2.3 is valid with π=⎡ ⎢ ⎣ πz1 . . . πzl⎤ ⎥ ⎦,=⎡ ⎢ ⎣ z1 . . . zl⎤ ⎥ ⎦,andπ=θ1 δ1, where the vector πis of dimension 2l×1, is the coefficient matrix of dimension 2l×2, and πis the vector with dimension 2 ×1. Given some selected latent state for z1,we could match this latent state across all observed states under the same conditions to those for Step 2 identification of the Simple Game in Section 2.3. 3. Multistep moment selection estimation of the payoff vector in the simple game As we demonstrate in Section 2.4, the parameters of interest in the variants of the Simple Game share the same minimum-distance characterization as the Simple Game with redefined π,,andπin the moment function. Without loss of generality, we focus on developing estimation and inference procedures for the Simple Game in Sections 3and 4. From Lemma 2.1, it follows that the true selection vector c0and the true parameter vector π0satisfy (c0,π0)=arg min c∈C,π∈Gc(π)2 W(c), (3.1) where Gc(π)=πc−cπand W(c)are a positive definite weighting matrix that can depend on c. The matrices πand depend on equilibrium CCPs and can be estimated by the plug-in approach using equations (2.6)and(2.9) once the equilibrium CCPs on all the observed and latent states are estimated. Existing methods such as those in Bonhomme, Jochmans, and Robin (2016)andXiao (2018) can be used to estimate the equilibrium CCPs. We focus on the CCP estimator developed by Xiao (2018) in this paper and present the steps in Appendix C.1. Denote the resulting estimators as πnand n.Wenote that this step is standard in the literature and can be implemented fast even for large l. This is because the eigendecomposition procedure is done for each observed state separately; and each procedure is fast to compute.13 We focus on the second step from now on. Let the sample moment functions be Gn(π)≡πn−nπ,forπ∈. 13Using 1000 simulations, the average time needed to compute the eigendecomposition and obtain player 1’s CCP on one observed state is less than 10−4second. 908 Fan, Jiang, and Shi Quantitative Economics 15 (2024) We use Gn,c(π)to denote the sample moment functions selected by c. The sample version of (3.1)is ( c,π)≡arg min c∈C,π∈Gn,c(π)2 Wn(c), (3.2) where Wn(c)is the sample weighting matrix. This is equivalent to the moment selection procedures in Andrews (1999) when applied to the Simple Game. Solving (3.2)requires performing discrete optimization over C. Since |C|=2l−1, implementing ( c,π)is computationally challenging for large l. For example, when there are seven exclusive states for each player, l=|Z2|×|Z3|=49. The size of Cbecomes 248 ≈2.8 ×1014.Thismotivates our computationally less costly multistep moment selection (MMS) procedure proposed in Section 3.1.InSection3.2, we show consistency of the MMS procedure and its time complexity result. In contrast to the estimator ( c,π), which has an exponential time complexity in l, the time complexity of the MMS is asymptotically linear in l. Section 3.3 provides some guidance on the practical implementation of the MMS procedure. Proofs of the theorems in this section are provided in the Supplemental Appendix. 3.1 Multistep moment selection procedure As the number of exclusive states |Z2|or |Z3|increases, the value of lrises sharply. The MMS procedure explores an important feature of the game to reduce the computation time: the true payoff vector π0is only defined for the system selected by c0, and none of the other systems selected by c∈Cand c= c0has a solution. Specifically, in the MMS procedure, we eliminate the matchings/selection vectors c∈Cthat are certainly incorrect in multiple steps instead of one step as in the computation of ( c,π). With careful design of the steps involved, we are able to construct an effective parameter space for c0of a much smaller size than C(see the last step in the procedure). The MMS procedure selects the correct matching and estimates the payoff vector using the effective parameter space for c0. To succinctly introduce our idea, we present a two-step moment selection (TMS) procedure first and then extend it to the general MMS procedure. For any vector sc of dimension 2lconsisting of zeros and ones, we use Gn,sc(π)to denote the moment functions selected by sc from Gn(π). Different from the selection vectors in C,weletsc select fewer than lmoments and call it a subselection vector. We partition sc into lsubvectors, where each subvector contains two elements. Denote sct for t=1, ,las the tth subvector of sc such that sc ≡[sc1,,scl]. Define Jn(sc)≡min π∈Gn,sc(π)2. 3.1.1 The TMS procedure Let l1∈{lπ,lπ+1, ,l}. Heuristically, if we know that the first l1moments selected by some selection vector contains incorrect moments, then all the 2l−l1selection vectors in Cthat select the same first l1moments can be ignored in the estimation of (c0,π0), because a matching is correct only when all the lmoments are selected correctly. Step 1 below identifies matchings of the first l1moments that are incorrect with high probability (wp →1). In Step 2, we estimate the correct matching and the true payoff vector by minimizing an objective function over the product space Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 909 of the effective parameter space, which excludes the incorrect matchings identified in Step 1 and the parameter space . We present the detailed steps below. Step 0: Set l1∈{lπ,lπ+1, ,l},α1∈(0, 1],andλ∈(−1, 0). Step 1: Define the collection of subselection vectors in Step 1 as SC1≡[sc1,,scl]∈R2l:sc1=[1, 0];sct∈[1, 0],[0, 1], for t∈{2, ,l1};andsct=[0, 0]for t∈{l1+1, ,l}. By definition, sc1∈SC1selects none of the last 2(l−l1)moments. Sort Jn(sc1)for all sc1∈SC1, and denote Jα1 nas the value of the 100α1% smallest. Compare Jα1 nwith nλ.If Jα1 n>n λ, then collect all sc1such that Jn(sc1)≤Jα1 n;otherwise,collectallsc1such that Jn(sc1)≤nλ. Denote the collection as SC1 n: SC1 n≡sc1∈SC1:Jnsc1≤maxJα1 n,nλ. The set SC1 nis the output of Step 1. Step 2: Define the effective parameter space for c0as Cn≡[c1,,cl]∈R2l:[c1,,cl1]=sc1 1,,sc1 l1for some sc1∈SC1 n;andct∈[1, 0],[0, 1]for t∈{l1+1, ,l}. The TMS estimator is defined by the following minimization problem:14 ( c,π)≡arg min c∈Cn,π∈Gn,c(π)2 Wn(c). For each c∈Cn,thefirst2l1components of care the same as the first 2l1components of some sc1∈SC1 n;andthelast2 (l−l1)components can select any combination of the last 2(l−l1)moments allowed by C. Since every c∈Cnselects lmoments out of the l pairs, Cn⊆C. In the special case where SC1 n=SC1,wehaveCn=C. Let sc1 0∈SC1denote the subselection vector whose first 2l1elements are the same as c0. In Step 1, we determine if a subselection vector sc is part of an incorrect matching by comparing Jn(sc)with nλ, because Jn(sc1 0)<n λoccurs with high probability when n is large. At the same time, we keep at least 100α1%elementsinSC1to prevent sc1 0from being eliminated because of finite sample error. The size of SC1is 2l1−1, which is much smaller than the size of Cwhen l1is smaller than l. As a result, Step 1 can be implemented very fast. The set SC1 nhas α 12l1−1elements where α 1≡|SC1 n|/|SC1|; and the size of the effective parameter space Cnis (α 12l1−1)×2(l−l1)=α 12l−1.Whenα 1is small and lis moderately large, ( c,π)is computationally much faster than ( c,π). Remark 3.1. Setting α1=1 recovers ( c,π)in (3.2), and π=πwhenever  c= c. 14The definition of ( c,π)implicitly assumes that the solution to the minimization problem is unique. This can be shown to hold with probability approaching one. 910 Fan, Jiang, and Shi Quantitative Economics 15 (2024) 3.1.2 The MMS procedure When lis very large, implementing Step 2 above may still be time consuming, because α 12l−1can be large. To further reduce the computational time, we extend the above TMS to MMS with any finite number of steps as needed. For example, in an MMS with three steps, the first step is the same as the first step in TMS. Instead of selecting from all the possible combinations of (2l1+1)-th to 2l-th moments in the second step, we select from the (2l1+1)-th to 2l2-th moments, where l2≡l1+ for some prespecified ∈{1, ,l−l1}. In the third step, we select from the (2l2+1)-th to 2l-th moments. Below, we present the detailed procedure for implementing the MMS procedure with (S+1)steps. Let xdenote the smallest integer greater than or equal to x. Step 0: Set l1∈{lπ,lπ+1, ,l},α1∈(0, 1],λ∈(−1, 0),and∈{1, ,l−l1}.Let S=l−l1 and α=2−. Step 1: Apply the same procedure as Step 1 in the TMS procedure. The output is the set SC1 n. Steps2,3,...S:For s=2, ,S, define ls≡ls−1+. The input of Step sis the collection of subselection vectors defined as SCs≡⎧ ⎪ ⎨ ⎪ ⎩ [sc1,,scl]∈R2l:[sc1,,scls−1]=scs−1 1,,scs−1 ls−1for some scs−1∈SCs−1 n;sct∈[1, 0],[0, 1]for t∈{ls−1+1, ,ls}; and sct=[0, 0]for t∈{ls+1, ,l} ⎫ ⎪ ⎬ ⎪ ⎭. By definition, each scs∈SCs nconsists of three parts: the first 2ls−1components of scs are the same as the first 2ls−1components of some scs−1∈SCs−1 n;the(2ls−1+1)-th to 2ls-th components of scsselect any combinations allowed by C;andscsselects none of the last 2(l−ls)moments. Sort Jn(scs)for all scs∈SCs, and denote Jα nas the value of the 100α% smallest. Construct the output of Step s,SCs n,as SCs n≡scs∈SCs:Jnscs≤maxJα n,nλ. Step (S+1):Define the effective parameter space for c0as Cn≡[c1,,cl]∈R2l:[c1,,clS]=scS 1,,scS lSfor some scS∈SCS n;andct∈[1, 0],[0, 1]for t∈{lS+1, ,l}. The MMS estimator is defined by the following minimization problem: ( c,π)≡arg min c∈Cn,π∈Gn,c(π)2 Wn(c). (3.3) For each c∈Cn,thefirst2lScomponents of care the same as the first 2lScomponents of some scS∈SCS n;andthelast2 (l−lS)components can select any combination of the last 2(l−lS)moments allowed by C. Let α s≡|SCs n|/|SCs|.InStepsfor s=1, ,S, the input set SCshas the cardinality 2ls−1!s−1 i=1α i,andtheoutputsetSCs nhas the cardinality 2ls−1!s i=1α i.InStep(S+1), |Cn|=2l−1!S i=1α i.Forlargel, we usually have large Sand small α sfor s=1, ,S.The number of optimizations from Step 1 to Step (S+1)is much fewer than the number of optimizations required for computing ( c,π). Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 911 Remark 3.2. The choice of the tuning parameters l1,α1,λ,andare independent of l and n.SeeSection3.3 for more discussion. Remark 3.3. By replacing the zeros with ones and the ones with zeros in  c,weobtain an estimator for the true selection vector in C2. Based on it, we can estimate the payoff vector. Alternatively, we can apply the above MMS procedure to C2to obtain the estimators. 3.2 Asymptotic properties of the MMS procedure The consistency of ( c,π)is proved under the following assumptions. Assumption 3.1. The space is compact. Assumption 3.2. For ∀c∈Cn,Wn(c)p →W(c)for some positive definite matrix W(c). Assumption 3.2 imposes a standard assumption on the weighting matrix. Note that the weighting matrix Wn(c)is only used in the last step of the MMS procedure. The following theorem states consistency of the estimators  cand π. Theorem 3.1. Under Assumptions 2.1–2.6 and 3.1–3.2,it holds that  c=c0wp →1and πp →π0for any l1∈{lπ,lπ+1, ,l},α1∈(0, 1],λ∈(−1, 0),and ∈{1, ,l−l1}. Theorem 3.1 shows that the MMS procedure is consistent for any l1,α1,λ,andthat satisfy the requirements in the theorem. The values of the tuning parameters only affect the finite sample performance of the estimator. The theorem below shows that asymptotically the time and space complexities of the MMS are linear in l.15 Theorem 3.2. Let Assumptions 2.1–2.6 and 3.1 hold.Then with probability approaching one as n→∞,for all payoffs except for a set of Lebesgue measure zero,both the time and spacecomplexitiesoftheMMSprocedurearelinearinl. Consider the space of payoffs for all three players such that the assumptions in the theorem are satisfied. Theorem 3.2 shows that, except for a subset of Lebesgue measure zero in this space, both the computation time and memory storage required for performing the MMS procedure are linear in lwith probability approaching one as n→∞. In other words, except for certain “exceptional” payoffs, the linear time and space complexities hold with high probability when nis large. Although Theorem 3.2 is an asymptotic result, the simulation results in Section 6 show that the MMS is extremely fast to compute for all DGPs and sample sizes considered. To guarantee the consistency, the MMS cannot eliminate c∈Cif 15The space complexity measures the amount of memory space required for performing an algorithm. It is another important factor when evaluating the efficiency of an algorithm. 912 Fan, Jiang, and Shi Quantitative Economics 15 (2024) minπ∈Gn,c(π)2<n λ. However, for a small sample size, there might be some c= c0 such that the inequality holds.16 When nbecomes larger, fewer selection vectors would satisfy the inequality, because minπ∈Gn,c(π)2<n λholds for λ<0onlyifc=c0when n→∞.Asaresult,SCsin each step contains fewer elements for larger n.Thecomputation time of the MMS decreases and becomes linear in lin the limit. 3.3 Practical implementation We summarize the computation of the MMS estimator ( c,π)in Algorithm 1and provide guidance on the choice of tuning parameters l1,α1,λ,andin finite samples. We discuss the roles of the tuning parameters based on the ascending order of their relative importance to the computational time. For s=1, ,S,letscs 0denote the subselection Algorithm 1: The MMS procedure. 16Even if in rare cases where minπ∈Gn,c(π)2is small for all c=c0, by setting an aggressive λ, the MMS procedure can still improve upon (3.2) in running time. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 913 vector whose first 2lselements are the same as c0and the remaining elements are zeros. Namely, scs 0selects the correct first lsmoments. We first discuss the role of λ. In each step, nλserves as a threshold to identify scs∈ SCsthat is surely (wp →1) different from scs 0. The threshold is conservative for larger λ and aggressive for smaller λ. By the property of scs 0and Gn,scs 0(π),minπ∈Gn,scs 0(π)2= Op(n−1).Thus,ifminπ∈Gn,scs(π)2does not converge to zero at rate nλfor λ>−1 as n→∞,thenPr(scs= scs 0)→1. Excluding such scsfrom the output of Step s,SCs n, reduces the number of elements in the input of Step (s+1),SCs+1, and the inputs of all the next steps. We recommend λ=−0.01 based on the simulation study. The parameter α1acts as a safety net for keeping sc1 0in SC1 nin finite samples. It also indirectly prevents scs 0from being excluded from SCs nin finite samples for s=2, ,S. Because minπ∈Gn,scs 0(π)2may not be small due to the finite sample error, enough subselection vectors need to be included in SCs nso that scs 0is not eliminated in each step. We deliberately set α=2−, so that the number of elements in the output set does not decrease as the algorithm proceeds. There are at least α12l1−1elements in SCs nafter each step. When α1is larger, SCs ntends to have more elements, which increases the chance that scs 0∈SCs n. Extensive simulation suggests setting α1=0.5%. The tuning parameter l1affects the computational time of ( c,π), because the set SC1 ndirectly affects SC2in Step 2 and SCsin all the following steps. There are α 12l1−1 elements in SC1 n,whereα 1≡|SC1 n|/|SC1|, and the same order of elements in SCs n for s=2, ,S. The value of α 1∈[α1,1 ]is determined by the percentage of sc1’s in SC1 such that minπ∈Gn,sc1(π)2is small. If Jα1 n>n λ,thenα 1=α1, while if Jα1 n≤nλ,then 100α 1%ofsc1’s in SC1satisfy that Jn(sc1)≤nλ. In consequence, when only a small portion of elements in SC1 nmake minπ∈Gn,sc1(π)2small, α 1is small. Intuitively, minπ∈Gn,sc1(π)2tends to be small if no or a few incorrect moments are selected by sc1. Because the percentage of such sc1’s in SC1decreases with l1,α 1is smaller for larger l1, and vice versa. For example, the percentage of subselection vectors in SC1 that select only one incorrect moment is (l1−1)/2l1−1, which decreases dramatically as l1increases. At the same time, enough moments relative to lπshall be included in Step 1. Since the number of elements in SC1 nis a product of 2l1−1and α 1, we need to balance the two effects of l1to achieve faster running time. Based on extensive simulations, we suggest setting l1=5lπ.17 The value of affects the total number of steps and the number of optimizations in each step. Larger leads to fewer steps, because S=l−l1 . On the other hand, lowering decreases the computation time of each step. Given the number of elements in the output set of Step (s−1), the input set SCsof Step shas 2times more elements. Decreasing would then reduce the cardinality of SCsand the number of operations in each step. We recommend setting =2 based on extensive simulations. Once is chosen, the value of αis determined accordingly as 2−so that more moments we add in each step, more aggressive we are in the elimination of incorrect matchings. In summary, we recommend setting λ=−0.01, α1=0.5%, l1=5lπ,and=2inthe MMS procedure. We call such a choice the rule-of-thumb. See more discussion on the roles of the tuning parameters and the rule-of-thumb in Section 6.1. 17Since lπis small, for cases where l<5lπ,( c,π)can be employed directly. 914 Fan, Jiang, and Shi Quantitative Economics 15 (2024) 4. Inference on the payoff vector in the Simple Game This section develops a test for the following linear hypothesis: H0:Rπ0=ragainst H1:Rπ0=r, (4.1) where Ris of dimension lR×lπwith rank(R)=lRand ris of dimension lR×1. A simple test statistic would be min c∈C,Rπ=r√nGn,c(π)2 Wn(c), which is expected to be large if the null is incorrect. However, this test statistic can be computationally challenging when the parameter space Cis large. Similar to the multistep estimator proposed in Section 3.1, we propose the multistep test statistic: Tn≡min c∈Cn,Rπ=r√nGn,c(π)2 Wn(c), (4.2) where Cnis the effective parameter space for c0in the last step of the MMS.18 See Section 3.1. 4.1 Asymptotic validity and consistency Note that we are dealing with a post-selection inference problem because of the builtin moment selection in our test statistic. Albeit the many challenges faced with general post-selection inference documented in Leeb and Pötscher (2005)andLeeb and Pötscher (2008), we are able to construct an asymptotically uniformly valid and computationally simple test based on Tn. Assume that the model is fully characterized by ξ∈,whereis some compact parameter space and is possibly infinite-dimensional. For the Simple Game, ξincludes the distribution of private information, conditional probability of latent state on observed state, and payoff vectors for each individual. Denote Ras the parameter space consistent with the null hypothesis and Prξ(·)as the probability calculated under ξ.The objective is to find a critical value CV that controls the asymptotic size defined as AsySize ≡lim sup n→∞ sup ξ∈R Prξ(Tn>CV). (4.3) We consider the drifting model parameter sequence ξnand the set of drifting model parameter sequences under H0with limit ξas R(ξ)={ξn∈R:n≥1}:ξn→ξ∈R. (4.4) The important role of the analysis under drifting (sub)sequences has been emphasized in Andrews and Cheng (2012), Cheng (2015), and Andrews, Cheng, and Guggenberger 18A test analogous to the J-test can be applied to testing the joint validity of the model assumptions including the parametric form of the payoff function such as that in Game 1. Details are omitted due to space considerations. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 915 (2020). Its introduction is not intended as a literal description of real-world data, but merely a device that helps us study the asymptotic property of the test statistic that mimics its finite-sample behavior. For the system of moment functions G(π),aselectionis correct if Gc(π)=0for some π, and is incorrect if Gc(π)=0for any π. By Lemma 2.1, the only true selection is c0. However, under drifting sequence of model parameters, it is possible that Gξn c(π)=0but Gξn c(π)→0for some c=c0and π∈as n→∞,where Gξn c(π)denotes the moment functions selected by cunder the drifting model parameter sequence ξn. We call such selection a nearly true selection. When nearly true selections exist, the probability that c0is the solution to the minimization problem (4.2) does not approach one, so that incorrect moment functions may be selected even when n→∞. Such phenomenon occurs in the post-selection inference problem and often complicates the inference procedure. However, since the number of correct moments in the Simple Game is known to be l, the null asymptotic distribution of Tnunder drifting sequence is stochastically dominated by the chi-squared distribution with (l−lπ+lR)- degrees of freedom. This allows us to construct an asymptotically uniformly valid test using critical value from the chi-squared distribution with (l−lπ+lR)-degrees of freedom even in the presence of nearly true selections. Moreover, by Assumption 2.6,forany c=c0, the system Gc(π)=0does not have a solution. The test statistic diverges to infinity under the alternative hypothesis because limn→∞minRπ=rGn,c(π)2 Wn(c)>0forall c∈Cif Rπ0=r. Assumption 4.1. (i)The derivative of f(·)is bounded.(ii)For any ξ∈R,ztakes each value in Zwith probability bounded below by ε>0. (iii)For any ξ∈Rand the parameter sequence {ξn}∈R(ξ),given each c∈Cn,Wn(c)=W(c)+op(1)with W(c)being positive definite.(iv)W(c0)=−1 0for 0being the asymptotic variance of √n(Gn,c0(π0)−Gc0(π0)). Assumption 4.1(i) is satisfied by commonly used distributions and is needed for the uniform linear representation of the moment function given a uniform linear representation of the CCP estimator. Assumption 4.1(ii) assumes that the support of zis the same for all ξ∈Rand is one of the sufficient conditions needed for the uniform linear representation of Xiao (2018)’s CCP estimator. Assumption 4.1(iii) and (iv) require that the probability limit of Wn(c)be positive definite and that the optimal weighting matrix be used for c0. The asymptotic variance matrix 0being nonsingular is satisfied automatically by the setting of the Simple Game and is verified in the proof of Theorem 4.1. Denote χ2 [df ],1−αas the (1−α)-th quantile of the chi-squared distribution with df - degrees of freedom. The following theorem states the asymptotic validity and consistency of the test based upon the test statistic Tnand critical value χ2 [l−lπ+lR],1−α.The proof is provided in the Supplemental Appendix. Theorem 4.1. Let Assumptions 2.1–2.6 hold.For any l1∈{lπ,lπ+1, ,l},α1∈(0, 1], λ∈(−1, 0),and ∈{1, ,l−l1},(i)if in addition Assumptions 3.1 and 4.1 hold,then limsup n→∞ sup ξ∈R PrξTn>χ 2 [l−lπ+lR],1−α=α; 916 Fan, Jiang, and Shi Quantitative Economics 15 (2024) (ii)if in addition Assumptions 3.1–3.2 hold,then for any ξ/∈R, lim n→∞PrξTn>χ 2 [l−lπ+lR],1−α=1. Remark 4.1. We can also test hypotheses involving cross-player restrictions on some latent state or cross-latent state linear restrictions for some players. Both can be achieved by stacking the moment functions and adjusting the parameter space of the true selection vector. For example, let the null hypothesis be that the payoffs for players 1 and 2 are equal on some latent state. For i=1, 2, we can construct the sample moment functions Gni(πi)=πni −niπifor player i. Define Gn(π1,π2)≡Gn1(π1) Gn2(π2)=πn1 πn2−n10 0n2π1 π2and C≡[c1,,c2l]∈R4l:ct=ct+l∈[1, 0],[0, 1]for t∈{1, ,l}. In the construction of C, we keep the ordering of mixing components the same across players because the CCPs for different players are identifiable up to the same label swapping. The test can be carried out by the test statistic min c∈Cn,π1=π2√nGn,c(π1,π2)2 Wn(c) and the critical value χ2 [2l−lπ],1−α,whereCnis the effective parameter space constructed from a similar MMS procedure. 4.2 Bootstrap estimation of the weighting matrix To implement the proposed test for the Simple Game, the weighing matrix needs to satisfy Assumption 4.1(iii) and (iv), which involves estimating the asymptotic covariance matrix of √n(Gnc0(π0)−Gc0(π0)). Since πnand nare obtained from plugging in estimators of the equilibrium CCPs via the eigendecomposition procedure, estimating 0 from its analytical expression can be difficult. We propose a nonparametric bootstrap estimator of 0in this section. Any π∈satisfying the system of linear equations Rπ =rcan be expressed as πf+μ,whereis a known lπ×(lπ−lR)matrix, πfis the free parameter vector of dimension lπ−lR,andμis a known lπ×1 vector. Computation of bootstrap weighting matrix Wb n(c)includes the following steps. Step 1: For any given c∈Cn,ifarg minπfGn,c(πf+μ)2is not unique, then set Wb n(c)as some known positive definite matrix WPsuch as the identify matrix. Otherwise, let πf(c)=argminπfGn,c(πf+μ)2and continue to Step 2. Step 2: Compute the bootstrap variance b nc,πf(c)=n B B  b=1G(b) n,cπf(c)+μ−Gn,cG(b) n,cπf(c)+μ−Gn,c, Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 923 A computationally feasible test statistic defined as min c∈C1 n∪···∪C|z1| n,Rπ=r√nGn,c(π)2 Wn(c) can be applied and it behaves similar to Tndefined in (5.4). 6. Monte Carlo simulation In this section, we conduct a Monte Carlo simulation study to examine the performance of our estimation and inference methods in finite samples. We use two variants of the Simple Game and two variants of the General Game in this study to illustrate the applicability of the proposed methods beyond the Simple Game and the General Game. The two variants of the Simple Game are called Game 1 and Game 2; and the two variants of the General Game are called Game 3 and Game 4, respectively. In all four games, we fully parametrize the payoff functions. Game 1 and Game 2 are games with only unobserved heterogeneity but no multiple equilibria. Game 3 and Game 4 are games with both unobserved heterogeneity and multiple equilibria. Game 1 has been introduced in Section 2.4. We use it to study the effect of the tuning parameters on running time and correct selection rate (CSR) of the MMS procedure, where the CSR is computed as the number of times that  c=c0divided by the number of repetitions. Based on the simulation result, we recommend a rule-of-thumb for choosing the tuning parameters. Game 2 adds a common observed state to the Simple Game and a strategic effect that varies with state variables. It is used as a robustness check for the effectiveness of the rule-of-thumb. We investigate the finite sample performance of the estimator and test. Game 3 and Game 4 are used to evaluate the performance of the MMS procedure together with the consistent grouping method that separate multiple equilibria from unobserved heterogeneity. All the results on the running time in this section are obtained from a computer of 2.4GHz CPU and 1TB RAM. In Game 1, we let the normalized private information ifollow a logistic distribution. The structures of Games 2–4 are presented below.21 The parameter values are provided in Supplemental Appendix D.2. Game 2 We consider a game with a common observed state variable x∈Xthat takes discrete values. Let the payoff function for player ichoosing di=1be πi(1, d−i,zi,x,k)=βikx+δikzi j=i dj, where (βik,δik)are the parameters of interest, βik characterizes the effect of x,andδikzi captures the strategic effect that varies with zi. Both effects change with k.Thenormal21Other models with similar parameters of interest include Example 1 in Kasahara and Shimotsu (2009), in which a single agent dynamic discrete choice model has two parameters that depend on a common latent state with finite support. 924 Fan, Jiang, and Shi Quantitative Economics 15 (2024) ized private information ifollows the standard normal distribution. The conditional distribution of the latent state is specified as Pr(k=A|z,x)=⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 3 4−1 10$|x|+ 3  i=1|zi|%for (z,x)=z†,x†, 0.45 for (z,x)=z†,x†, for some z†∈Zand x†∈X. The values of (z,x)are chosen so that Pr(k=A|z,x)> Pr(k=B|z,x)for all (z,x)= (z†,x†). The ranking independence assumption does not hold, because the mixing weight for latent state Ais not always strictly larger than that for latent state B. Game 3 The game has 5 players, 18 observed states, and 2 latent states. The payoff function for player iwhen choosing di=1isgivenby πi(1, d−i,zi,k)=xθk+δk 1 N−1 j=i dj, where (θk,δk)are the parameters of interest. The normalized private information ifollows the standard normal distribution. Game 4 The number of players, observed states, and latent states are the same as Game 3. We let the payoff function for player ichoosing di=1be πi(1, d−i,zi,k)=xθk+1+x2δk 1 N−1 j=i (2dj−1), where (θk,δk)are the parameters of interest. This (normalized) payoff function is a result of the following two payoff functions for di=1anddi=0, respectively: πi(1, d−i,zi,k)=xθk+1+x2δk 1 N−1 j=i (dj=1)and πi(0, d−i,zi,k)=1+x2δk 1 N−1 j=i (dj=0). The normalized private information ifollows the logistic distribution. The identification strategies for Games 2–4 are similar to the one for Game 1 in Section 2.4. We discuss the identification and minimum-distance criterion of Games 2–4 in Supplemental Appendix D.1. 6.1 Rule-of-thumb choice of tuning parameters in the MMS procedure—Game 1 Before studying the effect of the tuning parameters in the MMS procedure, we demonstrate that Assumption 2.6 holds generically. We draw values for all primitive parameters Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 925 Table 1. Effect of tuning parameters in the TMS: running time (in seconds) and correct selection rate (CSR). l1=8l1=9l1=10 l1=11 l1=12 l1=13 α1λTime CSR Time CSR Time CSR Time CSR Time CSR Time CSR 0.5% −0.27 0.0482 0.93 0.0417 0.96 0.0432 0.99 0.0598 0.99 0.0891 0.99 0.1529 0.99 −0.09 0.0876 0.93 0.0397 0.96 0.0433 0.99 0.0596 0.99 0.0894 0.99 0.1524 0.99 −0.03 0.1659 0.94 0.0762 0.96 0.0441 0.99 0.0594 0.99 0.0886 0.99 0.1524 0.99 −0.01 0.2198 0.96 0.1082 0.96 0.0445 0.99 0.0607 0.99 0.0901 0.99 0.1537 0.99 1% −0.27 0.0766 0.95 0.0666 0.96 0.0742 0.99 0.0820 0.99 0.1110 0.99 0.1764 0.99 −0.09 0.0949 0.95 0.0689 0.96 0.0704 0.99 0.0816 0.99 0.1117 0.99 0.1770 0.99 −0.03 0.1838 0.95 0.0961 0.96 0.0716 0.99 0.0817 0.99 0.1108 0.99 0.1760 0.99 −0.01 0.2417 0.97 0.1170 0.96 0.0709 0.99 0.0823 0.99 0.1110 0.99 0.1742 0.99 1.5% −0.27 0.0753 0.95 0.0948 0.96 0.0889 0.99 0.1046 0.99 0.1339 0.99 0.1993 0.99 −0.09 0.0950 0.95 0.0900 0.96 0.0885 0.99 0.1057 0.99 0.1343 0.99 0.1992 0.99 −0.03 0.1867 0.95 0.1135 0.96 0.0931 0.99 0.1047 0.99 0.1338 0.99 0.1989 0.99 −0.01 0.2442 0.97 0.1529 0.96 0.0893 0.99 0.1043 0.99 0.1334 0.99 0.1985 0.99 2.5% −0.27 0.1481 0.95 0.1369 0.96 0.1319 0.99 0.1509 0.99 0.1828 0.99 0.2514 0.99 −0.09 0.1598 0.95 0.1329 0.96 0.1323 0.99 0.1507 0.99 0.1800 0.99 0.2511 0.99 −0.03 0.2429 0.95 0.1505 0.96 0.1312 0.99 0.1504 0.99 0.1801 0.99 0.2509 0.99 −0.01 0.2992 0.97 0.1679 0.96 0.1332 0.99 0.1496 0.99 0.1790 0.99 0.2505 0.99 independently from uniform distributions whose supports cover the parameter values used in the simulation. For all the drawn parameter values, Assumption 2.6 is satisfied. We interpret this as evidence that our identification assumption holds generically in the space of model primitives. Tables 1and 2study the effect of the tuning parameters in the TMS and MMS procedures on the running time and CSR. We use random samples with 500 observations per observed state. The values in the table are based on 100 repetitions. For the design in Table 1,l=18; and for the design in Table 2,l=27. It can be seen from both Table 2. Effect of tuning parameters in the MMS: running time (in seconds) and correct selection rate (CSR). =1=2=3=4=5=6 l1α1λTime CSR Time CSR Time CSR Time CSR Time CSR Time CSR 10 0.5% −0.03 0.0457 0.99 0.0423 0.99 0.0473 0.99 0.0529 0.99 0.0592 0.99 0.0729 0.99 −0.01 0.0458 0.99 0.0428 0.99 0.0471 0.99 0.0514 0.99 0.0582 0.99 0.0727 0.99 1% −0.03 0.0531 0.99 0.0489 0.99 0.0546 0.99 0.0676 0.99 0.0821 0.99 0.1093 0.99 −0.01 0.0527 0.99 0.0500 0.99 0.0574 0.99 0.0678 0.99 0.0840 0.99 0.1084 0.99 12 0.5% −0.03 0.1555 0.99 0.1564 0.99 0.1588 0.99 0.1953 0.99 0.2312 0.99 0.2639 0.99 −0.01 0.1534 0.99 0.1585 0.99 0.1557 0.99 0.1945 0.99 0.2294 0.99 0.2618 0.99 1% −0.03 0.1771 0.99 0.1767 0.99 0.1922 0.99 0.2349 0.99 0.3078 0.99 0.3687 0.99 −0.01 0.1748 0.99 0.1817 0.99 0.1875 0.99 0.2359 0.99 0.3092 0.99 0.3575 0.99 926 Fan, Jiang, and Shi Quantitative Economics 15 (2024) tables that the tuning parameter l1plays an important role in reducing the running time and improving accuracy. As long as l1≥10 =5lπ, the accuracy is higher or equal to 0.99. As we discussed in Section 3.3, increasing α1can increase the accuracy. But the effect is marginal. At the same time, the running time increases with α1.When the accuracy is high, for example, 99%, λdoes not affect the computation time. Table 2studies the role of in the MMS on the running time and CSR. The results suggest that when the number of moments is large, a multistep procedure shall be applied. The estimator achieves a high CSR and short running time when =2. When l increases from 18 to 27, the number of elements in the parameter space Cincreases more than 500 times. However, because the novel MMS procedure is computationally very efficient, its running time only increases slightly.22 As a comparison, ( c,π)has an average running time around 3000 seconds when l=27. Even with the least desirable choice of the tuning parameters, the MMS procedure is thousands of times faster than ( c,π). Based on Tables 1and 2, we recommend the following rule-of-thumb for setting the tuning parameters: l1=5lπ,α1=0.5%, λ=−0.01, and =2. In the subsequent simulation study, we adopt this rule for all the games and designs. To provide additional insight on the computational savings of the MMS procedure, we elaborate on its intermediate steps. Computing ( c,π)requires solving a quadratic optimization problem |C|times; while calculating the MMS estimator ( c,π)involves the same optimization problem "S s=1|SCs|+|Cn|times. When l= 18, the cardinality of Cis 2l−1=131,072. On the other hand, when implementing the MMS procedure with the rule-of-thumb proposed above, we have S=4with |SC1|=512 and |SCs|=|Cn|=12 for s=2, 3, 4 based on one simulation run. As a result, ( c,π)requires only about 1/250 number of optimizations compared to ( c,π). Although SC1contains 512 subselection vectors, many are certainly incorrect. In consequence, the output of Step 1, SC1 n, contains only 3 elements. More importantly, we do not just eliminate these 512 −3=509 number of subselection vectors, but all selection vectors that share the same first 2 ×l1elements as the eliminated sub-selection vectors. In total, we eliminate 509 ×2l−l1=130,304 selection vectors after Step 1, leaving only a few selection vectors to be considered in the following steps. 6.2 The MMS procedure, estimator, and test based on the rule-of-thumb Applying the suggested rule-of-thumb for choosing the tuning parameters, we investigate the finite sample performance of the estimator and test in this section. For Game 1 and Game 2, we introduce five designs for each game corresponding to different numbers of observed states. The largest number of observed states considered in the simulation is set to be larger than the sizes of the observed states in studies such as 22The running time for l=27 can even be shorter than that for l=18 because MMS rather than TMS is used when l=27. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 927 Sweeting (2009), De Paula and Tang (2012), Grieco (2014), Igami and Yang (2016), and Xiao (2018).23 Table 3reports the running time, CSR, and mean squared error (MSE) of the MMS procedure for different sample sizes and different designs constructed from Games 1 and 2.24 For each game, different designs correspond to different values of l.nsdenotes the number of observations per observed state, and MSE reported in the table that it is calculated as the sum of MSEs of each parameter. The values in the table are computed from 1000 repetitions. Table 3shows that the running time of the MMS increases very slowly with l. When the number of elements in the parameter space C increases millions of times, for example, from l=27 to l=64 in Game 1, the running time of the MMS only increases about two times. Even when there are more than 1024 (l=81) or 1029 (l=100) matchings, the MMS takes less than one second to compute. This is consistent with Theorem 3.2, which shows that with probability approaching one, the time complexity of the MMS becomes linear in lwhen the sample size goes to infinity. The results in Table 3also show that the running time either stays the same or decreases with the sample size. We suspect that the former case occurs because the running time is already close to being linear in land has little room to improve with the sample size. When the sample size increases, the CSR increases and the MSE decreases. It would be ideal to compare the CSR and MSE of the MMS with ( c,π). However, the extremely long running time of ( c,π)makes the comparison impossible. To study the finite sample performance of our inference procedure, we focus on Design 1 of Game 1 and consider two null hypotheses of the form H0:Rπ0=rfor R=I2, r=(θ1A,δ1A);andR=(0, 1),r=δ1A. The first hypothesis is on the whole payoff parameter vector and the second one is on the parameter of strategic interaction, which is of great interest in empirical research. The number of observed states is l=18. We set the nominal size as 5% and use the 95% quantile of χ2 18 and χ2 17 as the critical values for R=I2and R=(0, 1). In both cases, the bootstrap weighting matrices are calculated with 1000 bootstrap samples. The results are based on 5000 Monte Carlo repetitions. Table 4reports the results on the null rejection probabilities for different sample sizes. The size is well controlled and is getting closer to 0.05 as the sample size increases for both hypotheses. Table 5provides the finite sample power results when the model 23In Sweeting (2009), De Paula and Tang (2012), and Xiao (2018), the major observed state is the rank of the market according to population, and there are 144 ranks in total; in Grieco (2014), the cardinality of observed states for the baseline model is 12 (3 status for discretized population, 2 status for whether it is active in 1998 and 2 status for whether there is a supercenter within 20 miles); in the static game version of Igami and Yang (2016), the cardinality of observed states is 16 (4 categories for population and 4 categories for average income). 24We also run simulations with even smaller sample sizes. The estimated parameters become less accurate, whereas the running time is still short. As a sequential estimator, our MMS estimator is affected by the well-known finite sample bias documented in papers like Aguirregabiria and Mira (2007) and Aguirregabiria and Marcoux (2021). The bias largely results from poorly estimated CCPs at small sample sizes. Although developing CCP estimators with better finite sample performance is beyond the scope of this paper, we see much value in future research in this direction. 928 Fan, Jiang, and Shi Quantitative Economics 15 (2024) Table 3. Finite sample performance of the MMS procedure in different designs: Running time (in seconds), correct selection rate (CSR), and mean squared error (MSE). Design 1: l=18 Design 2: l=27 Design 3: l=64 Design 4: l=100 Design 5: l=288 nsTime CSR MSE Time CSR MSE Time CSR MSE Time CSR MSE Time CSR MSE Game 1 250 0.0400 0.944 0.3824 0.0448 0.967 0.0886 0.1206 0.912 0.2142 0.2338 0.895 0.3373 0.4518 0.795 0.5273 500 0.0363 0.996 0.0749 0.0433 0.997 0.0181 0.0811 0.994 0.0355 0.1980 0.990 0.0323 0.4638 0.982 0.0750 750 0.0363 1 0.0159 0.0443 1 0.0121 0.0606 1 0.0046 0.1409 1 0.0030 0.3900 0.998 0.0162 1000 0.0325 1 0.0121 0.0436 1 0.0086 0.0591 1 0.0033 0.1198 1 0.0020 0.3737 1 0.0012 Design 1: l=24 Design 2: l=36 Design 3: l=54 Design 4: l=81 Design 5: l=162 nsTime CSR MSE Time CSR MSE Time CSR MSE Time CSR MSE Time CSR MSE Game 2 250 0.0368 0.933 0.7600 0.0307 0.916 1.102 0.0622 0.845 2.366 0.1992 0.761 3.286 0.4459 0.740 3.596 500 0.0388 0.996 0.0725 0.0313 0.990 0.1774 0.0652 0.980 0.3602 0.1658 0.956 0.7004 0.3557 0.956 0.7468 750 0.0224 1 0.0237 0.0324 0.998 0.0623 0.0615 0.999 0.0415 0.1102 0.991 0.1656 0.2742 0.994 0.1844 1000 0.0212 1 0.0203 0.0292 0.999 0.0205 0.0531 1 0.0144 0.0839 0.992 0.1646 0.2194 0.996 0.1422 Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 929 Table 4. Finite sample rejection probabilities under H0for different sample sizes. ns500 625 750 875 1000 1125 1250 R=I20.0336 0.0334 0.0340 0.0394 0.0430 0.0406 0.0472 R=(0, 1)0.0252 0.0262 0.0294 0.0350 0.0392 0.0386 0.0436 deviates from the null hypothesis. When the sample size is fixed, Table 5shows that as the true value deviates further from the hypothesized value, the probability of rejecting the null hypothesis increases. At the same time, for any fixed deviation, the rejection probability increases with the sample size. 6.3 Separating unobserved heterogeneity from multiple equilibria We use Games 3 and 4 to examine the performance of our estimator for the General Game. For both games, we consider two designs: in Design 1, there are 2 equilibria on latent state Afor the 8th observed state; and in Design 2, there are 2 equilibria on latent state Aforboththe8thandthe16thobservedstate.Forobservedstatesonwhich there are no multiple equilibria, we let Pr(k=A|x)=0.5. For observed states on which there are multiple equilibria, the conditional distribution for the composite latent variable ωis specified as follows: ω=1 with probability 0.4, which corresponds to latent state Aand equilibrium 1; ω=2 with probability 0.3, which corresponds to latent state Aand equilibrium 2; ω=3 with probability 0.3, which corresponds to latent state B. The results of the simulations are reported in the table below. From 100 repetitions, we document the average running time and the correct grouping rate (CGR), where the running time is the total time to run our procedures developed in Sections 5.2.1 and 5.2.2, and the CGR is probability that  S Kis equal to the correct partition. When  S Kequals to the correct partition,  K=|K|and # tπkis the average of consistent estimators of tπk 0for k=1, ,|K|. From Table 6, we see that our estimation procedure developed in Section 5.2 for the General Game is both fast to run and accurate. The CGR is very close or equal to one across different designs and increases with sample size. Table 5. Finite sample rejection probabilities under H1for different deviations and sample sizes. Dev. −0.15 −0.1 −0.05 −0.025 0.025 0.05 0.1 0.15 R=I2ns=500 0.9586 0.4704 0.0662 0.0338 0.0722 0.2004 0.7822 0.9950 ns=750 0.9996 0.8298 0.1526 0.0422 0.0892 0.3012 0.9440 0.9998 ns=1000 1 0.9608 0.2596 0.0672 0.1126 0.4228 0.9904 1 Dev. −0.2 −0.15 −0.1 −0.05 0.05 0.1 0.15 0.2 R=(0, 1)ns=500 0.8850 0.4902 0.1364 0.0330 0.1358 0.4966 0.8708 0.9440 ns=750 0.9908 0.8064 0.2806 0.0470 0.2420 0.7710 0.9870 0.9950 ns=1000 1 0.9380 0.4372 0.0666 0.3618 0.9170 0.9998 1 930 Fan, Jiang, and Shi Quantitative Economics 15 (2024) Table 6. Performance of the consistent grouping method on top of MMS: running time (in seconds) and correct grouping rate (CGR). Game 3 Game 4 Design 1 Design 2 Design 1 Design 2 nsTime CGR Time CGR Time CGR Time CGR 250 4.8851 0.99 5.0575 1 5.4538 0.96 5.9654 0.98 500 4.7580 1 5.0110 1 5.0065 0.98 5.0314 0.99 750 5.0105 1 4.6777 1 4.9731 1 5.0438 1 1000 4.7189 1 4.6639 1 4.8997 1 4.9798 1 7. Conclusion In this paper, we have proposed a computationally fast sequential method to estimate the payoff function and to conduct uniform inference in static games of incomplete information with unobserved heterogeneity and multiple equilibria. It builds on a novel characterization of the matching-types problem as a minimum-distance problem with both correct and incorrect moments. Based on this characterization, we develop a new MMS procedure that is extremely fast to implement. For inference, we construct an asymptotically uniformly valid test for linear hypotheses on the payoff function. The test is easy to implement with known critical values from the chi-squared distribution. An extensive Monte Carlo study is carried out to investigate the finite sample performance of our estimation and inference procedures. Instead of employing sequential estimators, researchers could make use of the equilibrium condition to improve the finite sample performance of structural estimators. Aguirregabiria and Mira (2007) develop a nested pseudo-likelihood algorithm that imposes the equilibrium condition iteratively while avoids solving the equilibrium condition exactly for any parameter as in nested fixed-point algorithm. In a companion paper, we aim to extend the nested pseudo-likelihood algorithm to games with both multiple equilibria and unobserved heterogeneity.25 We shall address open questions on the stability and convergence of the algorithm and to combine it with our consistent grouping method to separate multiple equilibria from unobserved heterogeneity. The MMS procedure introduced in this paper has broad applicability besides the study of games. We are currently working on its extensions to the general moment selection problems discussed in Andrews (1999). Appendix A: Additional details of the General Game In this Appendix, we provide additional details of the General Game discussed in Section 5. In Appendix A.1, we provide the expressions of πand for constructing the system of moment functions. Appendix A.2 contains the detailed procedure for estimating (ch 0,πh 0)for h=1, ,|z1|by extending the MMS procedure developed in Section 3.1 for the Simple Game. In Appendix A.3, we prove that our estimators are consistent and 25We thank an anonymous referee for suggesting this future line of research. Quantitative Economics 15 (2024) Estimate games with unobserved heterogeneity 931 fast to compute. Appendix A.4 shows that the test is asymptotically uniformly valid and consistent. A.1 Expressions of πand  For s=1, ,|z|, we define ω(s,z)as the sth value for the composite latent variable on observed state vector z. The coefficient matrices in the moment function G(π)for the General Game are π=π1z1,,π1zland =1z1,,1zl, where πhas dimension J"l t=1|zt|,has dimension J"l t=1|zt|by J(J+1)N−1,and for t=1, ,l, π1zt= ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ π11, zt,ω1, zt . . . π1J,zt,ω1, zt . . . π11, zt,ω|zt|,zt . . . π1J,zt,ω|zt|,zt ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ and 1zt=⎡ ⎢ ⎣ ι11, zt . . . ι1|zt|,zt⎤ ⎥ ⎦. For s={1, ,|zt|}, the matrix ι1(s,zt)is a block diagonal matrix with Jidentical blocks given by ι1s,zt=⎡ ⎢ ⎣ p−1zt,ωs,zt 0 ... 0p −1zt,ωs,zt⎤ ⎥ ⎦, where p−1(zt,ω(s,zt))is a row vector with (J+1)N−1elements being the probabilities of joint actions for all other players in the same spirit as the Simple Game in Section 2.2.2. A.2 MMS procedure for estimating πh 0 We focus on developing the MMS procedure for (c1 0,π1 0)to simplify our discussion and notation. Let sc denote the subselection vector of dimension J"l t=1|zt|that consists of e1 and e0. Following Definition 5.1,denotesctfor t=1, ,las the tth subvector of sc such that sc ≡[sc1,,scl]. Define Jn(sc)≡minπ∈Gn,sc(π)2. Step 0: Set l1∈{lπ,lπ+1, ,l},α1∈(0, 1],λ∈(−1, 0),and∈{1, ,l−l1}.Let S=l−l1 and α=(2|z1|−1)−. The value of αis chosen according to the same spirit as the one in the MMS procedure for the Simple Game: the more moments we add in each step, the smaller proportion of matchings we tend to keep. See Section 3.3 for more detail. Relabel {z1,,zl}such that |z|for z∈{z1,,zl}are in an ascending order. 932 Fan, Jiang, and Shi Quantitative Economics 15 (2024) Step 1: The input of Step 1 is SC1≡⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ [sc1,,scl]:sc1=[sc1,1,,sc1,|z1|]with sc1,1 =e1 and sc1,j∈{e1,e0}for j=1; for t=2, ,l1,sct=[sct,1,,sct,|zt|]with sct,w ∈{e1,e0},where w∈1, ,|zt|and sct=[e0,,e0];fort=l1+1, ,l,sct=[e0,,e0] ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭ . Sort Jn(sc1)for all sc1∈SC1, and denote Jα1 nas the value of the 100α1% smallest. The output of Step 1 is SC1 n≡sc1∈SC1:Jnsc1≤maxJα1 n,nλ. Steps2,3,...S:For s=2, ,S, define ls≡ls−1+. The input of Step sis the collection of subselection vectors defined as SCs≡⎧ ⎪ ⎨ ⎪ ⎩ [sc1,,scl]:[sc1,,scls−1]=scs−1 1,,scs−1 ls−1for some scs−1∈SCs−1 n; for t=ls−1+1, ,ls,sct=[sct,1,,sct,|zt|]with sct,w ∈{e1,e0},where w∈1, ,|zt|and sct=[e0,,e0];fort=ls+1, ,l,sct=[e0,,e0] ⎫ ⎪ ⎬ ⎪ ⎭. The output of Step sis SCs n≡scs∈SCs:Jnscs≤maxJα n,nλ. Step (S+1):The effective parameter space for c1 0is C1 n≡⎧ ⎪ ⎨ ⎪ ⎩ [c1,,cl]:[c1,,clS]=scS 1,,scS lSfor some scS∈SCS n; for t=lS+1, ,l,ct=[ct,1,,ct,|zt|]with ct,w ∈{e1,e0}, where w ∈1, ,|zt|and ct=[e0,,e0] ⎫ ⎪ ⎬ ⎪ ⎭. Given the effective parameter space, the MMS estimator for (c1 0,π1 0)is defined as  c1,π1≡arg min c∈C1 n,π∈Gn,c(π)2 Wn(c)−ρ1c0κ1,n/n. By eliminating incorrect matchings in multiple steps, the size of the effective parameter space C1 nis much smaller than that of C1. As a result, the multistep estimator ( c1,π1)is much faster to compute than ( c1,π1). We repeat the above procedure to obtain estimators ( ch,πh)for h=2, ,|z1|. A.3 Asymptotic properties of the estimators In this section, we present results on the consistency of our estimators and the time and space complexities of our MMS procedure. We provide sufficient conditions that parallel those stated in the Simple Game. The proofs for the results in this section follow the similar arguments for the results in Sections 3.2. All proofs are collected in the Supplemental Appendix. We first provide assumptions for the consistency of the proposed estimator ( ch,πh) for h=1, ,|z1|.