# Fixed-Point Approaches to Computing Bertrand-Nash Equilibrium Prices Under
Mixed-Logit Demand: A Technical Framework for Analysis and Efficient
Computational Methods.

W. Ross Morrow  Departments of Mechanical Engineering and Economics, Iowa
State University, Ames IA 50011  and  Steven J. Skerlos  Department of
Mechanical Engineering, University of Michigan, Ann Arbor MI 48104

###### Contents

  1. 1 Introduction
  2. 2 A Technical Framework
    1. 2.1 Mathematical Notation
      1. 2.1.1 Sets.
      2. 2.1.2 Symbols.
      3. 2.1.3 Differentiation.
    2. 2.2 Consumers, Products, and Choice Probabilities
    3. 2.3 Utility Specification
    4. 2.4 Profits
      1. 2.4.1 Quantity-Dependent Costs
      2. 2.4.2 Bounded and Vanishing Profits
    5. 2.5 Local Equilibrium and the Simultaneous Stationarity Conditions
    6. 2.6 Choice Probability Derivatives
    7. 2.7 The BLP-Markup Equation
    8. 2.8 The $\zeta$-Markup function
    9. 2.9 Existence of Simultaneously Stationary Prices
  3. 3 Computational Methods
    1. 3.1 Newton’s Method
    2. 3.2 Newton’s Method on the Combined Gradient
    3. 3.3 Newton’s Method and the Markup Equations
    4. 3.4 Fixed-Point Iteration
      1. 3.4.1 $\zeta$ Fixed-Point Iteration
      2. 3.4.2 $\eta$ Fixed-Point Iteration
    5. 3.5 Practical Considerations
      1. 3.5.1 Simulation
      2. 3.5.2 Truncation of Low Purchase Probability Products
      3. 3.5.3 Termination Conditions
      4. 3.5.4 Second-Order Conditions.
      5. 3.5.5 Computational Burden
    6. 3.6 Computing Jacobian Matrices for Newton’s Method
      1. 3.6.1 Jacobian of the Combined Gradient
      2. 3.6.2 The $\boldsymbol{\eta}$ map.
      3. 3.6.3 The $\boldsymbol{\zeta}$ map.
  4. 4 The GMRES-Newton Hookstep Method
    1. 4.1 Inexact Newton Methods
    2. 4.2 GMRES
      1. 4.2.1 Householder GMRES
      2. 4.2.2 Preconditioning
    3. 4.3 The GMRES Hookstep
      1. 4.3.1 Model Trust Region Methods.
      2. 4.3.2 Model Trust Region Methods on a Subspace
      3. 4.3.3 The GMRES-Newton Hookstep
      4. 4.3.4 Directional Finite Differences
  5. 5 Other Methods
    1. 5.1 Variational Methods
      1. 5.1.1 The VI formulation is poorly posed
      2. 5.1.2 General Results.
      3. 5.1.3 The Resolution of Equilibria with $\boldsymbol{\zeta}$
    2. 5.2 Tatonnement
    3. 5.3 Least-Squares Minimization and the Gauss-Newton Method
  6. 6 Acknowledgements

##  1\. Introduction

Bertrand competiton has been a prominent paradigm for the empirical study of
differentiated product markets for at least twenty years. Firms engaged in
Bertrand competition maximize profits by choosing prices for portfolios of
differentiated products, and Bertrand-Nash equilibrium prices simultaneously
maximize profits for all firms. Models combining Bertrand competition with the
Mixed Logit discrete choice model of consumer demand have been used to study
the automotive industry, electronics, entertainment, and food products and
services; see Dube et al. (2002).

Many applications of Bertrand competition rely on counterfactual experiments:
exercises in which hypothetical market conditions are simulated with an
estimated model. Such experiments have been used to study corporate mergers
(Nevo, 2000a), novel products and services (Petrin, 2002; Goolsbee and Petrin,
2004; Beresteanu and Li, 2008), store locations (Thomadsen, 2005), and
regulatory policy changes (Goldberg, 1995, 1998; Beresteanu and Li, 2008). By
definition, simulating market outcomes in counterfactual experiments requires
computing equilibrium prices after changing the values of exogenous variables
such as the number of firms or the products offered. Numerical methods for
computing equilibrium prices have not yet received a thorough treatment in the
literature, which currently focuses on model specification and estimation; see
Knittel and Metaxoglou (2008); Dube et al. (2008); Su and Judd (2008) for
recent developments in estimation. Morrow and Skerlos (2010) fills this gap
with a detailed investigation of four approaches for computing Bertrand-Nash
equilibrium prices in single-period, multi-firm models with Mixed Logit
demand. This working paper provides most of the technical background for that
investigation.

Applying Newton’s method to some form of the first-order or “simultaneous
stationarity” condition is currently the de facto approach for computing
equilibrium prices; see, for example, Nevo (1997, 2000a); Petrin (2002); Smith
(2004); Doraszelski and Draganska (2006); Jacobsen (2006). Newton’s method
applied directly to the first-order condition may converge when started at
observed prices if changes in exogenous variables have a marginal impact on
equilibrium prices. However, when the changes to exogenous variables imply
significant changes in product prices Newton’s method applied directly to the
first-order conditions may fail to compute equilibrium prices. Furthermore
analyses that do not have observed prices to use as an initial guess will
require methods with greater reliability.

Morrow and Skerlos (2010) demonstrate that solving fixed-point equations
equivalent to the first-order condition for equilibrium is more reliable and
efficient than solving the first-order condition itself. One fixed-point
equation equivalent to the first-order conditions is the BLP-markup equation
popularized by Berry et al. (1995). A second fixed-point equation, here termed
the $\boldsymbol{\zeta}$-markup equation, is a novel way to write the same
condition on markups. Both markup equations lead to more robust numerical
methods than found with a simple application of Newton’s method to the first-
order condition. Using the fixed-point expressions in this way can be
considered “nonlinearly” or “analytically” pre-conditioning the first-order
condition satisfied by equilibrium prices, a technique well-known in applied
mathematics (Brown and Saad, 1990; Cai and Keyes, 2002).

The existence of fixed-point equations for equilibrium suggests applying
fixed-point iteration (Judd, 1998) to compute equilibrium prices, instead of
Newton’s method. The BLP-markup equation does not appear to be well-suited to
fixed-point iteration. Example 7 in Morrow and Skerlos (2010) provides a case
in which iterating on the BLP-markup equation is not necessarily locally
convergent, while iterating on the $\boldsymbol{\zeta}$-markup equation is
superlinearly locally convergent. Iterating on the $\boldsymbol{\zeta}$-markup
equation also eliminates the need to solve linear systems, required to
implement Newton’s method and to iterate on the BLP-markup equation. This
property makes fixed-point steps based on the $\zeta$-markup equation very
inexpensive relative to Newton steps, an essential property to obtaining fast
computations from generally linearly convergent fixed-point iterations.

Besides Newton’s method and fixed-point iteration, few other practical
approaches to the computation of equilibrium prices exist. Variational
formulations, widely applied in economic and engineering problems (Ferris and
Pang, 1997), contain many solutions that need not be equilibria of the
original problem. Explicit least-square minimization or Gauss-Newton methods
can also be implemented, but are computational disadvantages relative to
applications of standard Newton-type methods for nonlinear systems. Some
authors apply tattonement $-$ iterating on a game’s best response
correspondence $-$ to compute equilibrium in prices or other strategic
variables including product mix (Choi et al., 1990), product characteristics
(CBO, 2003; Austin and Dinan, 2005; Bento et al., 2005), and engineering
variables (Michalek et al., 2004). Tattonement, however, has three issues: it
requires the iterative computation of profit-optimal prices (a special case of
the problem discussed in this article), should be inefficient relative to
direct methods whenever optimal strategies are coupled, and lacks the global
convergence guarantees of contemporary Newton solvers. Section 5 reviews these
conclusions in more detail.

This article should be viewed as a companion to Morrow and Skerlos (2010);
some of our notation and text may seem out of place without first reviewing
that article. In several places, text from Morrow and Skerlos (2010) is
repeated.

##  2\. A Technical Framework

This section describes the mathematical framework employed in Morrow and
Skerlos (2010). Several key assumptions are introduced and summarized in Table
1.

Table 1. List of important assumptions used in this section. Assumption | Purpose
---|---
2.1 | To provide a general form for utility functions
2.2 | To ensure profits are bounded and vanish as prices increase without bound
2.3 | To ensure the Leibniz Rule holds, validating Eqn. (9)
2.4 | To ensure that $\boldsymbol{\eta}$ is bounded. Implies the coercivity of $\mathbf{F}_{\eta},\mathbf{F}_{\zeta}$
| and the existence of simultaneously stationary prices.
2.5 | To ensure that $\boldsymbol{\zeta}$ is bounded. Implies the coercivity of $\mathbf{F}_{\zeta}$
| and the existence of simultaneously stationary prices.
3.1 | To ensure that the derivatives of profit vanish as prices increase without bound
3.2 | To ensure the coercivity of $\mathbf{F}_{\eta},\mathbf{F}_{\zeta}$ under weaker conditions than
| Assumption 2.4.

###  2.1. Mathematical Notation

####  2.1.1. Sets.

Table 2 lists some important sets and the symbols used for them. $\mathbb{N}$
denotes the natural numbers $\\{1,2,\dotsc\\}$, and $\mathbb{N}(N)$ denotes
the natural numbers up to $N$, that is, $\mathbb{N}(N)=\\{1,\dotsc,N\\}$.
$\mathbb{R}$ denotes the set of real numbers $(-\infty,\infty)$, $[0,\infty)$
denotes the non-negative real numbers, and $[0,\infty]$ denotes the extended
non-negative half-line. We denote the $(J-1)$-dimensional simplex
$\\{(x_{1},\dotsc,x_{N})\in[0,1]^{N}:\sum_{n=1}^{N}x_{n}=1\\}$ by
$\mathbb{S}(N)$, and the $J$-dimensional “pyramid”
$\\{(x_{1},\dotsc,x_{N})\in[0,1]^{N}:\sum_{n=1}^{N}x_{n}\leq 1\\}$ by
$\triangle(J)$. Hyper-rectangles in $\mathbb{R}^{N}$, i.e. sets of the form
$[a_{1},b_{1}]\times\dotsb\times[a_{N},b_{N}]$ for some
$a_{n},b_{n}\in\mathbb{R}$ with $a_{n}<b_{n}$ for all $n\in\mathbb{N}(N)$, are
denoted by $[\mathbf{a},\mathbf{b}]$ where $\mathbf{a}=(a_{1},\dotsc,a_{N})$
and $\mathbf{b}=(b_{1},\dotsc,b_{N})$. $\mathcal{P}$ always denotes the non-
negative numbers: $\mathcal{P}=[0,\infty)$. For other sets, we typically use
calligraphic upper case letters such as “$\mathcal{A}$”. For any set
$\mathcal{A}$, $\left\lvert\mathcal{A}\right\rvert$ denotes its cardinality.
For any $\mathcal{B}\subset\mathcal{A}$, $\mathcal{A}\setminus\mathcal{B}$
denotes the set $\\{b\in\mathcal{A}:b\notin\mathcal{B}\\}$.

Table 2. Important sets. Symbol | Description
---|---
$\mathbb{N}$ | $=$ | $\\{1,2,\dotsc\\}$ | Natural numbers
$\mathbb{R}$ | $=$ | $(-\infty,\infty)$ | Real numbers
$\mathcal{P}$ | $=$ | $[0,\infty)$ | Non-negative real numbers
$\mathcal{J}$ | $=$ | $\\{1,\dotsc,J\\}$ | Set of product indices
$\mathcal{X}$ | $\subset$ | $\mathbb{R}^{K}$ | Set of product characteristics
$\mathcal{T}$ | $\subset$ | $\mathbb{R}^{L}$ | Set of individual characteristics

####  2.1.2. Symbols.

Table 3 itemizes specific symbols used in the text.

Table 3. Summary of important symbols. Symbol | Description | Defined in
---|---|---
Products (see Section 2.2)
$J$ | $\in$ | $\mathbb{N}$ | number of products |
$K$ | $\in$ | $\mathbb{N}$ | number of non-price product characteristics |
$\mathbf{x}_{j}$ | $\in$ | $\mathcal{X}$ | non-price characteristics of product $j$ |
$p_{j}$ | $\in$ | $\mathcal{P}$ | price of product $j$ |
$\mathbf{p}$ | $\in$ | $\mathcal{P}^{J}$ | vector of all product prices |
Individual Characteristics (see Section 2.2)
$\boldsymbol{\theta}$ | $\in$ | $\mathcal{T}$ | individual characteristics, including observed |
|  |  | demographics and “random coefficients” |
$\mu$ | $-$ | $-$ | distribution of individual characteristics |
Choice Probabilities (see Section 2.2)
$u_{j}(\boldsymbol{\theta},p_{j})$ | $\in$ | $[-\infty,\infty)$ | utility of product $j$ |
$\vartheta(\boldsymbol{\theta})$ | $\in$ | $[-\infty,\infty)$ | utility of the outside good |
$P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})$ | $\in$ | [0,1] | Logit choice probability for product $j$ | Eqn. (1)
$P_{j}(\mathbf{p})$ | $\in$ | [0,1] | Mixed Logit choice probability for product $j$ |
$\mathbf{P}(\mathbf{p})$ | $\in$ | $[0,1]^{J}$ | vector of Mixed Logit choice probabilities for all |
|  |  | products |
Firms, Costs, Profits, and Stationarity (see Section 2.4, 2.5)
$F$ | $\in$ | $\mathbb{N}$ | number of firms |
$\mathcal{J}_{f}$ | $\subset$ | $\mathcal{J}$ | indices of the products offered by firm $f$ |
$c_{j}$ | $\in$ | $\mathcal{P}$ | (fixed) unit cost of product $j$ |
$\mathbf{c}$ | $\in$ | $\mathcal{P}^{J}$ | vector of all (fixed) unit costs |
$\hat{\pi}_{f}(\mathbf{p})$ | $\in$ | $\mathbb{R}$ | expected profits for firm $f$ | Eqn. (2)
$(D_{k}\hat{\pi}_{f})(\mathbf{p})$ | $\in$ | $\mathbb{R}$ | derivative of firm $f$’s profits, with respect to the | Eqn. (6)
|  |  | price of product $k$ |
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})$ | $\in$ | $\mathbb{R}^{J}$ | Combined Gradient of profits | Prop. 2.2, Eqn. (7)
Choice Probability Derivatives (see Sections 2.5, 2.8)
$(D_{k}P_{j})(\mathbf{p})$ | $\in$ | $\mathbb{R}$ | derivative of product $j$’s choice probability |
|  |  | with respect to the price of product $k$ |
$(\tilde{D}\mathbf{P})(\mathbf{p})$ | $\in$ | $\mathbb{R}^{J\times J}$ | “intra-firm” Jacobian matrix of the choice | Eqn. (8)
|  |  | probability vector |
$\boldsymbol{\Lambda}(\mathbf{p})$, $\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ | $\in$ | $\mathbb{R}^{J\times J}$ | matrices appearing in our decomposition of $(\tilde{D}\mathbf{P})(\mathbf{p})$ | Eqn. (9),
Fixed-Point Equations (see Sections 2.7, 2.8)
$\boldsymbol{\eta}(\mathbf{p})$ | $\in$ | $\mathbb{R}^{J}$ | the BLP-markup function (Berry et al., 1995) | Eqn. (13)
$\boldsymbol{\zeta}(\mathbf{p})$ | $\in$ | $\mathbb{R}^{J}$ | our $\boldsymbol{\zeta}$-markup function | Eqn. (18)

Bold, un-italicized symbols (e.g., “$\mathbf{x}$”) denote vectors and
matrices; typically we reserve lower case letters to refer to vectors and use
upper case letters to refer to matrices; the vector of choice probabilities
“$\mathbf{P}$” is an exception. Throughout we use $\mathbf{1}$ to denote a
vector of ones of the appropriate size for the context in which it appears.
$\mathbf{I}$ always denotes the identity matrix of a size appropriate for the
context. For any $\mathbf{x}\in\mathbb{R}^{N}$, $\mathrm{diag}(\mathbf{x})$
denotes the $N\times N$ diagonal matrix whose diagonal is $\mathbf{x}$. Any
vector inequalities between vectors are to be taken componentwise: for
example, $\mathbf{x}<\mathbf{y}$ means $x_{n}<y_{n}$ for all $n$.

Random variables are denoted with capital letters “$X$”, with random vectors
being denoted with bold capital letters (e.g., “$\mathbf{Q}$”). While this
overlaps with our notation for matrices, it should not cause any confusion.
$\mathbb{P}$ denotes a probability and $\mathbb{E}$ denotes an expectation.
$\mathrm{ess}\sup_{\mu}f$ denotes the essential supremum of the (measurable)
function $f$ over $\mathcal{T}$, with respect to the measure $\mu$; see, e.g.,
Bartle (1966).

$\log$ always denotes the natural (base $e$) logarithm. We use the “Big-O”
notation $\mathcal{O}(g)$ as follows: If there exists some $M<\infty$ such
that $\lim_{p\to q}[f(p)/g(p)]\leq M$, we say $f\in\mathcal{O}(g)$; the point
$q$ is left implicit.

####  2.1.3. Differentiation.

Our conventions for denoting differentiation follow Munkres (1991). We use the
symbol “$D$” to denote differentiation using subscripts to invoke additional
specificity. Letting $\mathbf{f}:\mathbb{R}^{M}\to\mathbb{R}^{N}$,
$(D_{m}f_{n})(\mathbf{x})$ denotes the derivative of the $n^{\text{th}}$
component function with respect to the $m^{\text{th}}$ variable and
$(D\mathbf{f})(\mathbf{x})$ is the $N\times M$ derivative matrix of
$\mathbf{f}$ at $\mathbf{x}$ with components
$((D\mathbf{f})(\mathbf{x}))_{n,m}=(D_{m}f_{n})(\mathbf{x})$. Thus for
$f:\mathbb{R}^{M}\to\mathbb{R}$, $(Df)(\mathbf{x})$ is a row vector. If
$f:\mathbb{R}^{M}\to\mathbb{R}$, we define the gradient $(\nabla
f)(\mathbf{x})\in\mathbb{R}^{M}$ as the transposed derivative: $(\nabla
f)(\mathbf{x})=(Df)(\mathbf{x})^{\top}$.

###  2.2. Consumers, Products, and Choice Probabilities

