Revenue Management and Choice Models

Completed

Operations Research Probability·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 1: Independence of Irrelevant Alternatives with a Universal Benchmark Yields Logit Selection ProbabilitiesResearch Paper

Motivation

The conditional logit model is the workhorse of discrete choice analysis: it is used to forecast travel mode shares, to estimate demand for differentiated products, and, in operations research, as the multinomial logit (MNL) choice model behind assortment optimization and revenue management. Its selection probabilities have the form $P(x\mid s,B) = e^{v(s,x)}/\sum_{y\in B} e^{v(s,y)}$ . Daniel McFadden's 1974 chapter Conditional Logit Analysis of Qualitative Choice Behavior gave the model two behavioural foundations, one of which is the subject of this mission: the logit form is a consequence of a single axiom on how choice probabilities change when the set of available alternatives changes.

That axiom is Luce's choice axiom, which McFadden calls Independence of Irrelevant Alternatives (IIA): the relative odds of choosing one alternative over another do not depend on which other alternatives are present. Luce (1959) introduced it; McFadden (1974, §I) showed how, together with positivity and a mild condition on which alternative sets can occur, it yields the conditional logit form with a "utility indicator" $v(s,x)$ shared by all alternative sets.

Timeline. Luce, Individual Choice Behavior (1959): the choice axiom and its ratio-scale representation. McFadden (1974, pp. 109–110): the derivation in the econometric setting with measured attributes $s$ , the binary-odds identities (5)–(10), and footnote 3, which removes an extra axiom (Axiom 3) by a universal benchmark alternative. McFadden (1974, pp. 111–112): the companion random-utility characterization by extreme-value shocks, treated in mission 2 of this series.

Setting

Let $X$ be the universe of objects of choice and $S$ the universe of vectors of measured attributes of decision-makers. An alternative set is a finite set $B\subseteq X$ ; a designated family of finite sets is the family of possible alternative sets. The selection probability $P(x\mid s,B)$ is the probability that an individual drawn at random from the population, with attributes $s$ and facing $B$ , chooses $x\in B$ . For every $s$ and possible $B$ , $x\mapsto P(x\mid s,B)$ is a probability vector on $B$ . Whenever $x\neq y$ belong to a possible set, the pair $\{x,y\}$ is possible too, so binary choices are defined.

Axiom 1 (IIA). For all possible $B$ , all $s$ and all $x,y\in B$ : $P(x\mid s,\{x,y\})P(y\mid s,B) = P(y\mid s,\{x,y\})P(x\mid s,B)$ .
Axiom 2 (Positivity). $P(x\mid s,B)>0$ for all possible $B$ , all $s$ , all $x\in B$ .
Binary probabilities. $p_{xy}=P(x\mid s,\{x,y\})$ for $x\neq y$ , and $p_{xx}=\tfrac12$ by definition.
The function $V$ . $V(s,x,z)=\log(p_{xz}/p_{zx})$ .
Universal benchmark. An alternative $z$ such that $B\cup\{z\}$ is possible whenever $B$ is.

In Lean these are IsSelectionProb, PairsPossible, Axiom1, Axiom2, binProb, altSetV and IsUniversalBenchmark in the namespace McFadden1974.IIA.

Formalization targets

Goal: footnote 3 with Equation (12)

Under Axioms 1 and 2 and a universal benchmark $z$ , with $v(s,x)=V(s,x,z)$ , for every $s$ , every possible $B$ (containing $z$ or not) and every $x\in B$ :

P(x\mid s,B) = \frac{e^{v(s,x)}}{\sum_{y\in B} e^{v(s,y)}}.

The function $v$ is the same for all alternative sets; this is what distinguishes the goal from Equation (10).

Milestones, in the paper's order

Equation (5): for $x\neq y$ in $B$ with $P(x\mid s,B)>0$ , Axiom 1 gives $P(x\mid s,\{x,y\})>0$ and $\dfrac{P(y\mid s,\{x,y\})}{P(x\mid s,\{x,y\})}=\dfrac{P(y\mid s,B)}{P(x\mid s,B)}$ .
Equations (6)–(7): $P(y\mid s,B)=\dfrac{p_{yx}}{p_{xy}}P(x\mid s,B)$ and $1=\Big(\sum_{y\in B}\dfrac{p_{yx}}{p_{xy}}\Big)P(x\mid s,B)$ .
Equation (8): $P(x\mid s,B)=1\big/\sum_{y\in B}(p_{yx}/p_{xy})$ .
Equation (9): $\dfrac{p_{yx}}{p_{xy}}=\dfrac{p_{yz}/p_{zy}}{p_{xz}/p_{zx}}$ for $x,y,z$ in a possible set.
Equation (10): for a benchmark $z\in B$ , $P(x\mid s,B)=e^{V(s,x,z)}\big/\sum_{y\in B}e^{V(s,y,z)}$ .

Significance

The result. The goal identifies a testable axiom on choice probabilities, IIA, with a parametric functional form, the conditional logit model. It is what licenses the econometric specification $v(s,x)=\theta'z(s,x)$ estimated in the rest of McFadden's chapter, and it is the reason the MNL model is the default in assortment and pricing problems in operations research. It also makes the model's limitations precise: any population whose choices violate IIA (the auto/red-bus/blue-bus example on p. 113 of the chapter) cannot be logit.

Formalizing it. The result is classical and proved on paper. No machine-checked statement of it exists on the platform, which has the logit form only as a definition (soft-max, MNL revenue) and IIA only in Arrow's social-choice sense, a different axiom about preference aggregation. This mission produces a formal statement of the derivation with every standing assumption explicit, including two the paper leaves implicit: that selection probabilities are normalized on binary sets, and that binary subsets of possible sets are possible.

Difficulty

The algebra is elementary; the difficulty is bookkeeping of where each axiom may be applied. Axioms 1 and 2 are assumed only on possible alternative sets. Equation (10) needs the benchmark to lie in the alternative set, and the naive argument "pick $z\in B$ as benchmark" produces a function $V(s,x,z)$ that depends on the set through the choice of $z$ . The goal requires a single $v$ for all sets, including sets that do not contain $z$ , where neither Equation (10) nor the axioms on $B$ alone say anything about $z$ . A second subtlety is the diagonal: $\{x,x\}=\{x\}$ , so $p_{xx}$ is set to $\tfrac12$ by definition rather than read off a singleton choice.

Formalization scope

Alternatives form a type X with decidable equality, alternative sets are Finset X, possible sets are a Set (Finset X), and selection probabilities are a real-valued function P : S → Finset X → X → ℝ. Only values P s B x with x ∈ B and B possible are constrained; no statement depends on the others. binProb sets the diagonal to 1/2. altSetV uses Real.log, which is 0 on non-positive arguments; under Axiom 2 on the binary sets its argument is always positive where it is used.

The probability-vector hypothesis on every possible set, binary sets included, is part of every statement: without it the zero function satisfies Axiom 1 vacuously and Equations (7)–(8) fail. The goal is stated with the explicit $v(s,x)=V(s,x,z)$ , never as "for each $B$ there is a $v$ ", which would only restate (10).

Nothing beyond Mathlib's finite sums, Real.exp and Real.log is needed. Proofs of the milestones and of the goal are welcome, as is a formal statement of the auto/bus example or of the converse (logit selection probabilities satisfy Axioms 1 and 2).

Selected references

D. McFadden, Conditional logit analysis of qualitative choice behavior, in P. Zarembka (ed.), Frontiers in Econometrics, Academic Press, New York, 1974, pp. 105–142. https://eml.berkeley.edu/reprints/mcfadden/zarembka.pdf
R. D. Luce, Individual Choice Behavior: A Theoretical Analysis, Wiley, New York, 1959. https://doi.org/10.1037/14396-000

7 thms2 active usersReviewed

Completed

Convex Optimization Linear Optimization Statistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 4: Existence of the Maximum Likelihood Estimate Is Decided by a Quadratic ProgramResearch Paper

Why a likelihood maximum needs a diagnostic

The conditional logit model assigns probabilities to choices among alternatives whose observable attributes differ from trial to trial. A fitted parameter vector is usually obtained by maximizing a log-likelihood. For a finite data set, however, maximization need not produce a finite vector: some directions in parameter space can keep improving the likelihood while their length grows without bound. McFadden identifies a condition that rules out these directions and then gives a quadratic program that can test the condition. This mission formalizes that test, Lemma 4 of the published 1974 chapter Conditional Logit Analysis of Qualitative Choice Behavior.

The chapter develops a statistical model from observable choice data and addresses the existence of a maximum likelihood estimate in Lemma 3. Lemma 4 turns its existence condition into a finite optimization problem. The diagnostic matters because an optimization routine returning increasingly large parameter estimates is not, by itself, evidence that a finite maximizer exists. The result specifies a mathematical test tied to the observed choice counts and the attributes of the alternatives.

Choice experiments and weighted differences

There are $N\geq1$ trials. Trial $n$ offers $J_n$ alternatives, indexed by $i$ and $j$ . Alternative $i$ has an attribute vector $z_{in}\in\mathbb R^K$ , and $S_{in}$ counts how many times it was selected in that trial. Each trial has at least two alternatives and $R_n=\sum_iS_{in}>0$ observations. The vector $\theta\in\mathbb R^K$ is the unknown parameter of the underlying conditional logit model. Equation (16) assigns alternative $i$ a probability proportional to $\exp(z_{in}\cdot\theta)$ , with the probabilities normalized over the alternatives in the same trial McFadden, pp. 113–114, equation (16).

For the test, define the weighted difference

w_{nij}=S_{in}(z_{jn}-z_{in})\in\mathbb R^K.

It is indexed by every trial and every ordered pair of alternatives, including $i=j$ and alternatives whose observed count is zero. Such terms simply produce zero vectors. Keeping them in the index set makes the formal statement agree with the chapter's quantifiers and its quadratic program.

Axiom 5, called full rank in the chapter, says that the rows obtained by subtracting each trial's probability weighted mean attribute vector from its alternative attributes have rank $K$ . Equivalently, the vectors $z_{jn}-z_{in}$ span $\mathbb R^K$ ; the probability weights in that mean are strictly positive and sum to one. Axiom 6 says that no nonzero direction $\gamma\in\mathbb R^K$ satisfies $w_{nij}\cdot\gamma\leq0$ for every ordered index triple. These are conditions on the same observed experiment, but they serve different roles: full rank concerns the attribute geometry, while Axiom 6 also uses the choice counts McFadden, p. 116, Axioms 5–6.

Formalization targets

Lemma 4: a quadratic-programming test

Let $Q$ be the set of feasible vectors

Q=\left\{y=\sum_{n=1}^{N}\sum_{i,j=1}^{J_n}\alpha_{ijn}w_{nij}: \alpha_{ijn}\geq1\text{ for all }n,i,j\right\}.

The mission's goal is the equivalence in Lemma 4:

\text{Axiom 6 holds} \quad\Longleftrightarrow\quad \min_{y\in Q}y\cdot y=0.

The right side means that the program attains a value of zero. An infimum of zero without an attained feasible point would be a weaker statement and would not express the lemma. The three milestones follow the three assertions in the printed proof: a zero minimum implies Axiom 6; an interior origin in the cone generated by the $w_{nij}$ gives positive coefficients and a zero minimum; and a noninterior origin gives a separating direction that violates Axiom 6 McFadden, p. 117, Lemma 4 and equation (22).

What the result provides

Lemma 3 of the chapter states that Axiom 6 characterizes the existence of a vector maximizing the conditional-logit log-likelihood under the preceding axioms. Lemma 4 gives a finite quadratic-programming criterion for that same condition. It therefore allows the model's existence question to be checked from data before treating a numerical optimizer's output as an estimate McFadden, pp. 116–117, Lemmas 3–4.

The paper proves these results. The work here is to produce machine-checkable statements for the finite-dimensional data, the two axioms, the feasible set, and the equivalence, followed by proofs in the solver stage. The cone and separation milestones can support later formalizations of existence conditions in other finite exponential-family models, provided their hypotheses and signs are checked anew. This mission does not claim a general theorem for all such models.

Why the equivalence is delicate

The tempting diagnostic is to ask whether a numerical solve returns a small objective value. That does not settle the mathematical question: the objective's infimum could approach zero without the feasible set containing a zero vector. The paper's conclusion is about a minimum, so attainment must remain visible in the formal statement. There is also a distinction between positive coefficients in a cone representation and the printed constraints $\alpha_{ijn}\geq1$ in equation (22). Both conditions must appear in their proper places.

The full-rank condition alone does not ensure that the vectors $w_{nij}$ span the attribute space if a trial has no observed choices. The section describes $R_n$ repetitions of each trial, and the formal data require $R_n>0$ . This convention is needed for the strict-inequality claim in the first paragraph of Lemma 4's proof. The geometry also has to account for every ordered pair, even when its vector is zero; dropping these indices would alter the program stated in the chapter.

Formalization scope

Lean represents a nonempty set of trials by Fin N, alternatives in trial $n$ by Fin (J n), counts by natural numbers, and attributes by EuclideanSpace ℝ (Fin K). The count $R_n$ is the sum of observed choice counts. The model requires $J_n\geq2$ and $R_n>0$ for each trial. There is no extra assumption that $K>0$ : the zero-dimensional case is included and the equivalence has its ordinary degenerate meaning there.

Axiom 5 is encoded through the equivalent span of within-trial attribute differences. This removes the parameter dependent logit probabilities from a theorem that only uses rank. Axiom 6 retains exactly the nonpositive sign and every $n,i,j$ from the page. The feasible set uses coefficients at least one, while the auxiliary generated cone uses nonnegative coefficients. The quadratic objective is the square of the Euclidean norm. IsLeast on its image over the feasible set expresses an attained minimum, so the statement cannot be satisfied by a vacuous or unattained infimum.

The definition bundle and the three proof-step theorems are the mission's direct scope. A complete development needs finite-dimensional inner-product geometry, finite sums, a cone interior argument, and separation. The definitions of weighted differences and the feasible set are reusable for studying nearby existence tests. Contributions that prove the stated milestones or supply faithful finite-dimensional geometry for them are welcome; substitutions that weaken the coefficient constraint or the attainment claim do not establish Lemma 4.

Selected references

Daniel McFadden, “Conditional Logit Analysis of Qualitative Choice Behavior,” in P. Zarembka (ed.), Frontiers in Econometrics, Academic Press, 1974, pp. 105–142; especially pp. 113–117, Axioms 5–6, Lemmas 3–4, and equation (22). Book catalog search.

5 thms2 active usersReviewed

Operations Research Probability Statistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 5: The Maximum Likelihood Estimator Exists with Probability Tending to One and Is Consistent and Asymptotically NormalResearch Paper

Motivation

The conditional logit model is the workhorse of discrete choice analysis in econometrics, transportation planning, marketing and revenue management. An individual facing a finite set of alternatives picks alternative $i$ with probability proportional to $e^{z_i\theta}$ , where $z_i$ is a vector of observed attributes and $\theta$ an unknown parameter vector. Daniel McFadden's 1974 chapter, Conditional Logit Analysis of Qualitative Choice Behavior, derived this model from a theory of random utility maximization and set out how to estimate $\theta$ by maximum likelihood. McFadden received the 2000 Nobel Memorial Prize in Economic Sciences for his development of theory and methods for analyzing discrete choice.

Every confidence interval and hypothesis test computed from a fitted logit model rests on the large-sample theory in §III of that chapter: the maximum likelihood estimator exists with probability tending to one, converges to the true parameter, and is approximately normal with covariance given by the inverse information matrix. This mission formalizes that theory, Lemmas 5 and 6 of the paper, as proved in its Appendix.

Setting

Observations are indexed serially, $m = 0, 1, 2, \dots$ , as in the paper's Appendix ("Let m be a serial index of trials and repetitions"). Observation $m$ offers $J_m \ge 1$ alternatives, and alternative $i$ carries a vector $z_{im} \in \mathbb R^K$ of independent variables. For a parameter $\theta \in \mathbb R^K$ the selection probabilities are

P_{im}(\theta) = \frac{e^{z_{im}\theta}}{\sum_{j=1}^{J_m} e^{z_{jm}\theta}}, \qquad \bar z_m(\theta) = \sum_{i} P_{im}(\theta)\, z_{im}.

The data are generated at a true parameter $\theta^0$ : the chosen alternatives $Y_0, Y_1, \dots$ are independent random variables with $\Pr(Y_m = i) = P_{im}(\theta^0)$ . The log-likelihood of the first $q$ observations is $L^q(\theta) = \sum_{m<q}\log P_{Y_m m}(\theta)$ . The moment matrix of observation $m$ is

\Omega_m = \sum_{i} P_{im}(\theta^0)\,(z_{im}-\bar z_m)(z_{im}-\bar z_m)', \qquad \bar z_m = \bar z_m(\theta^0).

Axiom 7 asks that $J_m \le J_*$ and $|z_{im}| \le M$ uniformly, and that $\frac1q\sum_{m<q}\Omega_m$ converge to a positive definite matrix $\Omega$ . Axiom 6, for a given sample, asks that no nonzero $\gamma$ satisfy $(z_{jm} - z_{Y_m m})\gamma \le 0$ for all observed $m$ and all $j$ . A maximum likelihood estimator $\hat\theta^q$ is a measurable choice of a maximizer of $L^q$ , wherever one exists.

Formalization targets

Goal: Lemma 6

\hat\theta^q \xrightarrow{\Pr} \theta^0 \quad\text{and}\quad \sqrt q\,\Omega^{1/2}(\hat\theta^q - \theta^0) \xrightarrow{d} N(0, I_K) \qquad (q \to \infty).

Milestones

Axiom 7 implies Axiom 5 (the full-rank condition) in all sufficiently large samples.
Equation (42): $P_{im}(\theta) \ge 1/(J_* e^{2M|\theta|})$ .
Lemma 5: $\Pr(\text{Axiom 6 holds and } L^q \text{ attains its maximum}) \to 1$ .
Equation (43): the first three derivatives of $\log P_{im}$ are bounded by $2M$ , $4M^2$ , $8M^3$ .
Equation (46): each score $\nabla\log P_{Y_m m}(\theta^0)$ has mean zero.
Equation (47): each expected Hessian equals $-\Omega_m$ .
Consistency of $\hat\theta^q$ .
Equation (58): $q^{-1/2}\,\Omega^{-1/2}\sum_{m<q}\nabla\log P_{Y_m m}(\theta^0) \xrightarrow{d} N(0, I_K)$ .

Significance

The result. Lemma 6 is what licenses reading $\hat\theta^q$ as approximately $N(\theta^0, q^{-1}\Omega^{-1})$ , so that the diagonal of the inverse information matrix estimates the sampling variances and $q(\hat\theta^q-\theta^0)'\Omega(\hat\theta^q-\theta^0)$ is asymptotically $\chi^2_K$ . Lemma 5 complements it: in finite samples the likelihood can fail to have a maximum (the observations are then "explained" by a direction $\gamma$ of Axiom 6), and the lemma shows this failure is asymptotically negligible. The data are not identically distributed (each observation has its own alternatives), so the result is not an instance of the textbook i.i.d. maximum likelihood theorem.

Formalizing it. The results are proved in the paper, in outline. A machine-checked version adds: a complete proof of the existence part (Lemma 5), whose published argument is a sketch by induction over an infinite index set; a precise treatment of the estimator where no maximizer exists; the correction of two misprints in the published proof (the normalization $1/q$ in (58), which must be $1/\sqrt q$ , and a constant in (51)); and a multivariate Lindeberg–Feller central limit theorem for bounded, independent, non-identically distributed vectors, which the proof invokes and which is reusable well beyond this paper. No machine-checked proof of these results is known.

Difficulty

The obvious route, "the log-likelihood is concave, so its maximizer converges", needs a maximizer to exist, and in a finite sample it may not; the estimator is defined only on an event whose probability must first be shown to tend to one. Consistency then needs a uniform law of large numbers for the gradient on a sphere around $\theta^0$ , controlled by the third-derivative bound (43). Asymptotic normality needs a central limit theorem for independent but not identically distributed score vectors, with covariances $\Omega_m$ that converge only on average; the i.i.d. central limit theorem does not apply. Finally the random Hessian at an intermediate point must be shown to converge in probability, which ties the consistency result into the normality argument.

Formalization scope

