TL;DR
This paper revisits a comparison of two methods for estimating structural dynamic models: MPEC and NFXP. The authors demonstrate that a previously published study's conclusion of MPEC being significantly faster was due to an inefficient implementation of NFXP. Using a more efficient NFXP variant, they find the two methods are comparable in speed for small datasets, but NFXP-NK significantly outperforms MPEC for larger datasets.
What Problem Does This Paper Address?
Estimating structural dynamic models, which are crucial for understanding economic behavior and policy, often involves complex computational challenges. Two prominent approaches are:
- Mathematical Programming with Equilibrium Constraints (MPEC): This method frames the estimation problem as a constrained optimization problem. It directly incorporates the equilibrium conditions (like the Bellman equation in dynamic programming) as constraints.
- Nested Fixed Point (NFXP) Algorithm: This approach leverages the fact that the value function in a dynamic programming problem is a fixed point. It uses an iterative method to solve for this fixed point within the likelihood function evaluation.
A previous study by Su and Judd (SJ, 2012) concluded that MPEC was significantly faster than NFXP. However, this paper argues that SJ's comparison was flawed because they used an inefficient version of NFXP, relying solely on successive approximations (NFXP-SA) to solve the inner fixed-point problem. This is particularly problematic when the discount factor (a key parameter in dynamic models) is close to 1, as successive approximations become very slow. This paper aims to re-evaluate the performance comparison using a more efficient NFXP variant.
Methods
The core of this paper is a re-implementation and comparison of the MPEC and NFXP algorithms.
- NFXP-NK (Nested Fixed Point with Newton-Kantorovich): The authors employ a more efficient version of NFXP, termed NFXP-NK. This algorithm combines successive approximations (SA) with Newton-Kantorovich (NK) iterations. SA is used initially to ensure global convergence, and then NK iterations are used to achieve rapid, quadratic convergence once the algorithm is within the domain of attraction. This hybrid approach is known to be much faster and more reliable for solving fixed-point problems, especially with high discount factors.
- MPEC-AMPL: The authors use the same MPEC implementation as SJ, which utilizes the AMPL modeling language and first and second-order analytic derivatives.
- Monte Carlo Study: The authors replicate the Monte Carlo study from SJ, using the same bus engine replacement model. They compare CPU times and convergence properties of MPEC-AMPL and NFXP-NK across various discount factors and sample sizes.
Datasets
The study uses a simulated dataset based on the "optimal replacement of bus engines" model from Rust (1987). This is a standard benchmark in the literature for evaluating dynamic discrete choice estimation methods. The authors conducted Monte Carlo simulations with varying sample sizes, up to 6,000 observations in the presented table, and further experiments with sample sizes up to 1.2 million.
Key Insights and Ideas
- The Devil is in the Details (of Implementation): The paper highlights how the choice of algorithm implementation can drastically alter performance conclusions. SJ's finding of MPEC's superiority was an artifact of using an inefficient NFXP-SA.
- NFXP-NK's Robustness and Speed: The NFXP-NK algorithm, by incorporating Newton-Kantorovich iterations, achieves significantly faster convergence, especially for high discount factors, and is remarkably insensitive to the discount factor's value.
- Sample Size Matters: While MPEC and NFXP-NK are comparable for small sample sizes, NFXP-NK's advantage grows substantially with larger datasets. This suggests NFXP-NK is better suited for modern, large-scale empirical applications.
- MPEC's Computational Burden: MPEC's approach of simultaneously solving the fixed point and maximizing the likelihood leads to a high-dimensional optimization problem. This requires processing the entire dataset multiple times, making it computationally more expensive for large samples.
- NFXP's Structural Exploitation: NFXP's strength lies in its ability to exploit the specific structure of dynamic programming problems, treating the objective function as a sum of individual likelihoods. This allows for the use of standard, efficient optimization algorithms like BHHH.
Key Results
- Speed Comparison: For small sample sizes (e.g., 6,000 observations), MPEC-AMPL and NFXP-NK have comparable CPU times (around 0.07-0.08 seconds per estimation).
- Large Sample Performance: As sample size increases, NFXP-NK's speed advantage over MPEC-AMPL grows monotonically, reaching an order of magnitude difference for millions of observations.
- Discount Factor Insensitivity: NFXP-NK's performance is largely independent of the discount factor (β), whereas NFXP-SA's performance degrades significantly as β approaches 1.
- Convergence: NFXP-NK demonstrated robust convergence in all tested cases, while MPEC experienced a few convergence failures.
- Iterations: For a discount factor of 0.995, NFXP-SA required nearly 750,000 successive approximation iterations, while NFXP-NK required only about 145 iterations (including both SA and NK).
Limitations and Future Work
- Limited Model Scope: The study's conclusions are based on a single model (bus engine replacement). While the authors believe the findings are generalizable, they acknowledge that specific model characteristics could influence performance.
- MPEC Implementation: The authors note that MPEC might be more viable with better implementations, particularly for high-frequency or micro-data applications.
- Finite Horizon Models: For finite horizon problems where value functions are time-specific, MPEC might become infeasible due to memory constraints, making specialized NFXP algorithms necessary.
- Future Work: The paper implicitly suggests that further research into optimizing MPEC implementations or exploring other algorithms for large-scale dynamic model estimation would be valuable. The authors also discuss the strengths and weaknesses of both approaches in the context of practical estimation.
Summary updated