A collection of $F\in\mathbb{N}$ firms offer a total of $J\in\mathbb{N}$
products to a population of individuals (or households). Each product
$j\in\mathcal{J}=\\{1,\dotsc,J\\}$ is defined by a price,
$p_{j}\in\mathcal{P}=[0,\infty)$, and a vector of $K\in\mathbb{N}$ product
“characteristics” $\mathbf{x}_{j}\in\mathcal{X}\subset\mathbb{R}^{K}$.
Individuals are identified by a vector of characteristics
$\boldsymbol{\theta}$ from some set $\mathcal{T}$. These individual
characteristics can include both observed demographics and “random
coefficients” (Berry et al., 1995; Nevo, 2000b; Train, 2003) that characterize
unobserved individual-specific heterogeneity with respect to preference for
product characteristics. The relative density of individual characteristic
vectors in the population is described by a probability distribution $\mu$
over $\mathcal{T}$.

An individual identified by $\boldsymbol{\theta}\in\mathcal{T}$ receives the
(random) utility

$U_{j}(\boldsymbol{\theta},\mathbf{x}_{j},p_{j})=u(\boldsymbol{\theta},\mathbf{x}_{j},p_{j})+\mathcal{E}_{j}$

from purchasing product $j\in\mathcal{J}$, and

$U_{0}(\boldsymbol{\theta})=\vartheta(\boldsymbol{\theta})+\mathcal{E}_{0}$

for forgoing purchase of any of these products; i.e. “purchasing the outside
good.” Individuals choose the “product” $j\in\\{0,\dotsc,J\\}$ with maximum
utility. Here
$u:\mathcal{T}\times\mathcal{X}\times\mathcal{P}\to[-\infty,\infty)$ is a
systematic utility function, $\vartheta:\mathcal{T}\to\mathbb{R}$ is a
valuation of the no-purchase option or “outside good,” and
$\boldsymbol{\mathcal{E}}=\\{\mathcal{E}_{j}\\}_{j=0}^{J}$ is a random vector
of i.i.d. standard extreme value variables. Section 2.3 below gives a general
specification of utility functions appropriate for equilibrium pricing. The
basic requirements are that $u$ is continuously differentiable and strictly
decreasing in price, and without lower bound as prices increase.

Demand for each product $j$ is characterized by choice probabilities
$P_{j}:\mathcal{P}^{J}\to[0,1]$ derived from (random) utility maximization.
Given the distributional assumption on $\boldsymbol{\mathcal{E}}$, the choice
probabilities for an individual characterized by
$\boldsymbol{\theta}\in\mathcal{T}$ are those of the Logit model (Train, 2003,
Chapter 3):

(1)
$P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})=\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{k=1}^{J}e^{u_{k}(\boldsymbol{\theta},p_{k})}}.$

The vector $\mathbf{p}\in\mathcal{P}^{J}$ denotes the vector of all product
prices. Product-specific utility functions
$u_{j}:\mathcal{T}\times\mathcal{P}\to[-\infty,\infty)$ for all $j$, defined
by $u_{j}(\boldsymbol{\theta},p)=u(\boldsymbol{\theta},\mathbf{x}_{j},p)$ for
all $(\boldsymbol{\theta},p)\in\mathcal{T}\times\mathcal{P}$, are used in Eqn.
(1) and in the following sections. The Mixed Logit choice probabilities
$P_{j}(\mathbf{p})=\int
P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})$ follow
from integrating over the distribution of individual characteristics (Train,
2003, Chapter 6). The vector of Mixed Logit choice probabilities for all
products is denoted by $\mathbf{P}(\mathbf{p})\in[0,1]^{J}$.

The examples below review several instances of this choice model. Examples 1
and 2 are used in Morrow and Skerlos (2010). Example 3 illustrates the type
general specifications used in estimation. Example 4 describes one kind of
“simulation” of a Mixed Logit model (Train, 2003).

######  Example 1.

(Boyd and Mellman, 1980) Take $\mathcal{T}=\mathcal{P}\times\mathbb{R}^{K}$,
denoting $\boldsymbol{\theta}=(\alpha,\boldsymbol{\beta})$ for
$\alpha\in\mathcal{P}$ and $\boldsymbol{\beta}\in\mathbb{R}^{K}$. Set
$u(\alpha,\boldsymbol{\beta},\mathbf{x},p)=-\alpha
p+\boldsymbol{\beta}^{\top}\mathbf{x}$ and
$\vartheta(\alpha,\boldsymbol{\beta})=-\infty$ for all
$(\alpha,\boldsymbol{\beta})\in\mathcal{P}\times\mathbb{R}^{K}$. $\mu$ is
defined by specifying that $\alpha$ and $\boldsymbol{\beta}$ are independently
lognormally distributed (with appropriately chosen signs, means, and
variances).

######  Example 2.

(Berry et al., 1995) Take
$\mathcal{T}=\mathcal{P}\times\mathbb{R}^{K}\times\mathbb{R}$, denoting
$\boldsymbol{\theta}=(\phi,\boldsymbol{\beta},\beta_{0})$ for
$\phi\in\mathcal{P}$, $\boldsymbol{\beta}\in\mathbb{R}^{K}$, and
$\beta_{0}\in\mathbb{R}$. Set

$u(\phi,\boldsymbol{\beta},\mathbf{x},p)=\left\\{\begin{aligned}
&\alpha\log(\phi-p)+\boldsymbol{\beta}^{\top}\mathbf{x}&&\quad\text{if
}p<\phi\\\
&-\infty&&\quad\text{otherwise}\end{aligned}\right.\quad\quad\text{and}\quad\quad\vartheta(\phi,\beta_{0})=\alpha\log\phi+\beta_{0}$

for some fixed coefficient $\alpha>0$. $\phi$ represents income and is given a
lognormal distribution, while the random coefficients
$\boldsymbol{\beta},\beta_{0}$ are independently normally distributed with
some mean and variance. Note that income ($\phi$) serves as an upper bound on
the price an individual can pay for any product.

######  Example 3.

(Nevo, 2000b) Take
$\mathcal{T}=\mathcal{P}\times\mathbb{R}^{D}\times\mathbb{R}^{K+2}$, denoting
$\boldsymbol{\theta}=(\phi,\mathbf{d},\boldsymbol{\nu})$ for
$\phi\in\mathcal{P}$, $\mathbf{d}\in\mathbb{R}^{D}$, and
$\boldsymbol{\nu}\in\mathbb{R}^{K+2}$. Again, $\phi$ represents income;
$\mathbf{d}\in\mathbb{R}^{D}$ represents a vector of $D$ observed demographic
variables (which may include income); $\boldsymbol{\nu}\in\mathbb{R}^{K+2}$
represents a vector of $K+2$ random coefficients: one for each product
characteristic, one for price, and one for the outside good. Set

$\displaystyle u(\phi,\mathbf{d},\boldsymbol{\nu},\mathbf{x},p)$
$\displaystyle=(\alpha+\boldsymbol{\pi}_{p}^{\top}\mathbf{d}+\boldsymbol{\sigma}_{p}^{\top}\boldsymbol{\nu})(\phi-p)+\left(\boldsymbol{\beta}+\boldsymbol{\Pi}\mathbf{d}+\boldsymbol{\Sigma}\boldsymbol{\nu}\right)^{\top}\mathbf{x}$
$\displaystyle\vartheta(\phi,\mathbf{d},\boldsymbol{\nu})$
$\displaystyle=(\alpha+\boldsymbol{\pi}_{p}^{\top}\mathbf{d}+\boldsymbol{\sigma}_{p}^{\top}\boldsymbol{\nu})\phi+\boldsymbol{\pi}_{0}^{\top}\mathbf{d}+\boldsymbol{\sigma}_{0}^{\top}\boldsymbol{\nu}$

where $\alpha\in\mathbb{R}$, $\boldsymbol{\beta}\in\mathbb{R}^{K}$,
$\boldsymbol{\pi}_{p},\boldsymbol{\pi}_{0}\in\mathbb{R}^{D}$,
$\boldsymbol{\Pi}\in\mathbb{R}^{K\times D}$,
$\boldsymbol{\sigma}_{p},\boldsymbol{\sigma}_{0}\in\mathbb{R}^{K+2}$, and
$\boldsymbol{\Sigma}\in\mathbb{R}^{K\times(K+2)}$ are coefficients. The
distribution of $\mathbf{d}$ is estimated from available data (e.g., Census
data) and $\boldsymbol{\nu}$ is assumed to be standard independent
multivariate normal. When
$\alpha+\boldsymbol{\pi}_{p}^{\top}\mathbf{d}+\boldsymbol{\sigma}_{p}^{\top}\boldsymbol{\nu}$,
the coefficient on price, is positive, an individual prefers higher prices.

Petrin (2002) and Berry et al. (2004) adopt similar specifications that
eliminate this counterintuitive property. Petrin (2002) takes the price
component of utility to be $\alpha(\phi)\log(\phi-p)$, where
$\alpha:\mathcal{P}\to\mathcal{P}$ is a step function. Berry et al. (2004)
take the price component of utility to be $\alpha p$, but define
$\alpha=-e^{-(\alpha+\boldsymbol{\pi}_{p}^{\top}\mathbf{d}+\boldsymbol{\sigma}_{p}^{\top}\boldsymbol{\nu})}$.

######  Example 4.

(Simulation). Take any of the examples above, and draw $S\in\mathbb{N}$
vectors $\boldsymbol{\theta}_{s}\in\mathcal{T}$ according to the distribution
$\mu$. Let $\mathcal{T}^{\prime}=\\{\boldsymbol{\theta}_{s}\\}_{s=1}^{S}$ and
define a probability measure $\mu^{\prime}$ over $\mathcal{T}^{\prime}$ by
$\mu^{\prime}(\boldsymbol{\theta}_{s})=1/S$ for all $s$. Then
$(u,\vartheta,\mathcal{T}^{\prime},\mu^{\prime})$ defines a simulator of the
“full” Mixed Logit model with $(u,\vartheta,\mathcal{T},\mu)$; see Train
(2003). These approximations are essential in estimation of Mixed Logit models
and in computations of equilibrium prices.

###  2.3. Utility Specification

This section presents a generalization of the systematic utility functions
used in the examples given in the text, a specification closely related to the
one introduced by Caplin and Nalebuff (1991). Morrow (2008); Morrow and
Skerlos (2008) use a similar specification to analyze equilibrium prices in
simple Logit models.

######  Assumption 2.1.

For all $j$, there exist functions
$w_{j}:\mathcal{T}\times\mathcal{P}\to[-\infty,\infty)$ and
$v_{j}:\mathcal{T}\to(-\infty,\infty)$ such that the systematic utility
function $u_{j}:\mathcal{T}\times\mathcal{P}\to[-\infty,\infty)$ can be
written
$u_{j}(\boldsymbol{\theta},p)=w_{j}(\boldsymbol{\theta},p)+v_{j}(\boldsymbol{\theta})$.
Furthermore there exists $\varsigma:\mathcal{T}\to(0,\infty]$ such that
$w_{j}:\mathcal{T}\times[0,\infty]\to[-\infty,\infty)$ satisfies, for all $j$
and $\mu$-almost every (a.e.) $\boldsymbol{\theta}\in\mathcal{T}$,

  * (a)

$w_{j}(\boldsymbol{\theta},\cdot):(0,\varsigma(\boldsymbol{\theta}))\to[-\infty,\infty)$
is continuously differentiable, strictly decreasing, and finite

  * (b)

$w_{j}(\boldsymbol{\theta},p)=-\infty$ for all
$p\geq\varsigma(\boldsymbol{\theta})$, and

  * (c)

$w_{j}(\boldsymbol{\theta},p)\downarrow-\infty$ as
$p\uparrow\varsigma(\boldsymbol{\theta})$.

$v_{j}:\mathcal{T}\to(-\infty,\infty)$ is arbitrary.

Note that we have not restricted $\mu$, the distribution of individual
characteristics, with Assumption 2.1. Important examples of $\mu$ from the
econometrics and marketing literature include finitely supported distributions
(often empirical frequency distributions for integral observed demographic
variables), standard continuous distributions (e.g. normal, lognormal and
$\chi^{2}$), truncated standard continuous distributions, finite mixtures of
standard continuous distributions, and independent products of any of these
types of distributions. This generality allows us to address a wide variety of
otherwise disparate examples with a single notation. In particular, this
generality allows us to use a single framework to treat both “full” Mixed
Logit models defined by some $\mu$ with uncountable support and simulation-
based approximations to such models.

Some existing empirical specifications violate Assumption 2.1 by admiting
positive price coefficients for
$\boldsymbol{\theta}\in\mathcal{T}^{\prime}\subset\mathcal{T}$, where
$\mathcal{T}^{\prime}\subset\mathcal{T}$ has nonzero $\mu$-measure. See, for
example, Nevo (2000a) (Example 3) or Brownstone et al. (2000). This implies
that $w(\boldsymbol{\theta},\cdot)$ is increasing on $\mathcal{T}^{\prime}$.
If $w(\boldsymbol{\theta},\cdot)$ is not decreasing for $\mu$-a.e.
$\boldsymbol{\theta}$, or at least eventually decreasing for $\mu$-a.e.
$\boldsymbol{\theta}$ in the sense that there are always prices large enough
to ensure that $w(\boldsymbol{\theta},\cdot)$ is decreasing for $\mu$-a.e.
$\boldsymbol{\theta}$, then profit-optimal pricing is not a well-posed problem
and finite equilibrium prices will not exist.

The variable $\Sigma=\varsigma(\boldsymbol{\theta})$ represents an individual-
specific reservation price. As in the Berry et al. (1995) model of Example 2,
this reservation price is most often derived from household or individual
income. Correspondingly, $\Sigma$ is often given a lognormal distribution to
(roughly) fit empirical income data. In principle, this reservation price
could be related to purchasing power derived from observed demographic
variables other than income, or unobserved demographic variables such as
family wealth. Thus we allow this reservation price to be specified as a
function of all “demographic” characteristics, $\boldsymbol{\theta}$.
Conditions (b) and (c) in Assumption 2.1 imply that the probability an
individual characterized by $\boldsymbol{\theta}$ will purchase a product is
zero for any price above $\varsigma(\boldsymbol{\theta})$ and vanishes as the
price approaches $\varsigma(\boldsymbol{\theta})$. We set
$\varsigma_{*}=\mathrm{ess}\sup\varsigma$ and allow, but do not require,
$\varsigma_{*}=\infty$. For example, simulation-based approximations to the
Berry et al. demand model have $\varsigma_{*}<\infty$, as can be easily
checked.

Note also that Condition (c) in Assumption 2.1 ensures the continuity of
$P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})$ at any vector of prices with some
component equal to $\varsigma(\boldsymbol{\theta})$. We must require this of
the Logit choice probabilities to obtain Mixed Logit choice probabilities that
are continuous on $(0,\varsigma_{*})^{J}$ for the important class of
simulation-based approximations with finitely supported $\mu$. Continuous
Logit choice probabilities also imply continuous Mixed Logit choice
probabilities, by the Dominated Convergence Theorem.

###  2.4. Profits

To describe the optimal pricing problems faced by each firm we use the
following notation. Let $F\in\mathbb{N}$ denote the number of firms. For each
$f\in\\{1,\dotsc,F\\}$, there exists a set $\mathcal{J}_{f}\subset\mathcal{J}$
of indices that corresponds to the
$J_{f}=\left\lvert\mathcal{J}_{f}\right\rvert$ products offered by firm $f$.
The collection of all these sets, $\\{\mathcal{J}_{f}\\}_{f=1}^{F}$, forms a
partition of $\mathcal{J}$. Subsequently, in writing “$f(j)$” for some
$j\in\mathcal{J}$, we mean the unique $f\in\\{1,\dotsc,F\\}$ such that
$j\in\mathcal{J}_{f}$. The vector $\mathbf{p}_{f}\in\mathbb{R}^{J_{f}}$ refers
to the vector of prices of the products offered by firm $f$. Negative
subscripts denote competitor’s variables as in, for instance,
$\mathbf{p}_{-f}\in\mathbb{R}^{J_{-f}}$, where $J_{-f}=\sum_{g\neq f}J_{g}$,
is the vector of prices for products offered by all of firm $f$’s competitors.
Firm-specific choice probability functions are denoted by
$\mathbf{P}_{f}(\mathbf{p})\in\mathbb{R}^{J_{f}}$.

Two additional assumptions are required to complete the definition of firms’
profits in a manner consistent with empirical applications of Bertrand
competition. First, we must specify unit and fixed costs: for each product $j$
there exists a unit cost $c_{j}\in\mathcal{P}$ and for each firm there exists
a fixed cost $c_{f}^{F}\in\mathcal{P}$. Both $c_{j}$ and $c_{f}^{F}$ depend
only on the collection of product characteristics chosen by the firm, and not
on the quantity sold by the firm during the purchasing period for the reasons
discussed below. We let $\mathbf{c}_{f}\in\mathcal{P}^{J_{f}}$ denote the
vector of unit costs for the products offered by firm $f$, and
$\mathbf{c}\in\mathcal{P}^{J}$ denote the vector of unit costs for all
products.

Second, Bertrand competition entails the following “comittment” assumption on
the quantities produced (Baye and Kovenock, 2008). Let $Q_{j}(\mathbf{p})$
denote the (random) quantity of product $j$ that the population will demand
during the purchasing period, given prices for all products $\mathbf{p}$.
These random demands are derived from random utility maximization. We assume
each firm commits to producing exactly $Q_{j}(\mathbf{p})$ units of each
product $j\in\mathcal{J}_{f}$ during the purchasing period. This implies
either that there are no production capacity constraints that limit a firm’s
ability to meet any demands that arise during the purchase period, or that
production backlogs do not affect demand.

With the commitment and constant costs assumptions, the total cost firm $f$
incurs in producing (and selling) $Q_{j}(\mathbf{p})$ units of product $j$
during the purchasing period are given by the random variable

$\sum_{j\in\mathcal{J}_{f}}c_{j}Q_{j}(\mathbf{p})+c_{f}^{F}.$

Random revenues are, of course, given by
$\sum_{j\in\mathcal{J}_{f}}Q_{j}(\mathbf{p})p_{j}$. The random variable

$\Pi_{f}(\mathbf{p})=\sum_{j\in\mathcal{J}_{f}}Q_{j}(\mathbf{p})(p_{j}-c_{j})-c_{f}^{F}$

then gives firm $f$’s (random) profits for the purchasing period as a function
of all product prices. Following most of the theoretical and empirical
literature in both marketing and economics, we assume that firms take expected
profits,