Vectors live in EuclideanSpace ℝ (Fin K); $z\theta$ is the inner product, and all norms are Euclidean (footnote 11's sum-of-absolute-values norm is equivalent and gives the same qualitative axiom); derivative bounds use operator norms.
The paper's $N$ trials with $R_n$ repetitions are the special case of the serial indexing in which consecutive observations repeat their data; the sample size $\sum_n R_n$ is $q$ .
Axiom 7's limit (27) is taken in its serial form (48), with $P$ evaluated at $\theta^0$ .
The estimator is any measurable selection that maximizes $L^q$ whenever $L^q$ has a maximum, and is unconstrained otherwise. Requiring a maximizer for every sample would be unsatisfiable, since Axiom 6 fails with positive probability, and would make the goal vacuous; this convention rules that out.
Consistency is TendstoInMeasure. Asymptotic normality is TendstoInDistribution to a random vector whose law is stdGaussian. $\Omega^{1/2}$ is the positive semidefinite square root CFC.sqrt.
Needed infrastructure: derivatives of log-sum-exp, a law of large numbers for bounded independent vectors, and a multivariate Lindeberg–Feller theorem. Mathlib provides the one-dimensional i.i.d. central limit theorem only. Contributions of these general results as separate theorems are welcome.

Selected references

D. McFadden, Conditional logit analysis of qualitative choice behavior, in P. Zarembka (ed.), Frontiers in Econometrics, Academic Press, New York, 1974, pp. 105–142.
W. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, Wiley, 1966 (Lindeberg–Feller theorem, pp. 256–258).
C. R. Rao, Linear Statistical Inference and Its Applications, Wiley (cited by McFadden as Rao (1968), pp. 347–351, for the asymptotic $\chi^2$ test).

10 thms2 active usersReviewed

Operations Research Probability Statistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 2: Random Utility Maximizers Choose by Logit Exactly When Taste Shocks Are Extreme-Value DistributedResearch Paper

Motivation

The conditional logit model assigns to an alternative $i$ in a finite choice set the probability $e^{V_i}/\sum_j e^{V_j}$ , where $V_j$ is a "representative utility" built from observed attributes of the alternative and the decision maker. It is the workhorse of discrete choice econometrics, transportation demand forecasting, marketing and revenue management, where it underlies multinomial logit assortment and pricing models. Its appeal for applied work is computational; its appeal for economics is that it can be read as the aggregate behaviour of a population of utility maximizers. This mission formalizes the result that makes that reading exact: Lemmas 1 and 2 of D. McFadden, Conditional logit analysis of qualitative choice behavior (1974), which show that, under a mild regularity condition, logit choice probabilities arise from random utility maximization exactly when the idiosyncratic taste shocks follow the extreme value (Gumbel) distribution.

Timeline:

1959. J. Marschak gives a nonconstructive proof that i.i.d. extreme value shocks yield logit probabilities; R. D. Luce's choice axiom appears the same year.
1965. Luce and Suppes publish the constructive argument, attributed to E. Holman and A. Marley, that is reproduced as the proof of Lemma 1.
1974. McFadden proves the converse (Lemma 2): if i.i.d. shocks with a translation complete distribution produce logit probabilities, the distribution is extreme value.
Later. The random utility characterization was extended to correlated shocks (generalized extreme value models, McFadden 1978), which are not part of this mission.

Setting

An individual faces $J \ge 1$ alternatives with representative utilities $V_1, \dots, V_J \in \mathbb{R}$ . The utility of alternative $j$ is $U_j = V_j + \varepsilon_j$ , where the taste shocks $\varepsilon_1, \dots, \varepsilon_J$ are independent and identically distributed with a common law $\mu$ on $\mathbb{R}$ and distribution function $G(t) = \mu((-\infty, t])$ . The individual chooses the alternative of highest utility, so the selection probability of $i$ is (Equation (2) of the paper)

P_i(V) = \Pr\big[\varepsilon_j - \varepsilon_i < V_i - V_j \ \text{ for all } j \ne i\big],

computed under the product law of the shocks. The logit formula (Equation (12)) is $L_i(V) = e^{V_i}/\sum_{j=1}^J e^{V_j}$ . The extreme value law (Equation (13)) is $G(\varepsilon) = e^{-e^{-\varepsilon}}$ .

A law $\mu$ is translation complete if for every function $h$ of bounded total variation on $\mathbb{R}$ with $h(\pm\infty) = 0$ , the condition $\int h(e + a)\, d\mu(e) = 0$ for every real $a$ forces $h = 0$ outside a Lebesgue-null set. Laws whose characteristic function never vanishes, the extreme value law among them, are translation complete (footnote 5 of the paper).

In Lean the law is μ : Measure ℝ with [IsProbabilityMeasure μ], $G$ is ProbabilityTheory.cdf μ, the selection probability is selProb μ V i for V : Fin J → ℝ, and the logit formula is logitProb V i.

Formalization targets

Goal: the characterization

Fix a universe $X$ of alternatives with a representative utility map $u:X\to\mathbb R$ onto the real line. For a translation complete law $\mu$ normalized by $G(0) = e^{-1}$ ,

\Big(\text{for every finite }B\subseteq X,\ i\in B:\ P_i(B) = \frac{e^{u(i)}}{\sum_{j\in B} e^{u(j)}}\Big) \iff \Big(\forall \varepsilon \in \mathbb{R}:\ G(\varepsilon) = e^{-e^{-\varepsilon}}\Big).

The normalization only fixes the location of the shocks: without it the conclusion is the one-parameter family of Lemma 2 below.

Milestones

Equation (3) for i.i.d. shocks without atoms: $P_i(V) = \int \prod_{j \ne i} G(\varepsilon + V_i - V_j)\, dG(\varepsilon)$ .
The integrand of Lemma 1's proof: under (13), the density times the other distribution functions equals $e^{-\varepsilon} \exp\big(-e^{-\varepsilon} \sum_j e^{V_j - V_i}\big)$ .
Lemma 1: extreme value shocks give $P_i(V) = L_i(V)$ for every $J$ and $V$ .
The functional equation of Lemma 2's proof: $G(v - \log K) = G(v)^K$ for every positive integer $K$ and real $v$ .
Values at logarithms of rationals: with $\alpha = -\log G(0)$ , $\alpha > 0$ and $G(\log(K/L)) = e^{-\alpha L / K}$ for positive integers $K, L$ .
Lemma 2: $G(\varepsilon) = e^{-\alpha e^{-\varepsilon}}$ for some $\alpha > 0$ , and $G(0) = e^{-1}$ gives (13).

Significance

The result separates two readings of the logit formula. Lemma 1 shows that it is consistent with utility maximization; Lemma 2 shows that, within the class of i.i.d. additive random utility models with translation complete shocks, the extreme value law is the only one consistent with it. Consequences drawn from the random utility reading, such as the log-sum formula for expected maximum utility used in welfare analysis, therefore apply to logit models without further distributional assumptions inside that class. The same reading supports the interpretation of multinomial logit demand in assortment optimization and revenue management.

Both lemmas are proved in the paper and in later textbooks; neither is open. As far as a search of the Prove2Me catalog shows, neither has a machine-checked proof. The mission provides Lean statements of the random utility model with i.i.d. shocks, of translation completeness and of the extreme value law that later discrete choice formalizations can reuse.

Difficulty

Lemma 1 is a computation with the extreme value density; its formal cost lies in passing from the product-measure probability (2) to the iterated integral (3) and evaluating an improper integral. Lemma 2 is harder. The natural first idea is to differentiate the logit identity in the utilities and solve a differential equation for $G$ ; this requires a density, which Lemma 2 does not assume. Without a density, the only handle on $G$ is the logit identity itself, an equality of integrals against $dG$ that holds for every utility vector; turning such integral identities into pointwise information about $G$ is where the hypothesis of translation completeness enters, and it yields statements only outside a Lebesgue-null set, so one-sided continuity of distribution functions is needed to recover identities at every point. A second subtlety is that the paper's (14) is written with $G$ while the event (2) is strict, so with a general law the integrals involve left limits of $G$ .

Formalization scope

Alternatives are indexed by Fin J; the model is indexed by the utility vector, so the individual attributes $s$ and alternative attributes $x_j$ enter only through $V$ . The shocks have joint law Measure.pi (fun _ => μ), which is what "independently identically distributed" means; a general joint law is not allowed. The event in (2) uses strict inequalities, and the selection probability is defined for every law, with no density. Translation completeness quantifies over BoundedVariationOn h Set.univ with limits $0$ at both ends; such $h$ are bounded and measurable, so the integrals are genuine, and "measure zero" is Lebesgue measure.

Lemma 2's hypothesis is stated on every finite subset of the paper's alternative universe, with a surjective utility map. Distinct alternatives may have the same utility. The printed proof uses $K$ equal-utility alternatives, which surjectivity alone need not supply; proving the stated theorem requires an additional continuity argument. A trivializing formalization is ruled out: the selection probability is a genuine product-measure probability, and the hypotheses of the goal are met by the extreme value law, which is translation complete with $G(0) = e^{-1}$ .

A complete development needs: Fubini for Measure.pi over Fin J split at one coordinate; the Gumbel density and the improper integral $\int e^{-\varepsilon} e^{-c e^{-\varepsilon}} d\varepsilon = 1/c$ ; the facts that bounded-variation functions are bounded and measurable and that distribution functions are right-continuous with left limits. The integral representation (milestone 1) and the Gumbel computations are reusable in any random utility formalization. Proofs of the milestones, of the footnote-5 fact that the extreme value law is translation complete, and alternative proofs of Lemma 2 are welcome.

Selected references

D. McFadden, Conditional logit analysis of qualitative choice behavior, in P. Zarembka (ed.), Frontiers in Econometrics, Academic Press, New York, 1974, pp. 105–142.
J. Marschak, Binary choice constraints and random utility indicators, in K. Arrow, S. Karlin, P. Suppes (eds.), Mathematical Methods in the Social Sciences, Stanford University Press, 1960 (Stanford Symposium, 1959).
R. D. Luce and P. Suppes, Preference, utility, and subjective probability, in R. D. Luce, R. Bush, E. Galanter (eds.), Handbook of Mathematical Psychology, Vol. III, Wiley, 1965.
R. D. Luce, Individual Choice Behavior: A Theoretical Analysis, Wiley, 1959.
W. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, Wiley, 1966, p. 479.
D. McFadden, Modelling the choice of residential location, in A. Karlqvist et al. (eds.), Spatial Interaction Theory and Planning Models, North-Holland, 1978, pp. 75–96.

8 thms2 active usersReviewed

Completed

Convex Optimization Operations Research Statistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 3: The Conditional Logit Likelihood Has a Maximum Exactly When No Direction Makes Every Observed Choice Weakly BestResearch Paper

Motivation

The conditional logit model is the workhorse of discrete choice analysis in transportation, marketing, labour and industrial organization. McFadden's 1974 chapter derived it from a theory of population choice behaviour and showed how to estimate it by maximum likelihood; this line of work was recognized by his 2000 Nobel Prize in Economic Sciences, awarded for theory and methods of discrete choice analysis. Every applied logit estimation rests on a basic question: does the maximum likelihood estimate exist for the sample at hand? In small samples it may not. When one alternative is always chosen whenever it is available, the likelihood keeps increasing as a parameter tends to infinity, and numerical optimizers report diverging coefficients. This failure is known in the binary case as complete or quasi-complete separation. McFadden's Lemma 3 gives the exact condition, for the multinomial conditional logit model with general alternative sets, under which a maximizer exists.

Timeline. Berkson (1951, 1955) popularized binomial logit; multinomial versions were developed by Gurland (1960), Bloch (1967), Rassam (1971), McFadden (1968) and Theil (1969, 1970). McFadden (1974) stated the existence criterion for the conditional logit likelihood (Lemma 3) together with a quadratic-programming test for it (Lemma 4). Albert and Anderson (1984) later classified separation patterns for binary and multinomial logistic regression, and Haberman (1974) treated existence for log-linear models.

Setting

A choice experiment has $N \ge 1$ trials. Trial $n$ offers an alternative set of $J_n$ alternatives, indexed $i = 1,\dots,J_n$ , each described by an attribute vector $z_{in} \in \mathbb{R}^K$ (the values of $K$ specified functions of the individual's and the alternative's characteristics). Trial $n$ is repeated $R_n \ge 1$ times, and alternative $i$ is chosen $S_{in}$ times, so $R_n = \sum_{j} S_{jn}$ .

For a parameter $\theta \in \mathbb{R}^K$ , with $z_{in}\theta$ the inner product, the selection probabilities are

P_{in}(\theta) = \frac{e^{z_{in}\theta}}{\sum_{j=1}^{J_n} e^{z_{jn}\theta}} \qquad (16)

and the log-likelihood of the sample is

L(\theta) = C - \sum_{n=1}^N \sum_{i=1}^{J_n} S_{in} \log \sum_{j=1}^{J_n} e^{(z_{jn} - z_{in})\theta}, \qquad C = \sum_{n=1}^N \Big[\log R_n! - \sum_{j=1}^{J_n}\log S_{jn}!\Big]. \qquad (18)

Write $\bar z_n(\theta) = \sum_i z_{in}P_{in}(\theta)$ for the probability-weighted mean attribute vector of trial $n$ .

Axiom 5 (Full Rank). The $\big(\sum_n J_n\big)\times K$ matrix with rows $z_{in} - \bar z_n$ has rank $K$ .

Axiom 6. There is no nonzero $\gamma \in \mathbb{R}^K$ with $S_{in}(z_{jn} - z_{in})\gamma \le 0$ for all $i, j = 1,\dots,J_n$ and $n = 1,\dots,N$ . Equivalently, no nonzero direction makes every observed choice weakly best in its alternative set.

Formalization targets

Goal: Lemma 3

Under Axiom 5,

\big(\exists\, \hat\theta \in \mathbb{R}^K,\ \forall \theta,\ L(\theta) \le L(\hat\theta)\big) \iff \text{Axiom 6}.

Milestones

Equation (19): the gradient $\partial L/\partial\theta = \sum_n \sum_j (S_{jn} - R_nP_{jn}) z_{jn}$ .
Equation (20): the Hessian $\partial^2L/\partial\theta\,\partial\theta' = -\sum_n R_n \sum_j (z_{jn} - \bar z_n)'P_{jn}(z_{jn} - \bar z_n)$ .
$L$ is concave, and every critical point is a global maximizer.
A Hessian that is nonsingular everywhere makes $L$ strictly concave with at most one maximizer.
Axiom 5 holds at $\theta$ if and only if the Hessian at $\theta$ is negative definite.
Necessity: under Axiom 5, a maximizer forces Axiom 6.
Equation (21): under Axiom 6, $b(\gamma) = \max_n \max_{i,j} S_{in}(z_{jn}-z_{in})\gamma$ has a positive lower bound $b^*$ on the unit sphere.
The bound $L(\theta) - C \le -b^*|\theta|$ for all $\theta$ .
Sufficiency: Axiom 6 gives a maximizer.

Significance

Lemma 3 tells the practitioner when the conditional logit maximum likelihood estimate exists, before any numerical optimization is attempted. It is a linear-inequality condition on the data alone, so it can be checked by linear or quadratic programming (Lemma 4 of the same paper). The existence of the estimator is also the first step of McFadden's asymptotic theory: Lemma 5 shows that Axiom 6 holds with probability tending to one, and Lemma 6, consistency and asymptotic normality, concerns the estimator whose existence Lemma 3 characterizes. The concavity and Hessian formulas (19)–(20) are the basis of the Newton–Raphson computation of the estimator and of its asymptotic covariance matrix.

The result has been proved since 1974 and is classical. To our knowledge it has no machine-checked proof; Mathlib has no statement about the existence of logit or softmax-regression maximum likelihood estimates. Formalizing it produces a verified existence criterion for the multinomial logit likelihood, verified gradient and Hessian formulas for log-sum-exp likelihoods with repeated observations, and a verified link between full column rank and strict concavity.

Difficulty

The likelihood is concave, and concave functions on $\mathbb{R}^K$ need not attain their supremum. Concavity alone therefore gives nothing, and existence must come from a growth condition. The obvious approach, "the likelihood is bounded above by $C$ , hence attains its maximum", fails: $L$ is bounded but can approach its supremum only at infinity, which is exactly the separation case. Sufficiency needs a quantitative rate at which $L$ decreases, uniform over all directions; a direction-by-direction argument does not suffice. Necessity requires strict concavity, which is where Axiom 5 and the requirement that every trial be observed enter. A trial with $R_n = 0$ can supply the rank of Axiom 5 while contributing nothing to $L$ , so with such a trial necessity fails. The calculus part, (19)–(20), involves differentiating sums of log-sum-exp terms over dependent index types and identifying the result with a weighted covariance operator.

Formalization scope

Representation. $\mathbb{R}^K$ is EuclideanSpace ℝ (Fin K), so $|\theta| = (\theta'\theta)^{1/2}$ is the Euclidean norm and $z\theta$ is the inner product ⟪z, θ⟫. Trials are Fin N, alternatives of trial $n$ are Fin (J n), and the counts $S_{in}$ are natural numbers.
Data structure. The structure Data K bundles $N$ , $J$ , $z$ , $S$ and the standing assumptions $N \ge 1$ and $R_n = \sum_i S_{in} \ge 1$ for every trial; these make the trial and alternative index sets nonempty.
Axioms 1–4 are built in. The model is the logit form (16) with $v$ linear in $\theta$ (Axiom 4), so "Suppose Axioms 1–5 hold" becomes "Data plus Axiom 5".
Axiom 5 is read at every $\theta$ . The row space of the matrix does not depend on $\theta$ .
Hessian. The Hessian is the Fréchet derivative of the gradient vector field (19), as a continuous linear map.
The maximizer is global over all of $\mathbb{R}^K$ . Neither a local maximizer nor " $L(\hat\theta) \ge L(0)$ " is acceptable as the goal; that would make it trivial.
Infrastructure. Gradients and Hessians of log-sum-exp with dependent finite index types; positive definiteness from full column rank; attainment of the maximum of a coercive continuous function on a finite-dimensional space. The calculus lemmas are reusable for any multinomial logit or softmax likelihood. Missions 4 and 5 of this series reuse the same model. Contributions of general log-sum-exp lemmas, independent of this mission's definitions, are welcome.

Selected references

D. McFadden, Conditional logit analysis of qualitative choice behavior, in P. Zarembka (ed.), Frontiers in Econometrics, Academic Press, New York, 1974, pp. 105–142. https://eml.berkeley.edu/reprints/mcfadden/zarembka.pdf
A. Albert and J. A. Anderson, On the existence of maximum likelihood estimates in logistic regression models, Biometrika 71(1), 1984, pp. 1–10. https://doi.org/10.1093/biomet/71.1.1
S. J. Haberman, The Analysis of Frequency Data, University of Chicago Press, 1974.
J. Berkson, Maximum likelihood and minimum χ² estimates of the logistic function, Journal of the American Statistical Association 50, 1955, pp. 130–162. https://doi.org/10.1080/01621459.1955.10501255

12 thms3 active usersReviewed

Operations Research Optimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 2: With Dissimilarity Parameters at Most One and Fully-Captured Nests, a Nested-by-Revenue Assortment in Every Nest Is OptimalResearch Paper

Motivation

A retailer choosing which products to display, or an airline choosing which fare classes to open, solves an assortment optimization problem: pick the set of offered products that maximizes expected revenue when customers choose among what is offered according to a discrete choice model. Under the multinomial logit model the answer has a simple form: an optimal assortment consists of the few highest-revenue products (Talluri and van Ryzin, 2004). The multinomial logit model, however, forces every pair of products to compete in the same way. The nested logit model relaxes this by grouping products into nests (brands, store sections, departure times) and letting a customer first choose a nest and then a product inside it.

Davis, Gallego and Topaloglu (Operations Research, 2014; DOI 10.1287/opre.2014.1256) study how much of the multinomial logit structure survives under the nested logit model. Their first answer is the theorem this mission targets: when the nest dissimilarity parameters are at most one and no customer who chose a nest leaves it without buying, offering the top products of each nest is still optimal. The other missions of this series treat the cases where this fails: dissimilarity parameters above one (the problem becomes NP-hard) and nests with their own no-purchase option.

Setting

There are $m$ nests $M = \{1, \dots, m\}$ and, in each nest, $n$ products $N = \{1, \dots, n\}$ . Product $j$ of nest $i$ has a revenue $r_{ij} \ge 0$ and a preference weight $v_{ij} > 0$ ; products are ordered so that $r_{i1} \ge r_{i2} \ge \dots \ge r_{in}$ . Nest $i$ carries a dissimilarity parameter $\gamma_i > 0$ and a within-nest no-purchase weight $v_{i0} \ge 0$ , and $v_0 \ge 0$ is the weight of choosing no nest at all.

An assortment is a tuple $(S_1, \dots, S_m)$ of subsets $S_i \subseteq N$ . Write

V_i(S_i) = v_{i0} + \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(\emptyset) = 0.

A customer picks nest $i$ with probability $Q_i = V_i(S_i)^{\gamma_i} / (v_0 + \sum_{l \in M} V_l(S_l)^{\gamma_l})$ and then, inside the nest, product $j$ with probability $v_{ij}/V_i(S_i)$ . The expected revenue is

\Pi(S_1, \dots, S_m) = \sum_{i \in M} Q_i\, R_i(S_i) = \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}},

and problem (2) asks for $Z^* = \max \Pi(S_1, \dots, S_m)$ over all assortments. The nested-by-revenue assortment $N_{ij} = \{1, \dots, j\}$ collects the $j$ highest-revenue products of nest $i$ , with $N_{i0} = \emptyset$ and $N_+ = \{0, 1, \dots, n\}$ .

This mission works under the standing assumptions of §3 of the paper: competitive products, $\gamma_i \le 1$ , and fully-captured nests, $v_{i0} = 0$ , for every nest $i$ .

Formalization targets

Goal: Theorem 4 (p. 15)

If $\gamma_i \le 1$ and $v_{i0} = 0$ for all $i \in M$ , there exists an optimal solution $(S^*_1, \dots, S^*_m)$ of problem (2) such that

S^*_i = N_{ij} \ \text{ for some } j \in N_+, \qquad \text{for all } i \in M.

Milestones

The case $v_0 = 0$ (p. 14). Offering only the single product with the largest revenue $\max_{i} r_{i1}$ is optimal.
Proposition 2 (p. 14). If $S^*$ is optimal and $S^*_i \ne \emptyset$ , then $R_i(S^*_i) \ge Z^*$ .
Lemma 3 (p. 14). If $Z = \Pi(S)$ , $R_i(S_i) \ge Z$ and some $j \in S_i$ has $r_{ij} < \gamma_i Z + (1-\gamma_i) R_i(S_i)$ , removing $j$ strictly increases the expected revenue.
$g(\alpha) \le \gamma$ (p. 15). For $0 < \gamma \le 1$ and $0 < \alpha < 1$ : $(1 - \alpha^{\gamma})/(\alpha^{\gamma-1} - \alpha^{\gamma}) \le \gamma$ .
Revenue threshold (p. 15). Every $j \in S^*_i$ of an optimal $S^*$ has $r_{ij} \ge \gamma_i Z^* + (1-\gamma_i) R_i(S^*_i)$ .
$h(\alpha) \ge \gamma$ (p. 16). For $0 < \gamma \le 1$ and $0 < \alpha < 1$ : $(1 - \alpha^{\gamma})/(1 - \alpha) \ge \gamma$ .
Exchange step (p. 15). If $S^*$ is optimal, $j \in S^*_i$ , $k \notin S^*_i$ and $k < j$ , then adding $k$ to $S^*_i$ keeps the assortment optimal.

A companion item (not a milestone) states the algorithmic consequence at the end of §3: solving the linear program (4) over the candidates $\{N_{ij} : j \in N_+\}$ and choosing in each nest a maximizer of problem (5) gives an optimal solution of (2).

Significance

Theorem 4 reduces problem (2), a search over $2^{mn}$ assortments, to $(n+1)^m$ nested-by-revenue combinations, and the paper then finds the best one with a linear program with $1 + m$ variables and $1 + m(1+n)$ constraints. It marks the exact boundary of the classical multinomial logit structure inside the nested logit model: the paper's §4 shows that a single nest with $\gamma_i > 1$ already breaks it, and that the general problem is NP-hard. The structural statement is also the base case for the approximation guarantees of §§5–6, which compare against nested-by-revenue assortments.

The theorem is proved in the paper; to our knowledge it has no machine-checked proof. A formal proof would supply a verified reduction from a combinatorial revenue maximization over the nested logit model to a polynomial-size search, with every boundary case (empty nests, $v_0 = 0$ , ties in revenues) handled explicitly.

Difficulty

The obvious argument copies the multinomial logit proof: take an optimal assortment and swap a low-revenue product for a missing higher-revenue one. Under the nested logit model this exchange changes the nest's attraction $V_i(S_i)^{\gamma_i}$ non-linearly, so the revenue of the modified assortment is not an affine function of the change, and a simple swap can lower the expected revenue. The argument must instead control how adding or removing one product moves the nest weight relative to the nest revenue, and this is exactly where $\gamma_i \le 1$ enters, through two scalar inequalities in the ratio $\alpha$ of nest weights. With $\gamma_i > 1$ these inequalities fail and so does the theorem.

A second subtlety is ties: several optimal assortments may exist, and only some of them are nested by revenue. The statement asserts existence, not that every optimum has this form.

Formalization scope

All statements live in the namespace NestedLogitVariants.Competitive and share one definition file. Nests form a finite type ι with decidable equality; products are Fin n, indexed $0, \dots, n-1$ , so $N_{ij}$ is nbr n j $= \{k : k < j\}$ with $j \le n$ , and $j = 0$ gives $\emptyset$ . Powers are Real.rpow, and $x / 0 = 0$ , which gives $R_i(\emptyset) = 0$ . Optimality of an assortment means its revenue is at least that of every assortment.

