Computational considerations of multinomial probit versus binomial probit I'm using multinomial probit to estimate some parameters, and I keep seeing references to the fact that MNP was considered computationally "intractible" relative to binomial probit up until the early 21st century. The question is: why? I get that adding variables makes things take longer (I've got a background in CS), but for the life of me I can't see why estimation should be any worse than, say, $O(n^3)$ in the "nomial-ness" of the model. That is, when you add a new choice, you can update your simulations based on transformations of the joint error terms, and from there it's binomial probit with a couple indicators thrown in. Is there something deeper going on in the background that I'm not taking into consideration?
Many thanks,
Kyle
 A: It boils down to how you feel about assuming the Independence of Irrelevant Alternatives (IIA) as an assumption about choice behaviour.  So the first thing to do is look that up.
Multinomial logit assumes IIA and multinomial probit does not.  The computational price of not assuming it is what gets expensive.  Almost any econometrics text will cover the details, but assuming you already understand logistic regression, the intuitive picture is this: 
In latent variable formulation, logistic regression models need to integrate over a latent distribution to get the probability of a 1 rather than a 0. In choice modelling contexts this is thought of as the expected utility of choosing 1 rather than 0, although we only see the final (stochastic) choice.  
A similar situation arises when there are multiple choices.  If we are happy to assume IIA, that is: that a third choice does not affect your relative preferences over two existing choices, then the integrals are separable and straightforward.  If you are not happy to assume IIA (and that can be reasonable when the new choice is a plausible substitute for one of the existing ones) then you will have to estimate an arbitrary (unobserved) covariance structure over all the options and then do the multidimensional integrations to get your choice probabilities out.  It is these integrations or replacements for them that cause the computational problem.
A: The currently popular method of fitting multinomial probit models is maximum simulated likelihood using the Geweke–Hajivassiliou–Keane algorithm (Geweke 1989; Hajivassiliou and McFadden 1998; Keane and Wolpin 1994). So the algorithm dates from the late 1990s. If you've thought up a more efficient method I suggest you submit it to Econometrica.