(2)
$\mathbb{E}[\Pi_{f}(\mathbf{p})]=I\hat{\pi}_{f}(\mathbf{p})-c_{f}^{F}\quad\text{where}\quad\hat{\pi}_{f}(\mathbf{p})=\sum_{j\in\mathcal{J}_{f}}P_{j}(\mathbf{p})(p_{j}-c_{j})$

as the metric by which they optimize their pricing decisions in this
stochastic optimization problem. Here $I\in\mathbb{N}$ denotes the number of
individuals in the population.

Eqn. (2) demonstrates that neither the total firm fixed costs $c_{f}^{F}$ nor
the population size $I$ play a role in determining the prices that maximize
expected profits under the assumptions described above. Henceforth we focus on
the “population-normalized gross expected profits”
$\hat{\pi}_{f}(\mathbf{p})$, referred to in the text and below as simply
“profits”. Firms thus solve

(3) maximize
$\displaystyle\quad\hat{\pi}_{f}(\mathbf{p})=\sum_{j\in\mathcal{J}_{f}}P_{j}(\mathbf{p})(p_{j}-c_{j})$
$\displaystyle\mathrm{with\;respect\;to}$
$\displaystyle\quad\mathbf{p}_{f}\in\mathcal{P}^{J_{f}}$

Before continuing with our framework, we discuss quantity-dependent costs and
clarify when profits are bounded.

####  2.4.1. Quantity-Dependent Costs

Including costs that depend on quantities produced is certainly possible,
though this should introduce extra terms into the first-order equations
presented below (Eqn. (7)). Generally speaking, unit costs that depend on the
quantity produced would be expressed as $c_{j}:\mathbb{Z}_{+}\to\mathcal{P}$,
and unit costs that depended on the expected quantity produced would be
expressed as $c_{j}:\mathcal{P}\to\mathcal{P}$. If unit costs depend on the
quantity produced, then product $j$’s unit costs for the purchasing period (i)
are random and (ii) depend on prices. To see this, simply note that product
$j$’s unit costs for the purchasing period are $c_{j}(Q_{j}(\mathbf{p}))$.
Assuming quantity-dependent costs also obscures expected profits, since there
are now nonlinear terms $Q_{j}(\mathbf{p})c_{j}(Q_{j}(\mathbf{p}))$ in the
formula for random profits. If unit costs depend only on the expected quantity
produced, then unit costs are not random but still depend on prices:
$c_{j}(\mathbb{E}[Q_{j}(\mathbf{p})])=c_{j}(IP_{j}(\mathbf{p}))$. In either
case the derivatives of unit costs with respect to prices should appear in the
first-order conditions. This is acknowledged in the theoretical literature. As
these terms have not yet been included in the empirical literature, even when
costs are assumed to depend on quantities produced (Berry et al., 1995;
Petrin, 2002), we focus on costs that are independent of the quantity
produced.

####  2.4.2. Bounded and Vanishing Profits

Here we present a technical assumption that ensures that profits are not only
bounded, but vanish as all prices approach $\varsigma_{*}$.

######  Assumption 2.2.

For all $j$ there exists some $r_{j}:\mathcal{T}\to(1,\infty)$ and some
$\bar{p}_{j}:\mathcal{T}\to\mathcal{P}$ satisfying

(4)
$\sup\Big{\\{}\;p\mu(\\{\boldsymbol{\theta}:\bar{p}(\boldsymbol{\theta})>p\\})\;:\;p\in(0,\varsigma_{*})\;\Big{\\}}<\infty.$

such that

(5) $u_{j}(\boldsymbol{\theta},p)\leq-r_{j}(\boldsymbol{\theta})\log
p+\vartheta(\boldsymbol{\theta})$

for all $p\geq\bar{p}_{j}(\boldsymbol{\theta})$, $\mu$-a.e.

######  Lemma 2.1.

If Assumption 2.2 holds, then $\hat{\pi}_{f}(\mathbf{p})$ is bounded in
$\mathbf{p}$ and vanishes as
$\mathbf{p}_{f}\to\varsigma_{*}\mathbf{1}\in\mathbb{R}^{J_{f}}$.

###### Proof.

We use the Dominated Convergence Theorem. Eqn. (5) ensures that
$p_{j}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})$ vanishes $\mu$-a.e. as
$p_{j}\uparrow\varsigma_{*}$; see also Morrow and Skerlos (2008). Eqn. (4)
ensures that

$\hat{\pi}_{f}(\mathbf{p})=\sum_{j\in\mathcal{J}_{f}}\int
p_{j}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})-\sum_{j\in\mathcal{J}_{f}}c_{j}\int
P_{j}(\mathbf{p})$

is bounded as prices approach $\varsigma_{*}$, as we now show.

The key quantities in this integral are

$\int
p_{j}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})\leq\int
p_{j}\left(\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)d\mu(\boldsymbol{\theta});$

the $c_{j}P_{j}(\mathbf{p})$ terms vanish if $p_{j}\uparrow\varsigma_{*}$
since $P_{j}(\mathbf{p})$ vanishes. We must show that these terms are bounded
as $p_{j}\uparrow\varsigma_{*}$. By assumption,

$p_{j}\left(\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)\leq\left(\frac{1}{p_{j}}\right)^{r_{j}(\boldsymbol{\theta})-1}\left(\frac{1}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)$

for all $p_{j}\geq\bar{p}_{j}(\boldsymbol{\theta})$. Thus we write

$\displaystyle\int
p_{j}\left(\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)d\mu(\boldsymbol{\theta})$
$\displaystyle=\int_{\\{\boldsymbol{\theta}:p_{j}<\bar{p}_{j}(\boldsymbol{\theta})\\}}p_{j}\left(\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)d\mu(\boldsymbol{\theta})$
$\displaystyle\quad\quad\quad\quad\quad\quad+\int_{\\{\boldsymbol{\theta}:p_{j}\geq\bar{p}_{j}(\boldsymbol{\theta})\\}}p_{j}\left(\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}{1+e^{u_{j}(\boldsymbol{\theta},p_{j})-\vartheta(\boldsymbol{\theta})}}\right)d\mu(\boldsymbol{\theta})$
$\displaystyle\leq
p_{j}\mu{\\{\boldsymbol{\theta}:p_{j}<\bar{p}_{j}(\boldsymbol{\theta})\\}}$
$\displaystyle\quad\quad\quad\quad\quad\quad+\int_{\\{\boldsymbol{\theta}:p_{j}\geq\bar{p}_{j}(\boldsymbol{\theta})\\}}\left(\frac{1}{p_{j}}\right)^{r_{j}(\boldsymbol{\theta})-1}d\mu(\boldsymbol{\theta}).$

By Eqn. (4), the first term is bounded. We take $p_{j}>1$, without loss of
generality, so that $1/p^{r_{j}(\boldsymbol{\theta})-1}\leq 1$ for $\mu$-a.e.
$\boldsymbol{\theta}$ and the second term is bounded. ∎

We now make some remarks regarding Assumption 2.2.

Note that if $\varsigma(\boldsymbol{\theta})<\infty$ then Eqn. (5) holds for
any $r(\boldsymbol{\theta})>1$ by taking
$\bar{p}(\boldsymbol{\theta})=\varsigma(\boldsymbol{\theta})$. If
$\varsigma(\boldsymbol{\theta})=\infty$, Eqn. (5) admits any utility function
$u(\boldsymbol{\theta},\cdot)$ that is (eventually) concave in price.

If $\varsigma_{*}<\infty$, then $\varsigma(\boldsymbol{\theta})<\infty$ for
$\mu$-a.e. $\boldsymbol{\theta}$. Furthermore, Eqn. (4) is trivial.

To further analyze Eqn. (4), we assume $\varsigma_{*}=\infty$. We define
$Z=\bar{p}(\boldsymbol{\Theta})$, where $\boldsymbol{\Theta}$ is the
$\mathcal{T}$-valued random variable with
$\mathbb{P}(\boldsymbol{\Theta}\in\mathcal{A})=\mu(\mathcal{A})=\int_{\mathcal{A}}d\mu(\boldsymbol{\theta})$.
If $\varsigma(\boldsymbol{\theta})<\infty$ for $\mu$-a.e.
$\boldsymbol{\theta}$, then we can take
$Z=\Sigma=\varsigma(\boldsymbol{\Theta})$. Eqn. (4) can be re-written as
$\sup\\{p\mathbb{P}(Z>p):p\in(0,\infty)\\}<\infty$, or equivalently
$\lim_{p\to\infty}[p\mathbb{P}(Z>p)]<\infty$. Eqn. (4) admits any $Z$ with
finite expectation, and even admits any $Z$ with a “fat-tailed” distribution
satisfying $p^{1+\beta}\mathbb{P}(Z>p)\to 1$ as $p\to\infty$ for some
$\beta>0$. Eqn. (4) can be written $\mathbb{P}(Z>p)=\mathcal{O}(1/p)$.

###  2.5. Local Equilibrium and the Simultaneous Stationarity Conditions

Assuming that the choice probabilities are continuously differentiable in
prices, at equilibrium each firm’s prices satisfy the stationarity condition

(6)
$(D_{k}\hat{\pi}_{f})(\mathbf{p})=\sum_{j\in\mathcal{J}_{f}}(D_{k}P_{j})(\mathbf{p})(p_{j}-c_{j})+P_{k}(\mathbf{p})\quad\quad\text{for
all }k\in\mathcal{J}_{f}.$

Combining the stationarity condition for each firm we obtain the Simultaneous
Stationarity Condition, a first-order (necessary) condition for local
equilibrium prices.

######  Proposition 2.2 (Simultaneous Stationarity Condition).

Suppose $\mathbf{P}$ is continuously differentiable. Let
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})\in\mathbb{R}^{J}$ denote the “combined
gradient” with components
$((\tilde{\nabla}\hat{\pi})(\mathbf{p}))_{j}=(D_{j}\hat{\pi}_{f(j)})(\mathbf{p})$
where $f(j)$ denotes the index of the firm offering product $j$. If
$\mathbf{p}$ is a local equilibrium, then

(7)
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})=(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}(\mathbf{p}-\mathbf{c})+\mathbf{P}(\mathbf{p})=\mathbf{0}.$

where $(\tilde{D}\mathbf{P})(\mathbf{p})\in\mathbb{R}^{J\times J}$ is the
“intra-firm” Jacobian matrix of price derivatives of the choice probabilities
defined by

(8)
$\big{(}(\tilde{D}\mathbf{P})(\mathbf{p})\big{)}_{j,k}=\left\\{\begin{aligned}
&(D_{k}P_{j})(\mathbf{p})&&\quad\text{if products $j$ and $k$ are offered by
the same firm }\\\ &\quad\quad 0&&\quad\text{otherwise }\end{aligned}\right.$

Prices $\mathbf{p}$ satisfying Eqn. (7) are called “simultaneously
stationary.”

The matrix $-(\tilde{D}\mathbf{P})(\mathbf{p})$ has previously been denoted by
“$\triangle$” (Berry et al., 1995; Petrin, 2002; Beresteanu and Li, 2008),
“$\boldsymbol{\Omega}$” (Nevo, 2000a), and “$\boldsymbol{\Phi}$” (Dube et al.,
2002). We prefer the “$D$” notation to emphasize the relationship of
$(\tilde{D}\mathbf{P})(\mathbf{p})$ to the Jacobian matrix of the choice
probabilities $\mathbf{P}$, while using the superscript “$\sim$” to denote the
intra-firm sparsity structure.

A set of simultaneously stationary prices are a local equilibrium only if
every firm’s profits are locally maximized at those prices; this can be
verified by confirming that every firm’s profits are locally concave (Section
LABEL:SUBSECSufficiency). Note that there is no convenient condition to verify
that every firm’s profits are globally maximized at a particular local
equilibrium. That is, there is no convenient condition to ensure that certain
prices are a proper equilibrium.

###  2.6. Choice Probability Derivatives

In this section we examine the price derivatives of Mixed Logit choice
probabilities. In what follows, $(Dw_{j})(p_{j})$ denotes the derivative of
the price component of utility, $w_{j}$, with respect to price.

######  Proposition 2.3.

Fix $\mathbf{p}\in(0,\varsigma_{*})^{J}$, let $u_{j}$ be given as in
Assumption 2.1 for all $j$, and suppose the Leibniz Rule holds for the Mixed
Logit choice probabilities $P_{j}(\mathbf{p})=\int
P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})$; that is,
$(D_{k}P_{j})(\mathbf{p})=\int(D_{j}P_{k}^{L})(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})$.
Then the Jacobian matrix of $\mathbf{P}$ is given by

(9)
$(D\mathbf{P})(\mathbf{p})=\boldsymbol{\Lambda}(\mathbf{p})-\boldsymbol{\Gamma}(\mathbf{p})$

where $\boldsymbol{\Lambda}(\mathbf{p})\in\mathbb{R}^{J\times J}$ is the
diagonal matrix with diagonal entries

$\lambda_{j}(\mathbf{p})=\int_{\mathcal{L}(p_{j})}(Dw_{j})(\boldsymbol{\theta},p_{j})P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta}),\quad\quad\mathcal{L}(p)=\\{\boldsymbol{\theta}:\varsigma(\boldsymbol{\theta})>p\\}$

and $\boldsymbol{\Gamma}(\mathbf{p})$ is the full $J\times J$ matrix with
entries

$\gamma_{j,k}(\mathbf{p})=\int_{\mathcal{G}(p_{j},p_{k})}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{k})(\boldsymbol{\theta},p_{k})d\mu(\boldsymbol{\theta}),\quad\quad\mathcal{G}(p,q)=\mathcal{L}(p)\cap\mathcal{L}(q).$

The intra-firm price derivatives of the Mixed Logit choice probabilities are
given by
$(\tilde{D}\mathbf{P})(\mathbf{p})=\boldsymbol{\Lambda}(\mathbf{p})-\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$
where
$\big{(}\tilde{\boldsymbol{\Gamma}}(\mathbf{p})\big{)}_{j,k}=\gamma_{j,k}(\mathbf{p})$
if $f(j)=f(k)$ and
$\big{(}\tilde{\boldsymbol{\Gamma}}(\mathbf{p})\big{)}_{j,k}=0$ otherwise.

###### Proof.

We first characterize the Logit choice probabilities. For all $j,k$ we have

$\displaystyle(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})$
$\displaystyle=P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})(\delta_{j,k}-P_{k}^{L}(\boldsymbol{\theta},\mathbf{p}))(Dw_{k})(\boldsymbol{\theta},p_{k})$
$\displaystyle=\delta_{j,k}P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{k})(\boldsymbol{\theta},p_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{k})(\boldsymbol{\theta},p_{k})$

for any $\boldsymbol{\theta}\in\mathcal{L}(p_{k})$ and
$(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})=0$ for any
$\boldsymbol{\theta}\in\\{\boldsymbol{\theta}^{\prime}\in\mathcal{T}:p_{k}>\varsigma(\boldsymbol{\theta}^{\prime})\\}$
(because $P_{j}^{L}(\boldsymbol{\theta},\cdot)$ is identically zero in a
neighborhood of $\mathbf{p}$). Neglecting values
$\boldsymbol{\theta}\in\varsigma^{-1}(p_{k})$ for the moment, we observe that
these formulae and the Leibniz rule generate the desired expression for the
Mixed Logit choice probabilities.

We complete the proof by considering
$\boldsymbol{\theta}\in\varsigma^{-1}(p_{k})$. If $\varsigma^{-1}(p_{k})$ has
$\mu$-measure zero for any $p_{k}$, then we do not need to worry about Logit
choice probability derivatives at
$\boldsymbol{\theta}\in\varsigma^{-1}(p_{k})$. On the other hand if
$\varsigma^{-1}(p_{k})$ has positive $\mu$-measure for some $p_{k}$, we must
assume continuity of the Logit choice probability derivatives: i.e.
$(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})\to 0$ as
$p_{k}\uparrow\varsigma(\boldsymbol{\theta})$. Otherwise, the Logit choice
probability derivative is not defined on a set of demographics with positive
measure. ∎

$\boldsymbol{\lambda}$ is closely related to a familiar economic quantity.
Recall that the “inclusive value,” or expected maximum utility, conditional on
demographics is given by (Small and Rosen, 1981; Train, 2003)

$\iota^{L}(\boldsymbol{\theta},\mathbf{p})=\log\left(e^{\vartheta(\boldsymbol{\theta})}+\sum_{j=1}^{J}e^{u_{j}(\boldsymbol{\theta},p_{j})}\right)$

It is easy to see that $\lambda_{k}$ is the derivative of the “aggregate
inclusive value”
$\iota(\mathbf{p})=\int\iota^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})$
with respect to the $k^{\text{th}}$ price:
$\lambda_{k}(\mathbf{p})=(D_{k}\iota)(\mathbf{p})=\int(D_{k}\iota^{L})(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})$.

Note that $\boldsymbol{\Gamma}(\mathbf{p})$ and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ are not necessarily symmetric for
all $\mathbf{p}$. If $(Dw_{k})(\boldsymbol{\theta},p)$ is independent of both
$k$ and $p$, as in the case of the Boyd and Mellman (1980) model presented in
Example 1 above, then $\boldsymbol{\Gamma}(\mathbf{p})$ (and thus
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$) is symmetric for all $\mathbf{p}$.
On the other hand if $(Dw_{k})(\boldsymbol{\theta},\cdot)$ is independent of
$k$ and strictly monotone in $p$, as is the case of the strictly concave in
price utility from Berry et al. (1995), then
$\gamma_{j,k}(\mathbf{p})=\gamma_{k,j}(\mathbf{p})$ if and only if
$p_{j}=p_{k}$.

The following assumption gives a simple, abstract condition on
$(\mathbf{u},\vartheta,\mu)$ that guarantees the Leibniz Rule holds and
defines continuously differentiable choice probabilities.

######  Assumption 2.3.

Let $k$ be arbitrary and define
$\psi_{k}:\mathcal{T}\times\mathcal{P}\to\mathcal{P}$ by