Standing assumptions carried as hypotheses: $v_0 \ge 0$ , $v_{i0} \ge 0$ , revenues ordered within each nest, and §3's $\gamma_i \le 1$ and $v_{i0} = 0$ . Three pins are disclosed: $v_{ij} > 0$ (the paper allows zero-weight padding products, under which Proposition 2 fails), $r_{ij} \ge 0$ , and $\gamma_i > 0$ (the paper's $\gamma_i \ge 0$ ; its convention $V_i(\emptyset)^{\gamma_i} = 0$ fails at $\gamma_i = 0$ ). The section's "without loss of generality $v_0 > 0$ " is a hypothesis of Proposition 2, Lemma 3, the threshold, the exchange step and the LP item; the goal itself only assumes $v_0 \ge 0$ , and the case $v_0 = 0$ is milestone 1. The two scalar inequalities are stated as inequalities, not as monotonicity claims.

The goal is not trivialized by any hypothesis: it assumes none of the milestones, and stating "some nested-by-revenue assortment exists" (always true) or "every optimal assortment is nested by revenue" (false under ties) would be a different theorem.

Needed infrastructure is light: finite sums, real powers, and concavity of $x \mapsto x^{\gamma}$ for $\gamma \le 1$ . The scalar lemmas are reusable for other nested logit results. Proofs of any milestone are welcome independently.

Selected references

J. M. Davis, G. Gallego, H. Topaloglu, Assortment optimization under variants of the nested logit model, Operations Research 62(2), 250–273, 2014. https://doi.org/10.1287/opre.2014.1256 (cited from the authors' revised manuscript of June 18, 2013)
K. Talluri, G. van Ryzin, Revenue management under a general discrete choice model of consumer behavior, Management Science 50(1), 15–33, 2004. https://doi.org/10.1287/mnsc.1030.0147
D. McFadden, Modelling the choice of residential location, in A. Karlqvist et al. (eds.), Spatial Interaction Theory and Planning Models, North-Holland, 75–96, 1978.

9 thms2 active usersReviewed

Completed

Linear Optimization Operations Research Optimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 1: If the Restricted LP Optimum Scaled by α Is Feasible for the Full LP, Its Assortment Earns Within a Factor α of the Optimal RevenueResearch Paper

Motivation

A retailer that sells products in several categories, channels or stores has to decide which products to offer in each. Customers substitute: a product left out of the assortment sends some of its demand to other products, and some of it away. The nested logit model (McFadden 1974, 1981) is the standard choice model for this situation. It groups products into nests, so that substitution within a nest differs from substitution across nests. Assortment optimization under this model asks which products to offer in each nest so as to maximize expected revenue.

Davis, Gallego and Topaloglu (Oper. Res. 62(2), 2014) split the problem into four cases: dissimilarity parameters at most one or unrestricted, and nests that are fully or only partially captured. The problem is polynomially solvable in the first case and NP-hard in the other three. Every approximation guarantee in the paper for the hard cases (Theorems 7, 10, 11, 12) comes from one general framework, set up in §2: a linear program equivalent to the assortment problem, and Theorem 1, which turns a feasibility certificate for that linear program into a performance guarantee. This mission formalizes that framework.

Setting

There are $m$ nests $M$ and $n$ products $N = \{1, \dots, n\}$ in each nest. Product $j$ of nest $i$ has revenue $r_{ij} \ge 0$ and preference weight $v_{ij} > 0$ , and the products in each nest are ordered so that $r_{i1} \ge \dots \ge r_{in}$ . Nest $i$ has a no-purchase weight $v_{i0} \ge 0$ and a dissimilarity parameter $\gamma_i > 0$ . The weight of choosing no nest at all is $v_0 \ge 0$ . If the assortment $S_i \subseteq N$ is offered in nest $i$ , write

V_i(S_i) = v_{i0} + \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(\emptyset) = 0 .

A customer picks nest $i$ with probability $Q_i = V_i(S_i)^{\gamma_i} / (v_0 + \sum_{l\in M} V_l(S_l)^{\gamma_l})$ , and then a product of that nest by the multinomial logit model. The expected revenue is

\Pi(S_1, \dots, S_m) = \sum_{i \in M} Q_i(S_1, \dots, S_m)\, R_i(S_i),

and problem (2) is $Z^* = \max_{S_i \subseteq N} \Pi(S_1, \dots, S_m)$ .

The linear program (3) in the variables $(x, y_1, \dots, y_m)$ minimizes $x$ subject to

v_0 x \ge \sum_{i\in M} y_i, \qquad y_i \ge V_i(S_i)^{\gamma_i}\big(R_i(S_i) - x\big) \quad \forall S_i \subseteq N,\ i \in M.

Given candidate collections $\{A_{it} : t \in \mathcal T_i\}$ of assortments for each nest, the linear program (4) is (3) with the second family of constraints imposed only for $S_i$ in the collection of nest $i$ .

Formalization targets

Goal: Theorem 1 (p. 13)

Let $(\hat x, \hat y)$ be an optimal solution of (4), and let $\hat S_i$ solve $\max_{S_i \in \{A_{it}\}} V_i(S_i)^{\gamma_i}(R_i(S_i) - \hat x)$ , problem (5), in every nest. If $(\alpha \hat x, \beta \hat y)$ is feasible for (3) for some $\alpha, \beta$ , then, with $\hat Z = \Pi(\hat S_1, \dots, \hat S_m)$ ,

\alpha \hat Z \ \ge\ Z^* \ \ge\ \hat Z .

The theorem fixes no candidate collection and no value of $\alpha$ . Each later section of the paper instantiates it with its own collection and its own factor, so a formal proof applies to all of them.

Milestones (§2, pp. 11–12)

Problem (2) is equivalent to (3): $Z^*$ is the least $x$ for which some $y$ makes $(x, y)$ feasible for (3).
At an optimal solution of (4), the first constraint binds at the maximizers $\hat S_i$ of (5), and $\hat x = \Pi(\hat S_1, \dots, \hat S_m)$ .
Problem (4) relaxes (3), so $\hat x \le Z^*$ .

Companions (§7, pp. 29–30)

The tighter program (16), which lets each nest's assortment be a fractional vector $z_i \in [0,1]^n$ , has every feasible $x$ above $Z^*$ .
Proposition 13: $\hat F_i(x) = \max_{z_i \in [0,1]^n} F_i(z_i \mid x)$ is convex, with subgradient $-(v_{i0} + \sum_j v_{ij}\hat z_{ij}(x))^{\gamma_i}$ at $x$ .

Significance

Theorem 1 is the common step behind the paper's four approximation guarantees: the factor $\rho$ or $2\kappa$ of Theorem 7, the factor 2 of Theorem 10, the factor of Theorem 11, and the $\delta^{2\bar\gamma+1}$ of Theorem 12. Each of these reduces to checking that a scaled optimum of a small linear program is feasible for (3). With Theorem 1 formalized, those guarantees reduce to inequalities about candidate collections, which are the subject of the sister missions of this series. The upper bound (16) and Proposition 13 give the instance-specific bound that the paper uses to assess its assortments numerically.

The results are proved in the paper. To our knowledge none of them has a machine-checked proof. The formal work adds two things: the statements below are made exact at the degenerate inputs the prose passes over (an empty assortment, $v_0 = 0$ ), and a formal proof certifies the framework once for every later instantiation.

Difficulty

The equivalence of (2) and (3) rests on decomposing a maximum over joint assortments into a sum of per-nest maxima, and on reading the fractional objective $\Pi \le x$ as a linear constraint. Both steps need care where a denominator $v_0 + \sum_i V_i(S_i)^{\gamma_i}$ can vanish. The binding argument for (4) is a perturbation argument: lowering $\hat x$ must keep every constraint satisfiable, which needs a continuity and monotonicity property of the right-hand side in $x$ . The obvious one-line reading of Theorem 1, " $\hat x = \hat Z$ and $\alpha\hat x \ge Z^*$ ", is correct only once both of these facts are established with their hypotheses. In particular, it is false when $v_0 = 0$ (see below). Proposition 13 requires that the supremum over the box be finite, which comes from the boundedness of $F_i$ on $[0,1]^n$ .

Formalization scope

Nests are a finite type ι and products are Fin n, indexed $0, \dots, n-1$ . An assortment is a finite set of products per nest, and a candidate collection is a set of such finite sets. Powers are real powers, and Lean's $x / 0 = 0$ gives $R_i(\emptyset) = 0$ . $Z^*$ is $\Pi(S^*)$ for an arbitrary optimal assortment $S^*$ ; no supremum over assortments is taken. "Optimal solution of (4)" means feasible with minimal $x$ , and " $\hat S_i$ solves (5)" means $\hat S_i$ belongs to the collection of nest $i$ and maximizes the objective of (5) over it at $\hat x$ .

Standing assumptions and pins. These are $v_0, v_{i0} \ge 0$ and ordered revenues, together with $v_{ij} > 0$ , $r_{ij} \ge 0$ and $\gamma_i > 0$ . The paper allows zero-weight padding products and $\gamma_i = 0$ , but its own conventions fail there. Theorem 1 and the binding milestone add $v_0 > 0$ . The page allows $v_0 = 0$ , but then Theorem 1 is false: take one nest with $v_{10} = 0$ , $\gamma_1 = 1$ , $r_{11} = v_{11} = 1$ and candidates $\{\emptyset, \{1\}\}$ . Then $\hat x = 1$ and $\hat S_1 = \emptyset$ meet every hypothesis with $\alpha = \beta = 1$ , yet $\hat Z = 0 < Z^* = 1$ . The equivalence of (2) and (3) and the bound from (16) keep $v_0 \ge 0$ , as the page does, and assume at least one nest and one product: with neither and $v_0 = 0$ , every $x$ is feasible for (3).

A formalization that assumes the binding equality, the identity $\hat x = \hat Z$ , or the inequality $\hat x \le Z^*$ in the goal would trivialize it. Those facts appear only as milestones. Likewise, reading "optimal solution of (4)" as mere feasibility would make the goal false rather than easier.

The development needs only finite sums, real powers and elementary order reasoning. Proposition 13 also needs the boundedness of a continuous function on a box and the convexity of a pointwise supremum of affine functions. Welcome contributions include proofs of the milestones, the goal from them, and reusable lemmas on the per-nest decomposition of maxima, which the sister missions of this series use as well.

Selected references

J. M. Davis, G. Gallego, H. Topaloglu, Assortment optimization under variants of the nested logit model, Operations Research 62(2), 2014 (revised manuscript of June 18, 2013, cited here). https://doi.org/10.1287/opre.2014.1256
D. McFadden, Econometric models of probabilistic choice, in C. Manski, D. McFadden (eds.), Structural Analysis of Discrete Data with Econometric Applications, MIT Press, 1981. https://eml.berkeley.edu/~mcfadden/discrete.html
P. Rusmevichientong, D. Shmoys, H. Topaloglu, Assortment optimization with mixtures of logits, Technical report, Cornell University, 2010. https://people.orie.cornell.edu/huseyin/publications/publications.html
M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd ed., Wiley, 1993. https://doi.org/10.1002/0471787779

6 thms2 active usersReviewed

Combinatorics Operations Research Optimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper

Motivation

Assortment optimization asks which set of products a firm should offer when customers choose among the offered products according to a discrete choice model; it underlies shelf-space planning in retail and fare-class control in airline revenue management (Talluri and van Ryzin, 2004). Under the nested logit model products are grouped into nests, and a customer first picks a nest and then a product inside it. Davis, Gallego and Topaloglu (Operations Research, 2014; DOI 10.1287/opre.2014.1256) map out how hard this problem is across variants of the model.

When every nest dissimilarity parameter is at most one and a customer who chose a nest always buys there, offering the top-revenue products of each nest is optimal (Theorem 4 of the paper, the subject of an earlier mission of this series). Once a customer may leave a nest without buying — a partially-captured nest — that structure breaks and the problem becomes NP-hard (Theorem 8). This mission targets the paper's response: a small, explicitly constructed family of candidate assortments per nest from which a linear program recovers a solution within a factor of two of optimal.

Setting

There are $m$ nests $M$ and, in each nest, $n$ products $N = \{1, \dots, n\}$ . Product $j$ of nest $i$ has a revenue $r_{ij} \ge 0$ and a preference weight $v_{ij} > 0$ , with $r_{i1} \ge \dots \ge r_{in}$ . Nest $i$ has a dissimilarity parameter $\gamma_i > 0$ and a within-nest no-purchase weight $v_{i0} \ge 0$ ; $v_0 \ge 0$ is the weight of choosing no nest. For an assortment $S_i \subseteq N$ ,

V_i(S_i) = v_{i0} + \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(\emptyset)=0,

and the expected revenue of $(S_1, \dots, S_m)$ is $\Pi = \sum_i V_i(S_i)^{\gamma_i} R_i(S_i) / (v_0 + \sum_i V_i(S_i)^{\gamma_i})$ . The optimal expected revenue $Z^*$ is the optimal value of the linear program

\text{(3)}\quad \min\ x \quad\text{s.t.}\quad v_0 x \ge \sum_{i \in M} y_i,\qquad y_i \ge V_i(S_i)^{\gamma_i}\big(R_i(S_i) - x\big)\ \ \forall S_i \subseteq N,\ i \in M,

and problem (4) is the same program with the second family of constraints imposed only for a chosen collection of candidate assortments in each nest.

Throughout, $\gamma_i \le 1$ for every nest and the $v_{i0}$ are arbitrary. For a capacity $\epsilon_i \ge 0$ , the knapsack value $K_i(\epsilon_i)$ is the largest $\sum_{j \in S} r_{ij} v_{ij}$ over assortments $S$ with $\sum_{j \in S} v_{ij} \le \epsilon_i$ (display (9)). Its continuous relaxation (11) allows fractional $z_{ij} \in [0, \mathbf 1(v_{ij} \le \epsilon_i)]$ under the same capacity. The greedy solution $\hat z_i(\epsilon_i)$ of (11) fills the capacity with the products of weight at most $\epsilon_i$ in revenue order, each fully while it fits and the next one fractionally, and

\hat S_i(\epsilon_i) = \{ j \in N : \hat z_{ij}(\epsilon_i) = 1 \}.

Problem (10) replaces the per-assortment constraints of (3) by $y_i \ge \max_{\epsilon_i \ge 0} (v_{i0}+\epsilon_i)^{\gamma_i}[K_i(\epsilon_i)/(v_{i0}+\epsilon_i) - x]$ .

Formalization targets

Goal: Theorem 10 (p. 24)

Let $(\hat x, \hat y)$ be an optimal solution of (4) with candidate collections $\{\hat S_i(\epsilon_i) : \epsilon_i \in [0,\infty]\} \cup \{\{j\} : j \in N\}$ . Then

(2\hat x,\ 2\hat y) \ \text{ is feasible for (3).}

Milestones

Per-nest identity (proof of Lemma 9, p. 23). For $x \ge 0$ , $\max_{S_i} V_i(S_i)^{\gamma_i}(R_i(S_i) - x) = \max_{\epsilon_i \ge 0}(v_{i0}+\epsilon_i)^{\gamma_i}[K_i(\epsilon_i)/(v_{i0}+\epsilon_i) - x]$ .
Lemma 9 (p. 23). Problems (3) and (10) have the same optimal solutions.
Relaxation (p. 23). Every feasible point of (9) is feasible for (11), so $\hat K_i(\epsilon_i) \ge K_i(\epsilon_i)$ .
Greedy solution (pp. 23–24). $\hat z_i(\epsilon_i)$ is optimal for (11) and has at most one fractional component.
Sign (A.3, p. 45). $\hat x \ge 0$ .
Inequalities (28) and (29) (A.3, pp. 45–46). In both cases — $\hat z_i(\epsilon)$ with and without a fractional component — $2\hat y_i \ge (v_{i0}+\epsilon)^{\gamma_i}[K_i(\epsilon)/(v_{i0}+\epsilon) - 2\hat x]$ .

Two further statements accompany the goal: the factor-two revenue guarantee obtained from Theorem 10 and Theorem 1 of the paper, and the fact that every $\hat S_i(\epsilon_i)$ is one of the at most $1 + n^2$ assortments $N^k_{ij}$ , the first $j$ products by revenue among the $k$ lightest.

Significance

Theorem 10 turns an NP-hard assortment problem into a linear program with $1 + m$ variables and $1 + m(1 + n + n^2)$ constraints whose solution is within a factor of two of optimal. The construction is explicit: the candidates are defined by a greedy rule, not by an optimization oracle. The same template, a restricted linear program whose doubled optimum is feasible for the full one, is reused in §6 of the paper for the most general instances, and Lemma 9's knapsack reformulation is the link to the classical approximation theory of knapsack problems (Williamson and Shmoys, 2011).

The theorem is proved in the paper. No machine-checked proof of it, of Lemma 9, or of greedy optimality for the continuous knapsack with an eligibility bound exists on the platform. Formalizing it yields a checked factor-two guarantee and a reusable fractional-knapsack development.

Difficulty

The obvious argument would compare the restricted program (4) with (3) constraint by constraint. That fails: (3) has one constraint per subset of products, and most subsets are not candidates. The comparison has to pass through the knapsack reformulation (10), which requires showing that a maximum over all subsets equals a maximum over a one-dimensional capacity parameter, using $\gamma_i \le 1$ and $x \ge 0$ in an essential way. The second obstacle is that the greedy assortment $\hat S_i(\epsilon_i)$ keeps only the fully taken products, so its value can fall short of the continuous knapsack value, and no single candidate assortment need attain the knapsack bound. With dissimilarity parameters above one the monotonicity behind the reformulation is lost, and §6 of the paper needs a different factor.

Formalization scope

Products are Fin n (indices $0, \dots, n-1$ ), nests a finite type, and every quantity is real. Powers are Real.rpow; $x/0 = 0$ , which gives $R_i(\emptyset) = 0$ . An optimal solution of a linear program is a feasible pair whose $x$ is minimal among feasible pairs. The constraint " $y_i \ge \max_{\epsilon_i \ge 0}(\dots)$ " of (10) is stated in constraint form, for every $\epsilon_i \ge 0$ , so no real supremum is taken. $K_i(\epsilon)$ is defined for $\epsilon \ge 0$ only; its placeholder value for $\epsilon < 0$ is never used. Ties in revenue (and, for $N^k_{ij}$ , in weight) are broken by index. The candidate collection is taken over real $\epsilon_i \ge 0$ ; $\epsilon_i = \infty$ adds nothing, since every capacity of at least $\sum_j v_{ij}$ already gives $\hat S_i = N$ .

