Operations Research

Motivation

Many equilibrium problems in operations research have the form of a stochastic Nash game: each of $N$ players minimizes an expected cost that depends on the strategies of the others, and the expectation can only be sampled. The paper's introduction lists applications in generation-capacity and power markets and in communication networks (Abada, de Maere d'Aertrycke and Smeers, 2017; Başar, 2007). A natural way to compute an equilibrium is a best-response scheme: each player repeatedly re-optimizes against the current strategies of its rivals. In a large network the players cannot synchronize. They update at different times and see their rivals' strategies with delays.

Lei, Shanbhag, Pang and Sen (arXiv:1704.04578v2; Mathematics of Operations Research, 2020) analyze inexact proximal best-response schemes in three regimes: synchronous, randomized and asynchronous. This mission formalizes the asynchronous one (§5 and Appendix C). It adapts the partially asynchronous iterations of Bertsekas and Tsitsiklis (1989) to stochastic games with inexact, sampled best responses, and it gives an explicit bound on the number of stochastic gradient steps each player needs.

Setting

Player $i$ chooses $x_i$ in a nonempty compact convex set $X_i \subseteq \mathbb R^{n_i}$. A profile is $x = (x_1,\dots,x_N) \in X = \prod_i X_i$. Player $i$'s cost is $f_i(x_i, x_{-i}) = \mathbb E[\psi_i(x_i, x_{-i};\xi)]$, which is convex and twice continuously differentiable in a neighbourhood of $X$. A sampling oracle returns $\nabla_{x_i}\psi_i(x;\xi)$, whose second moment is at most $M_i^2$ (Assumption 1). A Nash equilibrium $x^*$ is a profile in which each $x^*_i$ minimizes $f_i(\cdot, x^*_{-i})$ over $X_i$.

For $\mu > 0$, the proximal best response of player $i$ to a profile $y \in X$ is

$$\hat x_i(y) = \operatorname*{argmin}_{x_i \in X_i}\Big[f_i(x_i, y_{-i}) + \tfrac{\mu}{2}\|x_i - y_i\|^2\Big].$$

The curvature constants $\zeta_{i,\min} = \inf_{x\in X}\lambda_{\min}(\nabla^2_{x_i}f_i(x))$ and $\zeta_{ij,\max} = \sup_{x\in X}\|\nabla^2_{x_ix_j}f_i(x)\|$ define the matrix $\Gamma$ with $\gamma_{ii} = \mu/(\mu+\zeta_{i,\min})$ and $\gamma_{ij} = \zeta_{ij,\max}/(\mu+\zeta_{i,\min})$. Assumption 5 (strict diagonal dominance) asks $\zeta_{i,\min} > \sum_{j\ne i}\zeta_{ij,\max}$. It makes $a_\infty = \|\Gamma\|_\infty$, the maximum absolute row sum, smaller than one.

The asynchronous scheme (Algorithm 3) runs on a deterministic schedule. At time $k$ the players in $I_k$ update. Player $i \in I_k$ sees the outdated profile $y^i_k = (x_{1,k-\tau_{i1}(k)},\dots,x_{N,k-\tau_{iN}(k)})$ and computes $x_{i,k+1} \in X_i$ with

$$\mathbb E\big[\|x_{i,k+1} - \hat x_i(y^i_k)\|^2 \mid \mathcal F_k\big] \le \alpha_{i,k}^2 .$$

The other players keep their strategies. Assumption 4 requires every player to update at least once in every $B_1$ consecutive times, and every delay to be at most $B_2$. The accuracy is $\alpha_{i,k} = \eta^{\beta_{i,k}}$, where $\beta_{i,k}$ counts player $i$'s updates so far. The inexact response is computed by $j_{i,k} = \lceil Q_i/\eta^{2(k+1)}\rceil$ projected stochastic gradient steps (43), with step size $1/(\mu(t+1))$ and $Q_i = 2M_i^2/\mu^2 + 2D_{X_i}^2$. Write $n_0 = \lceil B_2/B_1\rceil$, $\rho = (\max\{a_\infty,\eta\})^{1/(n_0+1)}$ and $c = \rho^{1/B_1}$.

Formalization targets

Goal: Theorem 3, (45)

Let $q \in (c,1)$, $D \ge 1/(e\ln(q/c))$, $\epsilon > 0$, and

$$\hat\epsilon = \frac{\epsilon}{C+D}\,\rho^{\frac{B_1-1}{B_1}} < 1,$$

where $\mathbb E\|x_{i,0}-x^*_i\|^2 \le C^2$. After $K = \lceil \ln(1/\hat\epsilon)/\ln(1/q)\rceil$ major iterations, $\max_i \mathbb E\|x_{i,K}-x^*_i\| \le \epsilon$, and player $i$ has taken at most

$$\ell^{(1)}_i(\eta) = \frac{Q_i}{\eta^4\ln(1/\eta^2)}\Big(\frac1{\hat\epsilon}\Big)^{\frac{\ln(1/\eta^2)}{\ln(1/q)}} + \Big\lceil\frac{\ln(1/\hat\epsilon)}{\ln(1/q)}\Big\rceil$$

projected gradient steps.

Milestones

In the order the proof uses them:

• the $\Gamma$-contraction (5) of the proximal best response;
• the fixed-point identity $x^*_i = \hat x_i(x^*)$;
• $a_\infty < 1$ under Assumption 5;
• its expected $\infty$-norm form (40), $\mathbb E\|\hat x_i(y)-x^*_i\| \le a_\infty\max_j\mathbb E\|y_j-x^*_j\|$;
• the one-step recursion (C.2) and the delay step (C.3) of Appendix C;
• Lemma 2, $zc^z \le Dq^z$;
• Lemma 7, the rate

$$\max_i\mathbb E\|x_{i,k}-x^*_i\| \le (C+k)\rho^{\lfloor k/B_1\rfloor},\qquad \max_i\mathbb E\|x_{i,k}-x^*_i\| \le \rho^{-\frac{B_1-1}{B_1}}(C+D)q^k;$$

• Lemma 8, the $Q_i/(t+1)$ mean-square error of the inner stochastic approximation loop;
• the summation bound (30).

Significance

Theorem 3 makes the cost of asynchrony explicit. Bounded delays and a bounded update window enter only through the rate per window, $\max\{a_\infty,\eta\}^{1/(n_0+1)}$. The overall effort stays polynomial in $1/\epsilon$, and the paper's Table 1 summarizes the exponent as $2B_1(1+\lceil B_2/B_1\rceil)+\delta$ for a suitable choice of $q$. The result connects classical partially asynchronous fixed-point theory with the sample-complexity analysis of stochastic approximation. Lemma 7 holds for any inexact solver that achieves the accuracy (38), not only for the stochastic gradient loop, so it applies to other subproblem solvers as well.