$\psi_{k}(\boldsymbol{\theta},p)=\left\\{\begin{aligned}
&\left\lvert(Dw_{k})(\boldsymbol{\theta},p)\right\rvert\left(\frac{e^{u_{k}(\boldsymbol{\theta},p)}}{e^{\vartheta(\boldsymbol{\theta})}+e^{u_{k}(\boldsymbol{\theta},p)}}\right)&&\quad\text{if
}p<\varsigma(\boldsymbol{\theta})\\\ &\quad\quad\quad\quad\quad
0&&\quad\text{if }p\geq\varsigma(\boldsymbol{\theta})\\\ \end{aligned}\right.$

Assume (i)
$\psi_{k}(\boldsymbol{\theta},\cdot):(0,\varsigma_{*})\to\mathcal{P}$ is
continuous for $\mu$-a.e. $\boldsymbol{\theta}\in\mathcal{T}$; that is,
$\psi_{k}(\boldsymbol{\theta},q)\to\psi_{k}(\boldsymbol{\theta},p)$ as $q\to
p$ for any $p\in(0,\varsigma_{*})$. (ii)
$\psi_{k}(\cdot,p^{\prime}):\mathcal{T}\to\mathcal{P}$ is uniformly
$\mu$-integrable for all $p^{\prime}$ in some neighborhood of any
$p\in(0,\varsigma_{*})$; that is, there exists some
$\varphi:\mathcal{T}\to[0,\infty)$ with
$\int\varphi(\boldsymbol{\theta})d\mu(\boldsymbol{\theta})<\infty$ (that may
depend on $k$ and $p$), such that
$\psi_{k}(\boldsymbol{\theta},p^{\prime})\leq\varphi(\boldsymbol{\theta})$ for
all $p^{\prime}$ in some neighborhood of $p$.

Note that under Assumption 2.1, (i) requires only that
$\psi_{k}(\boldsymbol{\theta},p)\to 0$ as
$p\uparrow\varsigma(\boldsymbol{\theta})$ for $\mu$-a.e.
$\boldsymbol{\theta}$.

######  Proposition 2.4.

If Assumption 2.3 holds, then the Leibniz Rule holds for the Mixed Logit
choice probabilities which are also continuously differentiable on
$(0,\varsigma_{*})^{J}$.

###### Proof.

Taking for granted that $(D_{k}P_{j}^{L})(\boldsymbol{\theta},\cdot)$ is
continuous at $\mathbf{p}$ and the differences

(10)
$h^{-1}\big{(}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}$

are uniformly $\mu$-integrable for small enough $h$, the Dominated Convergence
Theorem implies that

$\displaystyle\lim_{h\to 0}h^{-1}\Big{(}\int
P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})d\mu(\boldsymbol{\theta})-\int
P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta})\Big{)}$
$\displaystyle\quad\quad\quad\quad=\lim_{h\to 0}\int
h^{-1}\big{(}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}d\mu(\boldsymbol{\theta})$
$\displaystyle\quad\quad\quad\quad=\int\lim_{h\to
0}h^{-1}\big{(}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}d\mu(\boldsymbol{\theta})$
$\displaystyle\quad\quad\quad\quad=\int(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta}).$

This validates the Leibniz Rule. This proof is essentially that given in a
general setting by (Bartle, 1966, Chapter 5, pg. 46).

To complete the proof we must validate that
$(D_{k}P_{j}^{L})(\boldsymbol{\theta},\cdot)$ is continuous in $p_{k}$ and the
differences in Eqn. (10) are uniformly $\mu$-integrable in a neighborhood of
$p_{k}$. It is easy to see that the desired continuity follows from Assumption
2.1 and Assumption 2.3, Condition (i). Specifically, note that
$(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})=0=\psi_{k}(\boldsymbol{\theta},p_{k})$
for
$\boldsymbol{\theta}\in\\{\boldsymbol{\theta}^{\prime}\in\mathcal{T}:p_{k}>\varsigma(\boldsymbol{\theta}^{\prime})\\}$
and

$\displaystyle(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})$
$\displaystyle=\big{(}\delta_{j,k}-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{k})(\boldsymbol{\theta},p_{k})$
$\displaystyle=\big{(}\delta_{j,k}-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}\left(\frac{e^{\vartheta(\boldsymbol{\theta})}+e^{u_{k}(\boldsymbol{\theta},p_{k})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{i=1}^{J}e^{u_{i}(\boldsymbol{\theta},p_{i})}}\right)\left(\frac{e^{u_{k}(\boldsymbol{\theta},p_{k})}}{e^{\vartheta(\boldsymbol{\theta})}+e^{u_{k}(\boldsymbol{\theta},p_{k})}}\right)(Dw_{k})(\boldsymbol{\theta},p_{k})$
$\displaystyle=\big{(}\delta_{j,k}-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}\left(\frac{e^{\vartheta(\boldsymbol{\theta})}+e^{u_{k}(\boldsymbol{\theta},p_{k})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{i=1}^{J}e^{u_{i}(\boldsymbol{\theta},p_{i})}}\right)\psi_{k}(\boldsymbol{\theta},p_{k})$

for $\boldsymbol{\theta}\in\mathcal{L}(p_{k})$. Suppose
$p_{k}=\varsigma(\boldsymbol{\theta})$. By Assumption 2.1 (a) and (b), the
first two terms are continuous. By Assumption 2.1 (c),

$\displaystyle\lim_{\mathbf{q}\to\mathbf{p},q_{k}<\varsigma(\boldsymbol{\theta})}(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})$
$\displaystyle=\left(\delta_{j,k}-\frac{e^{u_{j}(\boldsymbol{\theta},p_{j})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{i\neq
k}e^{u_{i}(\boldsymbol{\theta},p_{i})}}\right)\left(\frac{e^{\vartheta(\boldsymbol{\theta})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{i\neq
k}e^{u_{i}(\boldsymbol{\theta},p_{i})}}\right)\lim_{q_{k}\uparrow\varsigma(\boldsymbol{\theta})}\psi_{k}(\boldsymbol{\theta},q_{k})$

Assumption 2.3, Condition (i) is then necessary for the continuity of
$(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})$ for all $j,k$ and
$\mathbf{p}\in(\mathbf{0},\varsigma_{*}\mathbf{1})$. Specifically if
$\psi_{k}(\boldsymbol{\theta},\cdot)$ is discontinuous at
$\varsigma(\boldsymbol{\theta})$, then

$\displaystyle\lim_{\mathbf{q}\to\mathbf{p},q_{k}<\varsigma(\boldsymbol{\theta})}(D_{k}P_{k}^{L})(\boldsymbol{\theta},\mathbf{p})$
$\displaystyle=\left(\frac{e^{\vartheta(\boldsymbol{\theta})}}{e^{\vartheta(\boldsymbol{\theta})}+\sum_{i\neq
k}e^{u_{i}(\boldsymbol{\theta},p_{i})}}\right)\lim_{q_{k}\uparrow\varsigma(\boldsymbol{\theta})}\psi_{k}(\boldsymbol{\theta},q_{k})$

To prove the integrability, we first note that for all $j,k$ and $\mathbf{p}$
we have
$\left\lvert(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})\right\rvert\leq\psi_{k}(\boldsymbol{\theta},p_{k})$.
This bound is a consequence of the formula above, and is tight as
$\mathbf{p}_{-k}$ varies. The mean value theorem for functions of a single
real variable states that

$\displaystyle
h^{-1}(P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}))=(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p}+\eta\mathbf{e}_{k})$

for some $\eta$ such that $\left\lvert\eta\right\rvert<\left\lvert
h\right\rvert$, and thus

$\displaystyle\left\lvert h\right\rvert^{-1}\left\lvert
P_{j}^{L}(\boldsymbol{\theta},\mathbf{p}+h\mathbf{e}_{k})-P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\right\rvert\leq\psi_{k}(\boldsymbol{\theta},p_{k}+\eta)\leq\varphi(\boldsymbol{\theta})$

for $\mu$-a.e. $\boldsymbol{\theta}\in\mathcal{T}$ and small enough $h$. Thus,
the desired uniform $\mu$-integrability follows from Assumption 2.3, Condition
(ii). ∎

An “easier” bound is simply
$\left\lvert(D_{k}P_{j}^{L})(\boldsymbol{\theta},\mathbf{p})\right\rvert\leq\left\lvert(Dw_{k})(\boldsymbol{\theta},p_{k})\right\rvert$,
and thus we might consider changing the statement of Proposition 2.4 to
hypothesize only the uniform $\mu$-integrability of the utility price
derivatives. In fact, this bound can be used to validate the Leibniz Rule for
the Boyd and Mellman model of Example 1 that lacks an outside good. However,
this bound fails to be useful for the Berry et al. model of Example 2, since
$w(p)=\alpha\log(\varsigma(\boldsymbol{\theta})-p)$ and
$\left\lvert(Dw_{k})(\boldsymbol{\theta},p_{k})\right\rvert=\alpha/(\varsigma(\boldsymbol{\theta})-p)$
is singular on $\varsigma^{-1}(p)$. In empirical applications, $\varsigma$ is
onto, generating a singularity somewhere in $\mathcal{T}$ for all $p$; this
singularity cannot be “controlled” for all $p$ by choosing the measure $\mu$.
In this case, a hypothesis only about the price derivatives of utility is not
useful.

We close this section by stating some basic results concerning
$(\tilde{D}\mathbf{P})(\mathbf{p})$ that are used below.

######  Lemma 2.5.

Under Assumption 2.1, $P_{j}(\mathbf{p})$ and $\lambda_{j}(\mathbf{p})$ are
never zero on $(0,\varsigma_{*})^{J}$. Thus $\boldsymbol{\Lambda}(\mathbf{p})$
is nonsingular for all $\mathbf{p}\in(0,\varsigma_{*})^{J}$.

###### Proof.

Note that $\mathcal{L}(p_{j})$ is nonempty and has positive $\mu$-measure,
$P_{j}^{L}(\cdot,\mathbf{p})$ is strictly positive on $\mathcal{L}(p_{j})$,
and $(Dw_{j})(\cdot,p_{j})P_{j}^{L}(\cdot,\mathbf{p})$ is strictly negative on
$\mathcal{L}(p_{j})$. It follows that $P_{j}(\mathbf{p})$ and
$\lambda_{j}(\mathbf{p})$ are nonzero. ∎

######  Lemma 2.6.

Let $\mathbf{p}\in(0,\varsigma_{*})^{J}$, suppose
$\vartheta:\mathcal{T}\to(-\infty,\infty)$, and define

(11) $\displaystyle\boldsymbol{\Omega}_{f}(\mathbf{p})$
$\displaystyle=\boldsymbol{\Lambda}_{f}(\mathbf{p})^{-1}\boldsymbol{\Gamma}_{f}(\mathbf{p})^{\top}\in\mathbb{R}^{J_{f}\times
J_{f}}\text{ for all }f$ (12)
$\displaystyle\tilde{\boldsymbol{\Omega}}(\mathbf{p})$
$\displaystyle=\boldsymbol{\Lambda}(\mathbf{p})^{-1}\tilde{\boldsymbol{\Gamma}}(\mathbf{p})^{\top}\in\mathbb{R}^{J\times
J}.$

These matrices are well-defined by Lemma 2.5, and have the following
properties:

  * (i)

$(D_{f}\mathbf{P}_{f})(\mathbf{p})^{\top}=\boldsymbol{\Lambda}_{f}(\mathbf{p})(\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p}))$
and
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}=\boldsymbol{\Lambda}(\mathbf{p})(\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p}))$.

  * (ii)

$\lvert\lvert\boldsymbol{\Omega}_{f}(\mathbf{p})\rvert\rvert_{\infty}<1$ and
$\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}<1$.

  * (iii)

$\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p})\in\mathbb{R}^{J_{f}\times
J_{f}}$ and
$\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})\in\mathbb{R}^{J\times J}$
are strictly diagonally dominant and nonsingular.

  * (iv)

$(\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p}))^{-1}\in\mathbb{R}^{J_{f}\times
J_{f}}$ and
$(\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p}))^{-1}\in\mathbb{R}^{J\times
J}$ map positive vectors to positive vectors.

###### Proof.

  * (i)

This follows immediately from Prop. 2.3.

  * (ii)

We note that

$\displaystyle\omega_{k,l}(\mathbf{p})=\frac{\gamma_{l,k}(\mathbf{p})}{\lambda_{k}(\mathbf{p})}=\int_{\mathcal{L}(p_{k})}P_{l}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})$

where $\mu_{k,\mathbf{p}}$ is the probability distribution with density, with
respect to $\mu$, given by

$d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})=\frac{P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})\left\lvert(Dw_{k})(\boldsymbol{\theta},p_{k})\right\rvert
d\mu(\boldsymbol{\theta})}{\int_{\mathcal{L}(p_{k})}P_{k}^{L}(\boldsymbol{\phi},\mathbf{p})\left\lvert(Dw_{k})(\boldsymbol{\phi},p_{k})\right\rvert
d\mu(\boldsymbol{\phi})}.$

Thus
$\boldsymbol{\Lambda}_{f}(\mathbf{p})^{-1}\boldsymbol{\Gamma}_{f}(\mathbf{p})^{\top}$
has row sums

$\displaystyle\int\left(\sum_{j\in\mathcal{J}_{f}}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\right)d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})<1.$

The additional assumption that $\vartheta:\mathcal{T}\to(-\infty,\infty)$
plays a role in establishing this inequality because then there is always a
set $\mathcal{T}_{k}^{\prime}\subset\mathcal{T}$ with
$\mu_{k,\mathbf{p}}(\mathcal{T}_{k}^{\prime})>0$ on which
$\sum_{j\in\mathcal{J}_{f}}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})<1$.

  * (iii)

The inequality

$\displaystyle
1>\int\left(\sum_{j\in\mathcal{J}_{f}}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\right)d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})$

is equivalent to

$\displaystyle\left\lvert 1-\omega_{k,k}(\mathbf{p})\right\rvert$
$\displaystyle=1-\int
P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})$
$\displaystyle>\int\left(\sum_{j\in\mathcal{J}_{f}\setminus
k}P_{j}^{L}(\boldsymbol{\theta},\mathbf{p})\right)d\mu_{k,\mathbf{p}}(\boldsymbol{\theta})=\sum_{l\neq
k}\omega_{k,l}(\mathbf{p}).$

The claim follows.

  * (iii)

Because $\boldsymbol{\Omega}_{f}(\mathbf{p})$ maps positive vectors to
positive vectors, so does its power series

$\sum_{n=1}^{\infty}\boldsymbol{\Omega}_{f}(\mathbf{p})^{n}=(\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p}))^{-1}.$

∎

######  Corollary 2.7.

$(D_{f}\mathbf{P}_{f})(\mathbf{p})^{\top}$ and
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}$ are strictly diagonally dominant
and nonsingular for $\mathbf{p}\in(\mathbf{0},\varsigma_{*}\mathbf{1})$.

###### Proof.

This follows directly from Lemma 2.6, claims (i) and (iii). ∎

###  2.7. The BLP-Markup Equation

A prominent form of the first-order conditions Eqn. (7) is the BLP-markup
equation:

(13)
$\mathbf{p}=\mathbf{c}+\boldsymbol{\eta}(\mathbf{p})\quad\text{where}\quad\boldsymbol{\eta}(\mathbf{p})=-(\tilde{D}\mathbf{P})(\mathbf{p})^{-\top}\mathbf{P}(\mathbf{p}).$

Note that $\boldsymbol{\eta}$ is defined for any continuously differentiable
choice probabilities with nonsingular
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}$. We have shown above that this
applies to certain Mixed Logit models (Section 2.6). Eqn. (13) and Corollary
2.7 show that $\boldsymbol{\eta}$ is well-defined and continuous, at least for
$\mathbf{p}\in(0,\varsigma_{*})^{J}$.

Traditionally, the BLP-markup equation (13) has been used to estimate costs
assuming observed prices are in equilibrium via the formula
$\mathbf{c}=\mathbf{p}-\boldsymbol{\eta}(\mathbf{p})$; see, e.g., Berry et al.
(1995) or Nevo (2000a). These cost estimates form the basis of counterfactual
experiments with an estimated demand model. Beresteanu and Li (2008) have
recently suggested that the BLP-markup equation is also useful for computing
equilibrium prices, a suggestion we explore further below. Note that the BLP-
markup equation must be interpreted as a nonlinear fixed-point equation when
applied to compute equilibrium prices.

We now derive several important properties of $\boldsymbol{\eta}$ from an
alternative form of Eqn. (13) based on Lemma 2.6, valid when
$\mathbf{p}\in(0,\varsigma_{*})^{J}$:

(14)
$\Big{(}\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})\Big{)}\boldsymbol{\eta}(\mathbf{p})=-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p}).$

First, Eqn. (14) proves that profit-optimal markups are positive for the class
of Mixed Logit models we consider, thanks to Lemma 2.6, claim (iv).

######  Corollary 2.8.

Suppose Assumptions 2.1-2.3 hold. Then
$\boldsymbol{\eta}(\mathbf{p})>\mathbf{0}$ for all
$\mathbf{p}\in(0,\varsigma_{*})^{J}$. Hence if
$\mathbf{p}\in(0,\varsigma_{*})^{J}$ is a local equilibrium, then
$\mathbf{p}>\mathbf{c}$.

Second, Eqn. (14), rather than Eqn. (13), should be used to actually compute
$\boldsymbol{\eta}$. Recall that $\kappa_{2}(\mathbf{A})$ denotes the 2-norm
condition number of the matrix $\mathbf{A}$ (Trefethen and Bau, 1997).

######  Lemma 2.9.

Suppose Assumptions 2.1-2.3 hold. Eqn. (14) is better conditioned than Eqn.
(13), in the sense that

$\kappa_{2}\big{(}\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})\big{)}\leq\left(\frac{\min_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}{\max_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}\right)\kappa_{2}\big{(}(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}\big{)}$

for all $\mathbf{p}\in(\mathbf{0},\varsigma_{*}\mathbf{1})$.

###### Proof.

This follows from Lemma 2.6, claim (i), the inequality
$\kappa_{2}(\mathbf{AB})\leq\kappa_{2}(\mathbf{A})\kappa_{2}(\mathbf{B})$
valid for any matrices $\mathbf{A}$ and $\mathbf{B}$, and the formula

$\kappa_{2}(\boldsymbol{\Lambda}(\mathbf{p})^{-1})=\frac{\min_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}{\max_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}.$

∎

Lemma 2.9 states that the greater the variation in aggregate absolute rate of
change in inclusive values, the more poorly conditioned
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}$ is relative to
$\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})$. Because
$\boldsymbol{\Lambda}(\mathbf{p})$ is diagonal,
$\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})\rvert\rvert_{1}=\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})\rvert\rvert_{2}=\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})\rvert\rvert_{\infty}$
and thus the same bound applies for condition numbers in norms other than the
2-norm.

Third, Eqn. (14) also provides bounds on the magnitude of values taken by
$\boldsymbol{\eta}$:

