Revenue Management and Choice Models

Motivation

Fashion and consumer-electronics retailers sell a product at full price early in a season and mark down what is left. Consumers learn the pattern, and some of them wait for the markdown. Such strategic consumers lower the revenue of the full-price period, and the retailer's stocking decision affects how deep the markdown is expected to be. Quick response — a second, more expensive replenishment placed after demand is observed — is usually valued as a way to match supply with exogenous demand (Fisher and Raman 1996; Cachon and Terwiesch, Matching Supply with Demand, 2005). Cachon and Swinney ask how strategic waiting changes that value.

The source is the authors' working paper of April 2007, revised November 25, 2007, not the 2009 Management Science version, whose numbering and wording may differ. Its answer: with strategic consumers the retailer stocks less (Theorem 1), and under an explicit cost condition, quick response is worth more to a retailer facing strategic consumers than to one facing only myopic consumers (Theorem 3).

Setting

A retailer sells over two periods. It sells at the exogenous full price $p$ in period 1 and at a markdown price $s\in[0,p]$ chosen at the start of period 2. Leftover units are worth $0$. First-period demand $D\ge0$ has density $f$ and distribution function $F$, and $f$ satisfies the monotone scaled likelihood ratio (MSLR) property: for every $\lambda\in(0,1]$, $x\mapsto f(\lambda x)/f(x)$ is monotonic on the support of $f$.

The market has three segments:

• myopic consumers, $(1-\alpha)D$ of them, with value $v_M$, who only buy in period 1;
• strategic consumers, $\alpha D$ of them, with value $v_M$ in period 1 and second-period values uniform on $[\underline v,\bar v]$;
• an unlimited pool of bargain hunters with value $v_B$, who only buy on sale.

The standing assumptions are $\bar v\le p$ and $\underline v\ge v_M-p+v_B$. Let $\bar G(s)$ be the fraction of strategic values above $s$.

By a threshold argument (Lemma 1), strategic consumers with value below some $\hat v$ buy at $p$ and the rest wait. A fraction $\xi=1-\bar G(\hat v)\alpha$ of demand then buys in period 1, and the inventory left for period 2 is $I=(q-\xi D)^+$. The period-2 revenue $R(s,I)$ counts the waiting strategic consumers with value at least $s$ and, if $s\le v_B$, the bargain hunters, up to the inventory $I$. The retailer's expected profit at unit cost $c$ is

$$\pi(q,\hat v)=\mathbb E\Big[p\min(q,\xi D)-cq+\sup_{0\le s\le p}R(s,I)\Big].$$

With quick response, units ordered before the season cost $c_1$ and units ordered after observing $D$ cost $c_2$, with $c_1\le c_2\le p$. The second order covers all first-period demand and may add stock for the sale. The resulting profit is $\pi_r(q,\hat v)$.

In the sale period, waiting strategic consumers are rationed: they effectively face the inventory $\theta I$, where $\theta\in[0,1]$ measures their place in the queue. A strategic consumer with value $\hat v$ who waits gains, in expectation,

$$\psi(\hat v)=(\hat v-v_B)\Pr(D<D_l\text{ and a unit is received}),$$

where $D_l$ is the demand level below which the retailer clears stock at $s_l=v_B$. A rational expectations equilibrium $(q^*,v^*)$ is a pair in which $q^*$ maximizes $\pi(\cdot,v^*)$ and $v^*$ is a best response of consumers who correctly expect $q^*$. The superscript $m$ denotes the benchmark with only myopic consumers ($\alpha=0$): $\pi^m$ and $\pi^m_r$ are the optimal myopic profits without and with quick response.

Formalization targets

Goal: Theorem 3

Assume MSLR and no rationing, $0<\alpha\le1$, $v_B<c_1<p$, $c_1\le c_2\le p$, and condition (6):

$$\frac{v_M-p}{\bar v-v_B}\ \ge\ \frac{c_2-c_1}{c_2-v_B}.$$

Let $(q^*,v^*)$ be any equilibrium without quick response, $(q_r^*,v_r^*)$ any equilibrium with it, and $\pi^m$, $\pi_r^m$ the myopic optima. Then

$$\pi_r(q_r^*,v_r^*)-\pi(q^*,v^*)\ \ge\ \pi_r^m-\pi^m .$$

Milestones

The milestones follow the paper's path:

• the threshold structure (Lemma 1);
• the optimal sale price (Lemma 2) and quasi-concavity of $\pi$ with first-order condition (2) (Lemma 3);
• the fill probability and the limits of the best response (Lemma 4);
• existence and the comparison $q^*\le q^m$, $\pi^*\le\pi^m$ (Theorem 1), with the myopic newsvendor $F(q^m)=(p-c)/(p-v_B)$;
• the quick-response analogues (Lemma 5, Theorem 2 (i)), with the myopic fractile $F(q^m_r)=(c_2-c_1)/(c_2-v_B)$;
• the statement that under (6) every equilibrium with quick response has $v^*_r=\bar v$ (Theorem 2, last sentence).

Corollary 1 is the percentage form, $\Delta/\pi^*\ge\Delta_m/\pi^m$.

Significance

Theorem 3 identifies a second channel through which quick response creates value. Beyond matching supply to demand, it lets the retailer keep its initial stock low enough that a deep markdown becomes unlikely, so strategic consumers buy at full price. Under (6), all of them do. Quick response thus reduces strategic waiting without withholding availability, unlike the inventory-signalling remedies in the literature, and the theorem quantifies when this effect dominates.

The results are proved in the working paper, partly in a technical appendix. No machine-checked version of them, or of the underlying markdown game, is known. A formalization pins down several statements that the paper states loosely:

• the uniqueness claims of Lemmas 2 and 5;
• the case condition of Lemma 4 (i), which is false as printed;
• the sign in display (5);
• the boundary cases of the threshold lemma.

It also produces reusable components: the newsvendor with salvage and the reactive-capacity fractile under a general density, and a rational-expectations equilibrium predicate for a retailer–consumer game.

Difficulty

The profit $\pi(\cdot,\hat v)$ is not concave: with strategic consumers it is concave–convex (Figure 4 of the paper). The newsvendor argument therefore does not give a unique optimal order, and Lemma 3's quasi-concavity rests on MSLR in a short appendix step.

Existence (Theorem 1) needs a fixed point of the map $q\mapsto$ best response, but the consumer best response is a correspondence, not a function, so the printed intermediate-value argument does not apply directly. Theorem 3 needs a statement about every equilibrium with quick response, while Theorem 2's proof only exhibits one. Ruling out an equilibrium with $v_r^*<\bar v$ requires comparing the derivative (4) of $\pi_r$ with the myopic derivative along the whole demand distribution.

Formalization scope

Lean represents prices, quantities and valuations as reals, demand by a density $f:\mathbb R\to\mathbb R$ on $[0,\infty)$, and expectations as Lebesgue integrals against $f$. The model carries the standing assumptions of §3 as fields, plus the following additions and corrections, each disclosed in the item notes:

