Revenue Management and Choice Models

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).

Motivation

Network revenue managers sell access to limited capacity over time. An airline, for example, may have several products that use the same seat inventory, with some products earning more revenue than others. The decision to accept a request must be made when it arrives, before future requests are known. A standard way to guide that decision is to solve a deterministic linear program using expected demand, then use its optimal allocation as a probability of acceptance. As inventory changes, one can solve the program again. Bumpensanti and Wang study how often to do so, and show that frequent re-solving has a real limitation when the linear program is degenerate: on a particular instance its expected loss grows at least as the square root of the selling horizon. Bumpensanti and Wang, arXiv:1802.06192v3, Sections 3.1 and 5.1.

The same paper gives an infrequent re-solving policy with uniformly bounded regret and an upper bound of order $\sqrt T$ for the frequent re-solving policy. The lower-bound result is the counterpart that identifies a case where that order cannot be removed by the frequent policy itself. It uses a two-class example small enough to expose the issue without other network complications. Bumpensanti and Wang, arXiv:1802.06192v3, Theorem 1 and Propositions 2–3.

Setting

There is one resource, initially with $T$ units of capacity, and two customer classes. Class $j$ arrives through an independent Poisson process of rate one. Accepting a customer uses one unit of capacity and earns price $r_j$, where $0<r_2<r_1$. Rejected requests earn nothing, and unused capacity has no terminal value. The higher-price class has priority in the deterministic allocation, but its realized demand is random. The horizon $T$ is a positive integer, divided into $T$ periods of length one. Bumpensanti and Wang, arXiv:1802.06192v3, Section 2, pp. 7–9, and Appendix C.1, p. 32.

At the start of a period with $k$ periods left and capacity $c$, the deterministic linear program (DLP) chooses rates $x_1,x_2$ that maximize $r_1x_1+r_2x_2$ subject to $x_1+x_2\le c/k$ and $0\le x_j\le1$. In this instance its first coordinate is $x_1=\min\{c/k,1\}$. The frequent re-solving policy (FR) accepts each class-$j$ request in that period with probability $x_j$, provided capacity remains. It re-solves the DLP at the next period with the new capacity. This is Algorithm 2 specialized to the example. Bumpensanti and Wang, arXiv:1802.06192v3, Algorithm 2, p. 11, and Appendix D, p. 42.

The hindsight optimum knows the total demand from both classes at the end of the horizon and chooses the best feasible allocation using that information. Its expected value is $v^{\mathrm{HO}}(T,T)$; the first argument is horizon length and the second is initial capacity. Let $v^{\mathrm{FR}}(T,T)$ be the frequent policy's expected revenue. Since hindsight has more information, their difference is a regret benchmark. The formulation uses the paper's hindsight linear program, which is exact on this unit-consumption instance. Bumpensanti and Wang, arXiv:1802.06192v3, Eq. (3) and Definition 1, p. 9.

Formalization targets

Main result

For every pair of prices $0<r_2<r_1$, there are $M>0$ and $T_0\ge1$ such that, for all integer $T\ge T_0$ and every optimal DLP selector used by FR,

$$v^{\mathrm{HO}}(T,T)-v^{\mathrm{FR}}(T,T)\ge M\sqrt T.$$

This specializes Proposition 2's existence statement to the explicit family in its Appendix C.1 proof. The constant may depend on the prices, but is chosen before the selector and the horizon. The benchmark is the hindsight value, as in the proposition. Bumpensanti and Wang, arXiv:1802.06192v3, Proposition 2, p. 18, and Appendix C.1, pp. 32–34.

Supporting results

The milestones record the optimal DLP allocation on the example and two clauses of Lemma 7. The latter estimate the probabilities that the high-price arrival count is moderately below its mean in the first third and moderately above its mean in the last third. With $T'$ an integer phase length and $N\sim\operatorname{Poisson}(T')$, the first bound is