Standing assumptions and added hypotheses: $\gamma_i \le 1$ for every nest (the section's assumption) on the goal and on every model milestone; the pins $v_{ij} > 0$ , $r_{ij} \ge 0$ , $\gamma_i > 0$ and the revenue ordering, shared by the series; $n \ge 1$ on Lemma 9, on $\hat x \ge 0$ and on (28)/(29), the paper's nonempty $N$ ; and $v_0 > 0$ on the factor-two revenue guarantee, where Theorem 1 of the paper fails without it.

The greedy assortments $\hat S_i(\epsilon_i)$ are defined explicitly. Quantifying over arbitrary optimal solutions of (11) instead would change the candidate collection and is not the paper's theorem. The goal states feasibility for the full program (3) and does not mention knapsack values, the greedy solution or the case split. A formalization that weakens the conclusion to feasibility for (10), or that drops the singletons from the candidate collection, is not a solution.

Needed infrastructure: fractional knapsack optimality of the greedy rule with an eligibility bound, monotonicity of $t \mapsto t^{\gamma}$ and $t \mapsto t^{\gamma - 1}$ for $\gamma \le 1$ , and finite maximization over subsets. The fractional-knapsack lemmas are reusable beyond this mission. Proofs of any milestone, and alternative decompositions of the goal, are welcome.

Selected references

J. M. Davis, G. Gallego, H. Topaloglu, Assortment Optimization under Variants of the Nested Logit Model, Operations Research 62(2), 2014 (revised manuscript of June 18, 2013, cited here). DOI 10.1287/opre.2014.1256
K. T. Talluri, G. J. van Ryzin, Revenue Management Under a General Discrete Choice Model of Consumer Behavior, Management Science 50(1), 15–33, 2004. DOI 10.1287/mnsc.1030.0147
D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. DOI 10.1017/CBO9780511921735

11 thms2 active usersReviewed

Operations Research Probability Statistics·Captain: mikedeng1

Simultaneously Learning and Optimizing Using Controlled Variance Pricing 2: Certainty Equivalent Pricing Fails to Converge to the Optimal Price with Positive ProbabilityResearch Paper

Why myopic pricing is a problem

A seller who does not know how demand responds to price has to learn the demand curve from its own sales while it is selling. The most natural policy is certainty equivalent pricing (also called myopic pricing or passive learning): after every period, estimate the unknown demand parameters from all data collected so far, and charge the price that would be optimal if the estimates were the truth. It is simple, uses all data, and is what a price manager would do without further thought.

den Boer and Zwart (Management Science 60(3):770–783, 2014) show that this policy can fail. In the linear-demand, Gaussian-noise model, the prices it produces fail to converge to the optimal price with positive probability: the policy is not strongly consistent. The result motivates the paper's main contribution, controlled variance pricing, which adds just enough price dispersion to keep learning (treated in the companion mission of this series).

The phenomenon has a history in adaptive control:

1976. Anderson and Taylor study the linear system $y_t = a_0 + a_1x_t + \epsilon_t$ controlled by a certainty equivalent rule that steers $y_t$ to a target, and examine by simulation the statistical properties of the least squares estimates it produces (Econometrica 44(6), 1976).
1982. Lai and Robbins (Adv. Appl. Math. 3(1), 1982) prove that there are parameter values for which the certainty equivalent controls converge with positive probability to a value different from the optimal control.
2014. den Boer and Zwart adapt the argument to revenue maximization with linear demand, without the conditions Lai and Robbins place on the initial inputs and the input bounds: any two different initial prices in $[p_l, p_h]$ give the failure with positive probability.

Setting

A monopolist sells one product in periods $t = 1, 2, \dots$ at prices $p_t$ from an interval $[p_l, p_h]$ with $0 < p_l < p_h$ . The demand in period $t$ is

d_t = a_0^{(0)} + a_1^{(0)} p_t + e_t ,

where $e_1, e_2, \dots$ are independent $N(0, \sigma^2)$ random variables. The parameters are unknown to the seller and satisfy $\sigma > 0$ , $a_0^{(0)} > 0$ , $a_1^{(0)} < 0$ , $a_0^{(0)} + a_1^{(0)}p_h \ge 0$ . The expected revenue at price $p$ is $r(p, a_0, a_1) = p(a_0 + a_1p)$ , maximized at the optimal price

p_{\mathrm{opt}} = -\frac{a_0^{(0)}}{2a_1^{(0)}}, \qquad p_l < p_{\mathrm{opt}} < p_h .

Certainty equivalent pricing charges two different initial prices $p_1 \ne p_2$ in $[p_l, p_h]$ . After $t \ge 2$ periods it computes the least squares estimates $\hat a_t = (\hat a_{0t}, \hat a_{1t})$ , the solution of the normal equations $\sum_{i \le t}(1, p_i)^{\mathsf T}(d_i - \hat a_{0t} - \hat a_{1t}p_i) = 0$ , and charges

p_{t+1} = \arg\max_{p \in [p_l, p_h]} p\,(\hat a_{0t} + \hat a_{1t}p),

with $p_{t+1} = p_h$ when the estimated slope $\hat a_{1t}$ is nonnegative.

Formalization targets

Goal: Proposition 1

P\big(p_t \not\to p_{\mathrm{opt}}\big) > 0 .

The goal states only the failure of convergence, for every admissible parameter and every pair of different initial prices; it does not fix where the prices go.

Stronger: the prices stick at the boundary

P\big(p_t = p_h \ \text{for all } t \ge 3\big) > 0 .

This is what the paper's argument establishes; since $p_{\mathrm{opt}} < p_h$ it implies the goal.

Milestones

The milestones are the displayed steps of the appendix proof, in attack order: the determinant of the coefficient matrix of the linear system (12); the bound $P(\sup_{t \ge 3}|(t-2)^{-1}\sum_{i=3}^t e_i| > \epsilon) \le 8\sigma^2\epsilon^{-2} < 1$ for $\epsilon > \sqrt 8\,\sigma$ ; positivity of the probability of an explicit event $A_\delta$ on the noise for large $\delta$ ; the case $t = 2$ (the first fitted line pushes $p_3$ to $p_h$ ); the representation $\hat a_t - a^{(0)} = (\bar e_t - \bar p_tC_t/V_t,\ C_t/V_t)$ of the least squares error; recursive and closed forms of $V_t$ and $C_t$ ; and the deterministic induction that every noise path in $A_\delta$ keeps the price at $p_h$ forever.

Significance

The result is the standard counterexample to certainty equivalence in dynamic pricing. It shows that estimation and optimization cannot be separated naively: a policy that always exploits its current estimate can lock itself into a price at which the data no longer move the estimate enough to correct it. Every later policy in this literature that forces exploration (controlled variance pricing, semi-myopic policies, constrained iterated least squares) is designed against this failure, and its necessity is argued by pointing to results of this kind.

The result is proved in the paper; nothing here is open. To our knowledge it has no machine-checked proof. Formalizing it adds:

a verified pathwise analysis of the least squares recursion along a price path, reusable for other proofs about adaptive estimation with two parameters;
a verified maximal bound for running means of i.i.d. Gaussian noise, of the kind used in many consistency proofs;
a clean probabilistic statement of the failure, against which consistency results for exploration policies can later be contrasted.

Difficulty

The obvious heuristic, "with positive probability the first two observations are so noisy that the fitted slope is wrong", is not enough: one bad estimate is corrected by later data unless the policy stops generating informative data. The proof has to control the whole infinite future. It does so by showing that on a single event, defined through the first two noise values and a uniform bound on all later running means, the price stays at $p_h$ forever, which requires the closed form of the least squares estimate along a price path that is constant from period 3 on. That event involves infinitely many noise variables, so its probability is positive only through a maximal inequality, and independence between $(e_1, e_2)$ and the later noise. A second subtlety is the choice of constants: the size of the band $\delta$ enters the conditions on $(e_1, e_2)$ , so the order in which $\delta$ and the set of admissible $(e_1, e_2)$ are chosen matters (the printed proof picks them in a circular order; a non-circular choice exists).

Formalization scope

Model. CVPricing.CertEquiv.Model bundles $p_l, p_h, a_0^{(0)}, a_1^{(0)}, \sigma$ with the standing assumptions of §2 as fields, including $p_l < p_{\mathrm{opt}} < p_h$ (the paper's neighbourhood assumption specialized to linear demand). The noise is the referenced published definition RobustBooking.Shared.GaussianNoise (measurable, mutually independent, each $N(0, \sigma^2)$ ); its Lean index $k$ is period $k+1$ , so the paper's $e_i$ is ε (i - 1).
Policy. cePrice is a deterministic recursion on a noise path, so the random price process is obtained by evaluating it at $\omega$ . Periods are 1-based. The least squares estimate is the referenced KeskinZeevi.SufficientConditions.lsEstimateOf, the solution of the normal equations (4), unique whenever $p_1 \ne p_2$ . The certainty equivalent rule is the projection of $-\hat a_{0t}/(2\hat a_{1t})$ onto $[p_l, p_h]$ when $\hat a_{1t} < 0$ , and $p_h$ when $\hat a_{1t} \ge 0$ ; the latter is the convention the paper's proof adopts for wrong-signed estimates.
Corrected slips. The definition of the event $A$ is printed with " $\delta|\bar e_t| \le \delta$ " (read $|\bar e_t| \le \delta$ ) and with its second line missing a factor $\delta$ on the term $(2p_h - p_1 - p_2)$ ; both are restored as in (12) and the last display of the proof. The intercept of the first fitted line is printed without $a_0^{(0)}$ ; the correct intercept is stated, and the printed condition remains sufficient for $p_3 = p_h$ .
WLOG. The steps of the proof assume $p_1 < p_2$ and are stated under that ordering; the goal and the stronger statement cover $p_1 \ne p_2$ .
No trivialization. The goal is a statement about the Gaussian law of the noise: a theorem that exhibits one bad noise path, or that assumes $P(A) > 0$ , does not prove it. The event in the goal is a set of outcomes whose measurability is not asserted.
Welcome contributions. Kolmogorov's maximal inequality for sums of independent square-integrable variables; least squares identities for two-parameter regression; the independence argument separating $(e_1, e_2)$ from the later noise.

Selected references

A. V. den Boer, B. Zwart, Simultaneously Learning and Optimizing Using Controlled Variance Pricing, Management Science 60(3):770–783, 2014. https://doi.org/10.1287/mnsc.2013.1788
T. L. Lai, H. Robbins, Iterated least squares in multiperiod control, Advances in Applied Mathematics 3(1):50–73, 1982. https://doi.org/10.1016/S0196-8858(82)80005-5
T. W. Anderson, J. B. Taylor, Some experimental results on the statistical properties of least squares estimates in control problems, Econometrica 44(6):1289–1302, 1976. https://doi.org/10.2307/1914261
Y. S. Chow, H. Teicher, Probability Theory: Independence, Interchangeability, Martingales, 3rd ed., Springer, 2003. https://doi.org/10.1007/978-1-4612-1950-7

15 thms2 active usersReviewed

Operations Research Probability Statistics·Captain: mikedeng1

Simultaneously Learning and Optimizing Using Controlled Variance Pricing 1: Controlled Variance Pricing Has Regret O(T^α + T^(1−α) log T)Research Paper

Motivation

A firm that sets prices without knowing how demand responds to them has to learn the demand curve from its own sales. Each price it charges is both a revenue decision and an experiment. The natural policy, certainty equivalent pricing, re-estimates the demand parameters after every period and charges the price that would be optimal if the estimates were exact. den Boer and Zwart show that this policy can fail: with positive probability its prices settle at a suboptimal value, because they converge too fast for the estimates to keep improving (den Boer–Zwart 2014, Proposition 1, the subject of the companion mission). The same phenomenon was found by Lai and Robbins (1982) for a linear control problem.

Their remedy, Controlled Variance Pricing (CVP), keeps certainty equivalent pricing but forces the sample variance of the chosen prices to decay no faster than $t^{\alpha-1}$ . The main result is that this small amount of enforced exploration gives regret $O(T^\alpha + T^{1-\alpha}\log T)$ , hence $O(T^{1/2+\delta})$ for every $\delta > 0$ , for a broad class of demand models that are specified only through their first two moments. Keskin and Zeevi (2014) later placed CVP in a larger family of semi-myopic policies with $\sqrt T\log T$ regret for linear demand.

Setting

A seller chooses in each period $t = 1, 2, \dots$ a price $p_t \in [p_l, p_h]$ , with $0 < p_l < p_h$ , and then observes demand $d_t$ . Demand at price $p$ has mean $h(a_0^{(0)} + a_1^{(0)}p)$ and variance $\sigma^2 v(h(a_0^{(0)} + a_1^{(0)}p))$ , where the link $h$ and variance function $v$ are known and $C^2$ on $[0,\infty)$ , $\dot h > 0$ , and the parameter $a^{(0)} = (a_0^{(0)}, a_1^{(0)})$ with $a_0^{(0)} > 0 > a_1^{(0)}$ is unknown. The noise $e_t = d_t - h(a_0^{(0)} + a_1^{(0)}p_t)$ is a martingale difference with conditional variance $\sigma^2 v(\cdot)$ and a uniformly bounded conditional moment of some order $r > 3$ .

The expected revenue is $r(p, a) = p\,h(a_0 + a_1p)$ . Near $a^{(0)}$ it has a unique maximizer $p(a)$ in the open interval $(p_l, p_h)$ with $\partial_p^2 r < 0$ there, and $p_{\mathrm{opt}} = p(a^{(0)})$ . The regret of a policy is

\operatorname{Regret}(T) = \mathbb E\Big[\sum_{t=1}^T r(p_{\mathrm{opt}}, a^{(0)}) - r(p_t, a^{(0)})\Big].

The estimate $\hat a_t$ is the maximum quasi-likelihood estimate (MQLE), the root of the quasi-score equation (3), $\sum_{i\le t} \frac{\dot h}{\sigma^2 v(h)}(1, p_i)^\top(d_i - h(\hat a_0 + \hat a_1 p_i)) = 0$ . With $\bar p_t$ and $\operatorname{Var}(p)_t$ the sample mean and variance of $p_1,\dots,p_t$ , the taboo interval is $\mathrm{TI}(t) = (\bar p_t - w_t, \bar p_t + w_t)$ with $w_t = \sqrt{c[(t+1)^\alpha - t^\alpha](t+1)/t}$ . CVP starts from two distinct prices $p_1, p_2$ , fixes $\alpha \in (0,1)$ and $0 < c < 2^{-\alpha}(p_1-p_2)^2\min\{1,(3\alpha)^{-1}\}$ , and for $t \ge 2$ : if $\hat a_t$ does not exist or has the wrong signs, it charges whichever of $p_1, p_2$ is farther from $\bar p_t$ ; otherwise it charges $p(\hat a_t)$ if that keeps $\operatorname{Var}(p)_{t+1} \ge c(t+1)^{\alpha-1}$ , and the best price outside $\mathrm{TI}(t)$ if not.

Formalization targets

Goal: Theorem 1

\operatorname{Regret}(T, \mathrm{CVP}) = O\big(T^\alpha + T^{1-\alpha}\log T\big) \qquad (1/2 < \alpha < 1),

stated as: there is $K > 0$ , depending on the model, $\alpha$ , $c$ and the initial prices but not on $T$ , with $\operatorname{Regret}(T) \le K(T^\alpha + T^{1-\alpha}\log T)$ for all $T \ge 1$ . The constant is left free, so the statement survives any sharpening of the constants.

Milestones

Proposition 2: $\operatorname{Var}(p)_t \ge c\,t^{\alpha-1}$ for all $t \ge 2$ along every CVP path.
Lemma 1: $\lambda_{\max}(P_t) \le (1+p_h^2)t$ and $t\operatorname{Var}(p)_t \le (1+p_h^2)\lambda_{\min}(P_t)$ for the design matrix $P_t = \sum_{i\le t}(1,p_i)^\top(1,p_i)$ .
Proposition 3: $\hat a_t$ eventually exists, $\hat a_t \to a^{(0)}$ a.s., and for some $\rho_0$ , $\mathbb E[T_{\rho_0}^{1/2}] < \infty$ and $\mathbb E[\|\hat a_t - a^{(0)}\|^2\mathbf 1_{t > T_{\rho_0}}] = O(\log t/t^\alpha)$ .
Eq. (11): in the normal–linear case, $\mathbb E\|\hat a_t - a^{(0)}\|^2 = O(\log t / t^\alpha)$ .
Eqs. (17), (18), (20): the quadratic revenue gap, the local Lipschitz bound on $p(a)$ , and $|p_{t+1} - p(\hat a_t)| \le |\mathrm{TI}(t)|$ for large $t$ .
The closing bound $\mathbb E[(p_t - p_{\mathrm{opt}})^2] = O(t^{\alpha-1} + \log t/t^\alpha)$ .

Significance

The theorem shows that a policy that is certainty equivalent almost all of the time, with a single interpretable tuning parameter $\alpha$ , attains regret $O(T^{1/2+\delta})$ in generalized linear demand models, without distributional assumptions beyond two moments. It explains the role of $\alpha$ precisely: $T^\alpha$ is the cost of exploration and $T^{1-\alpha}\log T$ the cost of estimation error. Proposition 2 and Lemma 1 are reusable for any policy that enforces a variance floor on its actions, and (11) is a self-contained rate for least squares under adaptively chosen designs.

The result is proved in the paper, with Proposition 3 delegated to den Boer and Zwart (2012) for general links. To our knowledge none of it has been machine-checked. A formalization would verify the delegated consistency argument, fix the conditions under which it applies (see Formalization scope), and provide a Lean development of adaptive least squares and quasi-likelihood rates that the related Keskin–Zeevi missions also need.

Difficulty

The deterministic parts are short. The difficulty is Proposition 3. The prices are chosen adaptively from past data, so the regressors are not independent of the noise, and standard rates for (quasi-)likelihood estimates do not apply. The natural argument, bounding $\|\hat a_t - a^{(0)}\|^2$ by $Q_t/\lambda_{\min}(P_t)$ with $Q_t$ a self-normalized martingale quadratic form, needs a bound $\mathbb E[Q_t] = O(\log t)$ that holds in expectation and not only almost surely, as in Lai and Wei (1982). For a non-linear link the MQLE is defined only implicitly, and its existence near $a^{(0)}$ has to be shown first, with a moment bound on the last time it fails. That is the random time $T_\rho$ . Turning almost-sure consistency into a rate in expectation is where most of the work lies.

Formalization scope

All declarations live in the namespace CVPricing.Regret. Periods are 1-based. Prices, demands and parameters are real; $a = (a_0, a_1) \in \mathbb R \times \mathbb R$ with the Euclidean norm (euclidNorm), not Mathlib's sup norm. The design matrix, sample mean and $t\operatorname{Var}(p)_t$ are the published Keskin–Zeevi definitions fisherOf, avgPriceOf, infoMetricOf. Every $O(\cdot)$ is "there is $K > 0$ such that for all $t$ ", with $K$ quantified after the model data. Rates are stated for $t \ge 2$ and the regret for $T \ge 1$ . $h$ and $v$ are total functions constrained on $[0,\infty)$ . A root of (3) counts only where $\hat a_0 + \hat a_1 p_i \ge 0$ for every observed $p_i$ . CVP is a predicate on a realized path that allows every maximizer in (7) and (8).

Disclosed deviations from the page:

the model requires $a_0^{(0)} + a_1^{(0)}p_h > 0$ (printed: $\ge 0$ ), because in the boundary case the policy's case (c) fires infinitely often and the proof of Theorem 1 does not cover it;
(3) is assumed to have at most one root (the page notes roots need not be unique, and the policy cannot select the root nearest $a^{(0)}$ );
the neighbourhood assumption is read as a unique maximizer over $[p_l, p_h]$ lying in $(p_l, p_h)$ ;
the demand process is given by its conditional mean, its conditional variance and (2), with integrable noise moments, not by a fixed law $D(p)$ ;
the initial prices are deterministic.

Corrected slips: Proposition 2 is stated for $c \le 2^{-\alpha}(p_1-p_2)^2\min\{1/2,(3\alpha)^{-1}\}$ , because the printed range fails at $t=2$ ( $\operatorname{Var}(p)_2 = (p_1-p_2)^2/4$ , not $/2$ ). Theorem 1 keeps the printed range. Eq. (20) is stated for $p_{t+1}$ and for $t$ beyond an explicit threshold.

The goal does not assume the variance bound, consistency or (20). The policy contains the variance check and the taboo interval, and the regret is the expectation over the actual price process. A statement that assumed any of these, or that dropped the taboo step, would be trivial or false. Contributions are welcome on adaptive least squares (Sherman–Morrison and determinant-ratio bounds), martingale last-time moment bounds, and the implicit-function step (18).

Selected references

A. V. den Boer, B. Zwart, Simultaneously Learning and Optimizing Using Controlled Variance Pricing, Management Science 60(3):770–783, 2014. https://doi.org/10.1287/mnsc.2013.1788
A. V. den Boer, B. Zwart, Mean square convergence rates for maximum quasi-likelihood estimators, Stochastic Systems 4(2):375–403, 2014 (cited as 2012 working paper). https://doi.org/10.1214/12-SSY086
T. L. Lai, C. Z. Wei, Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems, Annals of Statistics 10(1):154–166, 1982. https://doi.org/10.1214/aos/1176345697
T. L. Lai, H. Robbins, Iterated least squares in multiperiod control, Advances in Applied Mathematics 3(1):50–73, 1982. https://doi.org/10.1016/S0196-8858(82)80005-5
N. B. Keskin, A. Zeevi, Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies, Operations Research 62(5):1142–1167, 2014. https://doi.org/10.1287/opre.2014.1294

13 thms2 active usersReviewed

Operations Research Optimization Probability·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 1: A Fixed Price Earns at Least 1 − 1/(2√min{n, λ*t}) of the Optimal Expected RevenueResearch Paper

Motivation

A firm holds a fixed stock of a perishable or seasonal product: airline seats, hotel rooms, fashion goods, tickets. It must sell the stock over a finite season, and whatever is left at the end is worth nothing. The firm can change its price at any time, and demand responds to the price at random. Should it adjust its price continually as sales occur and time runs out, or is one well-chosen price nearly as good?

Gallego and van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons (Management Science 40(8), 1994, doi:10.1287/mnsc.40.8.999), set up this question as a continuous-time stochastic control problem and answered it. The source for this mission is the published 1994 article. Its answer is quantitative: the expected revenue of a single fixed price is within a factor $1-1/(2\sqrt{\min\{n,\lambda^*t\}})$ of the best possible dynamic policy. The paper is one of the founding results of dynamic pricing in revenue management. The deterministic (fluid) upper bound it introduced became the standard benchmark of the field, and later work on re-solving heuristics, network revenue management and learning-while-pricing builds on it.

Setting

Demand. The firm chooses a demand intensity $\lambda$ from an interval $\Lambda\ni 0$ of allowable rates, and the market charges the inverse-demand price $p(\lambda)$ . On nonzero rates, $p$ is strictly decreasing and nonnegative; rate $0$ corresponds to the null price $p_\infty$ , at which nothing sells. The revenue rate is $r(\lambda)=\lambda p(\lambda)$ . It has $r(0)=0$ , and it is continuous, concave and bounded on $\Lambda$ . $\lambda^*$ denotes its least maximizer, and $p^*=p(\lambda^*)$ , $r^*=r(\lambda^*)$ . Such data form a regular demand function (§2.1).

The stochastic problem. At time $0$ the firm holds $n$ items and has a horizon $[0,t]$ . A non-anticipating pricing policy $u$ chooses the intensity $\lambda_s\in\Lambda$ at each elapsed time $s$ as a function of the sales history so far. Sales follow a Poisson process with this controlled intensity, and at most $n$ items can be sold. A sale at time $s$ earns the current price $p_s$ . The expected revenue is $J_u(n,t)=E_u[\int_0^t p_s\,dN_s]$ , where $N_s$ counts the sales, and the optimal expected revenue is $J^*(n,t)=\sup_u J_u(n,t)$ .

The deterministic problem. Replacing random sales by their rates gives

J^D(x,t)=\sup\Big\{\int_0^t r(\lambda(s))\,ds:\ \lambda(s)\in\Lambda,\ \int_0^t\lambda(s)\,ds\le x\Big\}.

It is solved by the constant rate $\lambda^D=\min\{\lambda^*,x/t\}$ (Proposition 2).

Fixed-price heuristics. $J^{FP}(n,t)$ is the expected revenue of charging $p^D=p(\lambda^D)$ for the whole horizon. $J^{OFP}(n,t)$ is the expected revenue of the best constant price.

Formalization targets

Goal: Theorem 3

For $\lambda^*>0$ , $n\ge1$ and $t>0$ , $J^*(n,t)$ is finite and positive, and

\frac{J^{OFP}(n,t)}{J^*(n,t)}\ \ge\ \frac{J^{FP}(n,t)}{J^*(n,t)}\ \ge\ 1-\frac{1}{2\sqrt{\min\{n,\lambda^*t\}}}.

Milestones

Proposition 2: $\lambda^D$ solves (11), and $J^D(x,t)=t\,r(\lambda^D)$ .
Eqs. (13)–(14): $E_u[N_t]=E_u[\int_0^t\lambda_s ds]\le n$ and $J_u(n,t)=E_u[\int_0^t r(\lambda_s)ds]$ for every policy.
Eq. (15) and Lemma 1: $J_u(n,t)\le J_u(n,t,\mu)\le J^D(n,t,\mu)$ for all $\mu\ge0$ .
The zero duality gap: $J^D(n,t)=\min_{\mu\ge0}J^D(n,t,\mu)$ .
Theorem 2: $J^*(n,t)\le J^D(n,t)$ for all $n\ge 0$ , $t\ge0$ .
Eq. (17): a fixed price $p$ earns $p\,E[\min\{n,N_{\lambda(p)t}\}]$ , with $N$ Poisson.
Inequality (18), Gallego's bound $E[(N-n)^+]\le(\sqrt{\sigma^2+(n-\mu)^2}-(n-\mu))/2$ , already on the platform.
The two case bounds of the proof of Theorem 3, including (19), and the exact fixed-price revenue of the Remark.

Significance

The result. Theorem 2 says that uncertainty can only cost revenue. The deterministic value is a computable upper bound for every policy, so any heuristic can be judged against it. Theorem 3 turns this into a guarantee: with 400 items and scarce stock, a single price earns at least 97.5% of the optimum. The loss vanishes as the expected sales volume grows. This is the justification for the stable, rarely changed prices seen in practice, and the template for the asymptotic-optimality analyses that followed: fluid bounds, re-solving, bid prices.

Formalizing it. The results are proved on paper, and none is formalized. The platform has a discrete-time Bernoulli analogue of Theorem 2 (Talluri–van Ryzin, RevenueManagement.deterministic_upper_bound) and Bitran–Caldentey's periodic-review version as open items. Neither is this continuous-time model. A formalization would add a controlled Poisson sales process with a policy-dependent intensity, the compensator identities (13)–(14) for it, and a Lagrangian-duality argument over measurable rate paths. These are reusable for every continuous-time revenue-management model on the platform. Gallego's moment bound (18) is already proved there.

Difficulty

The deterministic side (Proposition 2, the duality gap) is convex analysis on one concave function. The fixed-price bounds reduce to a Poisson computation and (18). The obstacle is Theorem 2's stochastic step. The revenue is collected at random jump times chosen by an adaptive policy, and comparing it with a deterministic integral requires the compensator identity $E_u[\int p_s\,dN_s]=E_u[\int r(\lambda_s)\,ds]$ for an arbitrary non-anticipating intensity. The paper cites Brémaud's martingale theory for this, which Mathlib does not have. A first idea is to apply Jensen's inequality to $J_u$ directly. It fails because the stock constraint holds only pathwise, through $N_t\le n$ , and not in expectation for a rate path. Restricting to Markovian policies does not remove the need for the identity.

Formalization scope

Model. Rates are real numbers, and $\Lambda\subseteq[0,\infty)$ is an interval containing $0$ . $p$ is a real function, strictly decreasing and nonnegative on $\Lambda\setminus\{0\}$ . $r(\lambda)=\lambda p(\lambda)$ is continuous, concave and bounded above on $\Lambda$ , and $\lambda^*$ is its least maximizer. $p(0)$ is never used, since the null price may be $+\infty$ .
Policies depend on elapsed time and the past sale times (the internal history); randomized policies are not included. Intensities are jointly measurable and locally integrable.
The sales process is built from i.i.d. $\mathrm{Exp}(1)$ clocks, one per item. A sale occurs when the intensity integrated since the last sale reaches the next clock, so at most $n$ items are sold. Constraint (2) is part of the construction, not a hypothesis.
Values. Expected revenues and $J^*$ are in $[0,\infty]$ , as lower Lebesgue integrals and suprema. $J^D$ is a real supremum over measurable, integrable rate paths, nonempty and bounded for $x,t\ge0$ . $J^{FP}$ and $J^{OFP}$ are expected revenues of constant-price policies of this process, and the goal also asserts $0<J^*<\infty$ . Defining $J_u$ by the right side of (14), $J^*$ by the HJB equation, or $J^{FP}$ by formula (17) would trivialize the mission, and is ruled out.
Added hypotheses. Theorem 3 assumes $n\ge1$ , $t>0$ and $\lambda^*>0$ , which the page leaves implicit: the ratios divide by $J^*$ , which vanishes otherwise. Eqs. (13)–(14) are stated for every policy, without Proposition 1's bound $\lambda_s\le\lambda^*$ , and without the reduction to Markovian policies.
Corrected slips. (12) prints $J^D(x,t)=t\min\{r^*,r^0\}$ , which is false for $x>\lambda^*t$ (exponential demand with $x=at$ gives $r^0=0$ ). The statement uses $t\,r(\lambda^D)$ , and the printed form where $x\le\lambda^*t$ . The Remark's " $E(N_n-n)^+=n(1-P\{N_n=n\})$ " should read $E[\min\{N_n,n\}]$ ; its displayed $J^{FP}$ formula is right. Proposition 2's "the optimal solution" is stated as optimality, since uniqueness fails without strict concavity.
Welcome contributions. Infrastructure for counting processes with stochastic intensity (the clock construction, the compensator identity), Jensen and Lagrangian duality for concave integral functionals on rate paths, and Poisson truncated-mean computations.

Selected references

G. Gallego, G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8):999–1020, 1994. https://doi.org/10.1287/mnsc.40.8.999
G. Gallego, A Minmax Distribution Free Procedure for the (Q, R) Inventory Model, Operations Research Letters 11:55–60, 1992 (cited in the paper's references, p. 1019).
P. Brémaud, Point Processes and Queues: Martingale Dynamics, Springer-Verlag, New York, 1980 (as cited in the paper).
K. T. Talluri, G. J. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2004 (Chapter 5; on the platform as RevenueManagement.*).
G. Bitran, R. Caldentey, An Overview of Pricing Models for Revenue Management, Manufacturing & Service Operations Management 5(3):203–229, 2003 (on the platform as PricingRM.DetHeuristic.*).

15 thms2 active usersReviewed

Control Theory Operations Research Optimization·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 2: The Optimal Revenue Is Strictly Concave in Stock and Time; the Optimal Price Falls with Stock, Rises with TimeResearch Paper

Why the shape of the optimal pricing policy matters

A retailer holding a fixed stock of a perishable or seasonal good (fashion items, airline seats, hotel rooms, concert tickets) must sell it before a deadline, after which unsold units are worthless. Demand is random and depends on the posted price, and the firm may change its price at any time. Dynamic pricing asks how the price should depend on the remaining stock and the remaining time.

Gallego and van Ryzin (Management Science 40(8), 1994) posed this problem as a continuous-time intensity control problem and established its basic structure. Their Theorem 1 says that the optimal expected revenue is strictly increasing and strictly concave in both the stock and the time remaining, and that the optimal price falls as stock grows and rises with the time left to sell. The paper is a standard reference of revenue management; the structural result is the continuous-time counterpart of the monotonicity of marginal values in discrete-time models (Talluri and van Ryzin, The Theory and Practice of Revenue Management, 2004, Proposition 5.2), and it is what makes the optimal policy computable by restricting attention to monotone policies. The paper credits a slightly weaker version to Kincaid and Darling (1963). The source formalized here is the published 1994 article.

The model and the Hamilton–Jacobi system

The firm chooses a demand rate $\lambda$ from a set $\Lambda \subseteq [0,\infty)$ of allowable rates, an interval containing $0$ ; the market then sets the price $p(\lambda)$ , where $p$ is the inverse demand function, strictly decreasing and nonnegative on the positive rates. The rate $0$ corresponds to the null price at which nothing sells. The revenue rate is

r(\lambda) = \lambda\,p(\lambda), \qquad r(0) = 0.

The demand function is regular when $r$ is continuous, bounded and concave on $\Lambda$ and has a least maximizer $\lambda^* = \min\{\lambda : r(\lambda) = \max_{\mu\in\Lambda} r(\mu)\}$ . The exponential demand $\lambda(p) = ae^{-p}$ , with $\Lambda=[0,a]$ , $p(\lambda)=\log(a/\lambda)$ and $\lambda^*=a/e$ , is the running example.

With $n$ units in stock and time remaining $t$ , write $J(n,t)$ for the optimal expected revenue. The paper derives the Hamilton–Jacobi system

\frac{\partial J(n,t)}{\partial t} = \sup_{\lambda\in\Lambda}\big[r(\lambda) - \lambda\big(J(n,t)-J(n-1,t)\big)\big], \qquad n\ge1,\ t>0, \tag{8}

with $J(n,0)=0$ and $J(0,t)=0$ . The difference $J(n,t)-J(n-1,t)$ is the marginal value of an item; a rate attaining the supremum is an optimal intensity $\lambda^*(n,t)$ , and $p(\lambda^*(n,t))$ is the optimal price $p^*(n,t)$ .

Formalization targets

Goal: Theorem 1 (p. 1005)

For the solution $J$ of (8), with $r$ strictly concave, differentiable on the interior of $\Lambda$ , and $\lambda^*$ interior:

J(n,t)\ \text{strictly increasing in } n\ (t>0)\ \text{and in } t\ (n\ge1);\qquad J(n+1,t)-J(n,t) < J(n,t)-J(n-1,t);

t\mapsto J(n,t)\ \text{strictly concave};\qquad \exists\,\lambda^*(n,t):\ \lambda^*\!\uparrow_n,\ \lambda^*\!\downarrow_t,\quad p^*\!\downarrow_n,\ p^*\!\uparrow_t\ \text{(strictly)}.

Milestones

The supremum in (8) is a maximum over $[0,\lambda^*]$ whenever the marginal value is nonnegative (proof of Proposition 1).
Proposition 1: (8) has a unique solution, and $\lambda^*(n,s)\le\lambda^*$ .
Eq. (26): $J(n,t)-J(n-1,t) = r'(\lambda^*(n,t)) > 0$ for $t>0$ .
The case $n=1$ of Theorem 1: $\lambda^*(1,t)$ strictly decreasing and $J(1,t)$ strictly concave in $t$ .
$\lambda^*(n,0^+) = \lambda^*$ .
Eqs. (9)–(10), exponential demand: $J(n,t) = \log\sum_{i=0}^n(\lambda^*t)^i/i!$ and $p^*(n,t) = J(n,t)-J(n-1,t)+1$ .
Proposition 3, exponential demand: $\lambda^*(n,t)\le\lambda^D(n,t)=\min\{\lambda^*,n/t\}$ and $p^*(n,t)\ge p(\lambda^D(n,t))$ .

Significance

Theorem 1 is the qualitative backbone of single-product dynamic pricing. Concavity of $J$ in $n$ means that each additional unit is worth less than the previous one, which is the basis of bid-price and marginal-value reasoning in revenue management; the monotone price path justifies markdown practice as the deadline approaches and reduces the policy search to monotone policies. Proposition 3 answers, for exponential demand, a question raised by Mills (1959): the stochastic optimal price is never below the deterministic one. The closed form (9)–(10) is one of the few exactly solvable intensity control problems in pricing.

The results are proved in the paper; none of them has a machine-checked proof. Formalizing them requires the comparison and monotonicity theory of a countable system of coupled ordinary differential equations whose right-hand side is a convex conjugate, a theory that Mathlib does not package. A complete development would also certify the corrected hypotheses of Theorem 1 described below.

Difficulty

The value functions are defined only implicitly by (8), a triangular infinite system of ODEs in which each $J(n,\cdot)$ is driven by $J(n-1,\cdot)$ through the nonsmooth map $\Delta\mapsto\sup_\lambda[r(\lambda)-\lambda\Delta]$ . Monotonicity of the optimal intensity in $t$ is a statement about the time derivative of a marginal value, and the paper establishes it by an induction on $n$ combined with an argument by contradiction on the first interval where monotonicity could fail. The obvious approach of differentiating (8) twice in $t$ needs second derivatives of $r$ and of $J$ that the hypotheses do not provide, and the paper's own proof of Proposition 1 assumes that $J$ is nondecreasing in $n$ , which is only established in Theorem 1; a rigorous development must break this circularity.

Formalization scope

A regular demand function is a Lean structure (GVRPricing.Structure.Model) holding $\Lambda$ , $p$ and $\lambda^*$ with the paper's standing assumptions of §2.1: $0\in\Lambda\subseteq[0,\infty)$ an interval, $p$ strictly decreasing and nonnegative on $\Lambda\setminus\{0\}$ , $r(\lambda)=\lambda p(\lambda)$ continuous, concave and bounded on $\Lambda$ , and $\lambda^*$ the least maximizer. The definition IsHJBSolution encodes (8) for $J:\mathbb N\to\mathbb R\to\mathbb R$ , with the second argument the time remaining, the two-sided derivative at each $t>0$ , continuity on $[0,\infty)$ , the boundary conditions, and the requirement that the set inside the supremum be bounded above, so that the real supremum is never a default value. An optimal intensity at $(n,t)$ is any $\ell\in\Lambda$ maximizing $\lambda\mapsto r(\lambda)-\lambda(J(n,t)-J(n-1,t))$ over $\Lambda$ .

All theorems are about solutions of (8), on which the paper's proofs operate. The identification of the solution of (8) with the supremum of expected revenue over non-anticipating pricing policies is Brémaud's verification theorem, which the paper cites and does not prove; it is not part of this mission.

Added hypotheses and corrected statements.

As printed, Theorem 1 assumes only a regular demand function and is false: for $r(\lambda)=\sqrt\lambda$ on $[0,1]$ and $r=1$ beyond, $\lambda^*(1,t)=1$ for all $t\in(0,\ln2]$ ; for $r(\lambda)=\lambda-\lambda^2/4$ on $\Lambda=[0,1]$ , $\lambda^*=1$ is on the boundary and $\lambda^*(1,t)=1$ for small $t$ . The goal, eq. (26) and the case $n=1$ therefore assume that $r$ is strictly concave, differentiable on the interior of $\Lambda$ , and that $\lambda^*$ is interior; the appendix proof uses all three. Proposition 1, the restriction lemma and $\lambda^*(n,0^+)=\lambda^*$ use only the printed assumptions.
Strict claims in $n$ are made for $t>0$ , since $J(n,0)=0$ for all $n$ ; optimal intensities are considered for $n\ge1$ , $t>0$ .
Proposition 1's bound " $\lambda^*(n,s)\le\lambda^*$ for $0\le s$ " is read at $s=0$ as " $\lambda^*$ is optimal", since every maximizer of $r$ is optimal there.
Proposition 3 is stated for $n\ge1$ , $t>0$ (the page says $n\ge0$ , $t\ge0$ , where $n/t$ or the optimal intensity is undefined).
The exponential results use the paper's normalization $\alpha=1$ of $\lambda(p)=ae^{-\alpha p}$ .
The case $n=1$ omits the displayed identities involving $r''$ and $\lambda^{*\prime}$ , which presuppose second derivatives; its conclusions are stated.

A formalization that defines $J$ by a formula, or postulates a monotone function as the optimal intensity, would trivialize the goal: the goal quantifies over every solution of (8), and the optimal intensity it asserts must maximize the right-hand side of (8) at every $(n,t)$ .

A complete development needs comparison principles for scalar ODEs with Lipschitz right-hand sides, properties of the concave conjugate $\Delta\mapsto\sup_\lambda[r(\lambda)-\lambda\Delta]$ (monotonicity, Lipschitz continuity, envelope theorem), and monotone comparative statics of maximizers. These are reusable well beyond this mission; contributions of any of them, or of the milestones in any order, are welcome.

Selected references

G. Gallego, G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8), 999–1020, 1994. https://doi.org/10.1287/mnsc.40.8.999
P. Brémaud, Point Processes and Queues: Martingale Dynamics, Springer, 1981. https://doi.org/10.1007/978-1-4684-9477-8
W. M. Kincaid, D. A. Darling, An Inventory Pricing Problem, Journal of Mathematical Analysis and Applications 7, 183–208, 1963. https://doi.org/10.1016/0022-247X(63)90047-7
K. T. Talluri, G. J. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2004. https://doi.org/10.1007/b139000

10 thms2 active usersReviewed

Operations Research Optimization Theoretical Computer Science·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments I: Revenue-Ordered Assortments Earn OPT/(1 + ln(r_k/r_1)) Under Any Regular Choice ModelResearch Paper

Motivation

A retailer, an airline or an online platform decides which products to show a customer. Showing more is not always better: a customer who would have bought an expensive product may switch to a cheap one once it is offered. The assortment problem asks for the set of products that maximises expected revenue, given a model of how customers choose. It is a central problem of revenue management (Talluri and van Ryzin, 2004), and it is NP-hard even for mixtures of two multinomial logit models (Rusmevichientong, Shmoys, Tong and Topaloglu, 2014).

The standard heuristic in practice is revenue-ordered assortments: sort the products by price and only consider the sets consisting of the most expensive products down to some threshold. It is optimal under the multinomial logit model (Talluri and van Ryzin, 2004), but not in general. Berbeglia and Joret (arXiv:1606.01371) ask how much revenue the heuristic can lose under every reasonable choice model, and answer with guarantees that depend only on the prices.

Timeline:

2004: Talluri and van Ryzin prove revenue-ordered assortments optimal under the multinomial logit model.
2014: Rusmevichientong et al. show NP-hardness of the assortment problem for mixtures of logits, and prove that revenue-ordered assortments earn at least $\mathrm{OPT}/(e(1+\ln(r_k/r_1)))$ under mixed logit models.
2016–2019: Berbeglia and Joret prove the guarantees $1/k$ and $1/(1+\ln(r_k/r_1))$ under any regular choice model and show them tight (arXiv v1 2016, v3 2019; Algorithmica 2020). Aouad, Farias, Levi and Segev (2018) show that under random utility models no efficient algorithm does essentially better than these ratios.

Setting

There is a finite nonempty set $\mathcal C$ of products. For a choice set $S\subseteq\mathcal C$ , $\mathcal P(x,S)$ is the probability that a customer offered $S$ buys product $x$ , and $\mathcal P(0,S)=1-\sum_{x\in S}\mathcal P(x,S)$ is the probability that the customer buys nothing. The system $\mathcal P$ is a regular discrete choice model if

$\mathcal P(x,S)\ge0$ for every $x\in\mathcal C\cup\{0\}$ ;
$\mathcal P(x,S)=0$ whenever $x\notin S$ ;
$\sum_{x\in S}\mathcal P(x,S)\le1$ ;
$\mathcal P(x,S)\ge\mathcal P(x,S')$ whenever $S\subseteq S'$ and $x\in S\cup\{0\}$ .

Axiom 4, regularity, says that adding products never makes a given product, or leaving without buying, more likely. Every random utility model is regular.

Each product has a positive price $r(x)>0$ . The revenue of $S$ is $\operatorname{rev}(S)=\sum_{x\in S}\mathcal P(x,S)\,r(x)$ , and $\mathrm{OPT}=\max_{S\subseteq\mathcal C}\operatorname{rev}(S)$ . Let $0<r_1<\cdots<r_k$ be the distinct prices, so $k$ counts price levels and not products, and set $r_0=0$ . The revenue-ordered assortments are $S_i=\{x\in\mathcal C : r(x)\ge r_i\}$ , $i=1,\dots,k$ , and the heuristic earns

\mathrm{RO}=\max_{1\le i\le k}\operatorname{rev}(S_i).

Formalization targets

Goal: Theorem 3.2

\mathrm{OPT}\;\le\;\Big(\sum_{i=1}^{k}\frac{r_i-r_{i-1}}{r_i}\Big)\,\mathrm{RO} \qquad\text{and}\qquad \sum_{i=1}^{k}\frac{r_i-r_{i-1}}{r_i}\;\le\;1+\ln\frac{r_k}{r_1}.

The goal fixes no constant beyond the paper's own quantities. Both parts are required: the sum form is the sharper bound, and the paper shows it is attained (Theorem 3.4, a later mission of this series).

Milestones

Lemma 2.1: $\sum_{x\in S}\mathcal P(x,S)\le\sum_{x\in S'}\mathcal P(x,S')$ for $S\subseteq S'$ .
Inequality (5): $\operatorname{rev}(S_i)\ge r_i\sum_{x\in S^*\cap S_i}\mathcal P(x,S^*)$ for every $S^*$ and $i\in[k]$ .
Theorem 3.1: $\mathrm{OPT}\le k\cdot\mathrm{RO}$ .
Rearrangement (proof of Theorem 3.2): $\operatorname{rev}(S^*)=\sum_{\ell}(r_\ell-r_{\ell-1})\sum_{x\in S^*\cap S_\ell}\mathcal P(x,S^*)$ , and $\operatorname{rev}(S^*)\le\sum_\ell\frac{r_\ell-r_{\ell-1}}{r_\ell}\operatorname{rev}(S_\ell)$ .
Logarithmic bound: $\sum_{\ell=1}^k\frac{a_\ell-a_{\ell-1}}{a_\ell}\le1+\ln(a_k/a_1)$ for $0=a_0<a_1<\cdots<a_k$ .

Significance

The theorem shows that a pricing-only quantity controls the loss of the most common heuristic in revenue management, uniformly over all regular choice models, including every random utility model, mixtures of logits and Markov chain models. Combined with the hardness result of Aouad et al., it shows that revenue-ordered assortments achieve essentially the best ratio, as a function of $k$ or of $r_k/r_1$ , that an efficient algorithm can achieve. The same analysis transfers to the envy-free pricing and Stackelberg problems studied in the later sections of the paper.

The result is proved in the paper; to our knowledge it has no machine-checked proof. This mission produces a Lean formalization of regular choice models, the revenue-ordered heuristic and its two guarantees, on which the paper's tightness examples, the purchase-probability bound (Theorem 3.3) and the applications to pricing can build.

Difficulty

The argument is short, but two points are easy to get wrong. First, revenues of $S_i$ and of an optimal $S^*$ involve choice probabilities evaluated at different sets, so the comparison must pass through $S^*\cap S_i$ , using regularity once for products and once for the no-purchase option. A model that only assumes regularity for products does not satisfy the theorem. Second, the bound runs over distinct price levels, not products, and the first summand uses the convention $r_0=0$ ; indexing by products or dropping $r_0$ gives a different quantity. The comparison of the sum with $\ln(r_k/r_1)$ is a Riemann-sum estimate for $\int dt/t$ and needs a real-analysis lemma not phrased this way in Mathlib.

Formalization scope

Products are a finite nonempty type C with decidable equality; choice sets are Finset C. The choice probabilities are P : C → Finset C → ℝ, defined on all pairs. The no-purchase option is not a product: $\mathcal P(0,S)$ is the derived quantity noPurchase P S = 1 - ∑ x ∈ S, P x S.
IsRegular P carries axioms (i)–(iv), with (i) and (iv) each split into a product case and a no-purchase case. The no-purchase case of (i) is redundant with (iii) and is kept to match the page.
r : C → ℝ with the hypothesis ∀ x, 0 < r x. revenue P r S is $\operatorname{rev}(S)$ and opt P r is the maximum over all Finset C (Finset.sup'), including the empty set.
Price levels are 1-based: level r i is $r_i$ for $1\le i\le k$ and level r 0 = 0; numVals r is $k$ , the number of distinct values. roSet r i is $S_i$ ; roValue P r is the maximum over $i\in\{1,\dots,k\}$ only.
Approximation guarantees are stated in product form, $\mathrm{OPT}\le D\cdot\mathrm{RO}$ , never as a ratio. $\ln$ is Real.log, applied to $r_k/r_1\ge1$ .
Ruled out: a maximum over all subsets in place of $\mathrm{RO}$ (which makes the bound trivial), a regularity axiom without its no-purchase case, the logarithmic form alone in place of the sum form, and any specific choice model (logit, Markov chain, random utility) in place of an arbitrary regular $\mathcal P$ .

Needed infrastructure: finite sums over price levels and summation by parts, the comparison of $(b-a)/b$ with $\ln(b/a)$ , and the sorted enumeration of a finite set of reals (Finset.orderEmbOfFin). The regular model and the revenue-ordered sets are shared with the other missions of this series. Contributions of any milestone, alternative proofs of the logarithmic bound, and proofs that specific choice models are regular are welcome.

Selected references

G. Berbeglia and G. Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, 2019; Algorithmica 82, 2020. https://arxiv.org/abs/1606.01371
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
A. Aouad, V. Farias, R. Levi and D. Segev, The Approximability of Assortment Optimization Under Ranking Preferences, Operations Research 66(6), 2018. https://doi.org/10.1287/opre.2018.1724
P. Rusmevichientong, D. Shmoys, C. Tong and H. Topaloglu, Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters, Production and Operations Management 23(11), 2014. https://doi.org/10.1111/poms.12191

9 thms2 active usersReviewed

Operations Research Probability·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 3: With a Discrete Price Set the Two-Price Stopping-Time Heuristic Is Asymptotically OptimalResearch Paper

Motivation

Airlines, hotels and cruise lines rarely change prices continuously. They sell a fixed product (seats on one flight, rooms on one night) over a finite selling season, and they sell it at a small set of fares, opening and closing fare classes as the season unfolds. Gallego and van Ryzin, in Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons (Management Science 40(8), 1994, doi:10.1287/mnsc.40.8.999), model this as the sale of $n$ items over a horizon of length $t$ , with Poisson demand whose rate depends on the current price. Section 4 of the paper restricts the price to a finite menu and asks how much is lost by using a simple rule that charges only two adjacent prices and switches once. The answer, Theorem 5, gives one explanation of fixed-fare-class yield management: with two fares and one well-timed switch, a seller earns asymptotically the best revenue any policy over the menu can earn. The source of this mission is the published 1994 article.

The paper is the starting point of a long line of work on fluid (deterministic) approximations in revenue management, including Feng and Gallego (1995) on optimal switching times between two prices and later re-solving and bid-price analyses, all of which compare stochastic policies to the value of a deterministic problem in the same way.

Setting

A menu consists of $K\ge2$ prices $p_1<p_2<\dots<p_K$ and Poisson demand rates $\lambda_1>\lambda_2>\dots>\lambda_K>0$ ; the firm may also charge the null price $p_\infty$ , at which demand is $0$ . The revenue rates $r_k=p_k\lambda_k$ satisfy $r_1>r_2>\dots>r_K$ , and the points $(\lambda_k,r_k)$ lie on a concave function on $[0,\infty)$ vanishing at $0$ .

The deterministic problem replaces random demand by its rate. If $t_k\ge0$ is the time spent at price $p_k$ , the problem is the linear program

J^D(n,t)=\sup\Big\{\sum_k r_k t_k:\ \sum_k t_k\le t,\ \sum_k\lambda_k t_k\le n,\ t_k\ge0\Big\}.

Given $n\in\mathbb N$ and $t>0$ , let $k=k^*$ be the index with $\lambda_k t\ge n>\lambda_{k+1}t$ , and put

t_k=\frac{n-\lambda_{k+1}t}{\lambda_k-\lambda_{k+1}},\qquad m=\lceil\lambda_k t_k\rceil,\qquad t_m=\frac{m}{\lambda_k}.

The stopping-time (ST) heuristic starts at price $p_k$ and switches to $p_{k+1}$ at the random time $\tau=\min(T_m,t_m)$ , where $T_m$ is the time of the $m$ -th demand. Sales stop when the $n$ items are gone or at time $t$ . $J^{ST}(n,t)$ is its expected revenue.

Formalization targets

Goal: Theorem 5

For a fixed index $k$ with $1\le k\le K-1$ and any sequences $n_j\in\mathbb N$ , $t_j\to\infty$ with $\lambda_k t_j\ge n_j>\lambda_{k+1}t_j$ ,

\lim_{j\to\infty}\frac{J^{ST}(n_j,t_j)}{J^D(n_j,t_j)}=1.

No rate of convergence is fixed in the goal, and the ratio $n_j/t_j$ may vary along the sequence.

Milestones

Proposition 4. The LP is solved by pricing at $p_{k^*}$ for time $t_{k^*}$ and at $p_{k^*+1}$ for time $t_{k^*+1}=(\lambda_{k^*}t-n)/(\lambda_{k^*}-\lambda_{k^*+1})$ , together with the edge cases $k^*=0$ and $k^*=K$ .
The wasteful heuristic is a lower bound: $J^W(n,t)\le J^{ST}(n,t)$ , where the wasteful heuristic offers $m$ units at $p_k$ during $[0,t_m]$ and $n-m$ units at $p_{k+1}$ afterwards.
Equation (28): the shrunk horizon $t'=t_m+(n-m)/\lambda_{k+1}$ satisfies $t-(\lambda_k-\lambda_{k+1})/(\lambda_k\lambda_{k+1})<t'\le t$ .
The closed form of $J^D$ and $J^D(n,t)<J^D(n,t')+(p_{k+1}-p_k)$ .
Equation (29): $J^{ST}(n,t)/J^D(n,t)\ge J^W(n,t)/J^D(n,t)\ge J^W(n,t')/(J^D(n,t')+(p_{k+1}-p_k))$ .
The wasteful bound: $J^W(n,t')\ge p_k[m-\tfrac12\sqrt m]+p_{k+1}[(n-m)-\tfrac12\sqrt{n-m}]$ and $J^W(n,t')/J^D(n,t')\ge1-\tfrac12(1/\sqrt m+1/\sqrt{n-m})$ .

Significance

Theorem 5 says that a policy with one price change, chosen from the deterministic solution, loses a vanishing fraction of the deterministic revenue. Since $J^D$ bounds the optimal expected revenue over all non-anticipating policies with prices in the menu (§4.0.1 of the paper), the ST heuristic is asymptotically optimal, and the optimal policy, which solves a Hamilton–Jacobi–Bellman system with no closed form, can be replaced by a rule that is computed by hand. The result also shows that a finite menu, together with dynamic allocation of capacity between two neighbouring prices, can realize the effective price of a continuous demand curve.

The theorem is proved in the paper. As far as the platform's index shows, neither this result nor the controlled Poisson sales process it needs has been formalized; Mathlib has the exponential and Poisson distributions but no counting process with a policy-dependent intensity. The mission produces a machine-checked version of the paper's proof chain: the LP solution, the coupling inequality between two heuristics, the deterministic horizon estimate (28), and the Poisson overflow estimate built on Gallego's bound (inequality (18) of the paper, already proved on the platform as PricingRM.DetHeuristic.gallego_bound).

Difficulty

The deterministic parts (Proposition 4, (28), the closed form of $J^D$ ) are finite-dimensional linear algebra. The difficulty sits in the stochastic comparison $J^W\le J^{ST}$ . The ST heuristic's switching time depends on the sales process, and after the switch the remaining stock and the remaining time are both random. The obvious attempt, writing $J^{ST}$ as a sum of two independent Poisson terms, is wrong: the two phases are dependent through $\tau$ . Any comparison has to handle a second phase whose starting stock and starting time are both random, which brings in the behaviour of the sales process after a random time determined by the process itself. The limit step then needs the overflow bound uniformly along sequences whose ratio $n/t$ is not fixed.

Formalization scope

All declarations live in the namespace GVRPricing.StoppingTime. The committed conventions are:

Indices are 0-based (Fin K): Lean index $k$ is the paper's price number $k+1$ , and lamN, pN, rN extend the sequences by $0$ beyond $K$ , matching the paper's $\lambda_{K+1}=r_{K+1}=0$ .
The menu carries the printed conditions plus an added concavity condition: the points $(\lambda_k,r_k)$ lie on a concave function vanishing at $0$ . This is the reading of §4's "corresponding to price $p_k$ , we have a known demand rate $\lambda_k$ " for a regular demand function with concave revenue rate. Without it Proposition 4 and Theorem 5 are false: the menu $\lambda=(3,2,1)$ , $p=(1,1.01,1.5)$ meets every printed condition, but at $t=1$ , $n=1.5$ Proposition 4's allocation earns $1.76$ while a feasible mix of $p_1$ and $p_3$ earns $1.875$ , and the ST ratio tends to about $0.939$ .
$J^D$ is defined directly as the LP value; the reduction from the rate-path problem (11) is the paper's assertion and is not formalized.
The sales process is built from $n$ i.i.d. standard exponential clocks by the time change of the ST policy's cumulative intensity, so at most $n$ items are sold. Time is elapsed time from $0$ . $J^{ST}$ is the expectation of the sum of prices charged at sales in $[0,t]$ , a lower Lebesgue integral of a bounded nonnegative function.
$J^W$ is the paper's two-Poisson formula of p. 1018.
$J^*$ is not defined, so the left ratio of (29) uses $J^D$ in place of $J^*$ (a stronger inequality, since $J^*\le J^D$ ), and the §4.0.1 upper bound $J^*\le J^D$ is not a milestone.
Corrected slips: the page prints $t_{n-m}\doteq n-m/\lambda_{k+1}$ for $(n-m)/\lambda_{k+1}$ ; the wasteful bound is stated at the shrunk horizon $t'$ , where its integrality assumptions hold exactly, instead of along the paper's subsequence; the ratio bound assumes $m<n$ , since $1/\sqrt{n-m}$ is undefined otherwise. Proposition 4 is stated as optimality, without the uniqueness that fails when three menu points are collinear.
Excluded: the edge cases $k^*=0$ and $k^*=K$ of Theorem 5, treated on the page only in an unproved remark.

A trivializing formalization would define $J^{ST}$ through the wasteful formula, or by a closed-form expression, which makes the goal the wasteful bound; here $J^{ST}$ is the expected revenue of the switching rule $\tau=\min(T_m,t_m)$ on the sales process. Likewise the limit is taken along sequences with $t_j\to\infty$ , not at a single $(n,t)$ .

Useful infrastructure, reusable beyond this mission: the exponential-clock construction of a Poisson process with piecewise-constant intensity, the strong Markov property at a stopping time of the clocks, and the expected Poisson overflow $\mathbb E(N_\mu-\mu)^+$ . Contributions to any milestone, and alternative proofs of $J^W\le J^{ST}$ , are welcome.

Selected references

G. Gallego, G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8), 999–1020, 1994. doi:10.1287/mnsc.40.8.999
G. Gallego, A Minmax Distribution Free Procedure for the (Q, R) Inventory Model, Operations Research Letters 11, 55–60, 1992 (the source of inequality (18)).
Y. Feng, G. Gallego, Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares, Management Science 41(8), 1995.
P. Brémaud, Point Processes and Queues: Martingale Dynamics, Springer-Verlag, New York, 1980 (as cited in the source).

11 thms2 active usersReviewed

Bandit Algorithms Operations Research Probability+1·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms I: The Nonparametric Learn-then-Price Policy Has Regret at Most C(log n)^{1/2}/n^{1/4}Research Paper

Why price without knowing demand

A seller with a fixed stock of a single product and a finite selling season has to set prices without knowing how demand responds to them. This is the standard situation in revenue management: airline seats, hotel rooms, fashion goods and event tickets. The classical theory of dynamic pricing (Gallego and van Ryzin, 1994) assumes that the demand function $\lambda(p)$ , the rate of purchase requests at price $p$ , is known. In practice it has to be learned from sales, while the season runs and the stock is consumed.

Besbes and Zeevi (2009) asked how much revenue is lost for not knowing $\lambda$ . They answered it with explicit policies and matching-order bounds. Their setting differs from the multi-armed bandit literature it borrows from in three ways:

the problem is constrained by an initial inventory;
the set of prices is a continuum;
the set of possible demand functions is a nonparametric class.

This mission formalizes their first main result, Proposition 1: a simple learn-then-price policy has worst-case relative regret of order $(\log n)^{1/2}n^{-1/4}$ in a market of size $n$ .

Setting

Prices. Fix $0<\underline p<\overline p<\infty$ and an off price $p_\infty>0$ outside $[\underline p,\overline p]$ . The seller may charge any price in $[\underline p,\overline p]\cup\{p_\infty\}$ ; charging $p_\infty$ stops demand.

Demand. Requests arrive as a Poisson process whose intensity at time $t$ is $\lambda(p(t))$ . Let $N$ be a unit-rate Poisson process. By the time change (1), the cumulative requests up to time $t$ under a price path $p(\cdot)$ are $N\big(\int_0^t\lambda(p(s))\,ds\big)$ . The seller starts with inventory $x$ and sells until either the horizon $T$ ends or the stock runs out. The expected revenue of a policy $\pi$ is $J^\pi(x,T;\lambda)$ .

Demand class. $\mathcal L=\mathcal L(M,\underline K,\overline K,m)$ is the set of regular demand functions satisfying Assumption 1. Regular means:

$\lambda\ge0$ and $\lambda(p_\infty)=0$ ;
$\lambda$ is non-increasing on $[\underline p,\overline p]$ , with inverse $\gamma$ ;
the revenue rate $r(l)=l\gamma(l)$ is concave.

Assumption 1 requires:

(i) $\lambda\le M$ on $[\underline p,\overline p]$ ;
(ii) $\lambda$ is $\overline K$ -Lipschitz and $\gamma$ is $\underline K^{-1}$ -Lipschitz;
(iii) $\max_p p\lambda(p)\ge m$ .

Benchmark. The deterministic relaxation (5) replaces the random demand by its mean:

J^D(x,T\mid\lambda)=\sup\Big\{\int_0^T p(s)\lambda(p(s))\,ds:\int_0^T\lambda(p(s))\,ds\le x\Big\}.

The regret of a policy is $\mathcal R^\pi=1-J^\pi/J^D$ .

Scaling. In a market of size $n$ the inventory is $nx$ and the demand function is $n\lambda$ , as in (11). The corresponding quantities are $J^\pi_n$ , $J^D_n=nJ^D$ and $\mathcal R^\pi_n$ .

Algorithm 1, $\pi(\tau,\kappa)$ . The policy has three phases.

Learning. On $[0,\tau]$ it tests $\kappa$ equally spaced prices $p_i=\underline p+(i-1)(\overline p-\underline p)/\kappa$ , each for $\Delta=\tau/\kappa$ time units. It estimates $\lambda(p_i)$ by the normalized request counts $\hat\lambda(p_i)$ .
Optimization. It chooses $\hat p^u=\arg\max_i p_i\hat\lambda(p_i)$ and $\hat p^c=\arg\min_i|\hat\lambda(p_i)-x/T|$ , and sets $\hat p=\max\{\hat p^u,\hat p^c\}$ .
Pricing. It charges $\hat p$ on $(\tau,T]$ until the stock runs out.

Formalization targets

Goal: Proposition 1

Let $\tau_n\asymp n^{-1/4}$ and $\kappa_n\asymp n^{1/4}$ , and let $\pi_n=\pi(\tau_n,\kappa_n)$ . Then there is a finite constant $C$ , independent of $\lambda$ and $n$ , such that

\sup_{\lambda\in\mathcal L}\mathcal R^{\pi}_n(x,T;\lambda)\le\frac{C(\log n)^{1/2}}{n^{1/4}}\qquad(n\ge2).

The constant is left unspecified, as in the paper. Its dependence on the class parameters, $x$ and $T$ is "somewhat complex" (p. 12), and the order $(\log n)^{1/2}n^{-1/4}$ is the content of the result.

Milestones

The milestones follow the proof in the appendix, in order:

the scaling $J^D_n=nJ^D$ (p. 12);
Fact 1, $J^D\ge m\min\{T,x/M\}$ on $\mathcal L$ ;
Lemma 1, the solution of (5): charge $p^D=\max\{p^u,p^c\}$ until the stock runs out;
Lemma 2, a Poisson deviation bound;
the revenue lower bound (A-2);
Lemma 3, the learned price is near $p^D$ with high probability;
Lemma 4 and the Case 1 bound (A-11), for $\lambda(\overline p)\le x/T$ ;
Lemma 5 and the Case 2 bound (A-15), for $\lambda(\overline p)>x/T$ ;
the Step 4 bound $\mathcal R^\pi_n\le C_{12}(u_n+\tau_n)$ , where $u_n=(\log n)^{1/2}\max\{1/\kappa_n,(n\Delta_n)^{-1/2}\}$ .

Significance

Proposition 1 shows that a seller who knows only a nonparametric class of demand functions can approach the full-information revenue uniformly over the class. Learning costs a vanishing fraction of revenue, and the policy needs no parametric model. Together with the paper's lower bound of order $n^{-1/2}$ for every admissible policy (Proposition 2, not in this mission), it brackets the minimax regret of nonparametric pricing under an inventory constraint. The result is a reference point for the learning-and-earning literature in operations management that followed it.

The result is proved in the paper; to our knowledge, it has no machine-checked proof. Formalizing it requires:

a working theory of policies driven by a time-changed Poisson process, with sales capped by an inventory;
the deterministic relaxation of Gallego and van Ryzin for a continuum of prices with an off price;
uniform (over the class) Poisson concentration bounds.

The mission produces Lean statements of all of these. A proof would also check every constant chain of the appendix, where the argument uses some displays in a form slightly different from their printed statement (see the scope section).

Difficulty

The obvious argument controls the estimation error at the tested prices and concludes that $\hat p$ is close to the optimal price. It breaks in two places.

First, $p^D$ is the larger of two prices, the revenue maximizer and the price that sells the inventory exactly. Near the boundary between these regimes, the revenue rate at $\hat p$ is not controlled by the error in $\hat p$ alone: it needs the concavity of the revenue rate and the inverse Lipschitz bound on $\gamma$ .

Second, when demand at the highest price exceeds the inventory rate ( $\lambda(\overline p)>x/T$ ), the revenue is limited by stock-outs rather than by the price. The bound must then show that nearly all of the inventory is sold during the pricing phase, uniformly over the class.

Throughout, every constant must be independent of the demand function, so the estimates have to hold uniformly over an infinite-dimensional class.

Formalization scope

Poisson process. The demand is driven by IsPoissonProcess N 1 on a probability space $(\Omega,\mathbb P)$ , a published platform definition: ℕ-valued, $N(0)=0$ , monotone paths, independent Poisson increments. The time change (1) is rendered by evaluating $N$ at cumulative intensities.
Inventory. The inventory of the market of size $n$ is $\lfloor nx\rfloor$ units, and sales are $\min\{N(\cdot),\lfloor nx\rfloor\}$ . The cap is never dropped.
Revenue. $J^\pi_n$ is the Bochner expectation of a bounded, finitely-valued revenue, so it is a genuine integral.
Demand functions. A demand function is a map $\mathbb R\to\mathbb R$ , nonnegative, with $\lambda(p_\infty)=0$ . Regularity and Assumption 1 are imposed on $[\underline p,\overline p]$ , and the inverse $\gamma$ is Function.invFunOn.
Benchmark. $J^D$ is a supremum over measurable price paths with integrable demand rate. The supremum is genuine: the set of path revenues is nonempty and bounded.
Algorithm. The grid excludes $\overline p$ , as in the paper. Ties in the grid argmax and argmin go to the smallest index. The estimates compare $\hat\lambda(p_i)$ with $x/T$ .
Tuning. $\tau_n\asymp n^{-1/4}$ and $\kappa_n\asymp n^{1/4}$ are encoded with explicit constants $0<c\le c'$ , with $\tau_n\in(0,T]$ and $\kappa_n\ge1$ . Constants may depend on $c,c'$ , the class parameters, the prices, $x$ and $T$ , but never on $\lambda$ or $n$ .
Range of $n$ . Bounds whose right side vanishes at $n=1$ because $\log1=0$ are stated for $n\ge2$ : the goal and (A-15).
Typo correction. Lemma 5's event uses $nx-C_9nu_n$ , as in its proof, not the printed $nx-C_9u_n$ .
Ruled out. A specific demand curve, a fixed $n$ , deterministic demand, a finite price set, a known $\lambda$ , constants depending on $\lambda$ , or dropping the inventory cap would each make the statement a different and easier theorem. None is used.
Not included. The lower bound of Proposition 2 and the second assertion of Lemma 1 ( $J^\pi\le J^D$ for all admissible policies) are not included.

Contributions are welcome at any level: proofs of the milestones (Fact 1, Lemma 1 and Lemma 2 are self-contained), measurability and integrability lemmas for the revenue functional, and a reusable Poisson concentration library built on Mathlib's poissonMeasure.

Selected references

O. Besbes and A. Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6):1407–1420, 2009. https://doi.org/10.1287/opre.1080.0640
G. Gallego and G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8):999–1020, 1994. https://doi.org/10.1287/mnsc.40.8.999
K. Talluri and G. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2005. https://doi.org/10.1007/b139000

15 thms3 active usersReviewed

Bandit Algorithms Operations Research Probability+1·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms II: The Parametric Learn-then-Price Policy Has Regret at Most C(log n)^{1/2}/n^{1/3}Research Paper

Why learn demand while pricing?

A seller with a fixed inventory must choose prices before knowing how customers respond to them. A price that earns a high margin can sell too slowly; a price that sells quickly can exhaust stock before the selling season ends. Learning demand uses time and inventory, so the seller must account for the cost of its own experiments. This mission formalizes the parametric policy and regret bound of Besbes and Zeevi (2009), Proposition 3. Their setting differs from a finite-arm bandit: the permitted ordinary prices form an interval, customer arrivals are random, and the available stock caps total sales.

The paper first analyzes a nonparametric class with a slower upper bound in Proposition 1, then imposes a known finite-dimensional form on the unknown demand curve in Section 5. Proposition 3 shows how that additional information improves the regret rate for its Algorithm 2. The authors also prove a lower bound for a suitable parametric family in Proposition 4; that result is outside this mission's capstone, which concerns the performance guarantee of the concrete policy.

Market, demand, and policy

The selling horizon has length $T>0$ , and the initial stock is $x>0$ . An ordinary price $p$ lies in $[\underline p,\overline p]$ , with $0<\underline p<\overline p$ . The special price $p_\infty>0$ stops demand. At parameter $\theta\in\Theta\subseteq\mathbb R^k$ , the demand rate is $\lambda(p;\theta)\ge0$ . The parameter set $\Theta$ is nonempty, compact, and convex; $k$ is positive. The seller knows the family $\lambda(\cdot;\theta)$ but does not know the true parameter $\theta^*$ .

For each parameter, demand is nonincreasing in the price and has an inverse $\gamma(\cdot;\theta)$ on the attainable rate interval. The rate revenue is $r(\ell;\theta)=\ell\gamma(\ell;\theta)$ , a concave function of the rate. Every member of the family satisfies Assumption 1 with the same positive constants $M,\underline K,\overline K,m$ : demand is at most $M$ , its price variation is at most $\overline K$ times the price difference, its inverse is $\underline K^{-1}$ -Lipschitz, and some ordinary price earns revenue rate at least $m$ . These conditions define the class in which the bound is uniform. See §§3–4.2 of the source.

Customer requests follow a unit-rate Poisson process $N$ run on a demand-dependent clock. Under price $p(t)$ , cumulative requests at time $t$ equal $N(\int_0^t\lambda(p(s);\theta^*)\,ds)$ . The market of size $n$ has stock $nx$ and rate $n\lambda$ . Sales stop when stock runs out. The deterministic relaxation $J_n^D$ is the best integrated rate revenue over measurable price paths satisfying the expected-demand stock constraint, with the same scaling. The policy revenue $J_n^\pi$ is its expected sales revenue, and its relative regret is $R_n^\pi=1-J_n^\pi/J_n^D$ . Fact 1 states $J_n^D=nJ^D$ and gives a positive uniform lower bound on $J^D$ .

Assumption 2 selects $k$ distinct ordinary test prices. Their mean rates identify the parameter through a Lipschitz inverse map $g$ , and demand changes at most $\overline K_2\|\theta-\theta'\|_\infty$ as the parameter varies. The square root of each test-price rate is differentiable on $\Theta$ . Algorithm 2 spends $\tau_n$ time units testing these prices in equal subintervals, estimates each rate from its Poisson count increment, and sets $\widehat\theta=g(\widehat d)$ . It then posts $\widehat p=\max\{p^u(\widehat\theta),p^c(\widehat\theta)\}$ , where $p^u$ maximizes revenue rate and $p^c$ minimizes the distance of demand to $x/T$ . It keeps that price until time $T$ or stock-out. See §5.1–5.2.

Formalization targets

The capstone is the uniform bound in Proposition 3, equation (17). With $\tau_n\asymp n^{-1/3}$ , the mission asks for one constant $C>0$ , independent of $n$ , $\theta^*$ , the optimizer choices, and the probability space, such that

\forall\theta^*\in\Theta,\qquad R_n^\pi(x,T;\theta^*)\le C\frac{\sqrt{\log n}}{n^{1/3}}\quad(n\ge2).

The intermediate quantitative target is equation (A-25), which retains the learning time:

R_n^\pi\le\frac{C_3}{m^D}\left(\tau_n+\frac{\sqrt{\log n}}{\sqrt{n\tau_n}}\right),\qquad m^D=m\min\{T,x/M\}.

The milestone list also carries Fact 1, the optimal deterministic price path and value from the first assertion of Lemma 1, both Poisson tails of Lemma 2, the pricing-phase revenue bound (A-17), the deterministic stability bounds (A-19), (A-22), and (A-23), and the parameter-estimation bound of Lemma 6. The paper's assertion that the policy is “asymptotically optimal” follows from the displayed regret estimate together with nonnegative regret; the displayed numerical estimate is the formal goal.

What the result provides

A finite-dimensional demand model lets the seller learn from a fixed set of $k$ prices rather than probing an increasingly fine price grid. Proposition 3 quantifies the resulting revenue loss at $O(\sqrt{\log n}\,n^{-1/3})$ , compared with the paper's $O(\sqrt{\log n}\,n^{-1/4})$ upper bound for its nonparametric learn-then-price policy. Both guarantees compare actual expected revenue with the full-information deterministic benchmark, including stock-out. These rates are proved in the article; the mission seeks machine-checked Lean proofs of the stated model, auxiliary bounds, and capstone. No such proof is claimed here.

The formalization would also provide reusable interfaces for a unit-rate Poisson counting process, deterministic inventory-constrained revenue optimization, measurable price selectors, and a random price chosen from normalized count observations. The later single-parameter policy in the paper uses related ideas but is a separate mission with different stages and a different rate.

Main difficulty

A rate estimate can be close to the true rate while the selected price changes between two different optimizers: the unconstrained revenue maximizer and the price that matches inventory to expected demand. A bound for only one optimizer does not control the maximum of the two. The learning price is random, and the number of requests in the pricing phase is evaluated at a random Poisson clock. Stock-out further couples the learning phase to the amount available for later sales. These features prevent a direct substitution of an ordinary parameter-estimation bound into the final revenue formula.

Formalization scope

Lean uses $\mathrm{Fin}(k)\to\mathbb R$ with its sup norm for parameter vectors, a finite positive off price, and a Poisson process on an arbitrary probability space. Each demand curve is defined on all real prices but is constrained on $[\underline p,\overline p]$ and at $p_\infty$ ; the inverse and concavity conditions apply on the attainable rate interval. The deterministic benchmark is a real supremum over measurable, integrable admissible price paths. The class assumptions make its value nonempty and bounded. Policy revenue uses a nonnegative integral of pathwise revenue, avoiding a default zero from a nonintegrable signed expectation.

Inventory is measured in whole units, so the cap is $\lfloor nx\rfloor$ , equal to the paper's $nx$ when that quantity is integral. Test-price observations remain uncapped in the formula for $\widehat d$ ; if stock runs out during learning, capped later sales are already zero. The continuous optimizer choices are measurable selections satisfying the actual max/min properties for every member of $\Theta$ . The bound is uniform over these choices and over all unit-rate Poisson processes.

The printed Assumption 2(i)b asks for a solution to the test-rate equations for every vector in $\mathbb R^k$ . Such a solution cannot always lie in compact $\Theta$ , although the proof applies Assumption 2(ii) to $\widehat\theta$ . Here $g$ is a Lipschitz map into $\Theta$ that recovers each true parameter from its test-rate vector; it can be viewed as the unconstrained inverse followed by a nonexpansive projection in the paper's box example. This explicit convention is required to make the estimate and subsequent use of Assumption 2(ii) coherent. It is an interpretive repair of the printed condition.

The paper prints the regret bound for $n\ge1$ , where $\sqrt{\log1}=0$ . The exploration policy can lose revenue at $n=1$ , so the formal theorem starts at $n\ge2$ . The comparison $\tau_n\asymp n^{-1/3}$ is encoded by positive lower and upper multipliers after a fixed threshold, with $0<\tau_n\le T$ for all relevant market sizes. This admits the usual finite initial adjustments and leaves the bound uniform over the sequence. No fixed demand curve, known parameter, finite price grid, or uncapped sales model can satisfy this target by substitution.

Selected references

Omar Besbes and Assaf Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6), 2009, authors' final manuscript revised December 16, 2007. DOI: 10.1287/opre.1080.0640.