The paper proves these results by hand. As far as is known, no part of them has been machine-checked: there is no formal treatment of stochastic Nash games, of proximal best-response maps, or of asynchronous iterations with delays in Mathlib or on this platform. A formalization would check the induction over windows in Appendix C, whose index bookkeeping has several printed slips. It would also make precise which properties of the delays the argument needs.

Difficulty

The obvious argument does not carry over from the synchronous case. There, one step of the scheme contracts the whole error vector by $a$ in one norm. Here a step updates only some players, and each of them uses information up to $B_2$ steps old. No single step contracts anything. The proof has to show that every window of $B_1$ steps contracts the worst-case expected error by a factor $\rho$, with the delays absorbed into the root $1/(n_0+1)$. This requires a nested induction with case distinctions on the window position (Appendix C). The analysis also mixes three layers: a deterministic contraction of the exact best response; conditional expectations, Jensen's inequality and adaptedness for the inexact responses; and an $O(1/t)$ stochastic-approximation bound for the inner loop, which in turn needs strong convexity, the first-order optimality conditions and nonexpansiveness of the projection.

Formalization scope

Players are indexed by Fin N. Player $i$'s space is EuclideanSpace ℝ (Fin (n i)), and costs are functions of the whole profile: $f_i(z, y_{-i})$ is f i (Function.update y i z). The projection $\Pi_{X_i}$ is any map satisfying the published predicate SpectralProjGrad.Shared.IsProjOnto. The proximal best response is a map constrained by an argmin predicate on $X$. $\zeta_{i,\min}$ and $\zeta_{ij,\max}$ are Rayleigh-quotient infima and suprema of second Fréchet derivatives, and $\|\Gamma\|_\infty$ is the maximum absolute row sum. The probability space carries a filtration $(\mathcal F_k)$ to which the iterates are adapted. The inner-loop $\sigma$-algebras $\sigma\{\mathcal F_k,\xi^{[t-1]}_{i,k}\}$ are parameters satisfying the inclusions the proof uses. Conditional expectations are Mathlib's condExp.

Statement repairs and implicit hypotheses, each recorded in the item it affects:

• Deterministic delays. Assumption 4(c) allows random delays, but step (C.5) of the proof bounds an expectation at a random past time by the maximum over past times. That step is valid only when the delays do not depend on the iterates. The delays here are deterministic functions $\tau_{ij}(k) \le k$ with $\tau_{ii}(k) = 0$.
• Oracle second moment. Lemma 8 prints $\psi_i$ for $\nabla_{x_i}\psi_i$, and its hypothesis $\mathbb E[\|\nabla_{x_i}\psi_i\|^2\mid\cdot] = \|\nabla_{x_i}f_i\|^2$ forces zero noise. The bound $\le M_i^2$ that the proof uses replaces it.
• Regularity. Joint $C^2$ regularity of $f_i$ is assumed, which the mixed Hessian blocks in $\Gamma$ need, and $X_i$ is nonempty.
• Constants. Theorem 3 assumes $C \ge 0$ and $\hat\epsilon < 1$. Its "$D \ge /\ln((q/c)^e)$" is read as $D \ge 1/(e\ln(q/c))$, as in Lemma 7.
• Step count. Theorem 3 counts the steps over player $i$'s update times; the proof's bound is for the larger sum over all times.

The special case $B_1 = 1$, $B_2 = 0$ of Theorem 3, Corollary 3 (cyclic updates) and Theorem 4 are not stated.

The goal cannot be met trivially. The schedule is a parameter, not "every player at every step". The sampled gradients may be genuinely random, since the second-moment hypothesis is an inequality. $\hat x$ is tied to $f_i$ by its argmin property, and $x^*$ is a Nash equilibrium. Each expectation in a conclusion is of a bounded measurable quantity, so it cannot vanish by non-integrability.

The development needs the following:

• the contraction (5), which the paper only cites from Facchinei and Pang (2009, §12.6.1) and which uses the mean-value theorem along segments in $X$;
• strong-convexity optimality conditions on convex sets;
• nonexpansiveness of Euclidean projections;
• conditional Jensen and tower arguments;
• an integer-index induction over windows.

The projection and strong-convexity lemmas, and (5) itself, are reusable for the synchronous and randomized missions of this series. Proofs of individual milestones, or of general Mathlib-level facts such as the first-order optimality condition over a convex set, are welcome.

Selected references

• J. Lei, U. V. Shanbhag, J.-S. Pang, S. Sen, On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games, arXiv:1704.04578v2, 2018; Mathematics of Operations Research, 2020, https://doi.org/10.1287/moor.2018.0986. https://arxiv.org/abs/1704.04578v2
• D. P. Bertsekas, J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice Hall, 1989 (reference [9] of the paper).
• F. Facchinei, J.-S. Pang, Nash equilibria: the variational approach, in Convex Optimization in Signal Processing and Communications, Cambridge University Press, 2009 (reference [19] of the paper).
• I. Abada, G. de Maere d'Aertrycke, Y. Smeers, On the multiplicity of solutions in generation capacity investment models with incomplete markets, Mathematical Programming 165(1):5–69, 2017 (reference [1] of the paper).

Motivation

A retailer that decides which products to put on a shelf, or an airline that decides which fare classes to open, faces an assortment problem: the set of products offered changes which product a customer buys, and the firm wants the offer set that maximizes expected revenue. When customers first pick a category (a brand, a store aisle, a flight time) and then a product within it, the standard choice model is the nested logit model of Williams (1977) and McFadden (1978). Real offer sets are constrained: a shelf section displays at most a fixed number of products, and that limit is set per category.

Gallego and Topaloglu (Management Science, 2014) study assortment optimization under the nested logit model when the assortment in each nest must satisfy a cardinality or a space constraint. Their method reduces the joint problem over all nests to a small linear program, provided that each nest admits a short list of candidate assortments that always contains an optimal solution of a one-parameter single-nest subproblem. This mission formalizes the cardinality case, where the paper shows such a list of $O(n^2)$ candidates exists. For a single nest and the multinomial logit model, the cardinality-constrained problem was solved earlier by Rusmevichientong, Shen and Shmoys (Operations Research, 2010).

Setting

There are nests $i \in M$ and products $j \in N = \{1, \dots, n\}$ in every nest. Product $j$ of nest $i$ has a preference weight $v_{ij} > 0$ and a revenue $r_{ij} \in \mathbb{R}$. An assortment of nest $i$ is a subset $S_i \subseteq N$ (the paper writes it as a vector $S_i \in \{0,1\}^n$; the empty assortment is $\bar 0$). The total preference weight and the expected revenue of nest $i$ given that the customer chooses it are

$$V_i(S_i) = \sum_{j \in S_i} v_{ij}, \qquad R_i(S_i) = \frac{\sum_{j \in S_i} v_{ij} r_{ij}}{V_i(S_i)},$$

with $R_i(\bar 0) = 0$. Under cardinality constraints the feasible assortments of nest $i$ are