######  Lemma 2.10.

Suppose Assumptions 2.1-2.3 hold. For all
$\mathbf{p}\in(0,\varsigma_{*})^{J}$, $\boldsymbol{\eta}$ satisfies

(15)
$\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{1+\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}}\leq\lvert\lvert\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}\leq\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{1-\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}}.$

###### Proof.

This follows immediately from Eqn. (14), using the triangle inequality. ∎

The upper bound suggests the following assumptions to ensure that
$\boldsymbol{\eta}$ itself is bounded:

######  Assumption 2.4.

Suppose there exist $M\in(0,\infty)$ and $\varepsilon\in(0,1)$ such that

(16)
$\displaystyle\sup\big{\\{}\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}\;:\;\mathbf{p}\in(0,\varsigma_{*})^{J}\big{\\}}$
$\displaystyle=M<\infty$ (17)
$\displaystyle\sup\big{\\{}\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}\;:\;\mathbf{p}\in(0,\varsigma_{*})^{J}\big{\\}}$
$\displaystyle=1-\varepsilon<1.$

Under simple Logit,
$P_{k}^{L}(\mathbf{p})/\left\lvert\lambda_{k}(\mathbf{p})\right\rvert=\left\lvert(Dw_{k})(p_{k})\right\rvert^{-1}$
and
$\boldsymbol{\Omega}_{f}(\mathbf{p})=\mathbf{1}\mathbf{P}_{f}^{L}(\mathbf{p})^{\top}$.
Thus Eqn. (16) is akin to concavity of $w_{k}$ for all sufficiently large
$p_{k}$, and Eqn. (17) is implied by $\vartheta>-\infty$, i.e. the existence
of an outside good with positive purchase probability.

######  Lemma 2.11.

Suppose Assumptions 2.1-2.3 hold.

  * (i)

If Assumption 2.4 also holds,
$N=\sup\\{\lvert\lvert\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}:\mathbf{p}\in(0,\varsigma_{*})^{J}\\}<\infty$.

  * (ii)

Moreover Eqn. (16) in Assumption 2.4 is necessary for $N$ to be finite.

Unfortunately some simple models do not satisfy Assumption 2.4. A simple Logit
model with $w(p)=-\alpha\log p$ for some $\alpha>0$ violates Eqn. (16). More
generally, the Boyd and Mellman (1980) model of Example 1 does not satisfy
Eqn. (16). This is most easily seen by noting that finite-sample
approximations to this model have

$\lim_{p_{k}\to\infty}\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}=\max_{s=1,\dotsc,S}\left\\{\frac{1}{\alpha_{s}}\right\\}$

where $\\{\alpha_{s}\\}_{s=1}^{S}$ are the sampled price coefficients. Of
course, as $S\to\infty$, $\min_{s=1,\dotsc,S}\\{\alpha_{s}\\}\to 0$, and thus
$\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}\to\infty$.

###  2.8. The $\zeta$-Markup function

Substituting Eqn. (9) into Eqn. (7) yields the $\boldsymbol{\zeta}$-markup
equation introduced in Morrow and Skerlos (2010):

(18)
$\mathbf{p}=\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})\quad\text{where}\quad\boldsymbol{\zeta}(\mathbf{p})=\boldsymbol{\Lambda}(\mathbf{p})^{-1}\tilde{\boldsymbol{\Gamma}}(\mathbf{p})^{\top}(\mathbf{p}-\mathbf{c})-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})$

when $\boldsymbol{\Lambda}(\mathbf{p})$ is nonsingular (Section 2.6, 2.8).
Thus the $\boldsymbol{\zeta}$-markup equation is specific to Mixed Logit
models, unlike the BLP-markup equation.

We observe a relationship between the maps $\boldsymbol{\zeta}$ and
$\boldsymbol{\eta}$.

######  Proposition 2.12.

Suppose Assumption 2.1-2.3 hold. For any $\mathbf{p}\in(0,\varsigma_{*})^{J}$,
$\boldsymbol{\zeta}(\mathbf{p})=\tilde{\boldsymbol{\Omega}}(\mathbf{p})(\mathbf{p}-\mathbf{c})+(\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p}))\boldsymbol{\eta}(\mathbf{p})$.

###### Proof.

This follows directly from Eqns. (14) and (18). ∎

In so far as $\boldsymbol{\eta}$ and $\boldsymbol{\zeta}$ are distinct maps,
they can generate numerical methods for the computation of equilibrium prices
with entirely different properties. The equation above implies that
$\boldsymbol{\zeta}(\mathbf{p})=\boldsymbol{\eta}(\mathbf{p})$ if, and only
if,
$\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})=\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})$
lies in the null space of $\tilde{\boldsymbol{\Omega}}(\mathbf{p})$. Thus if
$\tilde{\boldsymbol{\Omega}}(\mathbf{p})$ is full-rank, $\boldsymbol{\zeta}$
and $\boldsymbol{\eta}$ coincide only at simultaneously stationary prices.
Simple examples of Mixed Logit models can be constructed that always have
$\mathrm{rank}(\tilde{\boldsymbol{\Omega}}(\mathbf{p}))=J$. For Logit,
$\boldsymbol{\Omega}_{f}(\mathbf{p})=\mathbf{1}\mathbf{P}_{f}^{L}(\mathbf{p})^{\top}$
for all $f$ and $\tilde{\boldsymbol{\Omega}}(\mathbf{p})$ always has rank
$F\leq J$. However the analysis in Morrow and Skerlos (2008) can be used to
show that $\boldsymbol{\zeta}$ and $\boldsymbol{\eta}$ coincide only at
simultaneously stationary prices.

We now explore $\boldsymbol{\zeta}$’s asymptotic properties.

######  Lemma 2.13.

Under Assumption 2.4
$\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}<\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}$
whenever
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}>M/\varepsilon$.
Moreover
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\to\infty$
as $\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}\to\infty$.

###### Proof.

We simply note that

$\displaystyle\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}$
$\displaystyle\leq\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}+\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}$
$\displaystyle\leq(1-\varepsilon)\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}+M$
$\displaystyle\leq\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-\big{(}\varepsilon\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-M\big{)}$
$\displaystyle\leq\left[1-\varepsilon+\frac{M}{\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}}\right]\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}$

Now if $\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}>M/\varepsilon$,
then $M/\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}<\varepsilon$.
Thus

$\displaystyle\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}<\left[1-\varepsilon+\varepsilon\right]\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}=\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}.$

To prove that
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\to\infty$,
note that

$\displaystyle\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\geq\left(\varepsilon-\frac{M}{\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}}\right)\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}$

For all
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}>M/\varepsilon$, the
term in parentheses is positive. Furthermore, this term approaches
$\varepsilon$ as
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}\to\infty$. Thus
$\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\to\infty$
as $\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}\to\infty$. ∎

A slightly different assumption concerning
$\tilde{\boldsymbol{\Omega}}(\mathbf{p})$ is useful when analyzing the
$\boldsymbol{\zeta}$ map.

######  Assumption 2.5.

Suppose

(19)
$\sup\Big{\\{}\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})(\mathbf{p}-\mathbf{c})\rvert\rvert_{\infty}:\mathbf{p}\in(0,\varsigma_{*})^{J}\Big{\\}}<\infty,$

######  Lemma 2.14.

Suppose Assumption 2.1-2.3 holds and $\varsigma_{*}=\infty$. Then
$\boldsymbol{\zeta}$ is bounded if, and only if, Eqn. (16) and Eqn. (19) hold.

###### Proof.

This follows directly from the triangle inequality and the non-negativity of
$\tilde{\boldsymbol{\Omega}}(\mathbf{p})(\mathbf{p}-\mathbf{c})$ and
$-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})$ for all
$\mathbf{p}\geq\mathbf{c}$. ∎

For future reference, we prove that Eqn. (19) strengthens Eqn. (17).

######  Lemma 2.15.

If Eqn. (19) holds, then Eqn. (17) holds.

###### Proof.

Note that Eqn. (19) implies that for any $k$,

$\lim_{p_{j}\to\infty}\big{(}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})\big{)}<\infty\quad\text{for
all}\quad j\in\mathcal{J}_{f(k)}.$

This, in turn, implies that $\omega_{k,j}(\mathbf{p})\to 0$ as
$p_{j}\to\infty$.

Now Eqn. (17) fails only if
$\lim_{\mathbf{p}\to\mathbf{q}}\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}=1$
where $\mathbf{q}$ has some $q_{j}=\infty$. But the row sums of
$\tilde{\boldsymbol{\Omega}}(\mathbf{p})$ satisfy

$\lim_{\mathbf{p}\to\mathbf{q}}\left[\sum_{j\in\mathcal{J}_{f(k)}}\omega_{k,j}(\mathbf{p})\right]=\sum_{j\in\mathcal{J}_{f(k)}\cup\\{j:q_{j}<\infty\\}}\omega_{k,j}(\mathbf{q})<1.$

Thus if Eqn. (19) holds, Eqn. (17) cannot fail. ∎

###  2.9. Existence of Simultaneously Stationary Prices

This section provides two existence results. Neither establish the existence
of a local equilibrium, or the uniqueness of simultaneously stationary points.
To address the existence of local equilibrium will require additional
conditions to ensure that each firm’s profits are locally concave at the
simultaneously stationary prices whose existence can be ensured (Morrow,
2008). Little is known about how to address the uniqueness of simultaneously
stationary points. Indeed, Morrow and Skerlos (2010) provide an example of a
Mixed Logit model with 9 simultaneously stationary prices, 4 of which are
local equilibria and 2 of which are proper equilibria.

Assumption 2.4 ensures the existence of finite simultaneously stationary
prices when $\varsigma_{*}=\infty$.

######  Corollary 2.16.

Suppose $\varsigma_{*}=\infty$ and Assumptions 2.1-2.3, 2.4 hold. Then there
exists at least one vector of finite simultaneously stationary prices.

###### Proof.

This is a direct consequence of Brouwer’s fixed-point theorem.
$\mathbf{c}+\boldsymbol{\eta}(\cdot)$ is a continuous map that takes the
compact, convex set $[0,M/\varepsilon]^{J}$ into itself, and thus there is at
least one fixed-point
$\mathbf{p}=\mathbf{c}+\boldsymbol{\eta}(\mathbf{p})\in[0,M/\varepsilon]^{J}$.
∎

To apply Corollary 2.16 to cases when $\varsigma_{*}<\infty$,
$\boldsymbol{\eta}$ must be extended from $(0,\varsigma_{*})$ to all of
$\mathcal{P}^{J}$ preserving the bounds (15). This is easy for many of the
simulation-based approximations encountered in practice, but difficult for the
general case.

We can extend this existence result using Eqn. (22) and the
$\boldsymbol{\zeta}$ map.

######  Lemma 2.17.

Suppose $\varsigma_{*}=\infty$, Assumptions 2.1-2.3, Eqn. (19), and Eqn. (22)
hold. Then there exists some $\bar{q}_{k}>c_{k}$ such that
$p_{k}-c_{k}-\zeta_{k}(\mathbf{p})>0$ for all $\mathbf{p}$ with
$p_{k}\geq\bar{q}_{k}$.

###### Proof.

The assumed bound implies

$\left\lvert\sum_{j\in\mathcal{J}_{f}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})\right\rvert\leq
L<\infty$

for any $k$ and any $\mathbf{p}\in(0,\infty)^{J}$. Consider

$\displaystyle p_{k}-c_{k}-\zeta_{k}(\mathbf{p})$
$\displaystyle=(p_{k}-c_{k})-\sum_{j\in\mathcal{J}_{f}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})+\frac{P_{k}(\mathbf{p})}{\lambda_{k}(\mathbf{p})}$
$\displaystyle=\left(1-\frac{P_{k}(\mathbf{p})}{\left\lvert\lambda_{k}(\mathbf{p})\right\rvert(p_{k}-c_{k})}\right)(p_{k}-c_{k})-\sum_{j\in\mathcal{J}_{f}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})$

If Eqn. (22) holds, then

$0\leq\lim_{p_{k}\to\infty}\left[\frac{P_{k}(\mathbf{p})}{\left\lvert\lambda_{k}(\mathbf{p})\right\rvert(p_{k}-c_{k})}\right]\leq\delta<1.$

Thus for any $\epsilon>0$, there exists some $\bar{p}_{k}>0$ and
$\triangle(\mathbf{p})$ with
$\left\lvert\triangle(\mathbf{p})\right\rvert<\epsilon$ such that

$\frac{P_{k}(\mathbf{p})}{\lambda_{k}(\mathbf{p})(p_{k}-c_{k})}\leq\delta+\triangle(\mathbf{p})\quad\quad\text{for
all}\quad\quad p_{k}>\bar{p}_{k}.$

Thus

$\displaystyle
p_{k}-c_{k}-\zeta_{k}(\mathbf{p})\geq(1-\delta+\triangle(\mathbf{p}))(p_{k}-c_{k})-L\quad\quad\text{for
all}\quad\quad p_{k}>\bar{p}_{k}.$

In particular, if we choose $\epsilon\leq(1-\delta)/2$ we have

$\displaystyle
p_{k}-c_{k}-\zeta_{k}(\mathbf{p})\geq\left(\frac{1-\delta}{2}\right)(p_{k}-c_{k})-L=\left(\frac{1-\delta}{2}\right)\left(p_{k}-c_{k}-\frac{2L}{1-\delta}\right)>0$

for all $p_{k}\geq\bar{q}_{k}=\max\\{c_{k}+2L/(1-\delta),\bar{p}_{k}\\}$. ∎

One consequence of this lemma is that infinite prices are never an
equilibrium.

######  Corollary 2.18.

Under the assumptions of Lemma 2.17, any profit derivative is eventually
negative.

###### Proof.

Note that

$(D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=-\left\lvert\lambda_{k}(\mathbf{p})\right\rvert(p_{k}-c_{k}-\zeta_{k}(\mathbf{p})).$

Since $p_{k}-c_{k}-\zeta_{k}(\mathbf{p})$ is positive for all large enough
$p_{k}$, $(D_{k}\hat{\pi}_{f(k)})(\mathbf{p})$ is negative for all large
enough $p_{k}$, regardless of $\mathbf{p}_{-k}$. ∎

Another consequence of Lemma 2.17 is an alternative existence result.

######  Corollary 2.19.

Under the assumptions of Lemma 2.17 there exists at least one simultaneously
stationary point.

###### Proof.

Following Morrow and Skerlos (2008), we prove this proposition using the
Poincare-Hopf Theorem (Milnor, 1965). The logic is simple: We will consider
the vector field $\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})$ on a
hyper-rectangle $[\mathbf{c},\bar{\mathbf{q}}]$ whose critical points are
simultaneously stationary; $\bar{\mathbf{q}}$ has components $\bar{q}_{k}$
defined in Lemma 2.17. The Poincare-Hopf Theorem then states that the sum of
the indices of all the critical points of this vector field equals one, the
Euler characteristic of $[\mathbf{c},\bar{\mathbf{q}}]$. Thus it is not
possible that the vector field have no critical points, for then the sum of
indices would be zero.

We must only prove one property of
$\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})$: that this vector field
points outward on the boundary of the chosen hyper-rectangle. Half of this
proof is Lemma 2.17, in which we prove that
$p_{k}-c_{k}-\zeta_{k}(\mathbf{p})>0$ if
$\mathbf{p}\in[\mathbf{c},\bar{\mathbf{q}}]$ with $p_{k}=\bar{q}_{k}$. We must
also show that $p_{k}-c_{k}-\zeta_{k}(\mathbf{p})<0$ if
$\mathbf{p}\in[\mathbf{c},\bar{\mathbf{q}}]$ with $p_{k}=c_{k}$. But

$\displaystyle
c_{k}-c_{k}-\zeta_{k}(\mathbf{p})=-\left(\sum_{j\in\mathcal{J}_{f}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})+\frac{P_{k}(\mathbf{p})}{\left\lvert\lambda_{k}(\mathbf{p})\right\rvert}\right)<0.$

∎

This proof does not need to make any claims about the number of critical
points, or of their indices. If it can be shown that any critical point of
$\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})$ cannot have a zero or
negative index, then the simultaneously stationary point is unique.

##  3\. Computational Methods

This section provides details for the four approaches to computing equilibrium
prices described in Morrow and Skerlos (2010); see Table 4. Section 3.1
briefly reviews Newton’s method, followed by application of Newton’s method to
solve Eqn. (7) in Section 3.2. Newton’s method applied directly to Eqn. (7)
may compute “spurious” solutions with infinite prices because the combined
gradient vanishes as prices increase without bound. Section 3.3 avoids this
difficulty by applying Newton’s method to the two markup equations instead of
Eqn. (7) itself. Section 3.4 discusses fixed-point iterations based on the
BLP- and $\boldsymbol{\zeta}$-markup equations, and Section 3.5 reviews a
number of practical considerations.

Table 4. Summary of the numerical methods examined in this article. Newton
Methods (NM)
---
Abbr. | Method | Section | Advantage | Our Experience${}^{\text{(a)}}$
CG-NM | Solve $\mathbf{F}_{\pi}(\mathbf{p})=(\tilde{\nabla}\hat{\pi})(\mathbf{p})=\mathbf{0}$ | 3.2 | $-$ | Unreliable, slow
$\boldsymbol{\eta}$-NM | Solve $\mathbf{F}_{\eta}(\mathbf{p})=\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})=\mathbf{0}$ | 3.3 | Coercive | Reliable, slow
$\boldsymbol{\zeta}$-NM | Solve $\mathbf{F}_{\zeta}(\mathbf{p})=\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})=\mathbf{0}$ | 3.3 | Coercive | Reliable, slow
Fixed-Point Iterations (FPI)
Abbr. | Method | Section | Advantage | Our Experience
$\boldsymbol{\zeta}$-FPI | Iterate $\mathbf{p}\leftarrow\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})$ | 3.4 | Easy to evaluate | Reliable, fast
$\boldsymbol{\eta}$-FPI | Iterate $\mathbf{p}\leftarrow\mathbf{c}+\boldsymbol{\eta}(\mathbf{p})$ | 3.4 | $-$ | Not convergent
(a) Conclusions on behavior of these methods is based on the numerical
experiments
described in Morrow and Skerlos (2010), using a novel GMRES-Newton method with
Levenberg-Marquardt style trust-region global convergence strategy.

###  3.1. Newton’s Method