13 thms2 active usersReviewed

Bandit Algorithms Operations Research Probability+1·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms III: With One Unknown Parameter, Staged Re-estimation Has Regret O((log log n)(log n)^{1/2}/n^{1/2})Research Paper

Motivation

A seller with a fixed stock of a single product and a finite selling season must post prices without knowing how demand responds to price. Revenue management treats this as a constrained stochastic control problem; with the demand curve known, the problem was solved by Gallego and van Ryzin (Management Science, 1994). When the curve is unknown, every price posted also serves as an experiment, so the seller faces an exploration–exploitation trade-off. Unlike a multi-armed bandit, this problem has a continuum of actions and a hard inventory constraint.

Besbes and Zeevi (Operations Research, 2009) measure a pricing policy by its worst-case relative revenue loss against a full-information benchmark, in an asymptotic regime where inventory and demand grow together. They give three upper bounds. This mission takes the third, Proposition 5: when the demand model has a single unknown scalar parameter, a policy that keeps re-estimating that parameter in stages of growing length has regret $O\big((\log\log n)(\log n)^{1/2}/n^{1/2}\big)$ . The paper's lower bound for parametric families (Proposition 4) is of order $n^{-1/2}$ , so the rate is optimal up to logarithmic factors.

Setting

Market. Prices lie in $[\underline p,\overline p]\cup\{p_\infty\}$ with $0<\underline p<\overline p<p_\infty$ . Posting the off price $p_\infty$ stops demand. The seller starts with inventory $x>0$ and sells over the horizon $[0,T]$ , $T>0$ .