• $v_B>0$: $D_l$ divides by $s_l=v_B$.
• $p<v_M$, strengthening $v_M\ge p$: Lemma 4 (ii) and Theorem 2's last claim need it.
• A finite mean: $\pi_r$ contains $\mathbb E[p\xi D]$.
• The paper's "$\theta_c\le\theta$" (p. 15) is replaced by the no-rationing condition $s_l\bar G(\hat v)\le\theta s_m\bar G(s_m)$ for every belief, which is exactly $D_l\le D_\theta$. The printed condition agrees with it only when $s_m=\hat v$.
• Lemma 4 (i) is stated with the corrected case split.
• Lemmas 2 and 5 claim uniqueness only off the tie points.
• $c<p$ is the reading of the "$p-c>0$" step in the proof of Theorem 1.
• In the quick-response profit, $\xi D$ replaces the $D$ that the proof of Theorem 2 prints.

Optimal revenues are suprema over all prices $s\in[0,p]$ (and $q_2\ge0$ with quick response). "Optimal order" means a maximizer over all $q\ge0$, never a stationary point, and the myopic benchmarks are the same functions at $\alpha=0$. Defining the optimal revenue by Lemma 2's closed form would make Lemma 2 and the first-order conditions definitional; it is not done.

The fill rate is $\min\{(1-\xi)x,\theta I\}/((1-\xi)x)$, set to $1$ when no strategic consumer waits. With Lean's $0/0=0$ instead, $\bar v$ would be a best response to every order and Theorem 2's last claim would be trivial.

A complete development needs:

• differentiation under the integral for piecewise-smooth integrands;
• quasi-concavity from a single-crossing derivative;
• a fixed-point argument for the equilibrium correspondence;
• the newsvendor and reactive-capacity fractiles.

The last two are reusable beyond this mission. Proofs of any milestone, alternative existence arguments, and sorry-free proofs of the newsvendor items are welcome. The comparison "$q_r^*\le q^*$, $\pi_r^*\ge\pi^*$" of Theorem 2 and §8's numerical study are outside the scope.

Selected references

• G. P. Cachon, R. Swinney, Purchasing, Pricing, and Quick Response in the Presence of Strategic Consumers, working paper, revised November 25, 2007; published in Management Science 55(3), 2009. https://doi.org/10.1287/mnsc.1080.0948
• M. L. Fisher, A. Raman, Reducing the Cost of Demand Uncertainty Through Accurate Response to Early Sales, Operations Research 44(1), 1996. https://doi.org/10.1287/opre.44.1.87
• J. F. Muth, Rational Expectations and the Theory of Price Movements, Econometrica 29(3), 1961. https://doi.org/10.2307/1909635

Motivation

A seller with replenishable inventory must decide how much to order and what price to charge before demand is known. A price that increases current revenue can also change the inventory left for later periods; a fixed charge for placing any positive order adds a discontinuity to the decision. Chen and Simchi-Levi study this coordination problem over a finite horizon with backlogging and random, price-dependent demand. Their general-demand result characterizes an optimal order-and-price policy even when a conventional two-threshold ordering rule can fail. The paper gives explicit counterexamples to ordinary $k$-concavity and to optimality of a standard $(s,S,p)$ policy in this setting (Chen and Simchi-Levi, 2004, §4, Lemmas 3–4).

Setting

There are periods $t=1,\ldots,T$. At the start of period $t$, the firm has inventory $x$, which may be negative because unmet demand is backlogged. It may order to any level $y\ge x$. If $y>x$, it pays a fixed ordering cost $k$ as well as a variable cost $c_t(y-x)$. After ordering it chooses an expected demand level $d$ in a closed interval $[\underline d_t,\overline d_t]$. The corresponding price is $P_t(d)$, the inverse of the period's decreasing demand curve, and expected revenue is $R_t(d)=dP_t(d)$.

Actual demand is $\alpha_t d+\beta_t$. The random pair $(\alpha_t,\beta_t)$ has a period-dependent law $\mu_t$, with $\mathbb E[\alpha_t]=1$ and $\mathbb E[\beta_t]=0$. No sign restriction is placed on $\alpha_t$ in the paper's general model. The inventory after demand is $y-\alpha_t d-\beta_t$, incurring a convex holding or backlog cost $h_t$ and entering the next period. The paper assumes the random perturbations are independent across periods. Its Bellman equation uses their individual period laws (Chen and Simchi-Levi, 2004, §2, Assumptions 1–5).

The profit-to-go $v_t(x)$ starts with $v_{T+1}(x)=0$. For a post-order inventory $y$ and expected demand $d$, write

$$g_t(y,d)=R_t(d)-c_ty+\mathbb E[-h_t(y-\alpha_t d-\beta_t)+v_{t+1}(y-\alpha_t d-\beta_t)].$$

The firm maximizes $g_t(y,d)$ over admissible $d$ and then maximizes the resulting value, less the fixed ordering charge, over $y\ge x$. This defines $v_t(x)$ by equation (2) of the paper. A symmetrically $k$-convex real function $f$ satisfies

$$f((1-\lambda)x_0+\lambda x_1)\le(1-\lambda)f(x_0)+\lambda f(x_1)+\max\{\lambda,1-\lambda\}k$$

for every $x_0,x_1\in\mathbb R$ and $\lambda\in[0,1]$. A function is symmetrically $k$-concave when its negative is symmetrically $k$-convex. This is Definition 4.1, equation (8), and preserves the symmetry between the two endpoint inventories (Chen and Simchi-Levi, 2004, p. 891).

Formalization targets

The goal is Theorem 4.1(c)–(d). If $G_t(y)=\max_{d\in[\underline d_t,\overline d_t]}g_t(y,d)$, then for every period

$$G_t\text{ and }v_t\text{ are symmetrically }k\text{-concave}.$$

There are thresholds $s_t\le S_t$ and a possibly empty set $A_t\subseteq[s_t,(s_t+S_t)/2]$. An optimal policy orders to $S_t$ if $x<s_t$ or $x\in A_t$, and places no order otherwise. It chooses the maximizing expected demand for the resulting post-order level. In particular, all states that order to $S_t$ can use the same demand level $d_t(S_t)$ and hence the same price $P_t(d_t(S_t))$.

The milestones state the preceding polynomial growth and continuity assertions from Theorem 4.1(a)–(b), the threshold structure of Lemma 5(d), and the named steps in the proof on p. 892. The link from the paper's earlier $k$-convexity to symmetric $k$-convexity is also included. These targets preserve the paper's general demand law rather than restricting it to the additive case.

Significance

The theorem describes an optimal decision at every inventory level under random price-dependent demand. The exceptional set $A_t$ records states where ordering to $S_t$ is optimal inside the interval where a single reorder threshold need not describe all optimal actions. Thus the result retains a concise policy description while allowing the behavior exhibited by the paper's counterexamples (Chen and Simchi-Levi, 2004, §4).

