Robust Product-line Pricing under Generalized Extreme Value Models

Robust Product-line Pricing under Generalized Extreme Value Models

\RUNAUTHOR{Mai T. and Jaillet P.}

\RUNTITLE{Robust Product-line Pricing under Generalized Extreme Value Models}

\TITLE{Robust Product-line Pricing under Generalized Extreme Value Models}

\ARTICLEAUTHORS{ \AUTHOR{Tien Mai} \AFF{School of Information Systems, Singapore Management University, \EMAIL{[email removed]}} \AUTHOR{Patrick Jaillet} \AFF{EECS, Massachusetts Institute of Technologies, \EMAIL{[email removed]}} }

\ABSTRACT{ We study robust versions of pricing problems where customers choose products according to a generalized extreme value (GEV) choice model, and the choice parameters are not known exactly but lie in an uncertainty set. We show that, when the robust problem is unconstrained and the price sensitivity parameters are homogeneous, the robust optimal prices have a constant markup over products and we provide formulas that allow to compute this constant markup by bisection. We further show that, in the case that the price sensitivity parameters are only homogeneous in each partition of the products, under the assumption that the choice probability generating function and the uncertainty set are partition-wise separable, a robust solution will have a constant markup in each subset, and this constant-markup vector can be found efficiently by convex optimization. We provide numerical results to illustrate the advantages of our robust approach in protecting from bad scenarios. {Our results generally hold for convex and bounded uncertainty sets,} and for any arbitrary GEV model, including the multinomial logit, nested or cross-nested logit. }

\KEYWORDS{Robust optimization, multi-product pricing, generalized extreme value model}

Introduction

In revenue management, pricing is an important problem that refers to the selection of prices for a set of products in order to maximize an expected revenue. This is motivated by the fact that prices are key features that may significantly affect demand for products. The literature of multi-product pricing has seen a large number of papers focusing on how to set prices when customers purchase products according to a discrete choice model Talluri2004RM,Gallego2014multiproduct,zhang2018multiproduct. To the best of our knowledge, prior work all assumes that the parameters of the choice models are known in advance or can be estimated exactly from data. Thus, the corresponding pricing optimization models are built based on pre-determined parameters and ignore any uncertainty in case the parameters are estimated. Nevertheless, in practice, the parameter estimates may vary significantly for different customer types or in different purchasing periods of the year. Thus, ignoring such uncertainties may lead to bad pricing decisions. To deal with the uncertainty issue, one may consider a stochastic approach, i.e., a model aiming at maximizing an average expected revenue over a finite number of scenarios of the choice parameters. This would require of course a trusted assumption and/or a solid optimization of these parameters in each of these scenarios. Moreover, such a stochastic optimization model would be computationally difficult to handle, as the objective function does not have nice properties to derive tractable solutions as in the deterministic case; e.g., a stochastic objective function would be non-unimodal and non-concave when defined in terms of purchase probabilities Li2018mixed_pricing.