Demand. A demand function $\lambda$ maps a price to a demand rate. The class $\mathcal L(M,\underline K,\overline K,m)$ consists of the functions that are non-increasing with an inverse $\gamma$ on $[\underline p,\overline p]$ , have a concave revenue rate $r(l)=l\gamma(l)$ , are bounded by $M$ , are $\overline K$ -Lipschitz with a $\underline K^{-1}$ -Lipschitz inverse, and attain a revenue rate $\max_p p\lambda(p)\ge m$ . The parametric family is $\lambda(p;\theta)$ , $\theta\in\Theta=[\theta_{\mathrm{lo}},\theta_{\mathrm{hi}}]$ , with every member in the class (Assumption 1). Assumption 2 adds a test price $p_1$ , differentiability of $\sqrt{\lambda(p_1;\cdot)}$ and the Lipschitz bound $|\lambda(p;\theta)-\lambda(p;\theta')|\le\overline K_2|\theta-\theta'|$ . Assumption 3 requires $\inf_{p,\theta}\lambda(p;\theta)>l_0>0$ and an $\alpha$ -Lipschitz solution map $d\mapsto g(p,d)$ of the equation $\lambda(p;\cdot)=d$ .

Demand process. Let $N$ be a unit-rate Poisson process. Under a price path $p(\cdot)$ and parameter $\theta^*$ , the cumulative demand up to time $t$ is $N\big(\int_0^t\lambda(p(s);\theta^*)\,ds\big)$ . Sales stop when the inventory runs out.

Benchmark and regret. The deterministic relaxation $J^D(x,T\mid\theta)$ is the supremum of $\int_0^T p(s)\lambda(p(s);\theta)\,ds$ over price paths with $\int_0^T\lambda(p(s);\theta)\,ds\le x$ . In the market of size $n$ the inventory is $nx$ and the demand $n\lambda$ . If $J^\pi_n(x,T;\theta)$ is the expected revenue of a policy $\pi$ , its regret is $\mathcal R^\pi_n=1-J^\pi_n/J^D_n$ .

Algorithm 3. Start from $\hat p_1=p_1$ and use stages of lengths $\Delta^{(1)}_n,\dots,\Delta^{(\ell_n)}_n$ summing to $T$ . Stage $i$ applies $\hat p_i$ , estimates the demand rate $\hat d_i$ from the stage's demand, solves for $\hat\theta_i=g(\hat p_i,\hat d_i)$ , and sets $\hat p_{i+1}=\max\{p^u(\hat\theta_i),p^c(\hat\theta_i)\}$ . Here $p^u(\theta)$ maximizes $p\lambda(p;\theta)$ and $p^c(\theta)$ minimizes $|\lambda(p;\theta)-x/T|$ . The tuning (19)–(20) is $\ell_n=(\log2)^{-1}\log\log n$ stages with $\Delta^{(m)}_n=\beta_n n^{(a_{\ell_n}/a_m)-1}$ and $a_m=2^{m-1}/(2^m-1)$ .

Formalization targets

Goal: Proposition 5

\exists\,C>0,\ \exists\,n_0,\quad \forall n\ge n_0,\ \forall\theta\in\Theta:\qquad \mathcal R^{\pi_n}_n(x,T;\theta)\le C\,\frac{(\log\log n)(\log n)^{1/2}}{n^{1/2}} .

The constants are uniform in $\theta$ and $n$ . This is the paper's (21): $\sup_\theta\mathcal R^{\pi}_n=O(\cdot)$ .

Milestones, in proof order

Fact 1: $J^D_n=nJ^D$ and $J^D\ge m\min\{T,x/M\}$ on the class.
Lemma 1: the deterministic relaxation is solved by the fixed price $p^D=\max\{p^u,p^c\}$ .
Lemma 2: Poisson deviation bounds at scale $(\log n/r_n)^{1/2}$ .
(A-27): a revenue lower bound that splits the loss into stage-wise terms and an overflow term.
The per-stage revenue gap $r(p^D)-\mathbb E\,r(\hat p_i)\le C_2(n\Delta^{(i-1)}_n)^{-1/2}$ .
(A-30): the stage- $i$ demand rate rarely exceeds the run-out rate.
The overflow bound $\mathbb E[(Y_n-nx)^+]\le nC_8(\log n)^{1/2}n^{a_{\ell_n}-1}$ .
(A-31): the revenue ratio before the exponents are evaluated.
The rate estimate $n^{a_{\ell_n}-1}\le e\,n^{-1/2}$ .

Milestones 6–8 hold in the case $\lambda(\overline p;\theta^*)\le x/T$ , the only case the paper's proof treats in detail.

Significance

Proposition 5 shows that with one unknown parameter, learning while earning reaches the $n^{-1/2}$ rate, up to logarithms. The learn-then-price policies of Propositions 1 and 3 stop learning after an initial phase and reach only $n^{-1/4}$ and $n^{-1/3}$ . The paper leaves open whether the multi-parameter case attains the lower bound.

The analysis combines a continuous-time controlled Poisson model, an inventory constraint and a staged estimator, which also appear in later work on dynamic pricing with learning. A formal development would provide a time-changed Poisson demand model with random stage boundaries, a deterministic-relaxation benchmark, and concentration bounds stated for the scales this literature uses.

The result is proved in the paper, but parts of the proof are only sketched. The case $\lambda(\overline p;\theta^*)>x/T$ is dismissed with "a similar result holds". The per-stage gap is obtained "by parallel reasoning". Display (A-30) has a typographical error in its threshold. To our knowledge, none of these results has been machine-checked.

Difficulty

The naive argument conditions each stage on its start time, as if that time were deterministic. It is not: the stage boundaries $\Lambda_i=\sum_{j\le i}n\lambda(\hat p_j;\theta^*)\Delta^{(j)}_n$ depend on all earlier observations, so every per-stage estimate needs the strong Markov property of the Poisson process at a random time. The inventory constraint makes the revenue a nonlinear function of the whole demand path. Bounding the loss therefore means controlling estimation error and overflow at the same time. The geometric stage lengths (20) are chosen so that the stage losses $\Delta^{(i)}_n/(n\Delta^{(i-1)}_n)^{1/2}$ are all of the same order. That balance has to be checked exactly, including the rounding of $\ell_n$ to an integer.

Formalization scope

Poisson process. A structure on an arbitrary probability space: $N(0)=0$ , monotone right-continuous paths, measurable marginals, Poisson increments, and independent increments over finite partitions. No process is published on the platform.
Class and family. Conditions on $\lambda$ are imposed on $[\underline p,\overline p]\cup\{p_\infty\}$ , the only prices a path uses. The inverse $\gamma$ is Function.invFunOn. $\Theta$ is a nonempty closed interval of $\mathbb R$ .
Assumption 3. As printed it cannot hold for $d>\sup_\theta\lambda(p;\theta)$ . It is read as an $\alpha$ -Lipschitz map $g(p,\cdot):[0,\infty)\to\Theta$ that inverts $\lambda(p;\cdot)$ on $\Theta$ . $g$ is jointly measurable, so that estimates at random prices are random variables.
Selections. $p^u,p^c$ are any measurable selections of the maximizer and minimizer; the statements hold for each.
Inventory. The inventory is $\lfloor nx\rfloor$ units, and sales are capped cumulative counts.
Time change. Eq. (1) is applied stage by stage with random stage boundaries.
Typos. In Algorithm 3, " $\lambda(p_i,\theta)$ " is read as $\lambda(\hat p_i;\theta)$ and " $x/t$ " as $x/T$ .
Stages. $\ell_n=\lceil\log_2\log n\rceil$ .
Integrals. Expectations are lower Lebesgue integrals of nonnegative quantities, converted to reals. The relaxation is a real supremum over measurable paths.
Asymptotics. The $O(\cdot)$ is rendered with an explicit $n_0$ . The clause "asymptotically optimal" is omitted, since it needs the second half of Lemma 1.
Ruled out. Each of the following would trivialize the statement: removing the inventory cap, replacing the random stage boundaries by deterministic ones, fixing $\theta$ , letting $C$ depend on $\theta$ , or using a non-measurable selection (whose expectation would be a junk value).

Contributions are welcome on every milestone. The Poisson process structure, its strong Markov property at stage boundaries, and Lemma 2 can be reused in other Poisson-demand pricing and queueing missions. Lemma 1 and Fact 1 are deterministic, and the rate estimate already has a local proof.

Selected references

O. Besbes and A. Zeevi, Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms, Operations Research 57(6):1407–1420, 2009. https://doi.org/10.1287/opre.1080.0640
G. Gallego and G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8):999–1020, 1994. https://doi.org/10.1287/mnsc.40.8.999
K. Talluri and G. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2005. https://doi.org/10.1007/b139000