Formalizing the result requires a reusable account of symmetric $k$-convexity, a fixed-cost ordering envelope, and a finite-horizon Bellman recursion with real-valued expectations. The source proves Theorem 4.1 on paper. This mission poses its statements as Lean goals; the theorem files currently contain sorry and therefore are not machine-checked proofs. The published platform definition BertsekasKConvex supplies the earlier notion from Definition 2.1, so the bridge to Definition 4.1 can be stated without duplicating it.

Difficulty

In the additive-demand case, a maximizing expected-demand choice can be selected so that post-demand inventory changes monotonically with the initial inventory. For general demand $\alpha_t d+\beta_t$, that monotonicity can fail: the random multiplier changes how a pricing choice moves the next inventory state. The earlier ordered-chord $k$-concavity argument therefore does not carry over unchanged. A second issue is the fixed ordering charge. It creates ties between ordering and not ordering, so the policy region can include isolated or noninterval states within $[s_t,(s_t+S_t)/2]$. The statement must assert Bellman optimality at every $x$, including those ties, rather than only the geometry of $A_t$ (Chen and Simchi-Levi, 2004, pp. 891–892).

Formalization scope

The Lean model uses expected demand $d$ as the decision variable and obtains price from $P_t(d)$, matching the paper's reformulation after Assumption 5. The admissible demand interval is nonempty. Periods are natural numbers $1,\ldots,T$, with $T>0$ and terminal value $v_{T+1}=0$. Random demand is integrated against a probability measure on $\mathbb R\times\mathbb R$. The first moments and the paper's demand moment condition are explicit; holding-cost and continuation integrability prevent a nonintegrable real integral from acquiring Lean's default zero value. The paper's $O(|y|^\rho)$ statements are encoded by constants multiplying $1+|y|^\rho$.

The formal assumptions include $k\ge0$ and $c_t\ge0$, and set $c_{T+1}=0$ where the paper's Assumption 3 uses that otherwise undefined terminal coefficient. The latter two restrictions make the printed finite-horizon claim valid under its cost interpretation; they are stated rather than silently supplied. The paper assumes temporal independence, while the formal Bellman recursion starts from the marginal laws and so needs no separate joint process. The paper's $(y,p)$ in Theorem 4.1(b) is expressed as $(y,d)$ through the continuous one-to-one price–expected-demand correspondence. The model places no positivity condition on $\alpha_t$.

The optimized demand value and ordering value are real suprema. The statements include maximizing choices and Bellman attainment; a proof cannot rely on a default value for an empty or unbounded supremum. The goal requires an actual optimal action for every inventory state. Contributions that establish integrability, continuity, coercivity, symmetric convexity preservation, or the ordering-envelope structure are useful beyond this mission.

Selected references

• Xin Chen and David 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. DOI: 10.1287/opre.1040.0127.

Motivation

Assortment optimization asks a retailer which products to offer when customers substitute among them. The nested logit model groups products into nests and is one of the most used choice models in revenue management, because it relaxes the independence of irrelevant alternatives of the plain multinomial logit model while keeping choice probabilities in closed form. Davis, Gallego and Topaloglu (Oper. Res. 62(2), 2014) study how the tractability of the assortment problem under this model depends on two features: whether the dissimilarity parameters of the nests are at most one, and whether a customer who selects a nest always buys there (fully-captured nests).

When the dissimilarity parameters are at most one and the nests are fully captured, offering the $j$ highest-revenue products in every nest is optimal (Theorem 4 of the paper). This mission concerns what survives when a dissimilarity parameter exceeds one, the regime the paper calls possibly synergistic products. Then the problem is NP-hard (Theorem 5), and the paper shows that the same nested-by-revenue assortments still achieve an explicit, data-dependent fraction of the optimal expected revenue.

Setting

There are nests $i \in M$ and products $j \in N = \{1, \dots, n\}$ in every nest. Product $j$ of nest $i$ has a revenue $r_{ij}$ and a preference weight $v_{ij} > 0$, ordered so that $r_{i1} \ge r_{i2} \ge \dots \ge r_{in}$. Nest $i$ has a dissimilarity parameter $\gamma_i > 0$, and $v_0 \ge 0$ is the weight of leaving without choosing a nest. Throughout this mission the nests are fully captured: the within-nest no-purchase weights $v_{i0}$ are zero. For an assortment $S_i \subseteq N$ in nest $i$,

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

and the expected revenue of $(S_1, \dots, S_m)$ is

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

Problem (2) maximizes $\Pi$; its optimal value is $Z^*$. 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\}$.

Problem (2) is equivalent to the linear program (3): minimize $x$ subject to $v_0 x \ge \sum_i y_i$ and $y_i \ge V_i(S_i)^{\gamma_i}(R_i(S_i) - x)$ for every nest $i$ and every $S_i \subseteq N$. Problem (4) keeps the second family of constraints only for candidate assortments; here the candidates are $\{N_{ij} : j \in N_+\}$, which gives a linear program with $1 + m$ variables and $1 + m(1 + n)$ constraints. The performance factor of the nested-by-revenue assortments is

$$\alpha = \max_{i \in M,\ j = 2, \dots, n} \left\{ \frac{R_i(N_{i,j-1})}{R_i(N_{ij})} \wedge \left(\frac{R_i(N_{ij})}{R_i(N_{i,j-1})}\, \frac{V_i(N_{ij})^{\gamma_i}}{V_i(N_{i,j-1})^{\gamma_i}}\right) \right\}, \qquad a \wedge b = \min\{a, b\}. \tag{6}$$

Formalization targets

Goal: Theorem 7

Assume $v_{i0} = 0$ for every nest, $\gamma_i > 1$ for some nest, positive revenues and $n \ge 2$. If $(\hat x, \hat y)$ is an optimal solution of (4) over the nested-by-revenue assortments, then

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

Combined with Theorem 1 of the paper this yields $Z^* \le \alpha\, \Pi(\hat S)$ for the assortment $\hat S$ read off the small linear program; that consequence is a companion item.

Milestones

1. Problem (3) is a relaxation of the fractional problem (7), in which $y_i$ dominates $\big(\sum_j v_{ij} z_{ij}\big)^{\gamma_i}\big[\sum_j r_{ij} v_{ij} z_{ij} / \sum_j v_{ij} z_{ij} - x\big]$ for all $z_i \in [0,1]^n$.
2. Lemma 6: the inner maximization (8) of (7) has a solution of the form $z_{i1} = \dots = z_{i,k-1} = 1$, $z_{ik} \in [0,1]$, $z_{i,k+1} = \dots = z_{in} = 0$.
3. $\hat y_i \ge 0$ and $\hat x \ge 0$.
4. The inequalities (20) and (22) with the coefficients $\alpha^1_{ik} = R_i(N_{i,k-1})/R_i(N_{ik})$ and $1 \vee \alpha^2_{ik}$.
5. $R_i(N_{ij}) \le R_i(N_{i,j-1})$, and Lemma 14: $\alpha \ge 1$ when some $\gamma_i > 1$.
6. The inequalities (24) and (25): $\alpha \hat y_i$ dominates the objective of (8) at $\alpha \hat x$ for every vector of Lemma 6's shape.