Newton’s method, a classical technique to compute a zero of an arbitrary
function $\mathbf{F}:\mathbb{R}^{J}\to\mathbb{R}^{J}$, is now a portfolio of
related approaches to solve nonlinear systems (Ortega and Rheinboldt, 1970;
Kelley, 1995; Dennis and Schnabel, 1996; Judd, 1998; Kelley, 2003). Generally
speaking, Newton-type methods are differentiated in two relatively independent
directions: (i) the technique used to approximate the Jacobian matrices
$(D\mathbf{F})$ and solve for the Newton step and (ii) the technique used to
enforce convergence from arbitrary initial conditions. See Dennis and Schnabel
(1996), Judd (1998), or Kelley (2003) for good treatments of these issues.
Choosing the right variant of Newton’s method determines the reliability and
efficiency of equilibrium price computations.

Problem formulation also determines the reliability and efficiency of
equilibrium price computations using Newton’s method. Scalings of the
variables and function values are one prominent example of a problem
transformation that improves the performance of Newton’s method (Dennis and
Schnabel, 1996). Nonlinear problem preconditioning can also be important (Cai
and Keyes, 2002), as the following example demonstrates.

######  Example 5.

Let $\mathbf{F}:\mathbb{R}^{N}\to\mathbb{R}^{N}$ be defined by
$\mathbf{F}(\mathbf{x})=\mathbf{x}/(1+\lvert\lvert\mathbf{x}\rvert\rvert_{2}^{2})$.
Iterating Newton steps converges to the unique (finite) zero
$\mathbf{x}_{*}=\mathbf{0}$ only from initial conditions $\mathbf{x}_{0}$ with
$\lvert\lvert\mathbf{x}_{0}\rvert\rvert_{2}<1/\sqrt{3}$. Newton’s method
diverges or fails for all other starting points. Standard global convergence
strategies for Newton’s method (line search, trust region methods) cannot
improve this poor global convergence behavior because
$\lvert\lvert\mathbf{F}(\mathbf{x})\rvert\rvert_{2}$ has unbounded level sets;
see Morrow and Skerlos (2010) for details.

A simple nonlinear transformation overcomes this poor global convergence
behavior. Note that
$\mathbf{F}(\mathbf{x})=\mathbf{A}(\mathbf{x})\mathbf{f}(\mathbf{x})$ where
$\mathbf{A}(\mathbf{x})=(1+\lvert\lvert\mathbf{x}\rvert\rvert_{2}^{2})^{-1}\mathbf{I}$
and $\mathbf{f}(\mathbf{x})=\mathbf{x}$. Because $\mathbf{A}(\mathbf{x})$ is
nonsingular for all $\mathbf{x}$, the problems
$\mathbf{F}(\mathbf{x})=\mathbf{0}$ and $\mathbf{f}(\mathbf{x})=\mathbf{0}$
have identical solution sets. However applying Newton’s method to the problem
$\mathbf{f}(\mathbf{x})=\mathbf{0}$ trivially converges in a single step from
any initial condition without a global convergence strategy.

Example 5 illustrates why computing equilibrium prices based on the markup
equations is more reliable and efficient than using Eqn. (7) directly. The
following two sections echo the pattern of this example to provide the
details.

###  3.2. Newton’s Method on the Combined Gradient

The most direct approach to compute equilibrium prices using Newton’s method
is to solve
$\mathbf{F}_{\pi}(\mathbf{p})=(\tilde{\nabla}\hat{\pi})(\mathbf{p})=\mathbf{0}$,
abbreviated CG-NM in Table 4. This approach works well when the initial
condition is near an equilibrium, as required by theory (Ortega and
Rheinboldt, 1970; Kelley, 1995; Dennis and Schnabel, 1996). In practice,
computing counterfactual equilibrium prices starting with the observed prices
may exploit this local convergence if changes to exogeneous variables have a
relatively small impact on equilibrium prices. On the other hand, CG-NM can be
unreliable when started “far” from equilibrium.

The challenge is the tendency for the derivatives of profits to vanish as
prices become large Morrow and Skerlos (2010), as demonstrated in Example 6
below.

######  Example 6.

Consider a simple Logit model with linear in price utility and an outside
good: $u(p)=-\alpha p+v$ for some $\alpha>0$ and any $v\in\mathbb{R}$, and
$\vartheta>-\infty$. The derivative of firm $f$’s profit function with respect
to the price of product $k\in\mathcal{J}_{f}$ is

$(D_{k}\hat{\pi}_{f})(\mathbf{p})=-\alpha
P_{k}^{L}(\mathbf{p})(p_{k}-c_{k})+\alpha
P_{k}^{L}(\mathbf{p})\hat{\pi}_{f}(\mathbf{p})+P_{k}^{L}(\mathbf{p}).$

Since $P_{k}^{L}(\mathbf{p})$ and $P_{k}^{L}(\mathbf{p})(p_{k}-c_{k})$ both
vanish as $p_{k}\to\infty$ (as is easily checked), $\hat{\pi}_{f}(\mathbf{p})$
is bounded in $\mathbf{p}$. Thus $(D_{k}\hat{\pi}_{f})(\mathbf{p})\to 0$ as
$p_{k}\to\infty$.

We now provide a general assumption under which
$(D_{k}\hat{\pi}_{f(k)})(\mathbf{p})\to 0$ as $p_{k}\uparrow\varsigma_{*}$.

######  Assumption 3.1.

Let $\psi_{k}$ be defined as in Assumption 2.3. Assume: (i)
$p_{k}\psi_{k}(\boldsymbol{\theta},p_{k})\to 0$ as
$p_{k}\uparrow\varsigma(\boldsymbol{\theta})$ for $\mu$-a.e.
$\boldsymbol{\theta}$. (ii) There exists $M<\infty$ and
$\bar{p}_{k}\in[0,\varsigma_{*})$ such that
$p_{k}\int\psi_{k}(\boldsymbol{\theta},p_{k})d\mu(\boldsymbol{\theta})\leq M$
for all $p_{k}\in(\bar{p}_{k},\varsigma_{*})$.

As with Assumption 2.3 above, (i) and (ii) are essentially conditions for the
Dominated Convergence Theorem.

Assumption 3.1 (i) extends Assumption 2.3 (i) to include a neighborhood of
$\varsigma_{*}$. Note that if $\varsigma(\boldsymbol{\theta})<\infty$ then (i)
holds if, and only if, $\psi_{k}(\boldsymbol{\theta},p_{k})\to 0$ as
$p_{k}\uparrow\varsigma(\boldsymbol{\theta})$; i.e.
$\psi_{k}(\boldsymbol{\theta},\cdot)$ is continuous at
$\varsigma(\boldsymbol{\theta})$. Thus if
$\varsigma(\boldsymbol{\theta})<\infty$ Assumption 3.1 (i) and Assumption 2.3
(i) are the same. If $\varsigma(\boldsymbol{\theta})=\infty$ and
$p_{k}\psi_{k}(\boldsymbol{\theta},p_{k})\to 0$ as $p_{k}\uparrow\infty$, then
necessarily $\psi_{k}(\boldsymbol{\theta},p_{k})\to 0$ as
$p_{k}\uparrow\infty$. The converse, however, need not hold.

If $\varsigma_{*}<\infty$, Assumption 3.1 (ii) simply says that
$\int\psi_{k}(\boldsymbol{\theta},p_{k})d\mu(\boldsymbol{\theta})$ is bounded
as $p_{k}\uparrow\varsigma_{*}$. This is not implied by Assumption 2.3 (ii),
but is a natural extension of it.

######  Lemma 3.1.

Suppose Assumptions 2.1-3.1 hold. Then
$p_{k}\left\lvert\lambda_{k}(\mathbf{p})\right\rvert\to 0$ as
$p_{k}\uparrow\varsigma_{*}$ for all $k$. Additionally,
$p_{k}\left\lvert\gamma_{j,k}(\mathbf{p})\right\rvert\to 0$ as
$p_{k}\uparrow\varsigma_{*}$ for all $j$. Subsequently,
$(D_{k}\hat{\pi}_{f(k)})(\mathbf{p})\to 0$ as $p_{k}\uparrow\varsigma_{*}$.

###### Proof.

Let $\\{p_{k}^{(n)}\\}_{n\in\mathbb{N}}\subset(0,\varsigma_{*})$ be any
sequence converging to $\varsigma_{*}$. Define
$\Psi_{k}^{(n)}:\mathcal{T}\to\mathcal{P}$ by
$\Psi_{k}^{(n)}(\boldsymbol{\theta})=p_{k}^{(n)}\psi_{k}(\boldsymbol{\theta},p_{k}^{(n)})$.
The functions $\\{\Psi_{k}^{(n)}\\}_{n\in\mathbb{N}}$ converge pointwise to
zero and have integrals uniformly bounded by the constant $M$. By the
Dominated Convergence Theorem

$\lim_{n\to\infty}\int\Psi_{k}^{(n)}(\boldsymbol{\theta})d\mu(\boldsymbol{\theta})=\int\Big{(}\lim_{n\to\infty}\Psi_{k}^{(n)}(\boldsymbol{\theta})\Big{)}d\mu(\boldsymbol{\theta})=0.$

∎

In other words, under Assumption 3.1 the components of $\mathbf{F}_{\pi}$
vanish as the corresponding price tends to $\varsigma_{*}$ even though this
may not mean that $\varsigma_{*}$ maximizes profits. Because of this, CG-NM
may converge to a zero of $\mathbf{F}_{\pi}$ at $\varsigma_{*}\mathbf{1}$, or
with some components equal to $\varsigma_{*}$, that is not an equilibrium.

Note that even though the price derivatives vanish at infinity, this does not
mean that infinite prices maximize profits. Nonetheless, CG-NM may converge to
a zero of $\mathbf{F}_{\pi}$ with some components equal to infinity that is
not an equilibrium. Moreover, because the components of
$\mathbf{F}_{\pi}(\mathbf{p})$ can vanish over some divergent sequences,
standard global convergence strategies based on minimizing
$\lvert\lvert\mathbf{F}_{\pi}(\mathbf{p})\rvert\rvert_{2}$ will not be
effective ways of avoiding this behavior. As in Example 5, we must reformulate
the problem to obtain reliable and efficient approaches for computing
equilibrium prices.

###  3.3. Newton’s Method and the Markup Equations

Reliable and efficient implementations of Newton’s method are found by
observing that the combined gradient, $\mathbf{F}_{\pi}$, can be written as
follows:

(20) $\displaystyle\mathbf{F}_{\pi}(\mathbf{p})$
$\displaystyle=(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}\mathbf{F}_{\eta}(\mathbf{p})$
where $\displaystyle\mathbf{F}_{\eta}(\mathbf{p})$
$\displaystyle=\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})$ (21)
$\displaystyle\mathbf{F}_{\pi}(\mathbf{p})$
$\displaystyle=\boldsymbol{\Lambda}(\mathbf{p})\mathbf{F}_{\zeta}(\mathbf{p})$
where $\displaystyle\mathbf{F}_{\zeta}(\mathbf{p})$
$\displaystyle=\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p}).$

Either $\mathbf{F}_{\eta}$ or $\mathbf{F}_{\zeta}$ can be used to compute
simultaneously stationary prices when
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}$ and
$\boldsymbol{\Lambda}(\mathbf{p})$, respectively, are nonsingular (Morrow and
Skerlos, 2010). Of course, $\mathbf{F}_{\eta}$ and $\mathbf{F}_{\zeta}$ recast
the first-order condition as a fixed-point problem: $\mathbf{F}_{\eta}$ is
zero if and only if the BLP-markup equation holds, and $\mathbf{F}_{\zeta}$ is
zero if and only if the $\boldsymbol{\zeta}$-markup equation holds.

Solving $\mathbf{F}_{\eta}(\mathbf{p})=\mathbf{0}$ or
$\mathbf{F}_{\zeta}(\mathbf{p})=\mathbf{0}$, abbreviated
$\boldsymbol{\eta}$-NM and $\boldsymbol{\zeta}$-NM respectively in Table 4,
requires the solution of nontrivial nonlinear systems with Newton’s method.
$\boldsymbol{\eta}$-NM and $\boldsymbol{\zeta}$-NM, however, are less likely
to have the computational problems that CG-NM exhibits because they exploit
norm-coercivity of the maps $\mathbf{F}_{\eta}$ and $\mathbf{F}_{\zeta}$
(Morrow and Skerlos, 2010). A norm-coercive map has a norm that tends to
infinity with the norm of its argument (Ortega and Rheinboldt, 1970; Harker
and Pang, 1990). Globally convergent implementations of Newton’s method that
decrease the value of $\lvert\lvert\mathbf{F}(\mathbf{p})\rvert\rvert_{2}$ in
each step produce bounded sequences of iterates when $\mathbf{F}$ is norm-
coercive. Thus, solving the BLP- or $\boldsymbol{\zeta}$-markup equation
instead of the literal first-order condition removes the tendency for
applications of Newton’s method to compute “spurious” solutions at infinity.

We now prove that the maps $\mathbf{F}_{\eta}$ and $\mathbf{F}_{\zeta}$ are
indeed coercive.

######  Lemma 3.2.

Suppose $\varsigma_{*}=\infty$ and Assumption 2.1-2.3 hold.

  * (i)

Norm-coercivity of $\mathbf{F}_{\zeta}(\mathbf{p})$ implies that of
$\mathbf{F}_{\eta}(\mathbf{p})$.

  * (ii)

If Eqn. (17) holds, then norm-coercivity of $\mathbf{F}_{\eta}(\mathbf{p})$
implies that of $\mathbf{F}_{\zeta}(\mathbf{p})$.

###### Proof.

Proposition 2.12 implies that

$\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})=\big{(}\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})\big{)}(\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})).$

To prove (i), note that

$\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}\geq\left(\frac{1}{1+\lvert\lvert\tilde{\boldsymbol{\Omega}}(\mathbf{p})\rvert\rvert_{\infty}}\right)\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\geq\left(\frac{1}{2}\right)\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}.$

To prove (ii), note that if Eqn. (17) holds,

$\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\geq\big{(}1-\lvert\lvert\boldsymbol{\Omega}(\mathbf{p})\rvert\rvert_{\infty}\big{)}\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}\geq\varepsilon\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}.$

∎

######  Lemma 3.3.

Suppose $\varsigma_{*}=\infty$ and Assumption 2.1-2.3 and 2.4 hold. Then

$\lim_{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\to\infty}\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}=\infty=\lim_{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\to\infty}\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}.$

###### Proof.

The norm-coercivity of $\boldsymbol{\eta}$ is a trivial consequence of the
boundedness of $\boldsymbol{\eta}$ under Assumption 2.4. The norm-coercivity
of $\boldsymbol{\zeta}$ then follows from Lemma 3.2. ∎

We now weaken Assumption 2.4’s Eqn. (16).

######  Assumption 3.2.

Suppose that $\varsigma_{*}=\infty$ and

(22)
$\displaystyle\lim_{M\uparrow\infty}\sup\left\\{\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}}:\mathbf{p}\in\mathcal{P}^{J},\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\geq
M\right\\}=\delta\in[0,1).$

Note that the limit is of a non-increasing sequence of non-negative numbers,
and thus exists.

######  Lemma 3.4.

Assuming Eqn. (22) is equivalent to assuming that for any sequence
$\mathbf{p}_{n}$ with
$\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}\to\infty$,
$\lim_{n\to\infty}\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{n})^{-1}\mathbf{P}(\mathbf{p}_{n})\rvert\rvert_{\infty}/\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}\leq\delta$.

###### Proof.

If Eqn. (22) holds, then for any $\varepsilon>0$ there exists an $M>0$ such
that

$\sup\left\\{\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}}:\mathbf{p}\in\mathcal{P}^{J},\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\geq
M\right\\}<\delta+\varepsilon.$

If $\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}\to\infty$, then there is
also an $N_{\epsilon}$ such that
$\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}\geq M$ for all
$n>N_{\epsilon}$. Thus

$\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{n})^{-1}\mathbf{P}(\mathbf{p}_{n})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}}<\delta+\varepsilon$

for all $n>N_{\epsilon}$, and thus

$\lim_{n\to\infty}\left[\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{n})^{-1}\mathbf{P}(\mathbf{p}_{n})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{n}\rvert\rvert_{\infty}}\right]\leq\delta.$

Conversely, if Eqn. (22) fails, then there is a $\bar{M}>0$ such that

$S(M)=\sup\left\\{\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}}:\mathbf{p}\in\mathcal{P}^{J},\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\geq
M\right\\}\geq 1$

for all $M\geq\bar{M}$. We can thus choose $\mathbf{p}_{M}$ with
$\lvert\lvert\mathbf{p}_{M}\rvert\rvert_{\infty}\geq M$ satisfying

$1-\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{M})^{-1}\mathbf{P}(\mathbf{p}_{M})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{M}\rvert\rvert_{\infty}}\leq
S(M)-\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{M})^{-1}\mathbf{P}(\mathbf{p}_{M})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{M}\rvert\rvert_{\infty}}\leq\frac{1}{M}.$

In other words,

$\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{M})^{-1}\mathbf{P}(\mathbf{p}_{M})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{M}\rvert\rvert_{\infty}}\geq
1-\frac{1}{M}$

for all $M\geq\bar{M}$, and thus

$\lim_{M\to\infty}\left[\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p}_{M})^{-1}\mathbf{P}(\mathbf{p}_{M})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}_{M}\rvert\rvert_{\infty}}\right]\geq
1.$

Hence the “sequence version” of Eqn. (22) fails, and thus by contraposition
the sequence version and Eqn. (22) are identical. ∎

Next we note that Eqn. (22) weakens Eqn. (16).

######  Lemma 3.5.

If Eqn. (16) holds, then Eqn. (22) holds.

###### Proof.

If
$\sup\\{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}:\mathbf{p}\in\mathcal{P}^{J}\\}\leq
M$, then

$S(L)=\sup\left\\{\frac{\lvert\lvert\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})\rvert\rvert_{\infty}}{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}}:\mathbf{p}\in\mathcal{P}^{J},\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\geq
L\right\\}\leq\frac{M}{L}.$

Thus $\lim_{L\to\infty}S(L)=0$, a special case of Eqn. (22). ∎

Now we prove the alternative coercivity result.

######  Lemma 3.6.

Suppose $\varsigma_{*}=\infty$ and Assumptions 2.1-2.3, 2.5 and 3.2 hold. Then

$\lim_{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\to\infty}\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}=\infty=\lim_{\lvert\lvert\mathbf{p}\rvert\rvert_{\infty}\to\infty}\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}.$

###### Proof.