15 thms2 active usersReviewed

Operations Research Optimization Probability·Captain: mikedeng1

Airline Seat Allocation with Multiple Nested Fare Classes 1: Protection Levels Solving f₁Pr[X₁ > p₁ ∩ … ∩ X₁ + … + X_k > p_k] = f_{k+1} Maximize Expected RevenueResearch Paper

Motivation

An airline sells the seats of one flight leg at several fares. Cheaper fares are booked earlier, so the airline must decide, while low-fare requests arrive, how many seats to hold back for later and more valuable passengers. In nested booking control a seat that could be sold at a low fare is always available to a higher fare. The airline therefore chooses protection levels: $p_k$ seats are reserved for the $k$ most expensive classes together, and a request of class $k+1$ is accepted only while more than $p_k$ seats remain.

For two classes the optimal protection level was found by Littlewood (1972): protect $p_1$ seats, where $f_1 \Pr[X_1 > p_1] = f_2$ . For more classes the industry used the EMSRa heuristic of Belobaba (1987, 1989), which applies Littlewood's rule to each pair of classes separately and adds the results. Brumelle and McGill (1993) gave the exact optimality conditions for any number of nested classes and showed that EMSRa is in general not optimal. Their conditions are part of the standard theory of single-leg revenue management, as presented in Talluri and van Ryzin (2004).

Setting

There are fare classes $k = 1, 2, \dots$ , numbered from the highest fare. Class $k$ has fare $f_k$ and random demand $X_k \ge 0$ . The standing assumptions (pp. 128–129) are: the demands are mutually independent random variables on a probability space $(\Omega, \mathcal F, P)$ , and the fares are strictly decreasing, $f_1 > f_2 > \cdots$ . Demands arrive in order of increasing fare: all of class $k+1$ before any of class $k$ . There are no cancellations or no-shows, and the decision to close a class depends only on the number of current bookings.

A protection-level policy is a vector $p = (p_1, p_2, \dots)$ with $p_k \ge 0$ ; the dummy $p_0 = 0$ . The revenue $R_k[s; p; x]$ of the $k$ highest classes with $s$ seats available and demand vector $x$ is defined recursively by (8)–(9), p. 130:

R_1[s; p; x] = f_1 \min(s, x_1),

R_{k+1}[s; p; x] = \begin{cases} R_k[s; p; x] & 0 \le s < p_k, \\ (s - p_k) f_{k+1} + R_k[p_k; p; x] & p_k \le s < p_k + x_{k+1}, \\ x_{k+1} f_{k+1} + R_k[s - x_{k+1}; p; x] & p_k + x_{k+1} \le s. \end{cases}

The expected revenue is $ER_k[s; p; X] = E\,R_k[s; p; X]$ . A policy $p$ is optimal if $ER_k[s; q; X] \le ER_k[s; p; X]$ for every policy $q$ , every $k \ge 1$ and every $s \ge 0$ .

For $g : \mathbb R \to \mathbb R$ , $\delta_+ g[s]$ and $\delta_- g[s]$ denote the right and left derivatives, and the subdifferential $\delta g[s]$ is the interval $[\delta_+ g[s], \delta_- g[s]]$ , with $\delta_- g[0] = +\infty$ (p. 131).

Formalization targets

Goal: Theorem 3 (p. 134)

If the protection levels satisfy

f_1 \Pr[X_1 > p_1 \cap X_1 + X_2 > p_2 \cap \dots \cap X_1 + \dots + X_k > p_k] = f_{k+1} \quad \text{for all } k \ge 1, \tag{31}

then $p$ is optimal.

Milestones

(27), p. 132: $ER_1$ is concave, and $\delta ER_1[s; p; X] = [f_1 \Pr[X_1 > s], f_1 \Pr[X_1 \ge s]]$ .
Lemma 1, p. 131: if $ER_k[\,\cdot\,; p; X]$ is concave on $s \ge 0$ and $f_{k+1} \in \delta ER_k[p_k; p; X]$ , then $E\{R_{k+1}[s; p; X] \mid X_{k+1}\}$ is concave in $s$ .
Corollary 1, p. 131: under the same conditions $ER_{k+1}[\,\cdot\,; p; X]$ is concave on $s \ge 0$ .
Theorem 1, p. 131: if $f_{k+1} \in \delta ER_k[p_k; p; X]$ for every $k$ (condition (20)), then $p$ is optimal.
Lemma 2, p. 134: under (31), for $s \ge p_k$ ,

\delta_+ E\{R_{k+1}[s; p; X] \mid X_{k+1}\} = f_1 \Pr[X_1 > p_1 \cap \dots \cap X_1 + \dots + X_k > p_k \cap X_1 + \dots + X_{k+1} > s \mid X_{k+1}].

Corollary 2, p. 134: the unconditional version (37) of Lemma 2 for $\delta_+ ER_{k+1}[s; p; X]$ .

Significance

Theorem 3 turns the optimal nested protection levels into a sequence of equations in the joint distribution of the cumulative demands $X_1 + \dots + X_j$ . For $k = 1$ it is Littlewood's rule. For $k \ge 2$ it identifies exactly what EMSRa approximates: EMSRa replaces the joint event in (31) by separate pairwise comparisons, and the paper shows (§4) that EMSRa can both over- and underestimate the optimal protection levels. The conditions are also the input of numerical methods: given demand forecasts, the levels $p_1, p_2, \dots$ are found one after another by solving (31), and §3.3 notes that a continuous joint demand distribution guarantees a solution exists.

The results are proved in the paper. As far as is known they have no machine-checked proof. Related platform items cover the two-class, integer-seat case from Belobaba (1987) (SeatInventory.Nested.emsr_protection_level_optimal) and the integer marginal-seat-revenue analogue of (27). They use a different model: two classes, natural-number seats and first differences. This mission formalizes the multi-class statement with real-valued seats and one-sided derivatives. A sister mission of the series proves the existence of optimal integer policies for integer-valued demand (Theorem 2).

Difficulty

The expected revenue is not differentiable: for discrete demand it is piecewise linear, so first-order conditions must be stated with one-sided derivatives and subdifferentials. The natural approach, to optimize each protection level separately with the others fixed, fails without concavity, and concavity of $ER_{k+1}$ in $s$ is not automatic. It holds only when the lower protection levels already satisfy the first-order conditions. Concavity and optimality must therefore be carried through one joint induction over the classes. Passing from (31) to (20) requires computing the right derivative of the expected revenue in closed form for every $s \ge p_k$ . This involves exchanging differentiation with expectation and conditioning on one class's demand at a time.

Formalization scope

Classes are indexed by $\mathbb N$ from $1$ ; fares, demands and protection levels are sequences $\mathbb N \to \mathbb R$ , with no bound on the number of classes. Seats and protection levels are real numbers.
Expectation is the Bochner integral on a probability space. The standing assumptions are a single predicate: probability measure, measurable nonnegative demands, mutual independence (iIndepFun), strictly decreasing fares.
$E\{\cdot \mid X_k\}$ evaluated at $X_k = y$ is the integral with the $k$ -th demand frozen at $y$ . Because the demands are independent this is a version of the conditional expectation, and "with probability 1" becomes "for every $y \ge 0$ ", which is stronger.
One-sided derivatives are HasDerivWithinAt on half-lines and must exist; derivWithin, which returns $0$ where no derivative exists, is not used. $\delta_- g[0] = +\infty$ is encoded as a disjunct.
Optimality is global: $p$ beats every policy $q$ at every level $k$ and every $s \ge 0$ . The page's proof of Theorem 1 shows coordinatewise optimality of $p_k$ , and the global form follows by induction on $k$ .
Fares are not assumed positive in the model: under (20) or (31) with strictly decreasing fares, $f_1 > 0$ follows. The milestone (27), stated with only the hypotheses on $X_1$ that it needs, assumes $X_1 \ge 0$ and $f_1 \ge 0$ , without which $ER_1$ is not concave.
No continuity of the demand distribution is assumed. Theorem 3 is conditional on a solution of (31).
The page's hypothesis of Lemma 1 has the misprint " $(p_0, \dots, p_{k+1})$ " for $(p_0, \dots, p_{k-1})$ . The formal statement uses the latter.

The goal assumes only the standing assumptions, $p \ge 0$ , and (31). It does not assume concavity, condition (20) or any derivative formula: those are milestones. A formalization that quantified optimality over one level, one value of $s$ , or policies differing from $p$ in one coordinate would be weaker than the paper and is excluded.

A complete development needs one-sided derivatives of integrals of piecewise-linear functions (dominated convergence for difference quotients), concavity of piecewise functions glued at points where the slopes decrease, and the independence calculus that turns $E[E\{\cdot \mid X_{k+1}\}]$ into an iterated integral. These pieces are reusable for other newsvendor-type and revenue-management models. Proofs of any milestone, and alternative arguments for Theorem 1, are welcome.

Selected references

S. L. Brumelle and J. I. McGill, Airline Seat Allocation with Multiple Nested Fare Classes, Operations Research 41(1), 127–137, 1993. https://doi.org/10.1287/opre.41.1.127
K. Littlewood, Forecasting and Control of Passenger Bookings, AGIFORS Symposium Proceedings 12, 95–117, 1972; reprinted in Journal of Revenue and Pricing Management 4(2), 2005. https://doi.org/10.1057/palgrave.rpm.5170134
P. P. Belobaba, Air Travel Demand and Airline Seat Inventory Management, PhD thesis, MIT, 1987. http://hdl.handle.net/1721.1/68077
P. P. Belobaba, Application of a Probabilistic Decision Model to Airline Seat Inventory Control, Operations Research 37(2), 183–197, 1989. https://doi.org/10.1287/opre.37.2.183
K. T. Talluri and G. J. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2004. https://doi.org/10.1007/b139000

8 thms2 active usersReviewed

Algorithmic Game Theory Operations Research Probability·Captain: mikedeng1

Revenue Management with Forward-Looking Buyers: Under Weakly Decreasing Demand the Deterministic Optimal Cutoffs Fall over Time and Satisfy One-Period Look-AheadResearch Paper

Motivation