$$\mathcal C_i = \Bigl\{ S_i \in \{0,1\}^n : \sum_{j \in N} S_{ij} \le c_i \Bigr\},$$

where $c_i \in \mathbb{N}$ is the maximum number of products that can be offered in nest $i$.

For a parameter $u \ge 0$, the paper's single-nest problem (7) is

$$\max_{S_i \in \mathcal C_i} \; V_i(S_i)\,\bigl(R_i(S_i) - u\bigr).$$

By identity (8), its objective equals $\sum_{j \in S_i} v_{ij}(r_{ij} - u)$, so under cardinality constraints (7) is the unit-weight knapsack problem (9)

$$\max\Bigl\{ \sum_{j \in N} v_{ij}(r_{ij} - u)\, x_{ij} : \sum_{j \in N} x_{ij} \le c_i,\ x_{ij} \in \{0,1\} \Bigr\}.$$

The utility lines of the products are $f_{ij}(u) = v_{ij}(r_{ij} - u)$ for $j \in N$, together with $f_{i0}(u) = 0$.

Formalization targets

Goal: Theorem 5 (p. 17)

For every nest $i$ there is a collection $\{A_i^t : t \in \mathcal T_i\} \subseteq \mathcal C_i$, fixed before $u$ is chosen, with

$$|\mathcal T_i| \le (n+1)^2,$$

such that for every $u \ge 0$ some $A_i^t$ is an optimal solution of problem (7):

$$V_i(A_i^t)\bigl(R_i(A_i^t) - u\bigr) \ge V_i(S_i)\bigl(R_i(S_i) - u\bigr) \quad \text{for all } S_i \in \mathcal C_i.$$

The paper states $|\mathcal T_i| = O(n^2)$. The goal pins this to $(n+1)^2$, which the paper's count of the intersection points of the utility lines supports, and leaves the exact constant unfixed beyond that.

Milestones

1. Identity (8), p. 15. $V_i(S_i)(R_i(S_i) - u) = \sum_{j \in S_i} v_{ij}(r_{ij} - u)$ for every assortment and every $u$.
2. Greedy solves (9), p. 16. A set made of products with positive utility, chosen in decreasing order of utility, up to $c_i$ products, is optimal for (9).
3. Order and signs determine the optimum, pp. 16–17. If two values $u, u'$ order the utilities $\{f_{ij}\}$ the same way and give them the same signs, then the optimal solutions of (9) at $u$ and at $u'$ coincide.

Significance

Combined with the paper's Theorem 4 (candidates containing an optimal solution of (7) for every $u \ge 0$ contain an optimal combination for the full problem) and Theorem 2 (the best combination of candidates is found by a linear program), Theorem 5 shows that the nested logit assortment problem with per-nest cardinality limits is solved exactly by a linear program with $1+m$ variables and $O(mn^2)$ constraints. The same parametric argument, in which a one-dimensional parameter $u$ sweeps the line and the combinatorial optimum changes only at intersection points of finitely many lines, recurs in the paper's treatment of space constraints and of joint assortment and pricing.

The result is proved in the paper; it has no machine-checked proof. A formal proof also makes explicit two points the paper leaves to the reader: that a solution optimal on an open interval of $u$ remains optimal at its endpoints, and how ties between utilities are handled.

Difficulty

The parameter $u$ ranges over an uncountable set, and the number of feasible assortments, $\sum_{k \le c_i}\binom{n}{k}$, is exponential in $n$ when $c_i$ grows with $n$. Taking the candidates to be all of $\mathcal C_i$ satisfies everything except the size bound, and choosing a different collection for each $u$ satisfies the size bound trivially. The content is the uniform bound with the collection chosen first. The step that needs care is passing from "the optimum does not change inside an interval between breakpoints" to a statement covering every $u \ge 0$, including the breakpoints themselves, where ties occur and the greedy choice is not unique.

Formalization scope