Two companion statements follow the goal: the bounds $\alpha \le \rho$ and $\alpha \le 2\kappa$ when revenues, respectively preference weights, within each nest differ by at most the factors $\rho$, $\kappa$; and the guarantee $Z^* \le \alpha\, \Pi(\hat S)$.

Significance

Because problem (2) is NP-hard once a dissimilarity parameter exceeds one (Theorem 5 of the paper), an exact polynomial algorithm is not expected, and a guarantee for a polynomial-size candidate family is the natural substitute. Theorem 7 gives one with an explicit factor computed from the data: $\alpha \le \rho$ when revenues within each nest are balanced, $\alpha \le 2\kappa$ when preference weights within each nest are balanced, and the nests may differ arbitrarily from one another. The same linear-programming argument (Theorem 1) is reused for partially-captured nests in §6 of the paper.

The result is proved in the paper (Appendix A.1); no machine-checked version is known. A formalization verifies an appendix argument that is stated with little detail, and fixes the conventions that the page leaves implicit, such as the value of the objective of (8) at $z_i = 0$ and the role of the standing assumption that some $\gamma_i$ exceeds one.

Difficulty

Theorem 7 is a feasibility statement for the exponentially many constraints of (3), one per subset of every nest, while optimality of $(\hat x, \hat y)$ only controls the $n + 1$ nested-by-revenue constraints per nest. The obvious approach, comparing each subset directly with a nested-by-revenue assortment, fails: when $\gamma_i > 1$ the nested-by-revenue assortments are not optimal within a nest, and the example of §4.1 shows that they can lose an unbounded factor. The constant $\alpha$ must absorb the gap between a fractional assortment and its two neighbouring nested-by-revenue assortments, which the dual-style solution $(\hat x, \hat y)$ of the small program does not see.

Formalization scope

Lean 4 with Mathlib. Nests form a finite type ι; products are Fin n, indexed from $0$, so $N_{ij}$ is nbr n j = {k | k < j} and product $k$ of the page is ⟨k - 1, _⟩. Powers are real powers (Real.rpow), and division is total ($x / 0 = 0$), which gives $R_i(\emptyset) = 0$ and value $0$ for the objective of (8) at $z_i = 0$.

Standing assumptions in every statement: $v_0 \ge 0$, $v_{i0} \ge 0$, $v_{ij} > 0$, $r_{ij} \ge 0$, $\gamma_i > 0$, revenues ordered within each nest (§1); $v_{i0} = 0$ for every nest and $\gamma_i > 1$ for some nest (§4, p. 16). Added and disclosed: $r_{ij} > 0$ wherever (6) appears, so that no denominator of (6) vanishes; $n \ge 2$, the nonempty range of (6); $v_0 > 0$ only in the guarantee $Z^* \le \alpha\,\Pi(\hat S)$, inherited from Theorem 1. The factor $\alpha$ enters as a real number with the hypothesis that it is the greatest element of the set of terms of (6). An optimal solution of (4) is a feasible pair whose $x$ is minimal among feasible pairs.

A trivializing formalization is ruled out: $\alpha$ is the maximum of (6), not an arbitrary upper bound, and the goal states feasibility for the full program (3) over every subset of every nest, not for (7) or for the candidate collection.

Needed infrastructure: maximization of a continuous function on $[0,1]^n$, the greedy solution of a continuous knapsack, monotonicity of weighted averages and elementary real-power calculus. These are reusable beyond this mission. Proofs of any milestone, of the companions, and of the §4.1 example 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. https://doi.org/10.1287/opre.2014.1256 (formalized from the 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), 2004. https://doi.org/10.1287/mnsc.1030.0147

Assortment planning with nested choice

A retailer that groups its products into categories (brands, store sections, flight classes) and decides which products to display in each faces the assortment problem: offering more products attracts more customers but also diverts sales away from the most profitable products. The nested logit model is the standard description of customer choice in this setting. A customer first selects a category (a nest), then a product within it. Choice-based models of this kind are the basis of revenue management under customer choice (Talluri and van Ryzin 2004).

Davis, Gallego and Topaloglu (DGT 2014) study the assortment problem under the nested logit model with two features that earlier work excluded: dissimilarity parameters larger than one, under which products in a nest act as complements rather than substitutes, and a no-purchase option inside each nest, under which a customer may enter a nest and still leave without buying. They show that the problem is NP-hard once either feature is present. For each regime they give a small linear program whose solution yields an assortment with a provable performance guarantee. This mission formalizes the guarantee for the most general instances, where both features occur together (§6.1, Theorem 11).

Timeline. Rusmevichientong, Shmoys and Topaloglu (2010) bound nested-by-revenue assortments under a multinomial logit mixture. [DGT 2014] prove that nested-by-revenue assortments are optimal for dissimilarity parameters at most one without within-nest no-purchase options (Theorem 4). They give factor-(6) guarantees with synergistic products, a factor-two guarantee via knapsack relaxations for partially-captured nests (Theorem 10), and the general factor (12) of Theorem 11. Li, Rusmevichientong and Topaloglu (2015) extend the nested-by-revenue result to $d$-level nested logit models.

The model

There are nests $i\in M=\{1,\dots,m\}$ and, in each nest, products $j\in N=\{1,\dots,n\}$. Product $j$ of nest $i$ has revenue $r_{ij}\ge0$ and preference weight $v_{ij}>0$, with $r_{i1}\ge r_{i2}\ge\dots\ge r_{in}$. Nest $i$ has a no-purchase weight $v_{i0}\ge0$ and a dissimilarity parameter $\gamma_i>0$, and $v_0\ge0$ is the weight of choosing no nest at all. 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)} .$$

A customer chooses nest $i$ with probability $V_i(S_i)^{\gamma_i}/(v_0+\sum_l V_l(S_l)^{\gamma_l})$, and the expected revenue is

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

The optimal value $Z^*$ of $\max\Pi$ equals the optimal value of the linear program

$$\text{(3)}\qquad \min\ x\quad\text{s.t.}\quad v_0x\ge\sum_i 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,$$

which has $2^n$ constraints per nest. Problem (4) keeps only the constraints for a chosen candidate collection of assortments in each nest.

A nest is fully captured if $v_{i0}=0$ ($i\in M^f$) and partially captured if $v_{i0}>0$ ($i\in M^p$). $N_{ij}=\{1,\dots,j\}$ is the nested-by-revenue assortment. $N^k_{ij}$ is the set of the $j$ highest-revenue products among the $k$ products of nest $i$ with the smallest preference weights, with $N^k_{i0}=\emptyset$ and $N^n_{ij}=N_{ij}$.

Formalization targets

Goal: Theorem 11

Let $(\hat x,\hat y)$ be an optimal solution of (4) when the candidate collection of every nest is $\{N^k_{ij}:k\in N,\ j=0,\dots,k\}\cup\{\{j\}:j\in N\}$, and let