Retailers of seasonal goods (fashion, electronics, airline seats) sell a fixed stock over a finite season to customers who arrive over time, and those customers know that prices may fall. A customer who expects a markdown waits, and a seller who ignores this loses revenue. The classical revenue-management literature (Gallego and van Ryzin 1994; Talluri and van Ryzin 2004) models myopic customers who buy on arrival or leave; the literature on forward-looking (strategic) buyers, for instance Aviv and Pazgal (2008), studies particular price paths.

Board and Skrzypacz ask the mechanism-design question: among all selling schemes, which maximizes the seller's expected discounted revenue when buyers arrive over time, have private values and time their purchases strategically? Their answer, published in the Journal of Political Economy in 2016, is that the optimal mechanism has a simple structure: in every period the seller sells to the highest remaining buyer if and only if his value exceeds a cutoff that depends only on the period and the number of units left. When demand is weakly decreasing over time, the cutoffs are characterized by one-period indifference conditions, which in the continuous-time limit can be implemented by posted prices. The source used here is the authors' accepted manuscript of February 6, 2015; all page numbers refer to that manuscript.

Setting

A seller has units of a good and sells them over periods $t\in\{1,\dots,T\}$ ; unsold units are worth zero after period $T$ . Payoffs are discounted by $\delta\in(0,1)$ . At the start of period $t$ a random number $N_t$ of buyers arrives, independently across periods, with a law that may depend on $t$ . Each buyer wants one unit; his value is drawn independently from a distribution with continuous density $f$ , distribution function $F$ and support $[\underline v,\bar v]$ . The marginal revenue of a buyer with value $v$ is

m(v)=v-\frac{1-F(v)}{f(v)},

assumed strictly increasing and continuously differentiable, with $m(\underline v)<0$ .

By the standard mechanism-design reduction (§2.1, eq. (2.5)), the seller's problem is to choose when to serve each buyer so as to maximize the expected discounted sum of the served buyers' marginal revenues. The state in period $t$ , after the period- $t$ entrants have arrived, is the number $k$ of units left and the values $y^1\ge y^2\ge\cdots$ of the buyers present. The value $\Pi^k_t$ and the pre-entry value $\tilde\Pi^k_{t}$ satisfy the Bellman equation (4.3):

\Pi^k_t(\mathbf y)=\max_{0\le j\le k}\Big[\sum_{i=1}^j m(y^i)+\delta\,\tilde\Pi^{k-j}_{t+1}(\mathbf y^{-j})\Big],\qquad \tilde\Pi^k_{t+1}(\mathbf y)=E_{t+1}\big[\Pi^k_{t+1}(\mathbf y\cup\mathbf v_{t+1})\big],

where $\mathbf y^{-j}$ is the set of buyers left after the $j$ highest are served and $\mathbf v_{t+1}$ the next period's entrants. Selling one unit to $y^1$ today rather than none gives the difference function

\Delta\Pi^k_t(y^1,\mathbf y^{-1})=m(y^1)+\delta\tilde\Pi^{k-1}_{t+1}(\mathbf y^{-1})-\delta\tilde\Pi^k_{t+1}(y^1,\mathbf y^{-1}),

and the cutoff $x^k_t$ is the smallest $y\in[\underline v,\bar v]$ with $\Delta\Pi^k_t(y,\varnothing)\ge 0$ . Comparing selling to $y^1$ today with waiting and selling at least one unit tomorrow (to the best of $y^1$ and the entrants) gives $D\Pi^k_t(y^1)$ (p. 17). Demand is weakly decreasing in the usual stochastic order if $P(N_{t+1}>x)\le P(N_t>x)$ for all $x$ and $t$ .

Formalization targets

Goal: Theorem 2 (p. 17)

If $N_t$ is weakly decreasing in the usual stochastic order then, for every $k\ge 1$ ,

x^k_{t+1}\le x^k_t\quad(1\le t\le T-1),\qquad D\Pi^k_t(x^k_t)=0,

and $x^k_t$ is the unique root of $D\Pi^k_t$ in $[\underline v,\bar v]$ for $t\le T-1$ : the seller is indifferent between selling to the cutoff type today and waiting one period to sell that unit tomorrow (the one-period-look-ahead property).

Central milestone: Theorem 1 (p. 15)

For every $t$ and $k\ge 1$ , the optimal rule sells to the highest buyer iff $y^1\ge x^k_t$ , whatever the values of the lower buyers; $x^{k+1}_t\le x^k_t$ ; and $x^k_t$ is the unique root of $\Delta\Pi^k_t$ .

Milestones

In attack order:

Lemma 1: allocations are monotone in values.
Lemma 2: with cutoffs decreasing in the unit index, units can be treated one at a time.
Equation (A.1): increasing differences of $\Pi$ .
Lemma 3: $\Delta\Pi$ is independent of lower buyers, continuous and strictly increasing in $y^1$ , and increasing in $k$ .
Footnote 12: the boundary values of $\Delta\Pi$ .
Theorem 1.
Strict monotonicity of $D\Pi$ in $y^1$ (p. 18).
Lemma 4: $D\Pi^k_{t+1}\ge D\Pi^k_t$ .

After the goal, (4.7) gives the period- $(T-1)$ cutoff equation $m(x^k_{T-1})=\delta E_T[\max\{m(x^k_{T-1}),m(v^k_T)\}]$ .

Significance

Theorem 1 says that the optimal allocation does not depend on how many buyers are present or what their values are, only on time and inventory. This is what makes the optimal mechanism implementable without eliciting values from buyers as they arrive. Theorem 2 turns the global dynamic program into local indifference conditions. In the continuous-time limit (§5 of the paper) these become differential equations, and the optimum is implemented by posted prices with an auction at the end of the season. Under weakly decreasing demand, therefore, the classical revenue-management practice of posting prices loses nothing against the best possible mechanism.

The paper's results are proved, in prose, with envelope-theorem and coupling arguments. They have not been machine-checked. A formal development would produce a verified backward-induction model of multi-unit dynamic allocation with random arrivals, with the structural results (monotonicity, deterministic cutoffs, monotone comparative statics in inventory and time) that recur across dynamic pricing and optimal stopping. Two printed gaps are recorded below: the positivity of $m(\bar v)$ , and the restriction of footnote 12 to $t\le T-1$ .

Difficulty

The obvious argument fails at "deterministic". A priori the cutoff for the highest buyer depends on the values of the lower buyers, because selling a unit today changes which of them will be served later and when. Lemma 3(a) holds only under the induction hypothesis that all future cutoffs are already deterministic and decreasing in inventory, so Lemma 3, Theorem 1 and (A.1) form a single backward induction over periods and units, and none of them can be proved in isolation. The value function is an expectation, over a random number of i.i.d. entrants, of a maximum over sorted values, so continuity and strict monotonicity in $y^1$ (Lemma 3(b), and the same for $D\Pi$ ) are not available from general facts. The tempting argument for Theorem 2, that cutoffs fall over time simply because fewer buyers arrive later, is incomplete: Lemma 4 has to compare two periods with different arrival laws and different future cutoffs at once.

Formalization scope

Periods are natural numbers $1,\dots,T$ with $T\ge1$ , and units are natural numbers. Values, marginal revenues and profits are real numbers. The buyers present form a finite multiset of reals, and an absent buyer is absent, never a value $0$ . The value law is the measure with density $f$ ; the density is positive and continuous on $[\underline v,\bar v]$ and zero outside, and $m$ is defined from $f$ and $F$ . Expectations over a cohort are lower Lebesgue integrals against $\sum_n P(N_t=n)\,\mu^{\otimes n}$ of nonnegative bounded quantities, so no non-measurable or non-integrable integrand can silently become $0$ . The value function is defined by the Bellman equation (4.3), with $\Pi_{T+1}\equiv0$ . The sequence problem (4.1) over purchase times is not formalized; the paper says either may be used (footnote 16).

Standing assumptions and handled gaps:

$\delta\in(0,1)$ ;
$N_t$ independent across periods (only the marginal laws enter);
$m$ strictly increasing and $C^1$ on $[\underline v,\bar v]$ with $m(\underline v)<0$ ;
added: $m(\bar v)>0$ , which footnote 12 uses without stating; without it no unit is ever sold and no cutoff exists;
added: $f>0$ on the closed support, needed for $m$ to be defined there;
footnote 12's equality $\Delta\Pi^k_t(\bar v)=(1-\delta)m(\bar v)$ is stated for $t\le T-1$ only, since $\Delta\Pi^k_T=m$ ;
$D\Pi^k_t$ is used only for $t\le T-1$ , and Lemma 4 needs $t+1\le T-1$ ;
"decreasing" and "increasing" are weak except in Lemma 3(b) and for $D\Pi$ ;
at $y^1=x^k_t$ both selling and waiting are optimal.

The cutoff is defined from $\Delta\Pi$ , never as the threshold of an optimal policy, and "optimal" always means maximal in (4.3) over every number of units sold. A formalization that postulates a threshold policy, replaces the random cohort by its mean, or sets absent buyers to value $0$ would trivialize or change the statements and is ruled out. The mechanism-design reduction (IC/IR to (2.5)) and the continuous-time results of §5 are out of scope.

The usual stochastic order is the published platform definition StochasticOrders.Usual.UsualOrder. A complete development needs finite-horizon dynamic programming over multisets, expectations of functions of sorted i.i.d. samples, envelope arguments, and monotone coupling for the usual stochastic order on $\mathbb N$ ; these parts are reusable beyond this mission. Proofs of any milestone are welcome, as is a proof that (4.3) agrees with the sequence problem (4.1).

Selected references

S. Board and A. Skrzypacz, Revenue Management with Forward-Looking Buyers, Journal of Political Economy 124(4), 2016. https://doi.org/10.1086/686713
R. B. Myerson, Optimal Auction Design, Mathematics of Operations Research 6(1), 1981. https://doi.org/10.1287/moor.6.1.58
G. Gallego and G. van Ryzin, Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons, Management Science 40(8), 1994. https://doi.org/10.1287/mnsc.40.8.999
Y. Aviv and A. Pazgal, Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers, Manufacturing & Service Operations Management 10(3), 2008. https://doi.org/10.1287/msom.1070.0183
K. T. Talluri and G. J. van Ryzin, The Theory and Practice of Revenue Management, Springer, 2004. https://doi.org/10.1007/b139000
M. Shaked and J. G. Shanthikumar, Stochastic Orders, Springer, 2007. https://doi.org/10.1007/978-0-387-34675-5

14 thms2 active usersReviewed

Dynamic Programming Operations Research Optimization+1·Captain: mikedeng1

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 1: Additive Demand: k-Concave Profit-to-Go, Optimal (s, S, p) PolicyResearch Paper

Motivation

A retailer that sets both its replenishment quantities and its prices over a finite selling season faces a coupled decision: the price shapes the demand that the inventory must serve, and the inventory position shapes which price is worth charging. With a fixed cost per order, the classical inventory answer is the (s, S) policy of Scarf (1960): when the stock falls below a reorder point $s$ , order up to the level $S$ . Thomas (1974) asked what happens when the price is also a decision, and conjectured that an (s, S, p) policy — an (s, S) ordering rule together with a price that depends on the stock level — is optimal "under fairly general conditions". He also gave a counterexample when prices are restricted to a discrete set.

Chen and Simchi-Levi (Operations Research 52(6), 2004) settled the conjecture for the finite horizon. When demand is additive in a random shock, $w_t = D_t(p_t) + \beta_t$ , the conjecture holds (§3, Theorem 3.1). When the shock is not additive, it fails, and a weaker policy class is optimal (§4, the second mission of this series). This mission formalizes the additive case.

Timeline:

Scarf (1960): (s, S) policies are optimal for the fixed-cost inventory problem, through k-convexity.
Thomas (1974): conjectures (s, S, p) optimality with a continuous price range.
Federgruen and Heching (1999): joint pricing and inventory without a fixed cost; base-stock list-price policies are optimal.
Polatoglu and Sahin (2000): the lost-sales variant; sufficient conditions for (s, S, p) optimality.
Chen and Simchi-Levi (2004): (s, S, p) optimality for additive demand with backlogging, and its failure in general.

Setting

There are $T$ periods $t = 1, \dots, T$ . In period $t$ the firm starts with inventory $x$ , orders up to a level $y \ge x$ at cost $k\,\delta(y - x) + c_t(y - x)$ , where $k \ge 0$ is a fixed cost, $c_t$ a unit cost and $\delta(u) = 1$ if $u > 0$ and $0$ otherwise, and sets a price. Demand is $w_t = \alpha_t D_t(p_t) + \beta_t$ for a random pair $\epsilon_t = (\alpha_t, \beta_t)$ with $\mathbb E\alpha_t = 1$ , $\mathbb E\beta_t = 0$ ; in the additive case $\alpha_t = 1$ . Unmet demand is backlogged, and an end-of-period inventory $x$ costs $h_t(x)$ , a convex function.

Since price and expected demand determine each other, the decision is an expected demand $d \in [\underline d_t, \bar d_t]$ , with price $P_t(d) = D_t^{-1}(d)$ and expected revenue $R_t(d) = d\,P_t(d)$ , assumed concave. With $G_t(y, d) = \mathbb E\,h_t(y - \alpha_t d - \beta_t)$ , the profit-to-go functions satisfy $v_{T+1} \equiv 0$ and, for $t = T, \dots, 1$ ,

v_t(x) = c_t x + \max_{y \ge x}\Big[-k\,\delta(y - x) + g_t\big(y, d_t(y)\big)\Big], \qquad (2)

g_t(y, d) = R_t(d) - c_t y + \mathbb E\big\{-h_t(y - \alpha_t d - \beta_t) + v_{t+1}(y - \alpha_t d - \beta_t)\big\}, \qquad (3)

where $d_t(y)$ maximizes $g_t(y, \cdot)$ over $[\underline d_t, \bar d_t]$ . A function $f$ is k-convex if $k + f(z + y) \ge f(y) + \frac{z}{b}\big(f(y) - f(y - b)\big)$ for all $z \ge 0$ , $b > 0$ , $y$ (Definition 2.1), and k-concave if $-f$ is k-convex. Assumptions 3–5 of the paper give $G_t$ the stated one-sided growth limits and polynomial growth $O(|y|^\rho)$ , and give demand a finite $\rho$ -th moment.

Formalization targets

Goal: Theorem 3.1(c)–(d)

For additive demand and every period $t$ : $g_t(y, \cdot)$ attains its maximum at some $d_t(y)$ , the functions $y \mapsto g_t(y, d_t(y))$ and $x \mapsto v_t(x)$ are k-concave, and there exist $s_t \le S_t$ such that

y^*(x) = \begin{cases} S_t, & x < s_t,\\ x, & x \ge s_t,\end{cases}

maximizes $-k\,\delta(y - x) + g_t(y, d_t(y))$ over $y \ge x$ , $v_t(x) = c_t x - k\,\delta(y^*(x) - x) + g_t(y^*(x), d_t(y^*(x)))$ , and a best expected demand exists at $y^*(x)$ ; the price is $D_t^{-1}$ of it.

Milestones

Definitions 2.1 and 2.2 of k-convexity are equivalent.
Lemma 1(d): a continuous coercive k-convex function has the (s, S) shape (already proved on the platform).
Lemma 2: a maximizer $d_t(y)$ can be chosen with $y - d_t(y)$ nondecreasing.
Theorem 3.1(a): $g_t(y, d) = O(|y|^\rho)$ and $v_t(x) = O(|x|^\rho)$ .
Theorem 3.1(b): $g_t$ is continuous, $g_t(y, d) \to -\infty$ as $|y| \to \infty$ , and $d_t(y)$ exists.
Inequality (7): $g_t(y, d_t(y))$ is k-concave when the continuation value is.
The display of $v_t$ : its (s, S) form and the transfer of k-concavity from $g_t(y, d_t(y))$ to $v_t$ .

Significance

The theorem identifies the structure of an optimal policy for a basic model of coordinated pricing and replenishment: two numbers per period determine the ordering decision, and the price is a function of the post-order stock. It confirms Thomas's conjecture in the additive case and tells a computation or an approximation scheme which policy class it may restrict to; §5 of the paper extends it to a nonincreasing fixed cost, the infinite horizon and Markovian demand.

The result is proved in the paper; to our knowledge it has no machine-checked proof. A formalization adds checked versions of the k-convexity toolkit (the equivalence of the two standard definitions; the (s, S) structure lemma), a checked monotone-selection argument for a parametric maximization, and a checked finite-horizon induction in which an expectation, a maximization over a continuous action and a fixed cost interact. The proof of part (a) is omitted in the paper ("similar to that of Theorem 1 in Federgruen and Heching (1999)"), so formalizing it supplies a missing argument.

Difficulty

The obvious argument fails at the expectation. A k-concave function composed with a shift $y \mapsto y - d - \beta$ is k-concave for a fixed $d$ , but here the demand decision depends on $y$ , and k-concavity, unlike concavity, is not preserved under an arbitrary reparametrization: Definition 2.2 is asymmetric in its two points. The inequality needed for the continuation value requires the post-demand levels $y - d_t(y) - \beta_t$ to be ordered like the inventory levels $y$ . That is the content of Lemma 2, and it uses additivity; for multiplicative demand the ordering fails, and so does the theorem (§4).

The second difficulty is analytic: each step of the induction needs a continuous continuation value of polynomial growth, so that the expectation in (3) is finite and continuous, the maximum over $d$ is attained, and $g_t$ is coercive.

Formalization scope

The model is a structure of real data indexed by $t \in \mathbb N$ , with periods $1, \dots, T$ ; the law of $(\alpha_t, \beta_t)$ is a probability measure on $\mathbb R^2$ and expectations are Bochner integrals. The formalization works in expected-demand space $d \in [\underline d_t, \bar d_t]$ , equivalent to price space because $D_t$ is a continuous strictly decreasing bijection. Additivity is " $\alpha_t = 1$ almost surely". The profit-to-go is defined by recursion on the number of periods to go, with $v_{T+1} = 0$ . Maxima are written as real suprema; every target that uses them asserts that they are attained, so the convention that an unbounded supremum is $0$ never enters. k-convexity is the platform's BertsekasKConvex (Definition 2.1); k-concavity of $f$ is k-convexity of $-f$ .

Conventions and restrictions relative to the printed page:

$O(|y|^\rho)$ is an explicit bound $C(1 + |y|^\rho)$ with $\rho \in \mathbb N$ , uniform in $d$ .
Assumption 5, printed $E\{D_t(p, \epsilon_t)\}^\rho < \infty$ , is read as $\mathbb E|\alpha_t d + \beta_t|^\rho < \infty$ .
Integrability of $h_t(y - \alpha_t d - \beta_t)$ is part of Assumption 4, and Theorem 3.1(a) also asserts that the expectation of $v_{t+1}$ in (3) is finite.
Added hypotheses: $c_{T+1} = 0$ (the paper uses $c_{T+1}$ without defining it), $c_t \ge 0$ (used in the proof of part (b); without it $g_t$ need not tend to $-\infty$ ), and $k \ge 0$ .
Independence across periods is not stated; the dynamic program uses only each period's marginal law.
The paper writes $s_t < S_t$ in the proof; for $k = 0$ equality is possible, so the targets use $s_t \le S_t$ .

A trivializing formalization is ruled out: the targets assert attainment of every maximum they mention and the identity between $v_t(x)$ and the maximized objective, so a supremum that defaults to $0$ , or an integral of a non-integrable function, cannot make them hold vacuously; and the assumptions are satisfiable (a one-period instance with $h(x) = |x|$ meets all of them).

A complete development needs: continuity of parametric integrals under polynomial domination; attainment of maxima over compact intervals; Topkis-style monotone selection for functions with increasing differences; the (s, S) structure lemma for k-convex functions (proved on the platform); and the closure of k-concavity under the operations above. The k-convexity results and the monotone-selection lemma are reusable for the general-demand mission of this series and for other fixed-cost inventory models. Contributions to any milestone are welcome, including proofs that rely on platform results by Topkis (Supermodularity.Monotonicity.argmax_increasing_of_increasing_differences).

Selected references

X. Chen, D. Simchi-Levi, Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case, Operations Research 52(6), 887–896, 2004. https://doi.org/10.1287/opre.1040.0127
H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
L. J. Thomas, Price and Production Decisions with Random Demand, Operations Research 22, 513–518, 1974.
E. L. Porteus, On the Optimality of Generalized (s, S) Policies, Management Science 17, 411–426, 1971.
A. Federgruen, A. Heching, Combined Pricing and Inventory Control Under Uncertainty, Operations Research 47(3), 454–475, 1999. https://doi.org/10.1287/opre.47.3.454
H. Polatoglu, I. Sahin, Optimal Procurement Policies under Price-Dependent Demand, International Journal of Production Economics 65, 141–171, 2000.
D. M. Topkis, Supermodularity and Complementarity, Princeton University Press, 1998.
D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, Athena Scientific, 1995.

11 thms3 active usersReviewed

Revenue Management and Choice Models

Missions

Conditional Logit Analysis of Qualitative Choice Behavior 1: Independence of Irrelevant Alternatives with a Universal Benchmark Yields Logit Selection ProbabilitiesResearch Paper

Motivation

Setting

Formalization targets

Goal: footnote 3 with Equation (12)

Milestones, in the paper's order

Significance

Difficulty

Formalization scope

Selected references

Conditional Logit Analysis of Qualitative Choice Behavior 4: Existence of the Maximum Likelihood Estimate Is Decided by a Quadratic ProgramResearch Paper

Why a likelihood maximum needs a diagnostic

Choice experiments and weighted differences

Formalization targets

Lemma 4: a quadratic-programming test

What the result provides

Why the equivalence is delicate

Formalization scope

Selected references

Conditional Logit Analysis of Qualitative Choice Behavior 5: The Maximum Likelihood Estimator Exists with Probability Tending to One and Is Consistent and Asymptotically NormalResearch Paper

Motivation

Setting

Formalization targets

Goal: Lemma 6

Milestones

Significance

Difficulty

Formalization scope

Selected references

Conditional Logit Analysis of Qualitative Choice Behavior 2: Random Utility Maximizers Choose by Logit Exactly When Taste Shocks Are Extreme-Value DistributedResearch Paper

Motivation

Setting

Formalization targets

Goal: the characterization

Milestones

Significance

Difficulty

Formalization scope

Selected references

Conditional Logit Analysis of Qualitative Choice Behavior 3: The Conditional Logit Likelihood Has a Maximum Exactly When No Direction Makes Every Observed Choice Weakly BestResearch Paper

Motivation

Setting

Formalization targets

Goal: Lemma 3

Milestones

Significance

Difficulty

Formalization scope

Selected references

Assortment Optimization under Variants of the Nested Logit Model 2: With Dissimilarity Parameters at Most One and Fully-Captured Nests, a Nested-by-Revenue Assortment in Every Nest Is OptimalResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 4 (p. 15)

Milestones

Significance

Difficulty

Formalization scope

Selected references

Assortment Optimization under Variants of the Nested Logit Model 1: If the Restricted LP Optimum Scaled by α Is Feasible for the Full LP, Its Assortment Earns Within a Factor α of the Optimal RevenueResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 1 (p. 13)

Milestones (§2, pp. 11–12)

Companions (§7, pp. 29–30)

Significance

Difficulty

Formalization scope

Selected references

Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 10 (p. 24)

Milestones

Significance

Difficulty