• Products are Fin n (0-based); assortments are Finset (Fin n) and $\bar 0$ is ∅; $c_i$ is a natural number.
• The instance is the published NestedLogitVariants.LP.Instance, with V, R from NestedLogitVariants.LP.Model. That model carries a within-nest no-purchase weight vnp i; every statement assumes vnp i = 0, which is this paper's model, so V I i S = ∑ j ∈ S, I.v i j. The paper's extension $V_i(S_i) = v_{i0}\mathbf 1(S_i \ne \bar 0) + \sum_j v_{ij} S_{ij}$ (p. 15) is not formalized.
• Positive preference weights $v_{ij} > 0$ are stated as a hypothesis (the paper's derivation $v_{ij} = e^{\bar u_{ij}/\gamma_i}$ makes them positive but the page does not restate it). Revenues are arbitrary reals; no ordering or sign is assumed.
• $R_i(\bar 0) = 0$ by Lean's $x/0 = 0$, which is the paper's convention.
• Problem (7) involves neither the dissimilarity parameters $\gamma_i$ nor $v_0$; the statements are per nest.
• The local definition module ConstrNestedLogit.Card.Knapsack defines $f_{ij}$, the objective of (9), and optimality for (7) and (9) over $\mathcal C_i$.

The goal cannot be satisfied by an unbounded collection ($A = \mathcal C_i$ is excluded by the bound $(n+1)^2$), by a collection chosen after $u$ (the collection is quantified first), or by a special case of the constraint: $c_i$ is arbitrary, and the optimal member must beat every assortment of $\mathcal C_i$, not only the other candidates.

Contributions welcome: proofs of the three milestones and the goal; a general lemma that finitely many affine functions of one real variable keep a fixed weak order and sign pattern between consecutive pairwise intersection points, which is reusable for the paper's §5 and §6 and for other parametric optimization results.

Selected references

• G. Gallego and H. Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science 60(10), 2014. https://doi.org/10.1287/mnsc.2014.1931 (authors' manuscript of September 11, 2013).
• H. C. W. L. Williams, On the formation of travel demand models and economic evaluation measures of user benefit, Environment and Planning A 9(3), 1977. https://doi.org/10.1068/a090285
• D. McFadden, Modeling the choice of residential location, in A. Karlqvist et al. (eds.), Spatial Interaction Theory and Planning Models, North-Holland, 1978.
• P. Rusmevichientong, Z.-J. M. Shen and D. B. Shmoys, Dynamic assortment optimization with a multinomial logit choice model and capacity constraint, Operations Research 58(6), 2010. https://doi.org/10.1287/opre.1100.0866
• K. Talluri and G. van Ryzin, Revenue management under a general discrete choice model of consumer behavior, Management Science 50(1), 2004. https://doi.org/10.1287/mnsc.1030.0147

Motivation

A retailer chooses which products to offer, knowing that what customers buy depends on what is on the shelf. In the nested logit model (Williams 1977) products are grouped into nests, and a customer first picks a nest (or leaves) and then a product inside it. Choosing the offer set to maximize expected revenue is the assortment problem. In practice each nest carries its own limit: at most $c_i$ products (a cardinality constraint) or a shelf of size $c_i$ (a space constraint). Gallego and Topaloglu (2014) show that the problem with cardinality constraints is solvable in polynomial time, and that the problem with space constraints, which is NP-hard, admits approximation guarantees.

The paper's method has two parts. The first (Theorem 2, mission 1 of this series) finds, by a small linear program, the best assortment that can be stitched together from given candidate assortments in each nest. The second, which this mission formalizes, says when such candidates are good enough: it reduces the multi-nest problem to a family of single-nest problems with a linear objective, one for each threshold $u \ge 0$. The authors call the two results the pivot of their approach; every later section of the paper (cardinality, space, joint pricing, the approximation scheme) invokes Theorem 4.

Setting

There are nests $M = \{1, \dots, m\}$ and products $N = \{1, \dots, n\}$. Product $j$ in nest $i$ has preference weight $v_{ij} > 0$ and revenue $r_{ij} \in \mathbb R$ (no sign is assumed); the no-purchase option has weight $v_0 > 0$; nest $i$ has a dissimilarity parameter $\gamma_i \in (0, 1]$. An assortment in nest $i$ is a set $S_i \subseteq N$; the empty assortment is written $\bar 0$. Define

$$V_i(S_i) = \sum_{j \in S_i} v_{ij}, \qquad R_i(S_i) = \frac{\sum_{j \in S_i} r_{ij} v_{ij}}{V_i(S_i)} \quad (R_i(\bar 0) = 0),$$

and the expected revenue per customer of the assortment $(S_1, \dots, S_m)$,

$$\Pi(S_1, \dots, S_m) = \frac{\sum_{i \in M} V_i(S_i)^{\gamma_i} R_i(S_i)}{v_0 + \sum_{i \in M} V_i(S_i)^{\gamma_i}}.$$

Each nest has a set $\mathcal C_i$ of feasible assortments, and problem (1) is

$$Z^* = \max_{(S_1, \dots, S_m) \in \mathcal C_1 \times \dots \times \mathcal C_m} \Pi(S_1, \dots, S_m), \tag{1}$$

with optimal solution $(S^*_1, \dots, S^*_m)$. For a threshold $u \ge 0$, problem (7) of nest $i$ is

$$\max_{S_i \in \mathcal C_i} \Big\{ V_i(S_i)\,\big(R_i(S_i) - u\big) \Big\}, \tag{7}$$

whose objective equals $\sum_{j \in S_i} v_{ij}(r_{ij} - u)$ and so is linear in the assortment. An $\alpha$-approximate solution of (7) at $u$ is some $\hat S_i \in \mathcal C_i$ with $\alpha V_i(\hat S_i)(R_i(\hat S_i) - u) \ge V_i(S_i)(R_i(S_i) - u)$ for every $S_i \in \mathcal C_i$. A candidate collection of nest $i$ is a set $\{A^t_i : t \in \mathcal T_i\} \subseteq \mathcal C_i$.

Formalization targets

Goal: Theorem 4 (p. 15)

Let $\alpha \ge 1$. If, for every nest $i$, the candidate collection $\{A^t_i : t \in \mathcal T_i\}$ contains an $\alpha$-approximate solution of (7) for every $u \ge 0$, then there is $(\hat S_1, \dots, \hat S_m)$ with each $\hat S_i$ a candidate and

$$\alpha\, \Pi(\hat S_1, \dots, \hat S_m) \ge Z^*.$$

The collection is fixed before $u$; the conclusion holds for any constraint family, any $\alpha \ge 1$ and any $\gamma_i \in (0, 1]$.

Milestones

1. Inequality (6) (p. 13): with $\hat V_i = V_i(\hat S_i)$, $V^*_i = V_i(S^*_i)$, $\hat R_i = R_i(\hat S_i)$, $R^*_i = R_i(S^*_i)$, for a nest with $R^*_i > Z^*$,

$$\alpha \hat V_i(\hat R_i - Z^*) \ge \big(\gamma_i V^*_i + \alpha(1 - \gamma_i)\hat V_i\big)(R^*_i - Z^*).$$

2. The subgradient inequality of $u^{\gamma}$ (p. 13): for $\gamma \in (0, 1]$, $\alpha \ge 1$, $u \ge 0$, $\hat u > 0$,

$$u^{\gamma} \le \hat u^{\gamma - 1}\big(\gamma u + (1 - \gamma)\hat u\big) \le \hat u^{\gamma - 1}\big(\gamma u + \alpha(1 - \gamma)\hat u\big).$$

3. The claim of Lemma 3's proof (pp. 13–14): $\alpha \hat V_i^{\gamma_i}(\hat R_i - Z^*) \ge (V^*_i)^{\gamma_i}(R^*_i - Z^*)$ for all $i \in M$.
4. Lemma 3 (p. 13): with $u^*_i = \max\{Z^*, \gamma_i Z^* + (1 - \gamma_i)R_i(S^*_i)\}$, if $\alpha \ge 1$ and $\alpha V_i(\hat S_i)(R_i(\hat S_i) - u^*_i) \ge \max_{S_i \in \mathcal C_i} V_i(S_i)(R_i(S_i) - u^*_i)$ for all $i$ (inequality (5)), then $\alpha \Pi(\hat S_1, \dots, \hat S_m) \ge Z^*$.

Milestones 1–3 are steps of the proof of Lemma 3, in the order the proof uses them; Lemma 3 holds at the single, unknown thresholds $u^*_i$, and Theorem 4 is its threshold-free form.

Significance

The result. Theorem 4 turns the combinatorial problem (1), whose objective couples all nests through a ratio and through the powers $V_i^{\gamma_i}$, into a family of single-nest problems with a linear objective, one per threshold. A candidate collection that is good for every threshold is then fed to the linear program of Theorem 2, with $1 + m$ variables and $1 + \sum_i |\mathcal T_i|$ constraints. The paper builds an exact collection of $O(n^2)$ candidates per nest under cardinality constraints (Theorem 5), a factor-$2$ and a factor-$1/(1-\epsilon)$ collection under space constraints (§5), an exact collection for joint assortment and pricing (§6), and a polynomial-time approximation scheme (Theorem 9); each of these rests on Theorem 4. The paper also notes (p. 15) that the argument uses only $V_i(\bar 0) = 0$, so it extends to a within-nest no-purchase option of the form $V_i(S_i) = v_{i0}\mathbf 1(S_i \ne \bar 0) + \sum_j v_{ij}$; that extension is not formalized here.

Formalizing it. The result is proved in the paper; it has no machine-checked proof. A formal proof supplies the reduction that the other missions of this series (cardinality, space, pricing, the approximation scheme) need to turn their per-nest statements into guarantees for problem (1). The related criterion of Davis, Gallego and Topaloglu (2014, Theorem 1), already on the platform for the unconstrained problem, is a different route to a factor $\alpha$ and does not imply Theorem 4.

Difficulty

The obvious approach compares the approximate and the optimal assortment nest by nest, but the objective is not separable: $\Pi$ is a ratio, and each nest enters through $V_i^{\gamma_i}$, not $V_i$. Problem (7) has no power $\gamma_i$, so a solution that is good for (7) is not obviously good for the nest's contribution $V_i^{\gamma_i}(R_i - Z^*)$. The threshold $u^*_i$ at which the comparison works depends on $Z^*$ and $S^*_i$, which are unknown, and it is not $Z^*$ itself when $\gamma_i < 1$. A further subtlety is the empty assortment: a nest offering nothing has $V_i = 0$, where the factor $\hat V_i^{\gamma_i - 1}$ is not finite, so the case split on the sign of $R^*_i - Z^*$ and the positivity of $\hat V_i$ have to be handled before any division.

Formalization scope

• The instance, $V_i$, $R_i$, $V_i^{\gamma_i}$ and $\Pi$ are the published NestedLogitVariants.LP.Model (referenced, not redefined). Every statement sets its within-nest no-purchase weight to zero (I.vnp i = 0), so V is the paper's $V_i$.
• Nests are any finite type; products are Fin n, indexed from $0$. Assortments are Finset (Fin n); $\bar 0$ is ∅. $R_i(\bar 0) = 0$ via $x/0 = 0$, the paper's convention. Powers are Real.rpow, with $0^{\gamma} = 0$ for $\gamma > 0$.
• Feasible sets are an arbitrary family C : ι → Set (Finset (Fin n)), covering cardinality and space constraints alike. Candidate collections are sets A i ⊆ C i; the index set $\mathcal T_i$ is not named and no finiteness is required.
• $Z^*$ is revenue I Sstar for a hypothesised optimum Sstar (IsOptimal1: feasible, and at least the revenue of every feasible assortment), not a defined maximum.
• Added hypotheses, each disclosed in its item: $v_0 > 0$ and $v_{ij} > 0$ (standing positivity of the model, not restated in the paper); $\bar 0 \in \mathcal C_i$ (the proof evaluates (5) at $\bar 0$; it holds for both constraint types of the paper); $\alpha \ge 1$ in Theorem 4 (the standing context of Lemma 3). The subgradient inequality is stated for $\hat u > 0$, because $0^{\gamma - 1}$ is $0$ in Lean but infinite on paper.
• Revenues are arbitrary reals; no ordering and no sign is assumed, and none is needed.
• Ruled out as trivializing: $\gamma_i = 1$ for all nests (the multinomial logit, where the concavity step disappears), a single nest, $\alpha = 1$ only, the hypothesis of Theorem 4 only at $u = u^*_i$ (that is Lemma 3), and candidates chosen after $u$.
• Welcome contributions: proofs of the milestones in order; lemmas $\Pi(\bar 0, \dots, \bar 0) = 0$ and $v_0 Z^* = \sum_i V_i(S^*_i)^{\gamma_i}(R_i(S^*_i) - Z^*)$ (the latter is a milestone of mission 1 and may be proved inline); a reusable tangent-line inequality for Real.rpow with exponent in $(0, 1]$.

Selected references

• G. Gallego and H. Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science 60(10), 2014; authors' manuscript of September 11, 2013, pp. 7–8, 13–15. https://doi.org/10.1287/mnsc.2014.1931
• J. M. Davis, G. Gallego and H. Topaloglu, Assortment Optimization Under Variants of the Nested Logit Model, Operations Research 62(2), 2014. https://doi.org/10.1287/opre.2014.1256
• H. C. W. L. Williams, On the Formation of Travel Demand Models and Economic Evaluation Measures of User Benefit, Environment and Planning A 9(3), 1977. https://doi.org/10.1068/a090285
• P. Rusmevichientong, Z.-J. M. Shen and D. B. Shmoys, Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint, Operations Research 58(6), 2010. https://doi.org/10.1287/opre.1100.0866

Motivation

A retailer that sells products in several categories has to decide which products to put on display. Under the nested logit model a customer first picks a category (a nest) and then a product inside it, so offering a product changes the purchase probabilities of every other product. Choosing the assortment that maximizes expected revenue is assortment optimization, a standard problem of revenue management. Gallego and Topaloglu (Management Science, 2014) study it when every nest carries its own constraint on the assortment. With a limit on the shelf space of each nest the problem is NP-hard even for a single nest, so the paper builds an assortment that is guaranteed to earn at least half of the optimum.

A worst-case factor of two says little about one concrete instance. For its computational study (§7.1) the paper therefore needs, instance by instance, a number that is provably at least the optimal expected revenue, and it obtains one from a linear program, (13), whose constraints come from the linear programming relaxations of knapsack problems. Proposition 7 (Online Supplement A, p. 33) proves that this linear program does give an upper bound. This mission formalizes that proposition.

Setting

There are nests $M = \{1, \dots, m\}$ and products $N = \{1, \dots, n\}$ in each nest. Product $j$ of nest $i$ has a preference weight $v_{ij} > 0$ and a revenue $r_{ij}$ (any real number); $v_0$ is the preference weight of buying nothing, and $\gamma_i \in (0, 1]$ is the dissimilarity parameter of nest $i$. For an assortment $S_i \subseteq N$ of nest $i$ put

$$V_i(S_i) = \sum_{j \in S_i} v_{ij}, \qquad R_i(S_i) = \frac{\sum_{j \in S_i} v_{ij} r_{ij}}{V_i(S_i)},$$

with $R_i(\bar 0) = 0$ for the empty assortment $\bar 0$. The expected revenue of $(S_1, \dots, S_m)$ is

$$\Pi(S_1, \dots, S_m) = \frac{\sum_{i \in M} V_i(S_i)^{\gamma_i} R_i(S_i)}{v_0 + \sum_{i \in M} V_i(S_i)^{\gamma_i}}.$$

Under space constraints product $j$ of nest $i$ uses $w_{ij}$ units of space and nest $i$ has capacity $c_i$, with $w_{ij} \le c_i$ for every product, so the feasible assortments are $\mathcal C_i = \{S_i : \sum_{j \in S_i} w_{ij} \le c_i\}$. Problem (1) is $Z^* = \max\{\Pi(S_1, \dots, S_m) : S_i \in \mathcal C_i \ \forall i\}$.

For a scalar $u$, the knapsack problem (10) of nest $i$ maximizes $\sum_j v_{ij}(r_{ij} - u) x_j$ over $x \in \{0,1\}^n$ with $\sum_j w_{ij} x_j \le c_i$. Its linear programming relaxation allows $x \in [0,1]^n$. The paper partitions $u \ge 0$ into finitely many intervals $\mathcal I_i^g$, $g \in \mathcal G_i$, on each of which one vector $x_i^g$ solves the relaxation. For a fractional vector $x$ it writes $V_i(x) = \sum_j v_{ij} x_j$ and $R_i(x) = \sum_j v_{ij} r_{ij} x_j / V_i(x)$.

The linear program (13) in the variables $(z, y_1, \dots, y_m)$ is

$$\min\Big\{ z : v_0 z \ge \sum_{i \in M} y_i,\ \ y_i \ge V_i(x_i^g)^{\gamma_i}\big(R_i(x_i^g) - z\big)\ \ \forall g \in \mathcal G_i,\ i \in M \Big\}.$$

Formalization targets

Goal: Proposition 7

If $(\hat z, \hat y)$ is an optimal solution of (13), then

$$\hat z \ge Z^*.$$

Milestones

1. Every feasible $(z, y)$ of (13) has $y_i \ge 0$ for all $i$ (p. 33).
2. For a nonempty $S \in \mathcal C_i$ with $R_i(S) > z$, $\hat u = \gamma_i z + (1 - \gamma_i) R_i(S)$, and a nonzero optimal solution $x$ of the relaxation at $\hat u$:

$$V_i(x)^{\gamma_i}\big(R_i(x) - z\big) \ge V_i(S)^{\gamma_i}\big(R_i(S) - z\big)\quad\text{(pp. 33–34).}$$

3. Under the same hypotheses, the zero vector is not an optimal solution of the relaxation at $\hat u$ (p. 34).
4. The claim of the proof: every feasible $(z, y)$ of (13) satisfies $y_i \ge V_i(S_i)^{\gamma_i}(R_i(S_i) - z)$ for every nest $i$ and every feasible assortment (pp. 33–34).

Significance

The proposition makes the optimality gaps of §7 meaningful: the expected revenue of any assortment that respects the space constraints, divided by the optimal value of (13), is a certified lower bound on its fraction of $Z^*$. The bound is a linear program with $1 + m$ variables and one constraint per interval solution, so it can be solved for instances where $Z^*$ itself, an NP-hard quantity, cannot be computed.

The result is proved in the paper; no machine-checked proof of it is known. Formalizing it checks the interplay of three ingredients that the paper treats briefly: the role of the interval solutions $x_i^g$ (only their feasibility and their optimality for every $u \ge 0$ matter), the extension of $V_i$ and $R_i$ to fractional vectors, and the concavity of $V \mapsto V^{\gamma_i}$. A related but different program is Davis, Gallego and Topaloglu's LP (16) (NestedLogitVariants.LP.lp16_upper_bound), which bounds the unconstrained problem by another argument.

Difficulty

The constraints of (13) are indexed by finitely many fractional vectors, while $Z^*$ is attained at an integral assortment that need not be among them. The obvious argument, that (13) is a relaxation of an exact linear-programming formulation of problem (1), does not apply: no constraint of (13) involves $S_i^*$ directly. The link between the two has to be made nest by nest, through the knapsack relaxations at values of $u$ that depend on the unknown optimum, and the fractional vectors $x_i^g$ are compared with integral assortments through the nonlinear map $V \mapsto V^{\gamma_i}$.

Formalization scope

The formalization references the published nested logit model NestedLogitVariants.General.Model (instance, $V_i$, $R_i$, $V_i^{\gamma_i}$, $\Pi$) and NestedLogitVariants.General.Relaxation (the unit box and the term $F$ of the constraints of (13)). The conventions are:

• nests are any finite type; products are Fin n, indexed from $0$; assortments are finite sets of products and $\bar 0$ is the empty set;
• the within-nest no-purchase weights of the published model are set to $0$ in every statement, which makes $V_i$ the paper's $V_i(S_i) = \sum_{j \in S_i} v_{ij}$;
• $v_0 > 0$, $v_{ij} > 0$ and $w_{ij} > 0$ are added hypotheses, and the paper's $w_{ij} \le c_i$ (p. 8) is kept wherever the proof needs the zero vector to be feasible for the relaxation; revenues are arbitrary reals; $\gamma_i \in (0, 1]$ as on p. 8;
• real powers are Real.rpow, and $a/0 = 0$, which gives $R_i(\bar 0) = 0$ as in the paper and makes the constraint term at $x = 0$ equal to $0$;
• the vectors $\{x_i^g\}$ are replaced by any finite sets $X_i$ of vectors that are feasible for the relaxation and contain an optimal solution of it for every $u \ge 0$, the family fixed before $u$; this is what the proof uses, and the paper's interval solutions satisfy it;
• $Z^*$ is the revenue of a hypothesised optimal assortment of problem (1) under the space constraints; an optimal solution of (13) is a feasible pair with minimal $z$.

The statement is not to be trivialized: setting $\gamma_i = 1$, taking $X_i$ to be the whole box $[0,1]^n$ (not a finite set and not LP (13)), assuming $0 \in X_i$, or proving the bound for one particular feasible point are all excluded.

A complete development needs the concavity (tangent-line) inequality of $V \mapsto V^{\gamma}$ at a positive point and elementary facts about fractional knapsack relaxations; both are reusable. Proofs of the milestones and of the goal are welcome.

Selected references

• G. Gallego and H. Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science, 2014 (authors' manuscript of September 11, 2013). https://doi.org/10.1287/mnsc.2014.1931
• J. M. Davis, G. Gallego and H. Topaloglu, Assortment Optimization Under Variants of the Nested Logit Model, Operations Research, 2014. https://doi.org/10.1287/opre.2014.1256
• P. Rusmevichientong, Z.-J. M. Shen and D. B. Shmoys, A PTAS for Capacitated Sum-of-Ratios Optimization, Operations Research Letters, 2009. https://doi.org/10.1016/j.orl.2009.03.002

Motivation

An assortment planner chooses which products to offer to arriving customers. When products are grouped into nests, a customer's choice of nest depends on all the assortments offered at once. A planner may nevertheless be able to generate only a short list of promising assortments for each nest. The remaining task is to choose one assortment from each list so that their combined expected revenue is as large as possible. Testing every combination requires a number of evaluations equal to the product of the list sizes. Gallego and Topaloglu show that the choice can instead be described through a linear program whose number of constraints grows with the sum of those sizes; this is Theorem 2 of their 2014 paper, in the authors' September 11, 2013 manuscript, pp. 10–12.

This mission isolates that selection result. Later parts of the paper address how to construct useful candidate lists under cardinality, space, and pricing constraints. Here the candidates are already given, and the question is which combination earns the most. The result matters whenever the candidate lists are much smaller than the space of all assortments: it makes the last step of those algorithms an exact optimization over the candidates, without enumerating their Cartesian product.

Setting

Let $M$ be a finite set of nests and $N$ a finite set of products available in each nest. An assortment $S_i\subseteq N$ is the set offered in nest $i$. Product $j$ in nest $i$ has preference weight $v_{ij}>0$ and revenue $r_{ij}\in\mathbb R$. The empty assortment is allowed. The main model has no within-nest no-purchase option, so its total offered weight is $V_i(S_i)=\sum_{j\in S_i}v_{ij}$. The conditional revenue in nest $i$ is $R_i(S_i)=\sum_{j\in S_i}v_{ij}r_{ij}/V_i(S_i)$, with $R_i(\varnothing)=0$ under the paper's $0/0=0$ convention.

The weight of no purchase outside the nests is $v_0>0$. Each nest has a dissimilarity parameter $\gamma_i\in(0,1]$. Its attraction weight is $V_i(S_i)^{\gamma_i}$. The expected revenue of a combined assortment $S=(S_i)_{i\in M}$ is

$$\Pi(S)=\frac{\sum_{i\in M}V_i(S_i)^{\gamma_i}R_i(S_i)} {v_0+\sum_{i\in M}V_i(S_i)^{\gamma_i}}.$$

For each nest, $A_i$ is a finite nonempty collection of candidate assortments. The paper obtains these from a feasible set $C_i$, which may impose a cardinality or space constraint; Theorem 2 compares only combinations drawn from the supplied candidates. Equation (2) defines a real scalar $\widehat z$ through the maximum, over $A_i$ separately, of $V_i(S_i)^{\gamma_i}(R_i(S_i)-z)$. Problem (3) selects a maximizing candidate $\widehat S_i$ in each nest at that scalar. Linear program (4) has decision variables $(z,y_i)_{i\in M}$, minimizes $z$, and imposes $v_0z\ge\sum_i y_i$ and $y_i\ge V_i(S_i)^{\gamma_i}(R_i(S_i)-z)$ for every $i$ and every $S_i\in A_i$.

Formalization targets

The goal is the exact candidate-selection claim of Theorem 2. If $(\widehat z,\widehat y)$ minimizes $z$ among all feasible pairs of program (4), and every $\widehat S_i$ solves problem (3) at $\widehat z$, then

$$\Pi(S_1,\ldots,S_m)\le\Pi(\widehat S_1,\ldots,\widehat S_m) \qquad\text{for every }S_i\in A_i.$$

The milestones record three statements from pp. 11–12: equation (2) has a unique real root; the balance equation and its inequality form characterize the expected revenue of a fixed assortment; and Lemma 1 identifies the root as the best revenue attainable from candidate combinations while showing that local maximizers attain it. They separate the paper's numerical characterization of the best candidate revenue from its LP formulation. The target does not prescribe how the candidate lists were generated or claim that the selected combination is best among assortments outside those lists.

Significance

The theorem gives an exact, compact choice rule for assembling nestwise candidates. If the lists contain useful assortments under the original constraints, their best combination can be selected through program (4). The rest of the paper establishes candidate-generation and approximation results under particular constraint families; the stitching theorem supplies the common final selection step for those results. A larger candidate list may improve the obtainable revenue, but its Cartesian product need not be searched explicitly. The authors' manuscript, p. 12, states that program (4) has $1+m$ variables and $1+\sum_i|T_i|$ constraints when the candidates are indexed by $T_i$.

Formalizing the theorem yields a reusable statement about the interaction of a fractional revenue objective, independent nestwise candidate families, and a shared scalar LP. The published Prove2Me definition NestedLogitVariants.LP.Model already supplies the instance, $V_i$, $R_i$, $\Pi$, and the feasibility and optimality predicates for program (4). Its previously proved lp4_opt_binding concerns an equality at an LP optimum under ordered, nonnegative revenues; it does not contain Theorem 2's maximality claim under this paper's revenue assumptions. The four statements in this mission are draft targets awaiting machine-checked proofs.

Difficulty

Optimizing a candidate independently in every nest at an arbitrary value of $z$ does not generally optimize the combined revenue: the revenue denominator couples all nests. Likewise, an LP-feasible value need not be its minimum, and using such a value in problem (3) does not establish the theorem. The substantive assertion is that choosing the local maximizers at the optimal LP value solves the combined selection problem. The unique-root statement also needs care at empty assortments, where a nest contributes zero attraction and the conditional revenue uses the paper's $0/0$ convention.

Formalization scope

Nests are represented by any finite type, and products by Fin n, indexed $0,\ldots,n-1$ rather than the paper's $1,\ldots,n$. A Boolean offer vector is represented by Finset (Fin n); $\overline 0$ is the empty finset. Each $A_i$ is a finite set of such assortments. There is no single-nest or $\gamma_i=1$ specialization, and no substitution of all possible assortments for the supplied candidates. The LP assumption is its full minimum objective property, not merely feasibility. The imported LP4Optimal predicate uses a set of candidates, supplied by coercing each finite $A_i$ to a set.

The source's main model is selected from the imported general instance by setting $v_{i0}=0$. In the paper's later extension, $V_i(S_i)=v_{i0}\mathbf1(S_i\ne\overline0)+\sum_jv_{ij}S_{ij}$; this is different from the imported unmodified $v_{i0}+\sum_jv_{ij}S_{ij}$ when $S_i=\overline0$, so the extension is outside this mission. Positive $v_0$ and product weights are stated explicitly to keep the probability denominator positive and to match the model's preference interpretation. Revenues remain arbitrary real numbers: neither an order nor nonnegativity is assumed. The dissimilarities satisfy the paper's $(0,1]$ range. The paper states candidate feasibility $A_i^t\in C_i$; this mission's claim holds for arbitrary candidate collections because no step compares against $C_i$. The definitions of revenue and LP feasibility are imported, so useful contributions include proofs of the balance characterization, the root result, Lemma 1, and the final LP statement.

Selected references

• Guillermo Gallego and Huseyin Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science, 2014. DOI: 10.1287/mnsc.2014.1931; authors' manuscript, September 11, 2013, pp. 7–12.
• James Davis, Guillermo Gallego, and Huseyin Topaloglu, Assortment Optimization under Variants of the Nested Logit Model, Operations Research, 2014. DOI: 10.1287/opre.2014.1256. The published Prove2Me model definition used here comes from this line of work.

Motivation

A retailer that sells through a choice model decides two things at once: which products to put on the shelf and at what price. Under the nested logit model of discrete choice, products are grouped into nests (brands, categories, store sections); a customer first picks a nest, or leaves without buying, and then picks a product inside the nest. The price of a product changes its attractiveness, and the attractiveness of every product changes the purchase probabilities of all the others, so assortment and price interact.

Gallego and Topaloglu (Management Science, 2014) study assortment optimization under the nested logit model with constraints on what may be offered in each nest. Their §6 treats joint assortment and pricing when each product can be sold at one of finitely many price levels. Earlier work on nested logit pricing, by Li and Huh (2011) and Gallego and Wang (2011), assumes that a product priced at $p_{ik}$ has preference weight $e^{\alpha_{ik}-\beta_{ik}p_{ik}}$. With a finite menu of price levels, no parametric link between price and preference weight is required, and the prices can be restricted to a range or a grid (for example $49.99, $59.99, …), as retail practice often demands.

Setting

There are $m$ nests $M$. In each nest $i$ there are $p$ products $P=\{1,\dots,p\}$, and each product can be offered at one of $b$ price levels $B=\{1,\dots,b\}$. Offering product $k$ at level $l$ in nest $i$ earns the price $\rho_{ik}^l$ and gives the product the preference weight $\nu_{ik}^l>0$. The relation between $\rho_{ik}^l$ and $\nu_{ik}^l$ is arbitrary.

Each pair (product, price level) is a virtual product. Nest $i$ has $n=pb$ virtual products $N=\{1,\dots,n\}$; $N_k\subseteq N$ is the set of the $b$ virtual products of product $k$, and the sets $N_k$ are disjoint. Virtual product $j\in N_k$ at level $l$ has revenue $r_{ij}=\rho_{ik}^l$ and preference weight $v_{ij}=\nu_{ik}^l$. An assortment of nest $i$ is a set $S_i\subseteq N$, and the feasible assortments are

$$\mathcal C_i=\Big\{S_i\in\{0,1\}^n:\ \sum_{j\in N_k}S_{ij}\le 1\ \ \forall k\in P\Big\},$$

so each product is offered at no more than one price, or not at all.

For an assortment $S_i$ write $V_i(S_i)=\sum_{j\in S_i}v_{ij}$ and $R_i(S_i)=\sum_{j\in S_i}r_{ij}v_{ij}/V_i(S_i)$, with $R_i(\emptyset)=0$. For a number $u\ge 0$, problem (7) of the paper is

$$\max_{S_i\in\mathcal C_i}\ V_i(S_i)\,\big(R_i(S_i)-u\big).$$

Its objective equals $\sum_{j\in S_i}f_{ij}(u)$ with $f_{ij}(u)=v_{ij}(r_{ij}-u)$; under $\mathcal C_i$ this is problem (12) of the paper.

Formalization targets

Goal: a small candidate collection per nest

For every nest $i$ there is a collection $\{A_i^t:t\in\mathcal T_i\}\subseteq\mathcal C_i$, fixed independently of $u$, with

$$|\mathcal T_i|\le p\,(b+1)^2+1,$$

such that for every $u\ge 0$ some $A_i^t$ is an optimal solution of problem (7). The page states $|\mathcal T_i|=O(pb^2)$; the explicit bound is the count of intervals left by the intersection points of the lines $f_{ij}$, $j\in N_k\cup\{0\}$, with $f_{i0}=0$.

Milestones

1. Selection rule (p. 24). For fixed $u$, the assortment that in each $N_k$ offers one virtual product with the largest coefficient $f_{ij}(u)$ when that coefficient is positive, and nothing otherwise, solves problem (7) over $\mathcal C_i$.
2. Order and signs (p. 24). If at $u$ and $u'$ the values $\{f_{ij}:j\in N_k\cup\{0\}\}$ are in the same weak order for every $k$, then the optimal solutions of (7) at $u$ and at $u'$ coincide.

Significance

The paper's Theorem 4 shows that a collection containing an optimal solution of (7) for every $u\ge 0$ yields an optimal solution of the full nested logit problem, and its Theorem 2 that the best combination of candidates solves a linear program with $1+m$ variables and $1+\sum_i|\mathcal T_i|$ constraints. With the goal above, the joint assortment and pricing problem is solved exactly by a linear program of polynomial size, $O(mpb^2)$ constraints, for arbitrary price–weight relations. This is one of the paper's three headline results.

The result is proved in the paper in prose, without a numbered statement. No machine-checked proof of it is known. The mission fixes the constant hidden in $O(pb^2)$, states the feasible set exactly, and isolates the two steps of the argument as separate statements.

Difficulty

The naive candidate set is all of $\mathcal C_i$, which has $(b+1)^p$ members; the content of the goal is the polynomial bound with the collection fixed before $u$. The argument must handle ties between coefficients, lines that coincide or never cross, intersection points at negative $u$, and the boundary points between intervals, where several assortments are optimal at once. The count must be made per product: a count over all pairs of virtual products gives $O(n^2)=O(p^2b^2)$ and misses the stated bound.

Formalization scope

• Nests are a type ι; virtual products are Fin n and products Fin p, both 0-based. $N_k$ is the fiber of a map prod : Fin n → Fin p; the hypothesis that every fiber has exactly $b$ elements is IsVirtualProductMap prod b. The price level of a virtual product is left implicit.
• Prices and weights are the published NestedLogitVariants.LP.Instance fields r i j and v i j; there is no parametric price–weight relation and no ordering of prices.
• Assortments are Finset (Fin n); the empty assortment is allowed and has objective $0$.
• The published $V$ is $v_{i0}+\sum_{j\in S}v_{ij}$. Every statement assumes $v_{i0}=0$, so it equals the paper's $V_i(S_i)$. The paper's extension $V_i(S_i)=v_{i0}\mathbf 1(S_i\neq\emptyset)+\sum_jv_{ij}S_{ij}$ (p. 15) is not formalized.
• Positive weights $v_{ij}>0$ are an explicit hypothesis; the paper takes them for granted.
• Optimality in problem (7) is over $\mathcal C_i$ only, for $u\ge 0$ (0 ≤ u).
• The bound $p(b+1)^2+1$ is in terms of $p$ and $b$, not $n$, and the collection is chosen before $u$. Statements with $b=1$ (pure assortment), a logit price–weight relation, no bound, or a collection chosen after $u$ are trivial or different theorems and are ruled out.

A complete development needs the reduction of (7) to the linear objective (identity (8)), the per-product optimality of problem (12), and a counting argument for the intersection points of finitely many lines on $[0,\infty)$. The last one is reusable beyond this mission: the paper's cardinality-constrained result uses the same kind of argument. Proofs of the milestones, and lemmas such as (8) for the published V and R, are welcome.

Selected references

• G. Gallego and H. Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science 60(10), 2014. https://doi.org/10.1287/mnsc.2014.1931 (authors' manuscript of Sept. 11, 2013, §6, pp. 23–25).
• H. Li and W. T. Huh, Pricing Multiple Products with the Multinomial Logit and Nested Logit Models: Concavity and Implications, Manufacturing & Service Operations Management 13(4), 2011. https://doi.org/10.1287/msom.1110.0342
• G. Gallego and R. Wang, Multi-Product Price Optimization and Competition under the Nested Logit Model with Product-Differentiated Price Sensitivities, Operations Research 62(2), 2014 (working paper 2011). https://doi.org/10.1287/opre.2013.1249
• J. M. Davis, G. Gallego and H. Topaloglu, Assortment Optimization Under Variants of the Nested Logit Model, Operations Research 62(2), 2014. https://doi.org/10.1287/opre.2014.1256