{In this paper, we formulate and solve pricing optimization problems under uncertainty in a robust manner. That is, we assume customers' behavior is driven by any choice model in the Generalized Extreme Value (GEV) family such as the Multinomial Logit (MNL) or nested logit model, and the parameters of the choice model are not known exactly but belong to an uncertainty set. The goal here is to maximize the worst-case expected revenue when the choice parameters vary in their support set. We consider problems where the price sensitivity parameters (PSP) are homogeneous or partition-wise homogeneous, i.e., the set of products can be separated into disjoint subsets and the PSP are the same in each subset but can be different over subsets. For the latter, we assume that the choice probability generating function Fosgerau2013GPGF has a separable structure and the uncertainty set is partition-wise separable. We also look at expected-sale requirements in pricing decisions and argue that the model with expected-sale constraints is not appropriate in our robust setting. Therefore, we propose an alternative formulation by adding a penalty term to the objective function for violated expected-sale constraints. We are able to show that the models can then be solved in a tractable way. Our results generally hold for any convex and bounded uncertainty set, and for any choice model in the GEV family. }

From now on, when saying “a GEV model”, we refer to any choice model in the GEV family. Each GEV model can be represented by a choice probability generating function (CPGF) $G(\cdot)$ (see our detailed definition in the next section). To relax the homogeneity of the PSP, we need to assume that the CPGF has a separable structure, which means that $G(\cdot)$ can be written as a sum of sub-CPGFs, each corresponding to a subset of products.

Our contributions: We consider robust versions of the standard pricing optimization problem under GEV models. The setting here is to assume that the parameters of the choice model are not known with certainty and the aim is to find optimal prices associated with products, which maximize the worst-case expected revenue when the choice parameters vary in an uncertainty set. For the unconstrained problem with homogeneous PSP, we show that if the uncertainty set is convex and compact, the robust optimal prices have a constant markup with respect to the products costs, i.e., the robust optimal price of a product is equal to its unit cost plus a constant that is the same over all products. We also provide formulas that allow efficient computation of that constant markup by binary search. This finding generalizes the results for the deterministic unconstrained problem with homogeneous PSP considered in zhang2018multiproduct. We also provide comparative insights showing how the robust optimal revenue and the robust optimal constant markups change as functions of the uncertainty level (i.e., the size of the uncertainty set).

\mtien{For the pricing problem with non-homogeneous PSP, we assume that the CPGF is partition-wise separable and in each partition, the PSP are homogeneous. Moreover, the uncertainty set is also assumed to be partition-wise separable. We show that the robust problem can be converted equivalently into a reduced optimization problem, which can be conveniently solved by convex optimization. As a result, the robust optimal prices have partition-wise constant markups, i.e., in each partition, the robust optimal prices have a constant markup with respect to their costs, and these constant markups can be obtained by convex optimization. We also provide comparative insights for the robust optimal prices and solutions when the size of the uncertainty set varies.}

\mtien{For both cases (i.e., homogeneous PSP and partition-wise homogeneous PSP), we further show that the robust optimal solutions form saddle points of the robust problems, leading to an equality between the objective functions of the max-min problem and its min-max counterpart. }

Previous studies zhang2018multiproduct,Song2007demand,Zhang2013assessing have been looking at constraints on the expected sales, as motivated by applications with inventory considerations Gallego1997multiproductPricing. In this context, the aim is to select prices that maximize the expected revenue while requiring that the expected sales of products lie in a convex set. The advantage of such constraints is that the pricing problem can be reformulated equivalently as a convex program where the decision variables are the purchase probabilities. {However, the final decision is a vector of prices and there may be no fixed prices under which the resulting purchase probabilities always satisfy the expected sale constraints when the choice parameters vary. For this reason, the use of the constrained formulation is not appropriate} in our robust setting. Thus, we propose an alternative formulation in which, instead of requiring that the expected sale constraints be satisfied, we add a penalty cost to the objective function for violated constraints. Our formulation, called pricing with over-expected-sale penalties, is more general than the constrained formulation, in the sense that if the penalty parameters increase to infinity, then the corresponding optimal solutions will converge to those from the constrained problem, and with zero penalty parameters, the pricing problem becomes the unconstrained one. We show that if the CPGF and the uncertainty set are partition-wise separable, then the robust problem can be converted into a reduced optimization problem, which can be conveniently solved by convex optimization.

\mtien{In summary, we show that the robust versions of the pricing problem with homogeneous PSP and partition-wise PSP, with and without over-expected-sale penalties, can be solved in tractable ways by bisection and convex optimization. Our results generally holds for convex and compact uncertainty sets, and for any choice model in the GEV family. In Table (ref) below we give a summary and comparison of the solution methods used to solve the robust pricing problems and their deterministic counterparts, under different settings. The solution methods proposed in this paper are highlighted in bold.}

Literature review: The GEV family includes most of the parametric discrete choice models in the demand modeling and operations research literatures. The simplest and most popular member is the MNL Mcfadden1978modeling,Mcfadden1980econometric and it is well-known that the MNL model retains the independence from irrelevant alternatives (IIA) property, which does not hold in many contexts. There are a number of GEV models that relax this property and provide flexibility in modeling the correlation between alternatives, for example, the nested logit model Ben1985discrete,Ben1973structure, the cross-nested logit Vovsha1998link, the generalized nested logit Wen2001generalized, the paired combinatorial logit koppelman2000paired, the ordered generalized extreme value Small1987discrete, the specialized compound generalized extreme value models Bhat1998accommodating,whelan2002flexible and network-based GEV Daly2006general,Mai2017dynamic models. Fosgerau2013GPGF show that the cross-nested logit model and its generalized version (i.e. network-based GEV) are fully flexible in the sense that they can approximate arbitrarily close any random utility maximization model. Beside the GEV family, it is worth noting that the mixed logit model Mcfadden2000mixed is also popular due to its flexibility in capturing utility correlation. There is a fundamental trade-off between the flexibility and the generality of the choice models and the complexity of their estimation andapplication in operational problems. For the case of GEV models, even being flexible in modeling choice behavior, the resulting operational problems (e.g., product assortment or pricing) are often nonlinear and non-convex, leading to difficulties solving them in practice.

There is a large amount of research on unconstrained pricing under different discrete choice models. For example, Hopp2005 and Dong2009dynamic consider the pricing problem under the MNL model, Li2011pricing consider the nested logit model, li2015d_nested consider the pricing problem under the paired combinatorial logit model, and zhang2018multiproduct consider the pricing problem under any choice model in the GEV family. Under the assumption that the PSP are the same over product, these authors show that the prices have a constant markup with respect to the product costs and provide formulas to explicitly computed this constant markup.

There are some papers trying to get over the assumption that the PSP are homogeneous over products. Li2011pricing study the pricing problem under the nested logit model and assume that the PSP are homogeneous only in each nest and can be different over nests. They then show that the PSP in each nest have a constant markup. zhang2018multiproduct generalize these results by considering the pricing problem under GEV models, in which the CPGF is partition-wise separable and the PSP are assumed to be homogeneous in each partition. The authors also show that, in this case, the optimal prices have a constant markup in each partition.

There are also publications considering the pricing problem with arbitrary PSP. Gallego2014dynamicPricing show that the pricing optimization problem under the nested logit model can have multiple local optimal solutions if the PSP are arbitrarily heterogeneous and provide sufficient conditions to ensure unimodality of the expected revenue function. li2015d_nested and Huh2015pricing consider the pricing problem under the $d$-nested and paired combinatorial logit models and also provide sufficient conditions on the PSP to ensure unimodality of the expected revenue function.

The constrained pricing problem where the prices are required to lie in a feasible set is difficult to solve as the expected revenue function is nonlinear and non-concave in the prices. Motivated by applications with inventory considerations Gallego1997multiproductPricing and the observation that the expected revenue function is concave in the purchase probabilities, researchers have consider the pricing problem with constraints on the expected sales. For example, Song2007demand,Zhang2013assessing consider the pricing problem under the MNL model and show that the expected revenue is concave in the purchase probabilities if the PSP are homogeneous. Keller2013 consider the pricing problem under the MNL and nested logit models and show that the expected revenue function is concave in the purchase probabilities under the MNL and arbitrary PSP, and establish sufficient conditions on the PSP to ensure that the expected revenue under the nested logit model is concave. zhang2018multiproduct also generalizes all these results by showing that, under any GEV model, if the PSP are homogeneous or partition-wise homogeneous, then the expected revenue is concave in purchasing probabilities, making the pricing problem with expected sale constraints tractable.

All above publications assume that the parameters of the choice model is given in advance and ignore any uncertainty associated with such parameters in the pricing problem. However, the choice parameters typically need to be inferred from data and uncertainties may occur, for instance, due to the heterogeneity of the market. In this work, we explicitly take into consider this issue by considering robust versions of the unconstrained and constrained pricing problems, with homogeneous and partition-wise homogeneous PSP. Our results directly generalize the results for deterministic pricing from zhang2018multiproduct, which already covers most of the pricing optimization studies in the literature.

Our work is concerned with robust solutions for the pricing problem under uncertainty, so it is directly related to the concept of robust optimization, an important research area in operations research which has received a growing attention over the past two decades. Robust optimization is motivated by the fact that many real-world decision problems arising in engineering and management science have uncertain parameters due to limited data or noisy measurements. The literature on robust optimization includes a larger number of excellent studies Ben1998robustconvex,Ben2000robust,Ben2006extending. Most of the studies in the literature of robust optimization focus on linear, piece-wise linear or convex objective functions. In our context, the expected revenue is nonlinear and non-convex/non-concave in the prices, implying that existing robust optimization results do not apply (except the part where we consider the constrained pricing problem under uncertain expected-sale constraints in Section (ref)), and making our robust problem challenging to solve in a tractable way. It is worth noting that our work is relevant to Rusmevichientong2012robust where the authors consider robust versions of the assortment planing problem. The main difference is that the decision variables in Rusmevichientong2012robust are discrete (i.e., a set of products).

Paper outline: We organize the paper as follows. In Section (ref), we present the deterministic pricing problem under GEV models and recall some results from previous work. In Section (ref) and (ref), we present our results for the robust pricing problem under homogeneous PSP and partition-wise homogeneous PSP. In Section (ref) we provide some experimental results and in Section (ref) we conclude. In the appendix, Section (ref) provides detailed proofs for our main claims and Section (ref) investigates the robust pricing problem with over-expected-sale penalties.

Notation: Boldface characters represent matrices (or vectors), and $a_i$ denotes the $i$-th element of vector $\textbf{a}$. We use $[m]$, for any $m\in \mathbb{N}$, to denote the set $\{1,\ldots,m\}$. For any vector $\textbf{b}$ with all equal elements, we use $\me{\textbf{b}}$ to denote the value of one element of the vector. Given two vectors of the same size $\textbf{a},\textbf{b} \in \mathbb{R}^m$, $\textbf{a} \succeq \textbf{b}$ is equivalent to $\textbf{a}-\textbf{b} \in\mathbb{R}_+^m$, and $\textbf{a} \preceq \textbf{b}$ is equivalent to $\textbf{b} \succeq \textbf{a}$.

Background: Deterministic Pricing under Generalized Extreme Value Models

We denote by ${\mathcal{V}} = \{1,\ldots,m\}$ the set of $m$ available products. There is a non-purchase item indexed by 0, so the set of all possible products is ${\mathcal{V}} \cup \{0\}$. We also denote by $x_i$ and $c_i$ the price and the cost of product $i$, respectively. The random utility maximization (RUM) framework Mcfadden1978modeling is the most popular approach to model discrete choice behavior. Under this framework, each product $i\in{\mathcal{V}}$ is assigned with a random utility $U_i$ and the additive RUM framework Fosgerau2013GPGF,Mcfadden1978modeling assumes that each random utility can be expressed as a sum of two part $U_i = u_i+\varepsilon_i$, where the term $u_i$ is deterministic and can include values representing characteristics of the product, and the term $\varepsilon_i$ is unknown to the analyst. The RUM principle then assume that the selections are made by maximizing these utilities and the probability that a product $i$ (including the non-purchase item) is selected can be computed as $P(U_i \geq U_j,\ \forall j\in{\mathcal{V}}\cup\{0\} )$.

In our context, we are interested in the effect of the prices on the expected revenue. So we assume that the deterministic terms $u_i$, $\forall i\in{\mathcal{V}}$, can be expressed as $u_i = a_i-b_i x_i$, where $b_i$ is the PSP associated with product $i$ and $a_i$ can include other information that may affect customer's demand such as the brand, size or color of the items. These values can be obtained by fitting the choice model with observation data.

A GEV model can be represented by a choice probability generating function (CPGF) $G(\textbf{Y})$, where $\textbf{Y}$ is a vector of size $m$ with entries $Y_i = e^{u_i}$, for all $i\in{\mathcal{V}}$. Given $i_1,\ldots,i_k \in [m]$, let $\partial G_{i_1,\ldots,i_k}(\textbf{Y})$ be the mixed partial derivatives of $G$ with respect to $Y_{i_1},\ldots,Y_{i_k}$. It is well-known that the CPGF $G(\cdot)$ and the mixed partial derivatives have the the following properties Mcfadden1978modeling,Ben1985discrete.

\mtien{Here we note that (i)-(iv) are basic properties of the CPGF to ensure that the choice model is consistent with the RUM principle Mcfadden1980econometric. Properties (v) and (vi) are direct results from the homogeneity property zhang2018multiproduct. }

Under a GEV model specified by a CPGF $G$, given any vector $\textbf{Y}\in\mathbb{R}^m$, the choice probability of product $i\in{\mathcal{V}}$ is given by \[ P_i(\textbf{Y}|G) = \frac{Y_i\partial G_i(\textbf{Y})}{1+G(\textbf{Y})}. \] Note that the above formulation also implies that the choice probability of the non-purchase item is $P_0(\textbf{Y}|G) = 1/(1+G(\textbf{Y}))$. The GEV becomes the MNL model if $G(\textbf{Y}) = \sum_{i=1}^m Y_i$, and it becomes the nested logit model if $G(\textbf{Y}) = \sum_{n\in {\mathcal{N}}} \left(\sum_{i\in C_n} (\sigma_{in}Y_i)^{\mu_n} \right)^{\mu/\mu_n}$, where ${\mathcal{N}}$ is the set of nests, $C_n$ is the set of items in nest $n$ and $\sigma_{in},\mu>0,\mu_n>0$ are the parameters of the nested logit model. In the generalized version of the nested logit model proposed by Daly2006general, called the network GEV, the corresponding CPGF can be computed recursively based on a rooted and cycle-free graph representing the correlation structure of the items.

Under a GEV model specified by a CPGF $G(\cdot)$, the deterministic version of the pricing problem is stated as

where $\textbf{Y}(\textbf{x},\textbf{a},\textbf{b}) \in \mathbb{R}^m$ with entries $Y_i(\textbf{x},\textbf{a},\textbf{b}) = \exp(a_i-b_ix_i)$. The expected revenue $R(\textbf{x})$ becomes more difficult to handle as the GEV model becomes more complicated. By leveraging the properties of GEV models stated in Remark (ref), zhang2018multiproduct manage to show that if the PSP are homogeneous, i.e., $b_i = b_j$ for all $i,j\in{\mathcal{V}}$ and if $\textbf{x}^*$ is an optimal solution to (ref), then

where $\gamma = G(Y_1(c_1),\ldots,Y_m(c_m))$ and $W(\cdot)$ is the Lambert-W function. The results in (ref) indeed imply that a constant markup solution is optimal to (ref) and this constant markup can be computed explicitly. Moreover, if the PSP are partition-wise homogeneous and $G$ is separable, then zhang2018multiproduct show that the optimal prices have a constant markup in each partition. These results also provide an explicit way to compute optimal prices for the pricing problem under the MNL with arbitrary PSP. zhang2018multiproduct also show that the expected revenue function is concave in the purchasing probabilities under any GEV model, making the pricing problem with expected sale constraints tractable.

Robust Pricing under Homogeneous Price Sensitivity Parameters

In this section, we study a robust version of the unconstrained pricing problem, under the setting that the choice parameters $(\textbf{a},\textbf{b})$ are not known exactly but belong to an uncertainty set. We focus here on the case of homogeneous PSP. In our robust model, we aim at maximizing the worst-case expected revenue over all parameters in the uncertainty set. The robust unconstrained pricing problem can be formulated as

where ${\mathcal{A}}$ is the uncertainty set of the parameters $(\textbf{a},\textbf{b})$. We denote $\Phi(\textbf{x},\textbf{a},\textbf{b}) = \sum_{i=1}^m (x_i-c_i) P_i(\textbf{Y}(\textbf{x},\textbf{a},\textbf{b})|G)$ for notational simplicity. We assume that ${\mathcal{A}}$ is convex and bounded. The convexity and boundedness assumptions are useful later in the section, as we need to show that, under a constant-markup style vector of prices, the objective function of the adversary's problem is convex on ${\mathcal{A}}$, which in turn helps identify a saddle point of the robust problem. The boundedness assumption is realistic in the context, as the choice parameters are often inferred from data and it is expected that they are finite. We also assume that the PSP are positive, i.e., ${\textbf{b}}>0$ for any $(\textbf{a},\textbf{b}) \in{\mathcal{A}}$, which is conventional from a behavior point of view.

When the PSP are the same over all the products, we will show that the robust optimal prices have a constant markup and this constant markup can be computed efficiently by binary search. The idea is motivated by the observation that if we consider the min-max counterpart of the robust problem $ \min_{(a,b)\in{\mathcal{A}}}\; \max_{\textbf{x}\in\mathbb{R}^{m} } \Big\{\Phi(\textbf{x},\textbf{a},\textbf{b})\Big\}, $ then we know that the adversary problem always yields a constant-markup optimal solution for any fixed choice parameters $(\textbf{a},\textbf{b})$ zhang2018multiproduct. So, the min-max counterpart is equivalent to

where $\textbf{X}$ is the set of constant-markup solutions, i.e., $\textbf{X} = \{\textbf{x}\in\mathbb{R}^m|\ x_i-c_i = x_j-c_j, \forall i,j\in[m]\}$. This suggests that if there is a saddle point of the max-min problem (ref), then it should have a constant-markup form.

To prove the result, we will consider the robust unconstrained pricing problem with constant-markup prices, i.e., we only look at prices $\textbf{x} \in \textbf{X}$. Then we show that there exist constant-markup prices $\textbf{x}^*$ such that if $(\textbf{a}^*,\textbf{b}^*)$ is an optimal solution to the adversary's problem under prices $\textbf{x}^*$, then $\textbf{x}^*$ is also optimal to the deterministic unconstrained problem with choice parameters $(\textbf{a}^*,\textbf{b}^*)$. In other words, $(\textbf{x}^*,\textbf{a}^*,\textbf{b}^*)$ is a saddle point of (ref) and $\textbf{x}^*$ is also an optimal solution to the robust problem.

Given constant-markup prices $\textbf{x}\in\textbf{X}$ and choice parameters $(\textbf{a}, \textbf{b})\in{\mathcal{A}}$, the expected revenue becomes \[

\] where $z = x_i-c_i$, $\forall i\in {\mathcal{V}}$ and $\textbf{Y}$ is a vector with entries $Y_i = \exp(a_i -b_i (z+c_i))$ for all $i\in {\mathcal{V}}$. For the sake of simplicity, from now on we will write $\textbf{Y}$ instead of $\textbf{Y}(\textbf{x},\textbf{a},\textbf{b})$. The expected revenue is a function of $z$ and $(\textbf{a},\textbf{b})$, and if $(\textbf{a}^*(z), \textbf{b}^*(z))$ is an optimal solution to the adversary's problem, then we also have

where $G(\textbf{Y}|z,\textbf{a},\textbf{b}) = G(Y_1,\ldots,Y_m)$ with $Y_i = e^{a_i-b_i(z+c_i)}$. In Proposition (ref) below, we first show that $G(\textbf{Y}|z,\textbf{a},\textbf{b})$ is strictly convex in $(\textbf{a},\textbf{b})$. As a result, $(\textbf{a}^*(z),\textbf{b}^*(z))$ is always uniquely determined. This result is important to identify a saddle point of the robust problem.

The proof is given in Appendix (ref). The proposition plays an important role in our main claim, as in the theorem below we will show that a solution to the robust problem can be found by solving a 1-dimensional fixed-point problem. The continuity of $(\textbf{a}^*(z),\textbf{b}^*(z))$ guarantees that this fixed-point problem always has a solution that can be found efficiently by bisection.

We highlight two important claims from Theorem (ref). First, the robustness preserves the constant-markup property of the solutions to the deterministic pricing problem, and second, the minimax equality holds. We note that the minimax equality is not straightforward to see at first sight, as the objective function $\Phi(\textbf{x},\textbf{a},\textbf{b})$ is not (quasi) concave in $\textbf{x}$ nor convex in $(\textbf{a},\textbf{b})$.

We will make use of Lemmas (ref) -(ref) below to prove the theorem. In Lemma (ref) we show that function $G(\textbf{Y}|z,\textbf{a}, \textbf{b})$ is always bounded. Together with the results established in Proposition (ref), it then becomes clear that there always exists a fixed point solution to (ref). As a result, if $z^*$ is a solution (ref), then it will form optimal constant-markup prices for the robust problem. Now, let us go into details of the lemmas and proofs.

The proof can be done quite easily using the properties of function $G(\cdot)$ and we refer the reader to Appendix (ref) for details. We are now ready to show that there is a solution to the fixed point problem (ref). In Lemma (ref) below we show this by making use of the continuity of $\textbf{a}^*(z),\textbf{b}^*(z)$ (showed above) and the boundedness assumption on ${\mathcal{A}}$ to identify an interval where we can find $z^*$. Without this assumption, one can simply choose 0 as a lower bound, as $f(0)$ is always less than 0. However, to identify an upper bound, one needs some limits from the uncertainty set. This is because even in the deterministic case, if the choice parameters $\textbf{b}$ approach zero, or $\textbf{a}$ increase to infinity, then the optimal constant markup will go to infinity (see Equation (ref)).

\proof{Proof:} Let $f(z) = z - ({1+W(\tau(z))}))/{\me{\textbf{b}^*(z)}}. $ From Lemma (ref), we have \[ \underline{Z}^0 \leq \frac{1+W(\tau(z))}{\me{\textbf{b}^*(z)}} \leq \overline{Z}^0,\ \forall z\in\mathbb{R}_+. \] Which means \[ f(\underline{Z}^0) \leq 0; \ f(\overline{Z}^0) \geq 0 \] Since $f(z)$ is continuous in $z$ (Proposition (ref)), equation $f(z) = 0$ always has a solution in the interval $\left[\underline{Z}^0,\overline{Z}^0 \right]$. \endproof We are now ready for the proof of Theorem (ref). Basically, we will show that a $z^*$ determined in Lemma (ref) and $(\textbf{a}^*(z^*),\textbf{b}^*(z^*)$ will form a saddle point to the robust problem.

\proof{Proof of Theorem (ref):} We know that there always exists $z^{*}$ being a fixed point solution to (ref) (Lemma (ref)). Given $\textbf{x}^{*}$ and $z^{*}$, we first remark that $(\textbf{a}^*(z^{*}), \textbf{b}^*(z^{*}))$ is also the unique solution of the adversary's problem \[ \underset{(\textbf{a},\textbf{b}) \in {\mathcal{A}}}{\text{argmin}}\qquad \Phi(\textbf{x}^{*},\textbf{a},\textbf{b}) \] Moreover, according to the way $\textbf{x}^{*}$ is computed and Theorem 3.1 of zhang2018multiproduct, $\textbf{x}^{*}$ is optimal to the following problem \[ \max_{\textbf{x}\in\mathbb{R}^m}\quad \left\{ \Phi(\textbf{x},\textbf{a}^*(z^{*}), \textbf{b}^*(z^{*}) ) \right\}. \] This leads to the fact that $(\textbf{x}^{*},\textbf{a}^*(z^{*}), \textbf{b}^*(z^{*}) )$ is a saddle point to the robust max-min problem (ref). In other words, $\textbf{x}^{*}$ is an optimal solution to the robust problem.

Note that the deterministic version of the unconstrained pricing problem always has a unique solution, which is a constant markup one. So, for any $\textbf{x} \neq \textbf{x}^{*}$ we have

Thus, there is only one solution to the robust pricing problem (ref) and there is only one solution to the equation (ref), as required. Since there is a saddle point to the max-min problem (ref), the minimax equality holds, i.e., $\min_{(\textbf{a},\textbf{b})\in{\mathcal{A}}} \max_{\textbf{x}\in\mathbb{R}^{m} } \Big\{\Phi(\textbf{x},\textbf{a},\textbf{b})\Big\} = \max_{\textbf{x}\in\mathbb{R}^{m} } \min_{(\textbf{a},\textbf{b})\in{\mathcal{A}}} \Big\{\Phi(\textbf{x},\textbf{a},\textbf{b})\Big\}$. \mtien{Note that the existence of a saddle point directly implies the minimax equality (a.k.a minimax equality), but the opposite does not always hold.} \endproof

Theorem (ref) implies that a solution to the robust problem can be found by solving the equation

in the interval $\left[\underline{Z}^0,\overline{Z}^0 \right]$, in which $\underline{Z}^0,\overline{Z}^0$ are defined in Lemma (ref). This is a one-dimensional problem which could be solved efficiently via bisection and convex optimization. That is, we use convex optimization to compute $f(x)$ for any given $z\in \left[\underline{Z}^0,\overline{Z}^0 \right]$ and use bisection to find $z^*$ such that $f(z^*) = 0$. In comparison with its deterministic counterpart, the robust problem requires an extra computing cost of $\delta {\mathcal{O}}(\ln(1/\epsilon))$ to obtain a constant markup that is in the $\epsilon$-neighbourhood of the optimal solution, where $\delta$ is the computation cost to solve the adversary problem.

{Robust Pricing under Partially Heterogeneous Price Sensitivity Parameters}

We relax the assumption that the PSP are homogeneous. Completely relaxing this assumption makes the pricing problem challenging, even for its deterministic version Gallego2014multiproduct. Thus, we assume that the products can be separated into partitions, and the PSP can be different over partitions. More specifically, we assume that the products can be partitioned into disjoint subsets and the products in each partition share the same PSP, and the CPGF is also partition-wise separable. This assumption has been used in previous work to derive tractable solutions to the deterministic pricing problems zhang2018multiproduct. More precisely, we partition the set of all products ${\mathcal{V}}$ into $N$ non-empty subsets ${\mathcal{V}}_1,\ldots,{\mathcal{V}}_N$ such that ${\mathcal{V}} = \bigcup_{n=1}^N {\mathcal{V}}_n$ and ${\mathcal{V}}_i \cap {\mathcal{V}}_j = \emptyset, \ \forall i\neq j, i,j\in[N]$. Moreover, we separate the vector $\textbf{Y}$ into sub-vectors $\textbf{Y}^1,\ldots,\textbf{Y}^N$ such that $\textbf{Y}^n = \{Y_i|\ i\in {\mathcal{V}}_n\}$ for all $n \in [N]$. We assume that the GEV-CPGF $G(\textbf{Y})$ can be separated into $N$ GEV-CPGFs as \[ G(\textbf{Y}) = \sum_{n=1}^N G^n(\textbf{Y}^n). \] Note that the nested logit model Ben1973structure, one of the most widely-used GEV models in the literature, also has this separating structure. For notational convenience, we also separate $(\textbf{a},\textbf{b}) \in \mathbb{R}_+^{2m}$ into sub-vectors $(\textbf{a}^1,\textbf{b}^1),\ldots, (\textbf{a}^N,\textbf{b}^N)$ such that $(\textbf{a}^n,\textbf{b}^n) = \{(a_i,b_i)|\ i\in {\mathcal{V}}_n\}$, $\forall n\in [N]$.

To deal with the robust problem, we further assume that the uncertainty set ${\mathcal{A}}$ is also partition-wise separable, i.e., ${\mathcal{A}} = \otimes_{n\in[N]} {\mathcal{A}}^n$, where $\otimes$ is the Cartesian operation, ${\mathcal{A}}^n\subset \mathbb{R}^{2|{\mathcal{V}}_n|}$ is the uncertainty set for the sub-vector $(\textbf{a}^n,\textbf{b}^n)$, and ${\mathcal{A}}^n$ are convex and bounded for all $n\in[N]$. In other words, we assume that the vector of choice parameters can vary independently across partitions. This assumption is a bit restrictive, but important to maintain the tractability of the robust problem. The reason is that if we use a general uncertainty set that allows for dependency between the choice parameters from different partitions, the adversary problem itself is generally not convex or quasi-convex in $(\textbf{a},\textbf{b})$, even under constant-markup prices, thus not tractable to solve. On the other hand, the assumption will allow us to handle each function $G^n(\textbf{Y}^n)$ independently, thus making it possible to convert the robust optimization problem into a convex one. In fact, one can construct a partition-wise separable uncertainty set by collecting some samples of choice parameter estimates from each partition. We will discuss this in more detail in Section (ref).

In this context, the difficulty lies in the fact that the optimal prices to the deterministic pricing problem do not have a single constant markup over all products. As a consequence, the robust optimal prices to (ref) would generally not have a single constant markup over all the products and the corresponding adversary's objective function would not be quasi-convex and solutions to the adversary's problem may not be unique. For this reason, we can not apply the techniques used in the previous section to identify a saddle point of the robust problem.

In the rest of the section, we will show that the robust problem can be converted equivalently into a convex optimization.

To start our exposition, we note that, in analogy to the analysis in the case of homogeneous PSP, we also see that the min-max counterpart always yields a partition-wise constant-markup solution zhang2018multiproduct. Thus, if there is a saddle point in the robust problem, then it should have a partition-wise constant-markup form. This motivates us to find such a saddle point of the max-min problem.

First, let us look at the robust problem where we only seek prices that have a constant markup in each partition, i.e., $\textbf{x}\in \textbf{X}^N$, where $\textbf{X}^N = \{\textbf{x}\in \mathbb{R}^m|\;x_i-c_i = x_j-c_j,\forall i,j\in{\mathcal{V}}_n, n\in[N]\}$. Let $z_n = x_i-c_i$ for all $i\in{\mathcal{V}}_n$ and $n\in[N]$. The robust problem becomes

or equivalently

where $G^n(\textbf{Y}^n|z,\textbf{a}^n,\textbf{b}^n) = G^n(Y_i,\ i\in{\mathcal{V}}_n)$ with $Y_i = e^{a_i-b_i(z_n+c_i)}$, for all $i\in {\mathcal{V}}_n$. For notational brevity, let $$\rho(\textbf{z},\textbf{a},\textbf{b}) = \frac{\sum_{n\in[N]} z_n G^n(\textbf{Y}^n|z_n,\textbf{a}^n,\textbf{b}^n)}{1 + \sum_{n\in[N]} G^n(\textbf{Y}^n|z_n,\textbf{a}^n,\textbf{b}^n)}.$$ Let us also denote \[ \underline{{\mathcal{G}}}^n(z_n) = \min_{(\textbf{a}^n,\textbf{b}^n) \in{\mathcal{A}}^n}\; \Big\{ G^n(\textbf{Y}^n| z_n,\textbf{a}^n,\textbf{b}^n)\Big\}. \] Since $G^n(\textbf{Y}^n| z_n,\textbf{a}^n,\textbf{b}^n)$ is strictly convex in $(\textbf{a}^n,\textbf{b}^n)$ (Proposition (ref)), we see that $\underline{{\mathcal{G}}}^n(z_n)$ is continuous and differentiable in $z_n$. Let $(\textbf{a}^{n*}(z_n), \textbf{b}^{n*}(z_n) = \text{argmin}_{(\textbf{a}^n,\textbf{b}^n) \in{\mathcal{A}}^n}\; \Big\{ G^n(\textbf{Y}^n| z_n,\textbf{a}^n,\textbf{b}^n)\Big\}$, which are always uniquely determined given any $z_n\in\mathbb{R}$ (Proposition (ref)). To handle the robust problem (ref), let us consider the following reduced optimization problem, which is obtained by forcing each component $G^n(\cdot)$ to its minimum value over ${\mathcal{A}}^n$.

In the rest of the section, we will focus on solving the robust problem (ref) by making use of Problems (ref) and (ref). More specifically, we will prove the following chain of results.

To make the technical results easier to follow, we separate the rest of the section into two subsections, where Section (ref) will focus on the reduced problem, and Section (ref) shows how to convert the original robust problem (ref) into the reduced one, which eventually leads to the result that (ref) and (ref) can be solved by convex optimization.

Convexity of the Reduced Problem

The reduced problem is indeed not convex if it is defined in terms of the prices $\textbf{x}$. Nevertheless, we can show that it becomes convex if we view it under purchase probabilities. More precisely, we will do some change of variables. Let use denote a vector $\textbf{p}^{G} \in \mathbb{R}^{N}$ with entries

then the objective function in (ref) can be written as ${\mathcal{W}}(\textbf{z}) = \sum_{n\in[N]} z_np^G_n$. This vector $\textbf{p}^G$ can be interpreted as an aggregated purchase probabilities for the partitions, i.e., $p^G_n = \sum_{i\in{\mathcal{V}}_n} p_i$, where $p_i$ is the purchase probability of item $i\in{\mathcal{V}}$. In Theorem (ref) below, we show that, given any $\textbf{p}^G \in {\mathcal{P}}^G= \{\textbf{p}^G\in \mathbb{R}^N_+|\ \sum_{n\in[N]} p^G_n <1 |\}$, there is a unique $\textbf{z}(\textbf{p}^G) \in \mathbb{R}^{N}$ satisfying (ref). Moreover, Problem (ref) can be formulated as a convex optimization program of variables $\textbf{p}^G$. Note that a similar result has been shown previously zhang2018multiproduct for the case that the choice parameters $(\textbf{a},\textbf{b})$ are fixed. In our setting, $(\textbf{a},\textbf{b})$ are a solution to convex optimization problems parameterized by $\textbf{z}(\textbf{p}^G)$, thus requiring a new and more complicated proof.

To prove the result, we first show that each function $\underline{{\mathcal{G}}}^n(z_n)$ is invertible. That is, for any $\alpha>0$ there is a unique $z_n\in \mathbb{R}_+$ such that $\underline{{\mathcal{G}}}^n(z_n) = \alpha$. This allows us to define the inverse function $(\underline{{\mathcal{G}}}^n)^{-1}$ such that $(\underline{{\mathcal{G}}}^n)^{-1}(\underline{{\mathcal{G}}}^n(z_n)) = z_n$. This inverse function can be computed by bisection. The existence of the inverse function is necessary for the claim that there is always a unique vector $\textbf{z}$ that yields a given purchase probability vector $\textbf{p}^G \in{\mathcal{P}}^G$ and this vector can be computed as \[ \textbf{z}(\textbf{p}^G)_n = (\underline{{\mathcal{G}}}^n)^{-1}\left(\frac{p^G_n}{1-\sum_{l\in[N]} p^G_l}\right). \] To show the convexity of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ in $\textbf{p}^G$, we first validate convexity of its deterministic counterpart, i.e., the version in which all the choice parameters are given $ \widetilde{{\mathcal{W}}}(\widetilde{\textbf{z}}(\textbf{p}^G|\textbf{a},\textbf{b})) = \sum_{n\in[N]} \widetilde{\textbf{z}}(\textbf{p}^G|\textbf{a},\textbf{b})_n p^G_n, $ where $\widetilde{\textbf{z}}(\textbf{p}^G|\textbf{a},\textbf{b}) \in \mathbb{R}^N$ are a vector of constant-markups that archive vector $\textbf{p}^G$ as

Once the convexity of $\widetilde{\textbf{z}}(\textbf{p}^G|\textbf{a},\textbf{b})$ is validated, we can further take the derivatives of $\textbf{z}(\textbf{p}^G)$ with respect to $\textbf{p}^G$ and show that they are equal to the derivative values of a deterministic function. This is the key result to show that the second-order derivative of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ is positive-definite, leading to the convexity of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$. We provide the detailed proof in Appendix (ref).

We further characterize a solution to (ref). In Proposition (ref) below we show that (ref) always has a unique local optimal $\textbf{z}^*$ (i.e., ${\mathcal{W}}(\textbf{z})$ is unimodal), and this solution will satisfy a fixed point system that is an extended version of the one shown in Theorem (ref). Note that the uniqueness of a local optimal solution of (ref) defined in terms of $\textbf{p}^G$ is straightforward due to the concavity of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$. It is however not trivial when the objective function is defined in terms of $\textbf{z}$.

Proposition (ref) implies that solving the fixed-point problem (ref) will yield a solution to (ref). However, directly solving (ref) would be not tractable. Instead, Theorem (ref) show that it can be solved conveniently by convex optimization. The fixed-point system in Proposition (ref) is however important to establish the saddle point result in the next section (Proposition (ref)).

Solving the Robust Problem

We know from the previous section that the reduced problem is tractable to solve. We now move to the second part showing that the original robust optimization problem can be converted into the reduced problem, for which a solution can be found by convex optimization. We first state the following result connecting the reduced problem and (ref).

The general idea to prove the theorem is to show that, under the optimal price solution, the adversary will force each component $G^n(\textbf{Y}^n|z_n,\textbf{a}^n,\textbf{b}^n)$ of the objective function to its minimum values. We refer the reader to Appendix (ref) for a detailed proof.

We now come back to the original robust problem (ref) with partition-wise homogeneous PSP. We will gather all the results established above to show how we can get an optimal solution of (ref) by convex optimization. Before stating the main theorem, let us introduce the following result saying that a solution obtained by solving the reduced problem (ref) forms a saddle point to (ref), thus the minimax equality holds.

\proof{Proof:} It is clear from Theorem (ref) that if $\textbf{z}^*$ to a solution to (ref), then $(\textbf{a}^*(\textbf{z}^*),\textbf{b}^*(\textbf{z}^*))$ is a solution to the corresponding adversary's problem. Moreover, from Proposition (ref) and Theorem C1 of zhang2018multiproduct, we also see that $\textbf{z}^*$ is a solution to the pricing problem under fixed parameters $(\textbf{a}^*(\textbf{z}^*),\textbf{b}^*(\textbf{z}^*))$, i.e., $\max_{\textbf{z} \in\mathbb{R}^N} \rho(\textbf{z},\textbf{a}^*(\textbf{z}^*),\textbf{b}^*(\textbf{z}^*)) $. Thus, $(\textbf{z}^*,\textbf{a}^*(\textbf{z}^*),\textbf{b}^*(\textbf{z}^*))$ is clearly a saddle point of (ref). The minimax equality follows directly from the existence of a saddle point. \endproof

We now gather all the previous results to establish our main theorem. Theorem (ref) below states that a solution to the robust problem (ref) will have a constant-markup style and this constant-markup vector can be found be convex optimization. The proof can be done easily given all the claims we have in Section (ref) and Theorem (ref) above.

\proof{Proof:} We first prove the minimax equality property by the chain

where $(a)$ is from the well-known max-min inequality, $(b)$ is from the property that any deterministic pricing problem (with fixed $(\textbf{a}, \textbf{b})$) always yields a partition-wise constant-markup solution, $(c)$ is due to the minimax equality of (ref) shown in Proposition (ref) above. This chain of (in)equalities leads to the minimax equality property of (ref) and the result that $\textbf{x}^*$ defined by a constant-markup solution $\textbf{z}^*$ of (ref) is a robust solution to (ref) and $(\textbf{x}^*,\textbf{a}^*(\textbf{z}^*),\textbf{b}^*(\textbf{z}^*))$ forms a saddle point of the max-min problem (ref). \endproof

We now discuss in detail how to solve the reduced problem (ref). Since the problem is convex when the objective function is defined in terms of the purchase probability $\textbf{p}^G$, we show how to compute ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ and its gradients, which are crucial for the optimization process. Given a purchase probability $\textbf{p}^G\in{\mathcal{P}}^G$, from Lemma (ref), we can compute ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ as \[ {\mathcal{W}}(\textbf{z}(\textbf{p}^G)) = \sum_{n \in[N]} z(\textbf{p}^G)_n p^G_n = \sum_{n\in[N]} (\underline{{\mathcal{G}}}^n)^{-1}\left(\frac{p^G_n}{1-\sum_{l\in[N]} p^G_l}\right) p^G_n \] where the inverse function $\underline{{\mathcal{G}}}^n)^{-1}(\cdot)$ can be computed efficiently by bisection. The gradients of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ are more difficult to get and we show how to do it in Proposition (ref) below.

The proof (details in Appendix (ref)) can be done by directly taking the derivatives of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ with respect to $\textbf{p}^G$ and using (ref). The computation of ${\mathcal{W}}(\textbf{z}(\textbf{p}^G))$ for a given $\textbf{p}^G\in{\mathcal{P}}^G$ can be done by performing the following steps: (i) compute $\textbf{z}(\textbf{p}^G)$ using Lemma (ref), (ii) compute $(\textbf{a}^*(\textbf{z}),\textbf{a}^*(\textbf{z}))$ as (unique) optimal solutions of the problems $ \min_{(\textbf{a}^n,\textbf{b}^n) \in{\mathcal{A}}^n}\; \Big\{ G^n(\textbf{Y}^n| z_n,\textbf{a}^n,\textbf{b}^n)\Big\}$, $n\in [N]$, (iii) compute ${\mathcal{W}}(\textbf{z}(\textbf{p}^G)) = \textbf{z}(\textbf{p}^G)^\text{\tiny T} \textbf{p}^G$ and its gradients by (ref). Since the objective function is strictly concave, we know that the optimization problem can be solved efficiently by a convex optimization solver. When the uncertainty set is rectangular, the reduced optimization problem can be further simplified, as a solution to $ \min_{(\textbf{a}^n,\textbf{b}^n) \in{\mathcal{A}}^n}\; \Big\{ G^n(\textbf{Y}^n| z_n,\textbf{a}^n,\textbf{b}^n)\Big\}$ can be identified, thus the reduced problem can be transformed equivalently to a deterministic pricing problem with fixed choice parameters and it is known that such a deterministic pricing problem yields closed form solutions zhang2018multiproduct. We state this result in the following corollary.

The result is easy to validate, as from Lemma (ref) we see that $(\underline{\textbf{a}}^n,\overline{\textbf{b}}^n) = \text{argmin}_{(\textbf{a},\textbf{b})\in{\mathcal{A}}} G^n(\textbf{Y}^n|z_n, \textbf{a}^n,\textbf{b}^n)$ for any $z_n\in\mathbb{R}$.

Numerical experiments

We provide experimental results to show how the robust model considered above (i.e., robust unconstrained pricing with homogeneous and partition-wise homogeneous PSP) protect us from choice parameter uncertainties. We first discuss our approach to construct uncertainty sets and different baseline approaches for the sake of comparison.

Constructing Uncertainty Sets

Inspired by Rusmevichientong2012robust in the context of robust assortment optimization, such an uncertainty set can be created for the situation that the market is heterogeneous, i.e., the market has several costumer types and the choice parameters would vary across them, but the proportion of each customer type is not known with certainty. To be more precise, let assume that the true parameters for the underlying GEV choice model can be one of $K$ vectors $\{(\textbf{a}^{(1)}, \textbf{b}^{(1)}),\ldots, (\textbf{a}^{(K)}, \textbf{b}^{(K)})\}$, representing $K$ types of customers. For ease of notation, let $\textbf{w}^k = (\textbf{a}^{(k)}, \textbf{b}^{(k)})$ for all $k\in [K]$. Let $\tau_1,\ldots,\tau_K \in [0,1]$ be the proportion of each customer type with $\sum_{k\in [K]}\tau_k = 1$.

We are interested in the situation that the proportions can be estimated somehow using historical data, but estimation may have errors and the proportion estimates may not make good representation to the “true” ones. In this situation, an uncertainty set can be constructed around the proportion estimates as

In the partially homogeneous case, as our results require partition-wise separable uncertainty sets, such an uncertainty set can be constructed in a similar way as follows. For each customer type $k$, let $\textbf{w}^{k,n}$ be the vector of choice parameters of partition $n\in[N]$. The uncertainty set for each partition can be defined as

Here $\epsilon\in[0,1]$ reflects an “uncertainty level” of the uncertainty set. Larger $\epsilon$ values provide larger uncertainty sets, corresponding to more conservative models that may help protect well against worst-case scenarios, but may lead to low average performance. On the other hand, smaller $\epsilon$ values provide smaller uncertainty sets and would lead to less conservative robust solutions, which may perform well in terms of average performance but would be worse in protecting bad scenarios of the choice parameters. Adjusting $\epsilon$ would help the firm balance the worst-case protection and average performance. Clearly, $\epsilon = 0$ corresponds to the deterministic case, i.e., the proportion of each customer type are given with certainty, and $\epsilon = 1$ reflects the situation that we are totally uncertain about how likely the proportion of each customer type is, and have to ignore the predefined proportions $\{\tau_1,\ldots,\tau_K\}$.

Baseline Approaches

We discuss tractable baseline approaches that would be used to solve the pricing problem when facing the issue of choice parameter uncertainty. A straightforward approach would be to employ the mean values of the choice parameters and solve the deterministic version. In this context, we know that the pricing problem is computationally tractable. Alternatively, one may look at different possibilities of the choice parameters and define a mixed formulation where the market is divided into a finite number of market segments and each segment is governed by a scenario of the choice parameters. However, one can show that the expected revenue in this context is no longer unimodal and the constant-markup property identified for the GEV pricing problem no-longer holds, {even if there are only two market segments} Li2019productMMNL. As a result, this mixed version is not computationally tractable.

Another baseline approach is to sample some choice parameters from the uncertainty set and use simulation to select a solution that provides best protection from worst-case scenarios. More precisely, let assume that the firm needs to make a pricing decision while being aware that the choice parameters may vary in an uncertainty set. In this context, the firm can sample some points from the uncertainty set and compute the corresponding optimal prices for each selection, using the deterministic approach. Then, for each price vector, the firm can sample a sufficiently large number of vector of choice parameters from the uncertainty set, in order to evaluate how each price vector obtained performs when the choice parameters vary in the uncertainty set. This can be done by simply selecting the solution that gives the best worst-case profit among the samples. This approach may be computationally tractable with a reasonable number of samples, but would be much more computationally expensive than the robust and deterministic approaches. We refer to this as the sampling-based approach. One can show that solutions given by this approach will converge to those from the robust counterpart when the sample sizes grow to infinity.

In these experiments, we will compare our robust models (denoted as RO), which are computationally tractable, against the sampling-based approach (denoted as SA) and the deterministic one with mean-value choice parameters (denoted as DET). We will employ two popular GEV models in the literature, i.e., the MNL and nested logit models. {For the SA approach, we sample points uniformly from the uncertainty set since we do not make any assumption about the distribution of the choice parameters. One can argue that the uniform distribution may not be the best choice in the case that the firm believes that it has some ideas (perhaps via estimation) about the distribution of the choice parameters. Nevertheless, estimating such a distribution is not easy in practice. A common approach in choice modeling is to assume that the parameters follow some distributions (e.g. normal distribution) with unknown coefficients and try to estimate these coefficients by maximum likelihood estimation Mcfadden2000mixed. This approach, even though popular, does not guarantee that the distribution obtained is the true distribution of the choice parameters, assuming that there exists a true distribution. As such, the distribution of the choice parameters is typically only known ambiguously. Distributionally robust optimization is a robust approach that is explicitly designed to handle this ambiguity Shapiro2018tutorialDRO, which we keep for future research.}

Experimental Settings

We choose $m = 50$, and $K = 5$ (i.e., there are 5 customer types) and randomly choose the proportions and the underlying choice parameter vectors $\{\textbf{w}^1,\ldots,\textbf{w}^5\}$. For each $\epsilon>0$ we define the uncertainty set as in (ref). The comparison is done as follows. For each $\epsilon$, we solve the corresponding robust problem and obtain a robust solution $\textbf{x}^{\textsc{RO}}$. For the DET, we solve the deterministic model with the weighted average parameters $\widetilde{\textbf{w}} = \sum_{k\in [K]} \tau_k \textbf{w}^k$ and obtain an optimal solution $\textbf{x}^\textsc{DET}$. For the SA approach, we sample randomly and uniformly $s_1$ points from the uncertainty set, and for each point compute the corresponding optimal prices, which have a constant markup over products. For each pricing solution, we again sample randomly and uniformly $1000$ choice parameters from ${\mathcal{A}}$, and compute and pick a pricing solution with the largest worst-case expected revenue among the 1000 samples. We test this approach with $s_1 = 10$ and $s_1 = 50$ and denote the corresponding solutions as $\textbf{x}^{\textsc{SA10}}$, $\textbf{x}^{\textsc{SA50}}$, respectively. Larger $s_1$ can be chosen, but it would mean that the SA becomes way more expensive as compared to the RO and DET approaches. For example, if we choose $s_1 = 100$, the SA requires to solve 100 deterministic problems and compute $10^5$ expected revenues to obtain a pricing solution.

Comparison Results

We provide experimental results for the robust model under the nested logit model. The CPGF of the nested logit model is given as $ G(\textbf{Y}) = \sum_{n\in [N]} \left(\sum_{i\in C_n} Y_i^{\mu_n} \right)^{\mu/\mu_n}, $ where $[N]$ is the set of nests and for each $n\in [N]$, $C_n$ is the corresponding subset of the items, $\mu$ and $\mu_n$, $n\in{\mathcal{N}}$ are the positive parameters of the nested logit model. In this experiment, we separate the whole item set into 5 nests of the same size (10 items per each nest), i.e. $N = 5$ and $| C_n| =10$ for all $n\in [N]$. To evaluate the performance of the three approaches when the choice parameters vary, given the uncertainty set defined above, we randomly and uniformly sample 1000 parameters $(\textbf{a}, \textbf{b})$ from the set ${\mathcal{A}}$, and compute the expected revenues given by $\textbf{x}^\textsc{RO}$, $\textbf{x}^\textsc{SA10}$, $\textbf{x}^\textsc{SA50}$, and $\textbf{x}^\textsc{DET}$. So, for each solution, we get a distribution of expected revenues over 1000 samples. We then draw the histograms of of the distributions to compare. We first provide experiments for the case of homogeneous PSP and then move to the case of partition-wise homogeneous PSP.

Homogeneous PSP.

The histograms of the distributions obtained in Figure (ref) for $\epsilon \in \{0.02,0.04, 0.06\}$. We see that the distributions given by the RO approach always have higher peaks, lower variances and shorter tails, as compared to the other approaches. The difference becomes clearer with larger $\epsilon$ This demonstrates the capability of the RO approach in giving not-too-low revenues. In addition, the sampling-based approach (SA10 and SA50) perform better then the DET in terms of protecting us against too low revenues. In this aspect, the SA50 also performs better than the SA10, especially when $\epsilon$ increases.

In Table (ref), we provide more details about the average and worst-case values of the distributions given by the three approach. In particular, we compute the “percentile ranks” of the RO worst-case revenues, which indicates the percentages that the expected revenues given by the baseline approaches (DET, SA10 and SA50) are lower than the corresponding worst-case expected revenues given by the RO. For example, for $\epsilon = 0.1$, there are $23\%$ of the revenues given by the DET (over 1000 sampled revenues) are less than the corresponding RO worst-case revenue. Over $\epsilon \in\{0.02,\ldots,0.4\}$, the average percentile ranks of the RO worst-case revenues are 26.7%, 9.5% and 5.3% for the DET, SA10 and SA50 approaches, respectively, which clearly indicates gains from the use of the RO approach. It can be seen that in terms of average revenue, the DET approach performs the best, followed by the the SA10, SA50 and RO approaches. In general, the baseline approaches (DET, SA10, SA50) always give higher average revenues, but lower worst-case revenues, which clearly indicates that the RO approach does a better job in protecting us from worst-case situations, but also show the trade-off of being robust. Moreover, the results in Table (ref) also tell us that if the firm cares more about the worst cases, a large $\epsilon$ can be chosen to have better protection against too low expected revenues. On the other hand, if average performance is of concern, then by choosing a small $\epsilon$, one can still get a protection from the robust solutions, but also get an average performance that is comparable to that of the solutions by the deterministic approach. This observation is also consistent with those from other robust work in the revenue management literature Li2019robustCVaR,Rusmevichientong2012robust.

Partition-wise Homogeneous PSP.

We provide comparison results for the case of partition-wise homogeneous PSP considered in Section (ref). We use the same nested logit model with partition-wise decomposable CPGF specified above, i.e., $ G(\textbf{Y}) = \sum_{n\in [N]} \left(\sum_{i\in C_n} Y_i^{\mu_n} \right)^{\mu/\mu_n} $, but the PSP are the same in each nest but different across nests. In this context, we know that the robust problem can be converted equivalently into a convex optimization problem. On the other hand, for the SA approach, if we select $s_1$ vectors of choice parameters from the uncertainty set, we need to solve $s_1$ convex optimization problems.

We select $N = 5$ partitions of the same size. For each uncertainty level $\epsilon>0$ and for each partition (or nest) $n\in [N]$, we define a polyhedron uncertainty set as in Section (ref) above. Similarly to the previous section, we first solve the deterministic problem by bisection with the weighted average parameters $\widetilde{\textbf{w}} = \sum_{k\in [K]} \tau_k \textbf{w}^k$ to obtain a solution $\textbf{x}^{\textsc{DET}}$. Then, for each set ${\mathcal{A}}^\epsilon$ we solve the RO problem by convex optimization to obtain a robust solution $\textbf{x}^\textsc{RO}$. We also sample $s_1=10$ and $s_1 = 50$ points from the uncertainty set for the SA approach.

To evaluate the performance of the solutions obtained, we also sample 1000 points randomly and uniformly from ${\mathcal{A}}^n$, $n\in[N],$ and compute the expected revenues given by $\textbf{x}^\textsc{RO}$, $\textbf{x}^\textsc{SA10}$, $\textbf{x}^\textsc{SA50}$, and $\textbf{x}^\textsc{DET}$. The distributions of the expected revenue over 1000 samples with $\epsilon \in\{0.02,0.04,0.06\}$ are plotted in Figure (ref). There is nothing surprising, as similarly to the previous experiments, distributions given by $\textbf{x}^\textsc{RO}$ have small variances, higher peaks, shorter tails and higher worst-case revenues, as compared to those from $\textbf{x}^\textsc{SA10}$, $\textbf{x}^\textsc{SA50}$ and $\textbf{x}^\textsc{DET}$. In Table (ref),we report in detail the average, maximum and worst-case revenues when $\epsilon$ increases from 0.02 to 0.4. We also see that the RO approach always gives higher worst-case revenues but lower average revenues, and the SA approaches also provide some protections against low revenues. However, in this case, the percentile ranks for the DET and SA approaches are significantly lower (3.45 on average). In particular, we see that there are some instances where the percentile ranks are only 3-th, which means that only 3% of the revenues are lower than the corresponding RO worst-case revenues. Nevertheless , the average revenues given by the SA50 are remarkably higher than those from the RO, especially when $\epsilon$ is large. From this view point, the RO seems too conservative.

In summary, our experiments show {gains} from our robust models in protecting us from revenues that would be too low. The histograms given by the robust models have higher peaks, smaller variances, higher worst-case revenues, but lower averages, as compared to their deterministic and sampling-based counterparts. This observation also shows the trade-off in being robust in making pricing decisions when the choice parameters are uncertain, and also consistent with observations from other relevant studies in the revenue management literature Rusmevichientong2012robust,Li2019robustCVaR.

Conclusion

In this paper, we have considered robust versions of the pricing problem under GEV choice models, in which the choice parameters are not given in advance but lie in an uncertainty set. These robust models are motivated by the fact that uncertainties may occur in the estimation procedure of the choice parameters. We have shown that when the problem is unconstrained and the PSP are the same over all the products, the robust optimal prices have a constant markup with respect to the product costs and we have shown how to efficiently compute this constant markup by bisection. When the PSP are partition-wise homogeneous and the CPGF and the uncertainty set are also partition-wise separable, we have shown that the robust problem can be converted equivalently into a reduced optimization program, and the reduce problem can be solved conveniently by convex optimization.

We have also considered the pricing problem with over-expected-revenue-penalties as an alternative to the constrained pricing problem. We have shown that under the same assumptions as in the case of partition-wise homogeneous PSP , the robust problem can be converted equivalently into a reduced one, which can be further solved by convex optimization. Experimental results based on the nested logit model have shown the {advantages} of our robust model in providing protection against bad-case revenues. In future research, it would be interesting to look at distributionally robust versions of the pricing problem, which may help provide less conservative robust solutions as compared to the standard robust optimization approaches. We are also interested in robust approaches for the joint assortment and pricing problem under GEV choice models.

\ACKNOWLEDGMENT{This research is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) program, Singapore-MIT Alliance for Research and Technology (SMART) Future Urban Mobility (FM) IRG.}