$$\beta=\max_{i\in M^f,\ j=2,\dots,n}\left\{\frac{V_i(N_{ij})}{V_i(N_{i,j-1})}\right\}\vee\max_{i\in M^p,\ j=1,\dots,n}\left\{\frac{V_i(N_{ij})}{V_i(N_{i,j-1})}\right\}\vee2 \qquad (12).$$

Then $(\beta\hat x,\beta\hat y)$ is feasible for problem (3).

The theorem assumes $\bar\gamma=\max_i\gamma_i>1$, as all of §6 does. Otherwise it places no restriction on the $\gamma_i$ or the $v_{i0}$.

Milestones

1. $\hat x\ge0$ (A.4, p. 46).
2. Every greedy knapsack assortment $\hat S_i(\epsilon_i)$ of §5 is one of the $N^k_{ij}$ (pp. 24–25).
3. The relaxed nest problem over $[0,1]^n$ has an optimal solution of fractional-prefix form (A.4 Case 1, p. 47).
4. Inequality (30): for a nest with $\gamma_i>1$ and $\hat y_i\ge0$, $\beta\hat y_i$ bounds the relaxed objective at every fractional prefix (p. 47).
5. Case 1: $\gamma_i>1$, $\hat y_i\ge0$ gives the constraints of (3) for nest $i$ (pp. 47–48).
6. Problem (31) has a nested-by-revenue optimal solution when $\gamma_i>1$ and its coefficient $b=\beta\hat y_i$ is negative (p. 48).
7. Case 2: $\gamma_i>1$, $\hat y_i<0$ (p. 48).
8. Case 3: $\gamma_i\le1$, through the factor-two argument of Theorem 10 (pp. 48–49).

Two companions follow the goal. One is the resulting guarantee $\beta\,\Pi(\hat S)\ge Z^*\ge\Pi(\hat S)$, through Theorem 1. The other is the bound $\beta\le2\kappa$ when the preference weights within a nest differ by at most a factor $\kappa$ (p. 26).

Significance

Theorem 11, combined with Theorem 1 of the paper, gives a polynomial-size method for an NP-hard problem. The method solves one linear program with $1+m$ variables and $1+m(1+n+n^2)$ constraints, then reads off an assortment whose expected revenue is within the factor $\beta$ of the optimum. This holds for every nested logit instance, including nests where customers may walk away and nests whose products are complements. When the weights inside each nest are within a factor $\kappa$ of each other, the guarantee is at most $2\kappa$.

The theorem is proved in the paper's appendix. No part of it is machine-checked. Formalizing it checks a case analysis that reuses, by reference, arguments from two other theorems: Theorem 7 (synergistic, fully-captured nests) and Theorem 10 (competitive, partially-captured nests). It makes precise what these arguments need when the two regimes are mixed in one instance. The formalization also fixes the boundary conventions the printed proof leaves implicit: fully-captured nests with $k=1$, zero-weight denominators, and the sign of $\hat y_i$.

Difficulty

Each nest falls into one of three regimes, and a different argument controls each. With $\gamma_i\le1$ the nest behaves like a knapsack problem. Its guarantee of two needs the knapsack collection of §5 to sit inside $\{N^k_{ij}\}$. With $\gamma_i>1$ and $\hat y_i\ge0$, the constraint must be extended from nested-by-revenue sets to every subset. This goes through a continuous relaxation whose optimum has a fractional coordinate, and it costs the ratio $V_i(N_{ik})/V_i(N_{i,k-1})$, which is where (12) comes from. With $\gamma_i>1$ and $\hat y_i<0$, the scaling argument of Case 1 fails because multiplying by a factor at most one no longer preserves the inequality. The proof switches to the different objective (31), whose convexity in one coordinate forces an integral optimum.

The first idea, bounding every assortment by a nested-by-revenue one, is false here. With $\gamma_i>1$ or $v_{i0}>0$, nested-by-revenue assortments are not optimal, and the loss is exactly the factor $\beta$.

Formalization scope

Products are Fin n; $N_{ij}$ is nbr n j. Powers are Real.rpow, and $x/0=0$, so $R_i(\emptyset)=0$. Problems (3) and (4) are stated in constraint form: LP4Optimal means feasible and with $x$ minimal among feasible points. $\beta$ is the greatest element of the finite set betaSet I, which contains $2$ and the ratios of (12). Fully-captured nests skip $j=1$, as on the page. The collection is constructed: nestedPR breaks weight ties by index and revenue ties by index.

Standing assumptions, all disclosed:

• $v_{ij}>0$, $r_{ij}\ge0$ and $\gamma_i>0$. The page allows zero-weight padding products and $\gamma_i=0$, but its arguments do not cover them.
• $\bar\gamma>1$ on every statement set in Theorem 11's context.
• $n\ge1$ for the collection claim and the prefix claim.
• $v_{i0}>0$ for the statement about (31). That is the only kind of nest where Case 2 arises. For $v_{i0}=0$, Lean's $0^{1-\gamma_i}=0$ would remove the page's $+\infty$.
• $v_0>0$ for the guarantee, where Theorem 1 fails otherwise.
• $\kappa\ge1$, and $v_{i0}$ counted among the weights of a partially-captured nest ($v_{ij}\le\kappa v_{i0}$, $v_{i0}\le\kappa v_{ij}$), for the $2\kappa$ bound.

A trivializing formalization is ruled out. The goal states only feasibility for (3), with $\beta$ the maximum of (12), not any upper bound. The collection is the page's, not an arbitrary family containing it. The goal mentions none of the cases or the relaxations.

A complete development needs continuous knapsack solutions (greedy optimality, fractional prefixes), convexity of $t\mapsto t^{1-\gamma}$ on $(0,\infty)$, and the factor-two argument of Theorem 10. The knapsack and fractional-prefix lemmas are reusable for the companion missions of this series. Proofs of individual cases, and proofs of milestones in greater generality, 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). https://doi.org/10.1287/opre.2014.1256
• P. Rusmevichientong, D. B. Shmoys, H. Topaloglu, Assortment optimization with mixtures of logits, technical report, Cornell University, 2010. http://legacy.orie.cornell.edu/~huseyin/publications/publications.html
• G. Li, P. Rusmevichientong, H. Topaloglu, The d-level nested logit model: assortment and price optimization problems, Operations Research 63(2), 2015.
• 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. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511921735

Motivation

Network revenue management decides, in real time, which customer requests to accept when every request consumes a bundle of scarce, perishable resources: seats on several flight legs of an itinerary, room-nights of a multi-night hotel stay, bandwidth on several links. The exact dynamic program is intractable for realistic networks, so practice and theory rely on heuristics built from a deterministic linear program (DLP) that replaces random demand by its mean. The question is how much revenue such heuristics lose.