We prove the claim for $\boldsymbol{\zeta}$; the result for
$\boldsymbol{\eta}$ then follows from Lemma 2.15. Note that

$\displaystyle\left\lvert
p_{k}-c_{k}-\sum_{j\in\mathcal{J}_{f(k)}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})-\frac{P_{k}(\mathbf{p})}{\lambda_{k}(\mathbf{p})}\right\rvert$
$\displaystyle\quad\quad\quad\quad\quad\quad=\left\lvert\left(1-\frac{P_{k}(\mathbf{p})}{p_{k}\lambda_{k}(\mathbf{p})}\right)p_{k}-c_{k}-\sum_{j\in\mathcal{J}_{f(k)}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})\right\rvert$
$\displaystyle\quad\quad\quad\quad\quad\quad\geq\left\lvert\;\left\lvert
1-\frac{P_{k}(\mathbf{p})}{p_{k}\lambda_{k}(\mathbf{p})}\right\rvert
p_{k}-\Bigg{|}c_{k}+\sum_{j\in\mathcal{J}_{f(k)}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})\Bigg{|}\;\right\rvert$

Suppose that $p_{k}\to\infty$. By assumption,

$\lim_{n\to\infty}\left[1-\frac{P_{k}(\mathbf{p})}{p_{k}\lambda_{k}(\mathbf{p})}\right]\geq
1-\delta>0$

while the second term is bounded. Thus

$\displaystyle\left\lvert
p_{k}-c_{k}-\sum_{j\in\mathcal{J}_{f(k)}}\omega_{k,j}(\mathbf{p})(p_{j}-c_{j})-\frac{P_{k}(\mathbf{p})}{\lambda_{k}(\mathbf{p})}\right\rvert\to\infty.$

∎

Note that since we did not require that Eqn. (17) held, $\boldsymbol{\zeta}$
need not be bounded for $\mathbf{F}_{\eta}$ and $\mathbf{F}_{\zeta}$ to be
coercive.

###  3.4. Fixed-Point Iteration

In addition to applications of Newton’s method, the BLP- and
$\boldsymbol{\zeta}$-markup equations suggest applying fixed-point iteration
to solve for equilibrium prices. We examine fixed-point iterations based on
both equations.

####  3.4.1. $\zeta$ Fixed-Point Iteration

The fixed-point iteration
$\mathbf{p}\leftarrow\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})$ based on the
$\boldsymbol{\zeta}$-markup equation, here abbreviated
$\boldsymbol{\zeta}$-FPI, can efficiently compute equilibrium prices for some
problems. $\boldsymbol{\zeta}$-FPI has relatively efficient steps because no
linear systems need to be solved, unlike every other method listed in Table 4.
While we are not aware of a general convergence proof for
$\boldsymbol{\zeta}$-FPI, this iteration has converged reliably on test
problems including the examples in Morrow and Skerlos (2010).

The first observation we make is that the $\boldsymbol{\zeta}$-FPI steps
always point in directions of “myopic gradient ascent.”

######  Lemma 3.7.

Let $\mathbf{p}\in(0,\varsigma_{*})^{J}$, and let
$\boldsymbol{\delta}\mathbf{p}=\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})-\mathbf{p}$
denote the $\boldsymbol{\zeta}$-FPI step. Then

$\frac{1}{\max_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}\leq\frac{(\tilde{\nabla}\hat{\pi})(\mathbf{p})^{\top}\boldsymbol{\delta}\mathbf{p}}{(\tilde{\nabla}\hat{\pi})(\mathbf{p})^{\top}(\tilde{\nabla}\hat{\pi})(\mathbf{p})}\leq\frac{1}{\min_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}.$

Similarly, let $\theta(\mathbf{p})$ denote the angle between
$\boldsymbol{\delta}\mathbf{p}$ and $(\tilde{\nabla}\hat{\pi})(\mathbf{p})$,
and suppose $\mathbf{p}$ is not simultaneously stationary. Then

$\cos\theta(\mathbf{p})\geq\frac{\min_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}{\max_{j}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}.$

###### Proof.

Both results follows directly from the equation
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})=\left\lvert\boldsymbol{\Lambda}(\mathbf{p})\right\rvert\boldsymbol{\delta}\mathbf{p}$
where $\left\lvert\boldsymbol{\Lambda}(\mathbf{p})\right\rvert$ denotes the
absolute value of the components of $\boldsymbol{\Lambda}(\mathbf{p})$. ∎

Specifically, the $\boldsymbol{\zeta}$-FPI steps have a positive projection
onto the combined gradient, and cannot become orthogonal to the combined
gradient over any sequence of non-simultaneously stationary prices that stay
in $(0,\varsigma_{*})^{J}$.

If $F=1$, and the equilibrium problem is an optimization problem, this implies
$\boldsymbol{\zeta}$-FPI has steps that point in gradient ascent directions
and, when properly scaled, converge to local maximizers of profit. More
specifically, $\boldsymbol{\zeta}$-FPI cannot converge to minimizers of
profits. This may generate the properties of $\boldsymbol{\zeta}$-FPI observed
in Example 10 from Morrow and Skerlos (2010).

######  Corollary 3.8.

Let Assumptions 2.1-2.4 hold, and suppose
$\\{\mathbf{p}^{(n)}\\}_{n=1}^{\infty}$ is the $\boldsymbol{\zeta}$-FPI
sequence. Then $\\{\mathbf{p}^{(n)}\\}_{n=1}^{\infty}$ is bounded.

###### Proof.

By Lemma 2.13, for any sufficiently large $M>0$ we can find some $L>0$ such
that

$\lvert\lvert\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}<\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}-M\quad\text{for
all}\quad\lvert\lvert\mathbf{p}-\mathbf{c}\rvert\rvert_{\infty}>L.$

If the $\boldsymbol{\zeta}$-FPI sequence diverges, then for any such $L$ there
is an $N$ such that

$\lvert\lvert\mathbf{p}^{(n)}-\mathbf{c}\rvert\rvert_{\infty}>L\quad\text{for
all}\quad n>N.$

But then

$\lvert\lvert\mathbf{p}^{(n+1)}-\mathbf{c}\rvert\rvert_{\infty}=\lvert\lvert\boldsymbol{\zeta}(\mathbf{p}^{(n)})\rvert\rvert_{\infty}<\lvert\lvert\mathbf{p}^{(n)}-\mathbf{c}\rvert\rvert_{\infty}-M<\lvert\lvert\mathbf{p}^{(n)}-\mathbf{c}\rvert\rvert_{\infty}\quad\text{for
all}\quad n>N,$

which states that the $\boldsymbol{\zeta}$-FPI sequence is decreasing. This is
a contradiction of the hypothesis that the $\boldsymbol{\zeta}$-FPI sequence
diverges. ∎

To implement $\boldsymbol{\zeta}$-FPI, one simply needs to iterate the
assignment $\mathbf{p}\leftarrow\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})$
where Eqn. (18) defines $\boldsymbol{\zeta}(\mathbf{p})$. As shown in Table 5
below, integral approximations, rather than the actual computation of the
step, drive the computational burden. Given a price vector, utilities, and
utility derivatives, computing $\mathbf{P}(\mathbf{p})$,
$\boldsymbol{\Lambda}(\mathbf{p})$, and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ for a set of $S$ samples requires
$\mathcal{O}(S\sum_{f=1}^{F}J_{f}^{2})$ floating point operations (flops),
while the fixed-point step itself only requires
$\mathcal{O}(\sum_{f=1}^{F}J_{f}^{2})$ flops. Note that computing the fixed-
point step $\mathbf{c}+\boldsymbol{\zeta}(\mathbf{p})$ requires an equivalent
amount of work as computing the combined gradient
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})$. Furthermore, because
$\boldsymbol{\Lambda}(\mathbf{p})$ is a diagonal matrix, no serious obstacles
to computing the fixed point step arise as $J$ becomes large.

####  3.4.2. $\eta$ Fixed-Point Iteration

The fixed-point iteration
$\mathbf{p}\leftarrow\mathbf{c}+\boldsymbol{\eta}(\mathbf{p})$, abbreviated
$\boldsymbol{\eta}$-FPI, based on the BLP-markup equation need not converge.
Example 7 below, repeated from Morrow and Skerlos (2010), gives a case in
which $\boldsymbol{\eta}$ can fail to be even locally convergent.

######  Example 7.

Consider multi-product monopoly pricing with a simple Logit model having
$u_{j}(p)=-\alpha p+v_{j}$ for some $\alpha>0$, any $v_{j}\in\mathbb{R}$, and
$\vartheta>-\infty$. It is well known that for a single-product firm, unique
profit-maximizing prices exist (Anderson and de Palma, 1988; Milgrom and
Roberts, 1990; Caplin and Nalebuff, 1991). Morrow (2008) proves that profit-
optimal prices $\mathbf{p}_{*}$ are unique for the multi-product case $-$ and
even so with multiple firms $-$ even though profits are not quasi-concave
(Hanson and Martin, 1996).

In this example, $\boldsymbol{\eta}$-FPI is not always locally convergent near
$\mathbf{p}_{*}$, while $\boldsymbol{\zeta}$-FPI is always superlinearly
locally convergent. For an arbitrary continuously differentiable function
$\mathbf{F}$ and $\mathbf{p}_{*}=\mathbf{F}(\mathbf{p}_{*})$, $\mathbf{F}$ is
contractive on some neighborhood of $\mathbf{p}_{*}$ in some norm
$\lvert\lvert\cdot\rvert\rvert$ if $\rho((D\mathbf{F})(\mathbf{p}_{*}))<1$
where $\rho(\mathbf{A})$ (Ortega and Rheinboldt, 1970). We show that
$\rho((D\boldsymbol{\eta})(\mathbf{p}_{*}))>1$ may hold while
$\rho((D\boldsymbol{\zeta})(\mathbf{p}_{*}))=0$, where $\rho(\mathbf{A})$
denotes the spectral radius of the matrix $\mathbf{A}$.

The components of the BLP-markup function $\boldsymbol{\eta}$ are given by
$\eta_{k}(\mathbf{p})=\alpha^{-1}(1-\sum_{j=1}^{J}P_{j}^{L}(\mathbf{p}))^{-1}$
for all $k$. From this formula the equation

$\rho((D\boldsymbol{\eta})(\mathbf{p}_{*}))=\frac{\sum_{j=1}^{J}P_{j}^{L}(\mathbf{p}_{*})}{1-\sum_{j=1}^{J}P_{j}^{L}(\mathbf{p}_{*})}=\sum_{j=1}^{J}e^{u_{j}(p_{j,*})-\vartheta}$

can be derived. For valuations of the outside good, $\vartheta$, sufficiently
close to $-\infty$, $\rho((D\boldsymbol{\eta})(\mathbf{p}_{*}))>1$ can hold;
see Morrow and Skerlos (2010) for details.

To prove the claim regarding $\rho((D\boldsymbol{\zeta})(\mathbf{p}_{*}))$,
note that $\zeta_{k}(\mathbf{p})=\hat{\pi}(\mathbf{p})+1/\alpha$, and thus
$(D_{l}\zeta_{k})(\mathbf{p}_{*})=(D_{l}\hat{\pi})(\mathbf{p}_{*})=0$ for all
$k,l$.

Even if the BLP-markup equation does generate a convergent fixed-point
iteration, evaluating $\boldsymbol{\eta}$ involves the solution of $F$ linear
systems that grow in size with the number of products offered by the firms.
The work required to evaluate $\boldsymbol{\eta}$ using a direct method like
PLU or QR factorization is $\mathcal{O}([\max_{f}J_{f}]^{3})$, given values of
$\mathbf{P}(\mathbf{p})$, $\boldsymbol{\Lambda}(\mathbf{p})$, and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ as approximated using simulation.
The work to evaluate $\boldsymbol{\zeta}$ is only
$\mathcal{O}([\max_{f}J_{f}]^{2})$ given $\mathbf{P}(\mathbf{p})$,
$\boldsymbol{\Lambda}(\mathbf{p})$, and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ (Table 5). Generally speaking,
function evaluations must be cheap for the linear convergence of fixed-point
iterations to result in faster computations than the superlinearly or
quadratically convergent variants of Newton’s method.

###  3.5. Practical Considerations

This section addresses several practical considerations.

####  3.5.1. Simulation

Any method for computing equilibrium prices under Mixed Logit models faces a
common obstacle: the integrals that define the choice probabilities
($\mathbf{P}$) and their derivatives
($\boldsymbol{\Lambda},\tilde{\boldsymbol{\Gamma}}$) cannot be computed
exactly. We employ finite-sample versions of the methods discussed below by
drawing $S\in\mathbb{N}$ samples from the demographic distribution and
applying the method to the finite-sample model thus generated. Particularly,
these samples are used to compute approximate $\mathbf{P}(\mathbf{p})$,
$\boldsymbol{\Lambda}(\mathbf{p})$, and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$; see Table 5. These samples are kept
fixed for all steps of the method and, in principle, can be generated in any
way. We draw directly from the demographic distribution, although importance
and quasi-random sampling (e.g., see Train (2003)) can also be employed. The
Law of Large Numbers motivates this widely-used approach to econometric
analysis (e.g., see McFadden (1989) and Draganska and Jain (2004)). While all
numerical approaches for computing equilibrium prices described here rely on a
Law of Large Numbers for simultaneously stationary prices, we do not provide a
formal convergence theorem. We do provide numerical evidence that computed
equilibrium prices based on the fixed-point iteration for our examples do
indeed follow such a law.

####  3.5.2. Truncation of Low Purchase Probability Products

All of the methods we implement can be built to ignore products with
excessively low choice probabilities. That is, one can ignore price updates
for all products with $P_{j}(\mathbf{p})\leq\varepsilon_{P}$, where
$\varepsilon_{P}$ is some small value (say $10^{-10}$). Products with a choice
probability this small (or smaller) need not be considered a part of the
market in the price equilibrium computations. For example, Wards (2007)
reports total sales of cars and light trucks during 2005 as $N=16,947,754$.
Particularly, 7,667,066 cars and 9,280,688 light trucks. Because expected
demand is defined by $\mathbb{E}[Q_{j}(\mathbf{p})]=NP_{j}(\mathbf{p})$, any
$\varepsilon_{P}\leq 0.5*N^{-1}\approx 3\times 10^{-8}$ ignores any vehicle
that, as priced, is not expected to have a single customer out of the millions
of customers that bought or considered buying new vehicles. There are also
technical reasons for this truncation. Particularly,
$\boldsymbol{\Lambda}(\mathbf{p})$ and
$(D\tilde{\nabla}\hat{\pi})(\mathbf{p})$ become singular as
$P_{j}(\mathbf{p})\to 0$, for any $j$. Truncating avoids this non-singularity
and hopefully helps conditioning.

####  3.5.3. Termination Conditions

We terminate all iterations with the numerical simultaneous stationarity
condition
$\lvert\lvert(\tilde{\nabla}\hat{\pi})(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}$
where $\varepsilon_{T}$ is some small number (e.g., $10^{-6}$). Note that a
standard application of Newton’s method to solve
$\mathbf{F}_{\eta}(\mathbf{p})=\mathbf{0}$ or
$\mathbf{F}_{\zeta}(\mathbf{p})=\mathbf{0}$ would terminate when either

(23)
$\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}\quad\quad\text{or}\quad\quad\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T},$

respectively. For example, Aguirregabiria and Vicentini (2006) use the
condition
$\lvert\lvert\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}$.
Ensuring that Eqn. (23) holds does not necessarily imply that
$\lvert\lvert(\tilde{\nabla}\hat{\pi})(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}$,
the strictly interpreted first-order condition.

Because

$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}(\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p}))=(\tilde{\nabla}\hat{\pi})(\mathbf{p})=\boldsymbol{\Lambda}(\mathbf{p})(\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})),$

it is easy to terminate all methods, CG-NM, $\boldsymbol{\eta}$-NM,
$\boldsymbol{\zeta}$-NM, and $\boldsymbol{\zeta}$-FPI, when
$\lvert\lvert(\tilde{\nabla}\hat{\pi})(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}$.
While this is done here to ensure consistency in our comparisons of different
methods,
$\lvert\lvert(\tilde{\nabla}\hat{\pi})(\mathbf{p})\rvert\rvert_{\infty}\leq\varepsilon_{T}$
should always be the termination condition for price equilibrium computations.

Three other standard termination conditions are used (Brown and Saad, 1990;
Dennis and Schnabel, 1996). We terminate the iteration if the (relative) step
length becomes too small, if a maximum number of iterations is exceeded, or if
an exceptional event occurs (e.g. division by zero). These three conditions
are considered “failure” as the iteration has failed to compute a numerically
simultaneously stationary point in the sense of the first termination
condition.

####  3.5.4. Second-Order Conditions.

Each method in Table 4 finds simultaneously stationary points, rather than
local equilibria. Unlike in optimization, there is no a priori assurance that
first-order iterative methods for equilibrium problems will converge to
certain types of stationary points. Thus in computing equilibria it is vitally
important to check the second-order sufficient conditions to verify that a
local equilibrium has indeed been found.

In local equilibrium every firm’s profit Hessian,
$(D_{f}\nabla_{f}\hat{\pi}_{f})(\mathbf{p})$, should also be negative
definite. The formulas given in Proposition 3.9 below provide an expression
for $(D_{f}\nabla_{f}\hat{\pi}_{f})(\mathbf{p})$ that we use to check the
second-order sufficient condition. Cholesky factorization, rather than direct
approximation of the spectrum, is used to test the negative definiteness of
$(D_{f}\nabla_{f}\hat{\pi}_{f})(\mathbf{p})$ (Golub and Loan, 1996).

####  3.5.5. Computational Burden

Table 5 reviews the formulae and computational burden of computing
$(\tilde{\nabla}\hat{\pi})$, $\boldsymbol{\eta}$, and $\boldsymbol{\zeta}$.