$$\mathbb P(T'-4\sqrt{T'}\le N\le T'-3\sqrt{T'}) \ge 0.0013-0.9496/\sqrt{T'}.$$

The third-phase bound uses the standard normal cumulative distribution function $\Phi$ and the unrounded constant $\Phi(7)-\Phi(6)$. Bumpensanti and Wang, arXiv:1802.06192v3, Lemma 7 and Eqs. (49)–(53), p. 40.

Significance

This result shows that solving the DLP every period does not, by itself, give a horizon-independent expected loss. The example has only one resource and two customer classes; the gap cannot be attributed to a large network. The paper's separate bounded-regret result uses a different re-solving schedule and acceptance rule, so formalizing this lower bound helps distinguish guarantees for the two policies. Together with the upper bound for FR, it identifies the square-root order as the relevant scale for this policy on the example. Bumpensanti and Wang, arXiv:1802.06192v3, Sections 4–5.

The mathematical proposition is proved in the cited paper; the Lean goal here remains an open theorem statement. Formalizing it requires precise interfaces for a Poisson arrival model, a capacity-limited randomized policy, a hindsight LP benchmark, and asymptotic lower bounds. Those interfaces can be reused in later revenue-management results, while the two-class instance gives a concrete check on the conventions.

Difficulty

The initial DLP solution allocates the average capacity to the high-price class. A simple intuition might therefore predict that repeated re-solving preserves capacity for that class. The remaining-capacity ratio, however, responds to realized arrivals; when the ratio rises above one, the re-solved LP assigns positive acceptance probability to the lower-price class. The policy then spends capacity before later high-price arrivals are known. The lower-bound analysis needs a path event that controls arrivals through the middle phase and a joint event involving the policy's accepted requests. Marginal Poisson counts alone do not determine those admissions. Bumpensanti and Wang, arXiv:1802.06192v3, Appendix C.1, pp. 32–34.

Formalization scope

Lean uses Fin 2 for classes and Fin 1 for the resource. The general model takes positive Poisson rates, nonnegative prices and nonnegative consumption. On the lower-bound instance the rates and consumptions equal one, capacity equals $T$, and prices satisfy $0<r_2<r_1$. These are the operational standing assumptions of the paper's Section 2 and the positive-price reading used by the example. Optimal DLP ties are represented by quantifying over every selector. The LP value is the published RLPBidPrice.Unbiased.piValue definition, evaluated on nonnegative capacity vectors; the rate and capacity conventions make its real supremum well posed.

The window law superposes the independent class Poisson processes into a Poisson total count, independent class labels, and independent Bernoulli acceptance marks. A fold over ordered arrivals applies Algorithm 2's capacity check after every acceptance. The expected hindsight value sums over independent total demand counts, and the FR value is a backward recursion over the remaining unit periods. The target's $M$ is strictly positive and fixed before the horizon, so neither a zero constant nor a horizon-dependent constant can satisfy it trivially.

The two Lemma 7 milestones cover only $Q_1$ and $Q_3$. Its continuous-time $Q_2$ event and the joint admission event require a path probability space and are outside this draft. Equation (52) yields $\Phi(7)-\Phi(6)$; the printed $9.8531\times10^{-10}$ rounds that value upward. The source proof divides $T$ into three exact integer-length phases, while Proposition 2 is stated for all sufficiently large $T$; this gap requires attention in a complete proof. The source here is arXiv:1802.06192v3, whose printed and PDF page numbers coincide.

Selected references

• Bumpensanti, P. and Wang, H., A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv preprint arXiv:1802.06192v3, 2018. PDF.

Motivation

A retailer that decides which products to display, an online platform that decides which items to show in a recommendation slot, and an airline that decides which fare classes to open all face the same problem: the set of options offered changes what customers buy, and the substitution pattern is not known in advance. The multinomial logit (MNL) model is the standard model of this substitution in revenue management (Talluri and van Ryzin 2004), and optimizing the offered set under a known MNL model is a classical, efficiently solvable problem (e.g. Rusmevichientong, Shen and Shmoys 2010, for a capacity constraint).

The MNL-Bandit asks what happens when the MNL parameters are unknown and must be learned from the purchases themselves, while revenue is being earned. Earlier approaches (Rusmevichientong, Shen and Shmoys 2010; Sauré and Zeevi 2013) separate exploration from exploitation and need the gap between the best and the second-best assortment to be known. Agrawal, Avadhanula, Goyal and Zeevi (Oper. Res. 2019, arXiv:1706.03880) give a single upper-confidence-bound policy whose regret is of order $\sqrt{NT}$ up to logarithmic factors, with no such knowledge. This mission formalizes that result, Theorem 1 of the paper.

Setting

There are $N$ products with known revenues $r_i\in[0,1]$. At each time $t=1,\dots,T$ the seller offers an assortment $S_t$ from a family $\mathcal S$ of feasible subsets of $\{1,\dots,N\}$, and one customer either buys a product $c_t\in S_t$ or buys nothing ($c_t=0$). Given $S_t=S$, the choice follows the MNL model with attraction parameters $v_1,\dots,v_N\ge0$ and $v_0=1$:

$$p_i(S)=\frac{v_i}{1+\sum_{j\in S}v_j}\quad(i\in S\cup\{0\}),\qquad p_i(S)=0\ \text{otherwise},$$

independently of the past. The expected revenue of $S$ is $R(S,v)=\sum_{i\in S}r_iv_i\big/\big(1+\sum_{j\in S}v_j\big)$. The family $\mathcal S$ is described by totally unimodular constraints, $\mathcal S=\{S : A\,x(S)\le b\}$ with $x(S)$ the incidence vector of $S$, $A$ totally unimodular and $b$ integral (cardinality constraints are the main example). A policy chooses $S_t$ from the past choices, and its regret is

$$\mathrm{Reg}_\pi(T,v)=T\,R(S^*,v)-\mathbb E_\pi\Big[\sum_{t=1}^TR(S_t,v)\Big],\qquad R(S^*,v)=\max_{S\in\mathcal S}R(S,v).$$

The seller knows $r$ and $\mathcal S$ but not $v$.

Algorithm 1 works in epochs: epoch $\ell$ offers one assortment $S_\ell$ repeatedly until a customer buys nothing. Let $\hat v_{i,\ell}$ be the number of purchases of $i$ in epoch $\ell$, $T_i(\ell)$ the number of the first $\ell$ epochs that offered $i$, and $\bar v_{i,\ell}$ the average of $\hat v_{i,\tau}$ over those epochs. The algorithm forms the upper confidence bounds

$$v^{\mathrm{UCB}}_{i,\ell}=\bar v_{i,\ell}+\sqrt{\bar v_{i,\ell}\,\frac{48\log(\sqrt N\ell+1)}{T_i(\ell)}}+\frac{48\log(\sqrt N\ell+1)}{T_i(\ell)},$$

starting from $v^{\mathrm{UCB}}_{i,0}=1$, and offers next the assortment in $\mathcal S$ that maximizes $R(S,v^{\mathrm{UCB}}_{\cdot,\ell})$.

Formalization targets

Goal: Theorem 1 (p. 11)

Under Assumption 4.1 (every $v_i\le v_0=1$, and $\mathcal S$ is closed under taking subsets) there are absolute constants $C_1,C_2$ such that for every instance and every horizon $T$,

$$\mathrm{Reg}_\pi(T,v)\le C_1\sqrt{NT\log NT}+C_2N\log^2NT .$$

The constants are not fixed: the goal asserts the order of the regret, which is what the paper claims.

Milestones

The milestones follow the proof in Appendix A of the paper:

1. The law of an epoch's purchase count: Lemma A.1, its moment generating function given the offered assortment.
2. Concentration: Theorem 5, Chernoff bounds for geometric variables; Corollary D.1; and Lemma A.2 for the averages $\bar v_{i,\ell}$ along Algorithm 1.
3. Lemma 4.1: $v^{\mathrm{UCB}}_{i,\ell}\ge v_i$ with probability at least $1-6/(N\ell)$, and its rate of convergence.
4. Optimism of the revenue estimate: Lemma A.3 (monotonicity of the optimal revenue in $v$) and Lemma 4.2.
5. The per-epoch error: Lemma A.4 (a Lipschitz bound) and Lemma 4.3.
6. The epoch decomposition of the regret, (A.14).

Significance

Theorem 1 shows that learning the choice model costs only $\tilde O(\sqrt{NT})$ revenue, with no dependence on how separated the instance is. The paper also proves a lower bound of order $\sqrt{NT/K}$ under a $K$-cardinality constraint (its Theorem 2), so for small $K$ the bound is optimal up to logarithmic factors. The epoch device used here reduces the analysis of a choice model with substitution to unbiased i.i.d. estimates of each $v_i$.

The result is proved in the paper (Appendix A, with the concentration bounds in Appendix D). It has not been machine-checked. A formal proof would also settle several printed slips that the formalization had to repair (listed under Formalization scope). The concentration bounds for geometric variables, Theorem 5 and Corollary D.1, are useful outside this mission.

Difficulty

The estimates $\hat v_{i,\ell}$ are counted in epochs whose assortments are chosen adaptively from earlier estimates, so they are not independent a priori. The paper's argument that they are i.i.d. geometric with mean $v_i$ has to be made rigorous for an adaptive policy. The variables are unbounded, so the standard Chernoff–Hoeffding bounds for bounded variables do not apply, and the number of samples $T_i(\ell)$ is random, which requires a union bound over all its possible values. Finally, the regret is a sum over customers while the analysis is per epoch, and the two are linked through the expected epoch length $1+\sum_{j\in S_\ell}v_j$ under a random number of epochs and a horizon that cuts the last one.

Formalization scope

• Model. Products are Fin N; a choice is none (no purchase) or some i. The parameter $v_0$ is normalized to $1$, as the paper allows. Algorithm 1 is deterministic, so a history of horizon $T$ is a sequence of $T$ choices with the product law $\prod_tp_{c_t}(S_t)$, and every expectation is a finite sum. The revenue $R(S,v)$ is the published definition ChoiceCDLP.MNL.mnlObjective v r 1 S.
• Feasible family. $\mathcal S$ is a finite family with the TU representation (2.3), closed under subsets, and nonempty (the paper presupposes nonemptiness when it writes $S^*=\arg\max$).
• Algorithm. Algorithm 1 is a policy defined by recursion on the history. It receives $r$ and an argmax selector for $\mathcal S$, never $v$. Every statement quantifies over all selectors, that is, over every tie-breaking rule. While a product has never been offered, its $v^{\mathrm{UCB}}$ stays at the initial value $1$.
• Epoch events. The lemmas about epoch $\ell$ are stated for every finite horizon $T$, on the event that epoch $\ell$ is completed by customer $T$; uniformity in $T$ is the paper's infinite-horizon statement.
• Repairs of the page, all disclosed in the items:
  1. Lemma A.2's misprinted $\log(\ell+1)$ is replaced by $\log(\sqrt N\ell+1)$.
  2. Lemmas 4.2 and 4.3 are indexed by the estimate built at the end of epoch $\ell$.
  3. Lemma 4.3's free index $i$ becomes the sum over $i\in S_{\ell+1}$.
  4. Lemmas 4.1 and 4.3 use the explicit constants $C_1=\sqrt{72}+\sqrt{24}$ and $C_2=144$ of the proof.
  5. Lemma A.3 and Lemma 4.2 require positive parameters on the optimal set; the printed versions are false otherwise.
  6. (A.14) is an inequality, since the horizon cuts the last epoch.
• Not stated. Corollary A.1 (the epoch estimates are i.i.d. geometric across the epochs of the adaptive policy) is not posed as an item: a single-epoch law would be a weaker statement than the page's.
• No trivialization. The policy cannot see $v$, the constants of the goal precede every other quantifier, and the regret is the paper's (2.6), so the goal cannot be met by a policy that offers $S^*$ or by constants that depend on the instance.
• Welcome contributions. Infrastructure for adaptive sampling (the i.i.d. property of the epoch estimates), Chernoff bounds for geometric and sub-exponential variables, and a Wald-type identity for epochs.

The paper's own proofs are in its Appendices A and D.

Selected references

• S. Agrawal, V. Avadhanula, V. Goyal, A. Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, Operations Research 67(5):1453–1485, 2019. arXiv:1706.03880v2, doi:10.1287/opre.2018.1832
• P. Rusmevichientong, Z.-J. M. Shen, D. B. Shmoys, Dynamic assortment optimization with a multinomial logit choice model and capacity constraint, Operations Research 58(6):1666–1680, 2010. doi:10.1287/opre.1100.0866
• D. Sauré, A. Zeevi, Optimal dynamic assortment planning with demand learning, Manufacturing & Service Operations Management 15(3):387–404, 2013. doi:10.1287/msom.2013.0429
• K. Talluri, G. 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
• M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge University Press, 2005.

Motivation

A retailer that can display only some of its products must choose an assortment: the set of products offered to an arriving customer. Customers substitute: whether a given product is bought depends on what else is on the shelf. The assortment problem asks for the offer set that maximises expected revenue under a model of this substitution behaviour. It is a core problem of revenue management (Talluri and van Ryzin, Management Science 2004), and it is NP-hard already for a mixture of two multinomial logit models (Rusmevichientong, Shmoys, Tong and Topaloglu, POMS 2014).

The heuristic used most widely in practice is revenue-ordered assortments: sort the products by price and offer, for some threshold, every product priced at least that threshold. It is optimal under the multinomial logit model (Talluri and van Ryzin 2004) but not in general. Berbeglia and Joret (arXiv:1606.01371v3, 2019; Algorithmica 2020) give a tight analysis of its approximation ratio for every regular discrete choice model, a class that includes all random utility models. They prove three incomparable guarantees. This mission formalizes the third, Theorem 3.3, whose ratio depends on the purchase behaviour of an optimal assortment rather than on the prices. Companion missions in this series cover the price-ratio bound (Theorem 3.2) and the tightness of all three bounds (Theorem 3.4).

Setting

Let $\mathcal C$ be a finite nonempty set of products. A system of choice probabilities gives, for every offer set $S\subseteq\mathcal C$ and product $x$, the probability $\mathcal P(x,S)$ that a customer offered $S$ buys $x$. Buying nothing is the option $0$, with $\mathcal P(0,S)=1-\sum_{x\in S}\mathcal P(x,S)$. The model is regular when

1. $\mathcal P(x,S)\ge0$ for products and for $x=0$;
2. $\mathcal P(x,S)=0$ for $x\notin S$;
3. $\sum_{x\in S}\mathcal P(x,S)\le1$;
4. $\mathcal P(x,S)\ge\mathcal P(x,S')$ whenever $S\subseteq S'$ and $x\in S\cup\{0\}$.

Axiom 4 at $x=0$ says that enlarging the offer set never makes buying nothing more likely.

Prices are a function $r:\mathcal C\to\mathbb R_{>0}$. Offering $S$ earns $\mathrm{rev}(S)=\sum_{x\in S}\mathcal P(x,S)\,r(x)$, and $\mathrm{OPT}=\max_{S\subseteq\mathcal C}\mathrm{rev}(S)$. Let $r_1<\dots<r_k$ be the distinct values of $r$, and let $S_i=\{x:r(x)\ge r_i\}$ for $i\in[k]$. The revenue-ordered strategy earns

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

For an assortment $S^*$, the purchase profile is

$$N_i=\sum_{x\in S^*,\ r(x)\ge r_i}\mathcal P(x,S^*)\qquad(i\in[k]),\qquad N_{k+1}:=0,$$

the probability that a customer offered $S^*$ buys something priced at least $r_i$. It is non-increasing in $i$.

Formalization targets

Goal: Theorem 3.3 (p. 9)

Let $S^*$ be optimal, $\mathrm{rev}(S^*)=\mathrm{OPT}$, suppose $N_1>0$, and let $\ell\in[k]$ be maximum with $N_\ell>0$. Then

$$\mathrm{OPT}\le\Big(\sum_{i=1}^{\ell}\frac{N_i-N_{i+1}}{N_i}\Big)\mathrm{RO} \qquad\text{and}\qquad \sum_{i=1}^{\ell}\frac{N_i-N_{i+1}}{N_i}\le1+\ln\nu,\quad\nu=\frac{N_1}{N_\ell}.$$

The first inequality is the paper's sum-form factor, the bound that Theorem 3.4 shows to be tight. The second is the closed form $1/(1+\ln\nu)$.

Milestones (in proof order)

• Lemma 2.1 (p. 6): $\sum_{x\in S}\mathcal P(x,S)\le\sum_{x\in S'}\mathcal P(x,S')$ for $S\subseteq S'$.
• First observation of the proof (p. 9): $N_i\le\sum_{x\in S_i}\mathcal P(x,S_i)$ and $N_ir_i\le\sum_{x\in S_i}\mathcal P(x,S_i)r_i$.
• Inequality (6) (p. 9): $N_ir_i\le\mathrm{RO}$ for every $i\in[k]$.
• Revenue identity (p. 9): $\mathrm{rev}(S^*)=\sum_{i=1}^{\ell}(N_i-N_{i+1})r_i=\sum_{i=1}^{\ell}\frac{N_i-N_{i+1}}{N_i}N_ir_i$.
• Logarithmic step (p. 9, the comparison $1/\sum\ge1/(1+\ln\nu)$ in Theorem 3.3, used in the last inequality of the proof): for $N_1\ge\dots\ge N_\ell>0$ and $N_{\ell+1}=0$, $\sum_{i=1}^{\ell}(N_i-N_{i+1})/N_i\le1+\ln(N_1/N_\ell)$. The paper states this step without proof.

Significance

Theorem 3.3 gives a guarantee that is independent of prices. The bound $1+\ln(r_k/r_1)$ of Theorem 3.2 grows when prices are spread out. The bound $1+\ln\nu$ is small whenever an optimal assortment sells its expensive products with probability comparable to its overall purchase probability. In §4 the paper combines it with a reduction from unit-demand pricing to derive, for example, the $1/(1+\ln m)$ guarantee of uniform pricing for the unit-demand min-pricing problem (Corollary 4.8, originally due to Aggarwal et al.). Together with Theorems 3.1 and 3.2, it describes the performance of the most common assortment heuristic over the whole class of regular models, with no parametric assumption on customer behaviour.

The theorem is proved on paper. To our knowledge it has no machine-checked proof, and no regular choice model has been formalized on the platform. This mission produces the regular model as a reusable definition, a statement of Theorem 3.3 in which every hypothesis is explicit, and formal versions of the proof's identities and inequalities. The logarithmic step is asserted without proof in the source, so a formal proof of it completes the paper's argument.

Difficulty

Each step is elementary. The difficulty is bookkeeping. The revenue of $S^*$ has to be regrouped by distinct price levels rather than by products: several products may share a price, and $k$ counts values. The regrouping uses an Abel-type rearrangement with the boundary convention $N_{k+1}=0$. Comparing $N_i$ with the purchase probability of $S_i$ needs regularity twice. First, axiom 4 for products passes from $S^*$ to $S^*\cap S_i$. Then the no-purchase case passes from $S^*\cap S_i$ to $S_i$. A proof that uses axiom 4 only for products fails at the second step, and the claim is false without it.

Formalization scope

• Products form a finite type C with [Fintype C] [DecidableEq C]. The goal adds [Nonempty C], the paper's $k\ge1$. Offer sets are Finset C, and $\mathcal P$ is P : C → Finset C → ℝ. The no-purchase option is not a product: $\mathcal P(0,S)$ is the derived quantity noPurchase P S. IsRegular P carries axioms 1–4, including both no-purchase cases.
• $\mathrm{OPT}$ is Finset.sup' over all subsets. $\mathrm{RO}$ is Finset.sup' over the indices $1,\dots,k$ of the threshold sets only.
• Indices are 1-based natural numbers. level r i is $r_i$ for $1\le i\le k$. purchaseProfile P r S i is $N_i$ for $1\le i\le k$ and $0$ otherwise, which builds in $N_{k+1}=0$.
• Optimality is the hypothesis $\mathrm{rev}(S^*)=\mathrm{OPT}$. The index $\ell$ is a variable with hypotheses $1\le\ell\le k$, $N_\ell>0$, and $N_i\not>0$ for $\ell<i\le k$. $N_1>0$ is kept as in the paper.
• The approximation factor is stated in product form, $\mathrm{OPT}\le D\cdot\mathrm{RO}$, never as a ratio. Both the sum form and the logarithmic form are stated. $\ln$ is Real.log, applied to $\nu\ge1$.
• The milestones other than the goal are stated for an arbitrary $S^*$, because the proof does not use optimality there.

The following statements are trivial or false and are not this mission: a maximum over all subsets in place of $\mathrm{RO}$; regularity without its no-purchase case; a purchase profile taken from a non-optimal set while $\mathrm{rev}(S^*)$ is still called the optimum; the logarithmic form alone; a specific choice model (MNL, Markov chain) in place of an arbitrary regular $\mathcal P$.

A complete development needs finite sums regrouped by the values of a function and an elementary logarithm inequality. The regular choice model and the revenue-ordered sets are shared with the other missions of this series and are reusable for any analysis of assortment heuristics. Proofs of any milestone are welcome. So are alternative arguments for the logarithmic step and a proof that $N$ is non-increasing.

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.01371v3
• 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
• 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