The classical answer (Gallego and van Ryzin 1994, 1997; Talluri and van Ryzin 1998) is that solving the DLP once and following its solution loses $O(\sqrt T)$ over a horizon of length $T$. Re-solving the DLP as capacity is consumed was long believed to help, and Jasin and Kumar (2012) proved that re-solving in every period has bounded loss if the DLP solution is nondegenerate. Bumpensanti and Wang (arXiv:1802.06192v3) showed that the nondegeneracy condition matters: frequent re-solving can lose $\Omega(\sqrt T)$ on degenerate instances. They then proposed a policy, Infrequent Re-solving with Thresholding (IRT), whose loss is bounded by a constant independent of the horizon and of the capacities, with no nondegeneracy assumption. This mission formalizes that result.

Setting

There are $n$ customer classes $j \in [n]$ and $m$ resources $l \in [m]$. Class-$j$ customers arrive as independent Poisson processes of rate $\lambda_j > 0$ on $[0, T]$. Accepting a class-$j$ customer earns $r_j \ge 0$ and consumes $a_{lj} \ge 0$ units of resource $l$; $A = (a_{lj})$ is the bill-of-materials matrix with columns $A_j$, and $C \in \mathbb R^m_{\ge 0}$ is the initial capacity. A customer can be accepted only if $A_j \le C'$ componentwise, $C'$ being the remaining capacity; leftover capacity is worthless at $T$.

The DLP with right-hand side $b$ is

$$\max_x \Big\{ \sum_j r_j x_j \ \Big|\ \sum_j A_j x_j \le b,\ 0 \le x_j \le \lambda_j \Big\},$$

and $v^{\mathrm{DLP}}(T, C)$ is $T$ times its value at $b = C/T$. The hindsight optimum is $v^{\mathrm{HO}}(T, C) = \mathbb E[V^{\mathrm{HO}}]$, where $V^{\mathrm{HO}}$ is the value of the same LP with capacity $C$ and the realized demands $\Lambda_j(T) \sim \mathrm{Poisson}(\lambda_j T)$ as upper bounds. It bounds the expected revenue of every non-anticipating policy, and the regret of a policy $\pi$ is $v^{\mathrm{HO}} - v^\pi$.