Table 5. Work required to evaluate $(\tilde{\nabla}\hat{\pi})$, $\boldsymbol{\eta}$, and $\boldsymbol{\zeta}$ given $S$ samples $\\{\boldsymbol{\theta}_{s}\\}_{s=1}^{S}\subset\mathcal{T}$, an $S\times J$ matrix $\mathbf{L}(\mathbf{p})$ of Logit choice probabilities ($(\mathbf{L}(\mathbf{p}))_{s,j}=P_{j}^{L}(\boldsymbol{\theta}_{s},\mathbf{p})$), and an $S\times J$ matrix of utility derivatives $\mathbf{D}(\mathbf{p})$ ($(\mathbf{D}(\mathbf{p}))_{s,j}=(Dw_{j})(\boldsymbol{\theta}_{s},p_{j})$). The first section gives work required for sample-average approximations to $\mathbf{P}(\mathbf{p})$, $\boldsymbol{\Lambda}(\mathbf{p})$, and $\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$. The second section takes $\mathbf{P}(\mathbf{p})$, $\boldsymbol{\Lambda}(\mathbf{p})$, and $\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ as given. Quantity | Formula | flops
---|---|---
$\mathbf{P}(\mathbf{p})$ | $S^{-1}\mathbf{L}(\mathbf{p})^{\top}\mathbf{1}$ | $SJ$
$\mathbf{V}(\mathbf{p})$ |  $\mathbf{L}(\mathbf{p})\cdot\mathbf{D}(\mathbf{p})$${}^{\text{(a)}}$ | $SJ$
$\boldsymbol{\Lambda}(\mathbf{p})$ | $S^{-1}\mathbf{V}(\mathbf{p})^{\top}\mathbf{1}$ | $SJ$
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ | $S^{-1}\mathbf{L}(\mathbf{p})^{\top}\mathbf{V}(\mathbf{p})$ | $2S\sum_{f=1}^{F}J_{f}^{2}$
Total work to compute $\mathbf{P}(\mathbf{p})$, $\boldsymbol{\Lambda}(\mathbf{p})$, and $\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ | $S\left(3J+2\sum_{f=1}^{F}J_{f}^{2}\right)$
$\boldsymbol{\zeta}(\mathbf{p})$ | $\tilde{\boldsymbol{\Omega}}(\mathbf{p})(\mathbf{p}-\mathbf{c})-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})$ | $2\sum_{f=1}^{F}J_{f}^{2}+4J$
$\boldsymbol{\eta}(\mathbf{p})$ | $(\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p}))\boldsymbol{\eta}(\mathbf{p})=-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})$ | $\left(\frac{4}{3}\right)\sum_{f=1}^{F}J_{f}^{3}+\left(\frac{7}{2}\right)\left(\sum_{f=1}^{F}J_{f}^{2}+J\right)-2$
$(\tilde{\nabla}\hat{\pi})(\mathbf{p})$ | $(\boldsymbol{\Lambda}(\mathbf{p})-\tilde{\boldsymbol{\Gamma}}(\mathbf{p})^{\top})(\mathbf{p}-\mathbf{c})+\mathbf{P}(\mathbf{p})$ | $2\sum_{f=1}^{F}J_{f}^{2}+5J$
| $=\boldsymbol{\Lambda}(\mathbf{p})(\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p}))$ | $2\sum_{f=1}^{F}J_{f}^{2}+6J$
(a) “$\cdot$” here denotes element-by-element multiplication.

Computing $\boldsymbol{\eta}$ and applying Newton’s method to
$\mathbf{F}_{\eta}$ requires solving linear systems. We give some more details
regarding these computations here. As stated above, the linear system

$(\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p}))\boldsymbol{\eta}(\mathbf{p})=-\boldsymbol{\Lambda}(\mathbf{p})^{-1}\mathbf{P}(\mathbf{p})$

should be used to solve for $\boldsymbol{\eta}(\mathbf{p})$. Note also that
only the systems

$(\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p}))\boldsymbol{\eta}_{f}(\mathbf{p})=-\boldsymbol{\Lambda}_{f}(\mathbf{p})^{-1}\mathbf{P}_{f}(\mathbf{p})$

for all $f$ need be solved. Of course, our condition bound applies within
firms as well:

$\kappa_{2}\big{(}(D_{f}\mathbf{P}_{f})(\mathbf{p})^{\top}\big{)}\geq\left(\frac{\max_{j\in\mathcal{J}_{f}}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}{\min_{j\in\mathcal{J}_{f}}\left\lvert\lambda_{j}(\mathbf{p})\right\rvert}\right)\kappa_{2}\big{(}\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p})\big{)}.$

If Householder QR factorization is used to solve these systems, then computing
$\boldsymbol{\eta}(\mathbf{p})$ from $\mathbf{P}(\mathbf{p})$,
$\boldsymbol{\Lambda}(\mathbf{p})$, and
$\tilde{\boldsymbol{\Gamma}}(\mathbf{p})$ requires
$\mathcal{O}(\sum_{f=1}^{F}J_{f}^{3})$ flops (Table 5).

This is a significant increase in computational effort relative to computing
$\boldsymbol{\zeta}(\mathbf{p})$ or $(\tilde{\nabla}\hat{\pi})(\mathbf{p})$.
The diagonal dominance of
$\mathbf{I}-\tilde{\boldsymbol{\Omega}}(\mathbf{p})$, indeed of
$(\tilde{D}\mathbf{P})(\mathbf{p})$ itself, suggests that Jacobi, Gauss-
Seidel, and Successive Over-Relaxation (SOR) iterations (Golub and Loan, 1996)
may be a relatively efficient way to compute $\boldsymbol{\eta}$.

Additional work is required to compute $(D\boldsymbol{\eta})(\mathbf{p})$, if
this is to be used in Newton’s method. Though it requires solving a matrix-
linear system of the type
$(\tilde{D}\mathbf{P})(\mathbf{p})(D\boldsymbol{\eta})(\mathbf{p})=\mathbf{B}(\mathbf{p})$,
the required matrix factorizations of
$\mathbf{I}-\boldsymbol{\Omega}_{f}(\mathbf{p})$ need only be computed once to
compute both $\boldsymbol{\eta}$ and $(D\boldsymbol{\eta})$, but must be
updated for each vector of prices.

###  3.6. Computing Jacobian Matrices for Newton’s Method

Standard “exact” or Quasi-Newton methods to solve
$\mathbf{F}(\mathbf{x})=\mathbf{0}$ either always or periodically require the
Jacobian matrix $(D\mathbf{F})(\mathbf{x})$. Using finite differences to
approximate Jacobian matrices requires $J$ evaluations of the function
$\mathbf{F}$, an unacceptable workload. In the 993 vehicle example from Morrow
and Skerlos (2010), approximating $(D\mathbf{F})(\mathbf{x})$ once with finite
differences would take roughly 993 evaluations of $\mathbf{F}$, when the work
of less than 50 evaluations appears to sufficient to converge to equilibrium
prices using the $\boldsymbol{\zeta}$-FPI.

We recommend directly approximating $(D\mathbf{F})(\mathbf{x})$ using integral
expressions for $(D\tilde{\nabla}\hat{\pi})(\mathbf{p})$,
$(D\boldsymbol{\eta})(\mathbf{p})$, and $(D\boldsymbol{\zeta})(\mathbf{p})$
provided below. An alternative is to use automatic differentiation, but we are
skeptical that this would in fact be faster than the direct formulae provided
here.

####  3.6.1. Jacobian of the Combined Gradient

Assuming a second application of the Leibniz Rule holds, we can derive
integral expressions for the second derivatives
$(D_{l}D_{k}\hat{\pi}_{f(k)})(\mathbf{p})$ through

$\big{(}(D\tilde{\nabla}\hat{\pi})(\mathbf{p})\big{)}_{k,l}=(D_{l}D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=\int(D_{l}D_{k}\hat{\pi}_{f(k)}^{L})(\boldsymbol{\theta},\mathbf{p})d\mu(\boldsymbol{\theta}).$

######  Proposition 3.9.

Let $w$ be twice continuously differentiable in $p$ and suppose a second
application of the Leibniz Rule holds for the Mixed Logit choice probabilities
at $\mathbf{p}$. Set

$\displaystyle\phi_{k,l}(\mathbf{p})$
$\displaystyle=\int(Dw_{k})(\boldsymbol{\theta},p_{k})P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})P_{l}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{l})(\boldsymbol{\theta},p_{l})d\mu(\boldsymbol{\theta})$
$\displaystyle\psi_{k,l}(\mathbf{p})$
$\displaystyle=\int(Dw_{k})(\boldsymbol{\theta},p_{k})P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})\hat{\pi}_{f(k)}^{L}(\boldsymbol{\theta},\mathbf{p})P_{l}^{L}(\boldsymbol{\theta},\mathbf{p})(Dw_{l})(\boldsymbol{\theta},p_{l})d\mu(\boldsymbol{\theta})$
$\displaystyle\chi_{k}(\mathbf{p})$
$\displaystyle=\left(\frac{1}{2}\right)\int\big{(}(D^{2}w_{k})(\boldsymbol{\theta},p_{k})+(Dw_{k})(\boldsymbol{\theta},p_{k})^{2}\big{)}$
$\displaystyle\quad\quad\quad\quad\quad\quad\times
P_{k}^{L}(\boldsymbol{\theta},\mathbf{p})\big{(}(p_{k}-c_{k})-\hat{\pi}_{f(k)}^{L}(\boldsymbol{\theta},\mathbf{p})\big{)}d\mu(\boldsymbol{\theta})$

  * (i)

Component form: Setting

$\xi_{k,l}(\mathbf{p})=\delta_{k,l}(\lambda_{k}(\mathbf{p})+\chi_{k}(\mathbf{p}))-\gamma_{k,l}(\mathbf{p})-(p_{k}-c_{k})\varphi_{k,l}(\mathbf{p})$

we have

$\displaystyle(D_{l}D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=\xi_{k,l}(\mathbf{p})+2\psi_{k,l}(\mathbf{p})+\delta_{f(k),f(l)}\xi_{l,k}(\mathbf{p})$

  * (ii)

Matrix form: Let $\boldsymbol{\Phi}(\mathbf{p})$,
$\boldsymbol{\Psi}(\mathbf{p})$ and
$\mathbf{X}(\mathbf{p})=\mathrm{diag}(\boldsymbol{\chi}(\mathbf{p}))$ be the
matrices of these quantities. Also set

$\boldsymbol{\Xi}(\mathbf{p})=\boldsymbol{\Lambda}(\mathbf{p})-\boldsymbol{\Gamma}(\mathbf{p})-\mathrm{diag}(\mathbf{p}-\mathbf{c})\boldsymbol{\Phi}(\mathbf{p})+\mathbf{X}(\mathbf{p}).$

and

$(\tilde{\boldsymbol{\Xi}}(\mathbf{p}))_{k,l}=\left\\{\begin{aligned}
&\xi_{k,l}(\mathbf{p})&&\quad\text{if }f(k)=f(l)\\\ &\quad 0&&\quad\text{if
}f(k)\neq f(l)\end{aligned}\right.$

Then

(24)
$(D\tilde{\nabla}\hat{\pi})(\mathbf{p})=\boldsymbol{\Xi}(\mathbf{p})+2\boldsymbol{\Psi}(\mathbf{p})+\tilde{\boldsymbol{\Xi}}(\mathbf{p})^{\top}.$

###### Proof.

To see that this only relies on a second application of the Leibniz Rule to
the choice probabilities, note that

$(D_{l}D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=\sum_{j\in\mathcal{J}_{f(k)}}(D_{l}D_{k}P_{j})(\mathbf{p})(p_{j}-c_{j})+\delta_{f(k),f(l)}(D_{k}P_{l})(\mathbf{p})+(D_{l}P_{k})(\mathbf{p})$

and thus the continuous second-order differentiability of
$\hat{\pi}_{f}(\mathbf{p})$ depends only on the second-order continuous
differentiability of $\mathbf{P}_{f}$. This result is then an immediate
consequence of the validity of the Leibniz Rule, if a bit tedious to derive. ∎

The validity of a second application of the Leibniz Rule to the choice
probabilities is ensured by the following condition.

######  Proposition 3.10.

Let $(u,\vartheta,\mu)=(w+v,\vartheta,\mu)$ be such that

  * (i)

$w(\boldsymbol{\theta},\mathbf{y},\cdot):(0,\varsigma_{*})\to\mathbb{R}$ is
twice continuously differentiable for all $\mathbf{y}\in\mathcal{Y}$ and
$\mu$-a.e. $\boldsymbol{\theta}\in\mathcal{T}$

  * (ii)

for all $(\mathbf{y},p)\in\mathcal{Y}\times(0,\varsigma_{*})$,
$\left\lvert(D^{2}w)(\cdot,\mathbf{y},q)+(Dw)(\cdot,\mathbf{y},q)^{2}\right\rvert
e^{u(\cdot,\mathbf{y},q)-\vartheta(\cdot)}:\mathcal{T}\to[0,\infty)$ is
uniformly $\mu$-integrable for all $q$ in some neighborhood of $p$.

  * (iii)

for all
$(\mathbf{y},p),(\mathbf{y}^{\prime},p^{\prime})\in\mathcal{Y}\times(0,\varsigma_{*})$,

$\left\lvert(Dw)(\cdot,\mathbf{y},q)\right\rvert
e^{u(\cdot,\mathbf{y},q)-\vartheta(\cdot)}e^{u(\cdot,\mathbf{y}^{\prime},q^{\prime})-\vartheta(\cdot)}\left\lvert(Dw)(\cdot,\mathbf{y}^{\prime},q^{\prime})\right\rvert:\mathcal{T}\to[0,\infty)$

is uniformly $\mu$-integrable for all $(q,q^{\prime})$ in some neighborhood of
$(p,p^{\prime})$.

Then a second application of the Leibniz Rule holds for the Mixed Logit choice
probabilities, which are also continuously differentiable on
$(\mathbf{0},\varsigma_{*}\mathbf{1})$.

This is proved in the same manner as Proposition 2.4.

We also observe the following.

######  Proposition 3.11.

If $P_{k}(\mathbf{p})=0$ then
$(D_{l}D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=(D_{k}D_{l}\hat{\pi}_{f(l)})(\mathbf{p})=0$
for all $l\in\mathbb{N}(J)$.

The proof follows from the derivative formulae given above. Of course, if
$P_{k}(\mathbf{p})=0$ then $(D_{k}\hat{\pi}_{f(k)})(\mathbf{p})=0$ as well and
we have the following situation: (i) the Newton system is consistent for any
$s_{k}^{N}(\mathbf{p})\in\mathbb{R}$ and (ii) $s_{l}^{N}(\mathbf{p})$ does not
depend on $s_{k}^{N}(\mathbf{p})$ for all $l\in\mathbb{N}(J)\setminus\\{k\\}$.
Thus, in practice one can restrict attention to the Newton step defined by the
submatrix of $(D\tilde{\nabla}\hat{\pi})(\mathbf{p})$ formed by rows and
columns indexed by $\\{j:P_{j}(\mathbf{p})>\varepsilon_{P}\\}$.

The formulae above give the following expression of the profit Hessians.

######  Corollary 3.12.

Let $w$ be twice continuously differentiable in $p$ and suppose a second
application of the Leibniz Rule holds for the Mixed Logit choice
probabilities. Firm $f$’s profit Hessian is given by

$(D_{f}\nabla_{f}\hat{\pi}_{f})(\mathbf{p})=\boldsymbol{\Xi}_{f,f}(\mathbf{p})+2\boldsymbol{\Psi}_{f,f}(\mathbf{p})+\boldsymbol{\Xi}_{f,f}(\mathbf{p})^{\top}.$

####  3.6.2. The $\boldsymbol{\eta}$ map.

For
$\mathbf{F}_{\eta}(\mathbf{p})=\mathbf{p}-\mathbf{c}-\boldsymbol{\eta}(\mathbf{p})$,
we have
$(D\mathbf{F}_{\eta})(\mathbf{p})=\mathbf{I}-(D\boldsymbol{\eta})(\mathbf{p})$
where $(D\boldsymbol{\eta})(\mathbf{p})$ solves the linear matrix equation

$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}(D\boldsymbol{\eta})(\mathbf{p})=-(\mathbf{A}(\mathbf{p})+(D\mathbf{P})(\mathbf{p})).$

Here
$(\mathbf{A}(\mathbf{p}))_{k,l}=\sum_{j\in\mathcal{J}_{f(k)}}(D_{l}D_{k}P_{j})(\mathbf{p})\eta_{j}(\mathbf{p})$.
This is easily derived from the defining formula
$(\tilde{D}\mathbf{P})(\mathbf{p})^{\top}\boldsymbol{\eta}(\mathbf{p})=-\mathbf{P}(\mathbf{p})$.

####  3.6.3. The $\boldsymbol{\zeta}$ map.

For
$\mathbf{F}_{\zeta}(\mathbf{p})=\mathbf{p}-\mathbf{c}-\boldsymbol{\zeta}(\mathbf{p})$,
we have
$(D\mathbf{F}_{\zeta})(\mathbf{p})=\mathbf{I}-(D\boldsymbol{\zeta})(\mathbf{p})$
where $(D\boldsymbol{\zeta})(\mathbf{p})$ can be computed using the following
formula:

$\displaystyle(D_{l}\zeta_{k})$
$\displaystyle=\lambda_{k}^{-1}\Bigg{[}\delta_{k,l}\left[\int
P_{k}^{L}\big{(}(D^{2}w_{k})+(Dw_{k})^{2}\big{)}\left(\hat{\pi}_{f(k)}^{L}-\zeta_{k}\right)-\lambda_{k}\right]$
$\displaystyle\quad\quad\quad\quad\quad\quad+\zeta_{k}\phi_{k,l}+\gamma_{k,l}+\delta_{f(k),f(l)}\phi_{k,l}(p_{l}-c_{l})+\delta_{f(k),f(l)}\gamma_{l,k}-2\psi_{k,l}\Bigg{]}.$

##  4\. The GMRES-Newton Hookstep Method

In this section we provide some details regarding the GMRES-Newton Hookstep
method employed in Morrow and Skerlos (2010). For complete details, see
Morrow10b.

###  4.1. Inexact Newton Methods

A strong theory of “Inexact” Newton methods exists for the solution of systems
of nonlinear equations when there are “many” variables. Inexact Newton steps
are simply “inexact” solutions to the Newton system; that is, an inexact
Newton step $\mathbf{s}^{IN}$ is any vector that satisfies

(25)
$\lvert\lvert\mathbf{F}(\mathbf{x})+(D\mathbf{F})(\mathbf{x})\mathbf{s}^{IN}\rvert\rvert\leq\delta\lvert\lvert\mathbf{F}(\mathbf{x})\rvert\rvert$

for some fixed $\delta\in(0,1)$ (Dembo et al., 1982; Brown and Saad, 1990;
Eisenstat and Walker, 1994, 1996; Pernice and Walker, 1998). The name
“truncated” Newton method has also been used for the specific case when the
inexactness comes from the use of iterative linear system solvers like GMRES
(Saad and Schultz, 1986; Walker, 1988) or BiCGSTAB (van der Vorst, 1992;