A probabilistic allocation on a window accepts each class-$j$ arrival with a fixed probability $p_j$ when capacity allows. The IRT policy uses $\tau_u = T^{(5/6)^u}$ and re-solving times $t^*_u = T - \tau_u$ for $u = 0, \dots, K$, where $K = \lceil \log\log T / \log(6/5)\rceil$. At $t^*_u$ it solves the DLP with right-hand side $C(t^*_u)/\tau_u$ (remaining capacity over remaining time), obtaining $x^u$. In the epochs $u < K$ it accepts class $j$ with probability $0$ if $x^u_j < \lambda_j\tau_u^{-1/4}$, else $1$ if $x^u_j > \lambda_j(1 - \tau_u^{-1/4})$, else $x^u_j/\lambda_j$; in the last epoch $[t^*_K, T]$ it uses $x^K_j/\lambda_j$. The family $\mathrm{IRT}^{K'}$ re-solves $K'$ times on the same schedule; $\mathrm{IRT}^0$ is static probabilistic allocation (SPA), and $\mathrm{HO}^{K'}$ follows $\mathrm{IRT}^{K'}$ until $t^*_{K'}$ and then earns the hindsight optimum of what remains.

Formalization targets

Goal: Theorem 1 (p. 16)

There is a constant $M = M(\lambda, r, A)$ such that for every horizon $T \in \{1, 2, \dots\}$ and every capacity vector $C \ge 0$,

$$v^{\mathrm{HO}}(T, C) - v^{\mathrm{IRT}}(T, C) \le M .$$

The constant is not fixed; the content is its independence of $T$, of $C$, and of the optimal LP solution chosen at each re-solve.

Milestones

• $v^{\mathrm{HO}} \le v^{\mathrm{DLP}}$ (Sec. 2.2.2, p. 9).
• Lemma 4 (p. 37): $\mathbb P(|X - \mu| \ge x) \le 2e^{-x^2/(3\mu)}$ for $X \sim \mathrm{Poisson}(\mu)$, $0 < x \le \mu$.
• Proposition 5 (p. 27): $v^{\mathrm{DLP}} - v^{\mathrm{SPA}} \le M\sqrt T$, uniformly in $C$.
• Proposition 1 (p. 16): with one re-solve at $T - T^{5/6}$,

$$v^{\mathrm{HO}} - v^{\mathrm{HO}^1} \le M T e^{-\kappa T^{1/6}},\qquad v^{\mathrm{HO}} - v^{\mathrm{IRT}^1} \le M T e^{-\kappa T^{1/6}} + M T^{5/12}.$$

• Eq. (13) (p. 29): for every $K'$,

$$v^{\mathrm{HO}} - v^{\mathrm{IRT}^{K'}} \le M\sum_{u=0}^{K'-1} T^{(5/6)^u} e^{-\kappa T^{(5/6)^u/6}} + M T^{(5/6)^{K'}/2}.$$

• p. 30: $T^{(5/6)^{K}} \le e$, and the right-hand side of (13) at $K' = K(T)$ is bounded uniformly in $T \ge 1$.

Significance

The result separates two design choices in re-solving heuristics: how often to re-solve and how to turn an LP solution into a control. It shows that re-solving only $O(\log\log T)$ times, combined with rounding nearly-degenerate acceptance probabilities to $0$ or $1$, is enough for bounded regret, and that the constant is uniform over all capacity-to-horizon ratios, so degenerate DLP solutions, which occur only at particular ratios, cause no loss of order. Since $v^{\mathrm{HO}} \ge v^*$, it also shows that the hindsight optimum is within a constant of the optimal policy's value in this model.

The result is proved on paper but not machine-checked. A formalization would produce a reusable Poisson-arrival revenue-management model, a precise account of the regret decomposition over re-solving epochs, and an independent check of a proof with known gaps (see Difficulty). No part of it is formalized on the platform.

Difficulty

The obvious argument compares the policy with the DLP solution and controls the deviation of Poisson demand by its standard deviation; this gives only $O(\sqrt T)$, because the DLP value exceeds the hindsight optimum by order $\sqrt T$ and the lost sales accumulate. Bounded regret needs a comparison with the hindsight LP, path by path: the acceptances made before the last re-solve must remain extendable to a hindsight-optimal solution with overwhelming probability. This requires LP sensitivity of the hindsight solution to the random right-hand side, uniformly over the degenerate cases, and the printed proof's statement of it (Lemma 5) is false as printed: on a two-class, single-resource instance its interval for $\bar z_1$ is empty. A correct argument needs a proximity bound for optimal LP solutions under a change of the demand bounds, summed over all classes, not only over $J_\lambda = \{j : x^*_j = \lambda_j\}$. The analysis of the schedule (the sum over epochs in (13)) is elementary but the printed chain of inequalities on p. 30 uses a monotonicity that fails for large arguments.

Formalization scope

All objects are in the definition item ResolvingNRM.IRT.Model. Classes are Fin n, resources Fin m, A : Matrix (Fin m) (Fin n) ℝ. LP values reuse piValue from the published RLPBidPrice.Unbiased.Model; the hindsight LP is over real $z$, as in (3). Expectations are explicit sums of Poisson weights. A window of probabilistic allocation is represented by its Poisson count of arrivals, i.i.d. classes with law $\lambda_j/\sum_i\lambda_i$ and independent Bernoulli acceptance coins, the standard representation for controls constant on the window. Policies are backward recursions over the re-solving epochs. Ties in the LP are left open: a policy takes an arbitrary optimal-solution selector, and every theorem quantifies over all selectors after its constants.

Conventions and deviations from the page, each disclosed in the item concerned:

• Standing assumptions of Sec. 2 (p. 7), left implicit there: $\lambda_j > 0$, $r \ge 0$, $A \ge 0$, $C \ge 0$.
• "$O(g)$" is read as: there is $M$, depending only on $(\lambda, r, A)$, with the bound $\le M g(T)$ for all $T \ge 1$ (or $T > 0$) and all $C \ge 0$.
• Milestones applied to sub-horizons $T^{(5/6)^u}$ take a real $T$; the goal takes $T \in \mathbb N$.
• Lemma 4 is stated for $0 < x \le \mu$; as printed (all $x > 0$) it is false, e.g. $\mu = 1$, $x = 5$.
• In Proposition 1 and (13), $\kappa > 0$ is existential and uniform in $C$; the printed $\kappa$ depends on $J_\lambda$ and is derived through Lemma 5.
• (13) is stated for every number $K'$ of re-solves.
• Algorithm 3 prints the re-solve right-hand side as $C(t^*_k)/\tau_k$; it is read with index $u$.
• For $1 \le T \le e$ the formula for $K$ is undefined or negative; the formalization takes $K = 0$, so IRT is SPA there.
• The optimal policy value $v^*$ and the paper's constant $\alpha$ are not defined; Lemmas 5 and 6 are not stated.

A statement that lets $M$ depend on $T$ or $C$, compares IRT with the DLP instead of the hindsight optimum, uses a fixed number of re-solves, or assumes a nondegenerate or vertex LP solution is trivial or a different theorem, and is ruled out by the quantifier order of the goal. The milestone $T^{(5/6)^K} \le e$ has a sorry-free local check.

Welcome contributions: LP proximity results (Cook–Gerards–Schrijver–Tardos type), Poisson concentration, superposition and thinning of Poisson processes, and lemmas on expectations of LP values. The source is arXiv:1802.06192v3; its printed page numbers equal the PDF page numbers.

Selected references

• P. Bumpensanti, H. Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, 2018; Management Science 66(7), 2020. https://arxiv.org/abs/1802.06192
• S. Jasin, S. Kumar, A Re-Solving Heuristic with Bounded Revenue Loss for Network Revenue Management with Customer Choice, Mathematics of Operations Research 37(2), 2012. https://doi.org/10.1287/moor.1110.0530
• G. Gallego, G. van Ryzin, A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management, Operations Research 45(1), 1997. https://doi.org/10.1287/opre.45.1.24
• K. Talluri, G. van Ryzin, An Analysis of Bid-Price Controls for Network Revenue Management, Management Science 44(11), 1998. https://doi.org/10.1287/mnsc.44.11.1577
• M. Reiman, Q. Wang, An Asymptotically Optimal Policy for a Quantity-Based Network Revenue Management Problem, Mathematics of Operations Research 33(2), 2008. https://doi.org/10.1287/moor.1070.0288
• W. Cook, A. M. H. Gerards, A. Schrijver, É. Tardos, Sensitivity Theorems in Integer Linear Programming, Mathematical Programming 34, 1986. https://doi.org/10.1007/BF01582230

Motivation

Online marketplaces, ad exchanges and real-estate platforms sell items that are each described by a vector of features and are rarely seen twice. A seller who prices such items cannot learn a demand curve item by item. It must learn how features map to values, while pricing, from accept/reject feedback alone. Cohen, Lobel and Paes Leme (Management Science, 2020; SSRN 2737045) model this as feature-based dynamic pricing with adversarial features and a linear valuation. They show that a direct multi-dimensional binary search (PolytopePricing) can have regret exponential in the dimension (their Theorem 1). Their EllipsoidPricing algorithm, a pricing variant of Khachiyan's ellipsoid method (Khachiyan 1979), has worst-case regret quadratic in the dimension and logarithmic in the horizon (their Theorem 2). This mission formalizes Theorem 2 and the chain of lemmas behind it.

Setting

Fix a dimension $d \ge 2$, a radius $R > 0$ and a horizon $T$. Nature picks an unknown parameter $\theta \in \mathbb{R}^d$ with Euclidean norm $\|\theta\| \le R$. In each period $t = 1, \dots, T$ a product arrives with a feature vector $x_t \in \mathbb{R}^d$, $\|x_t\| \le 1$, and market value $\theta' x_t$. The seller sees $x_t$, posts a price $p_t$, and a sale occurs iff $p_t \le \theta' x_t$, earning $p_t$. The regret (Eq. (1)) is

$$\mathrm{Regret} = \sum_{t=1}^{T} \big[\theta' x_t - p_t\,\mathbb{I}\{\theta' x_t \ge p_t\}\big],$$

and the worst-case regret of a policy is its maximum over $\theta$ and over nature's (possibly adaptive) choice of features.

An ellipsoid with center $a$ and positive definite shape matrix $A$ is $E(A,a) = \{\theta : (\theta - a)' A^{-1} (\theta - a) \le 1\}$. EllipsoidPricing with parameter $\epsilon > 0$ keeps an ellipsoid $E_t = E(A_t, a_t)$, starting from the ball $E_1 = B(0,R)$. In period $t$ it computes

$$\underline b_t = x_t' a_t - \sqrt{x_t' A_t x_t}, \qquad \bar b_t = x_t' a_t + \sqrt{x_t' A_t x_t},$$

the minimum and maximum of $\hat\theta' x_t$ over $E_t$.

• If $\bar b_t - \underline b_t \le \epsilon$, it exploits: it posts $p_t = \underline b_t$ and keeps $E_{t+1} = E_t$.
• Otherwise it explores: it posts $p_t = \tfrac12(\bar b_t + \underline b_t)$ and replaces $E_t$ by the ellipsoid of Eq. (4) that covers the half of $E_t$ consistent with the feedback. With $b = A_t x_t / \sqrt{x_t' A_t x_t}$, the new shape is $\tilde A = \frac{d^2}{d^2-1}\big(A_t - \frac{2}{d+1} b b'\big)$ and the new center is $a_t \pm \frac{1}{d+1} b$, with $+$ after a sale.

Write $\lambda_d(A)$ for the smallest eigenvalue of a symmetric matrix $A$.

Formalization targets

Goal: Theorem 2

There is a universal constant $C > 0$ such that for all $d \ge 2$, $R > 0$, $T \ge 2d$, $\|\theta\| \le R$ and $\|x_t\| \le 1$, EllipsoidPricing run with $\epsilon = R d^2 / T$ satisfies

$$\mathrm{Regret} \le C \, R \, d^2 \ln(T/d).$$

This is the paper's $O(R d^2 \ln(T/d))$ claim, with no constant fixed.

Milestones, in the order of the paper's argument

• the closed forms of $\underline b_t, \bar b_t$ (§5.2);
• the containment of each half-ellipsoid in the updated ellipsoid (Eq. (4), already proved on the platform);
• $\theta \in E_t$ and $A_t \succ 0$ along the run;
• the volume formula $\operatorname{Vol} E(A,a) = V_d \sqrt{\prod_i \lambda_i(A)}$ and the volume decrease $\operatorname{Vol} E(\tilde A) \le e^{-1/2d} \operatorname{Vol} E(A)$ (§5.1);
• Lemma 2: if $z < \lambda_d(A)$ and $\det(A - \beta b b' - zI) \ge 0$, then $\lambda_d(A - \beta b b') \ge z$;
• Lemma 3: $\lambda_d(\tilde A) \ge \frac{d^2}{(d+1)^2} \lambda_d(A)$;
• Lemma 4: if $\lambda_d(A) \le \epsilon^2/(400 d^2)$ and $x' A x > \epsilon^2/4$, then $\lambda_d(\tilde A) \ge \lambda_d(A)$;
• the eigenvalue floor $\lambda_d(A_t) \ge \epsilon^2 / (400 (d+1)^2)$;
• Lemma 1: at most $2 d^2 \ln(20 R (d+1)/\epsilon)$ exploration periods;
• an exploitation period sells and has regret at most $\epsilon$.

Significance

The result. Theorem 2 shows that contextual posted-price learning with adversarial features costs only polynomially many "probing" sales in the dimension. A direct cutting-plane search over the polytope of consistent parameters (PolytopePricing) cannot do this: its worst-case regret is exponential in $d$ (Theorem 1). The ellipsoid analysis via the smallest eigenvalue (Lemmas 2–4) is reused in the paper's noisy-valuation extension (ShallowPricing, §6) and in later work on contextual pricing and contextual search.

Formalizing it. No part of the paper is machine-checked. The Eq. (4) containment is already proved on the platform (Bertsimas–Tsitsiklis Theorem 8.1). The volume factor there is $e^{-1/(2(d+1))}$, weaker than the $e^{-1/2d}$ used here. The eigenvalue lemmas on rank-one perturbations (Lemmas 2–4) are new to the platform and reusable for any analysis of ellipsoid-type updates. A formal proof of the goal would also settle a gap in the printed proof, noted under the formalization scope.

Difficulty

The obvious argument is the textbook ellipsoid bound: volume shrinks by $e^{-1/2d}$ per exploration, so exploration must stop. This fails because the ellipsoid need not become small in every direction. The volume can go to zero while one axis stays long, and then a feature along that axis keeps triggering exploration. The paper replaces the volume argument by a lower bound on the smallest eigenvalue, which needs a sign analysis of the characteristic polynomial of a rank-one perturbation (Lemmas 2–4) together with the exploration test $x_t' A_t x_t > \epsilon^2/4$. The constant $k = 1/(400 d^2)$ in Lemma 4 is chosen to make a specific inequality hold for every $d \ge 2$.

The regret bound needs, in addition, a per-round bound for exploration periods. The printed proof (p. 16) uses "the trivial bound of regret $R$ per round". That bound is not immediate when an exploration price is accepted, since the center $a_t$ can leave $B(0,R)$ and the round's regret is then only bounded by $\sqrt{x_t' A_t x_t}$. This is why the goal is the $O$-form with an unspecified universal constant rather than the proof's explicit inequality.

Formalization scope

• Types. Vectors are Fin d → ℝ; $\theta' x$ is the dot product θ ⬝ᵥ x. Both norms are Euclidean, encoded as $x\cdot x \le 1$ and $\theta\cdot\theta \le R^2$; Mathlib's ‖·‖ on Fin d → ℝ is the sup norm and is never used. Ellipsoids, the ball, and the update (4) are the published LinearOptimization.ellipsoid, ellipsoidBall, ellipsoidUpdateCenter and ellipsoidUpdateMatrix.
• Eigenvalues and volume. $\lambda_d(A)$ is the infimum of the real spectrum, i.e. the minimum eigenvalue of a symmetric matrix. Volumes are Lebesgue measure on Fin d → ℝ in $[0, \infty]$. $\varphi_D(z)$ is $\det(D - zI)$ as printed, not Mathlib's charpoly.
• The algorithm. EllipsoidPricing is a deterministic recursion indexed from $0$ (Lean period $t$ is the paper's $t+1$), started from $E_1 = B(0,R)$, which the paper allows ("or in fact any ellipsoid that contains $K_1$", p. 11). The paper's "smallest ellipsoid containing $H_{t+1}$" is replaced by its closed form (4), which the paper gives on p. 14. Because the algorithm is deterministic, a closed-loop nature generates a fixed feature sequence, and the worst case is a universal quantifier over $\theta$ in the ball and over sequences.
• Added hypotheses, all disclosed in the items.
  • $d \ge 2$ everywhere, since (4) divides by $d^2 - 1$.
  • $T \ge 2d$ in the goal, since $\ln(T/d) \le 0$ for $T \le d$.
  • $\epsilon \le 20 R (d+1)$ in Lemma 1 and the eigenvalue floor: for larger $\epsilon$ the printed bound is negative.
  • $\|x\| \le 1$ in Lemma 4, the §3 normalization that its proof uses.
• Not taken from the page. E₁ is not the Löwner–John ellipsoid of a general $K_1$: the proof's "$\tilde E_1$ lies in the ball of radius $R$" fails for it. The proof's explicit inequality $\mathrm{Regret} \le NR + (T-N)\epsilon$ is not a milestone, because of the per-round gap above.
• Ruled out. The goal may not be trivialized by any of the following:
  • a constant $C$ that depends on $d$, $R$, $T$ or the instance;
  • regret measured against a price the algorithm never posts, or an exploit price that is not accepted;
  • features bounded in the sup norm;
  • an explore test or update different from (4);
  • a single fixed feature sequence.
• Contributions welcome. Proofs of the volume formula and the $e^{-1/2d}$ decrease, which are reusable for any ellipsoid-method development; the eigenvalue lemmas; and the per-round bound for accepted exploration prices that the goal needs.

Selected references

• M. C. Cohen, I. Lobel, R. Paes Leme, Feature-Based Dynamic Pricing, Management Science 66(11), 2020. https://doi.org/10.1287/mnsc.2019.3485 (authors' copy: https://ssrn.com/abstract=2737045)
• L. G. Khachiyan, Polynomial algorithms in linear programming, USSR Comput. Math. Math. Phys. 20(1), 1980. https://doi.org/10.1016/0041-5553(80)90061-0
• M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1993. https://doi.org/10.1007/978-3-642-78240-4
• G. H. Golub, Some modified matrix eigenvalue problems, SIAM Review 15(2), 1973. https://doi.org/10.1137/1015032
• D. Bertsimas, J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997 (Theorem 8.1, the platform's ellipsoid update).