Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
132,691 characters · 16 sections · 115 citation commands
On the estimation of discrete choice models to capture irrational customer behaviors
\RUNAUTHOR{Jena et al.}
\RUNTITLE{ On the estimation of discrete choice models to capture irrational customer behaviors}
\TITLE{ On the estimation of discrete choice models to capture irrational customer behaviors }
\ARTICLEAUTHORS{
\AUTHOR{Sanjay Dominik Jena} \AFF{\'Ecole des Sciences de la Gestion, Universit\'e du Qu\'ebec \`a Montr\'eal,\\ Centre interuniversitaire de recherche sur les r\'eseaux d'entreprise, la logistique et le transport (CIRRELT) \EMAIL{[email removed]}}
\AUTHOR{Andrea Lodi} \AFF{Canada Excellence Research Chair in Data-Science for Real-time Decision-Making,\\Polytechnique Montr\'eal,\\ \EMAIL{[email removed]}}
\AUTHOR{Claudio Sole} \AFF{Canada Excellence Research Chair in Data-Science for Real-time Decision-Making, \\Polytechnique Montr\'eal,\\ \EMAIL{[email removed]}}
}
\ABSTRACT{ {\color{black} The Random Utility Maximization model is by far the most adopted framework to estimate consumer choice behavior. However, behavioral economics has provided strong empirical evidence of irrational choice behavior, such as halo effects, that are incompatible with this framework. Models belonging to the Random Utility Maximization family may therefore not accurately capture such irrational behavior.} Hence, more general choice models, overcoming such limitations, have been proposed. \textcolor{black}{However, the flexibility of such models comes at the price of increased risk of overfitting. As such, estimating such models remains a challenge.} In this work, we propose an estimation method for the recently proposed Generalized Stochastic Preference choice model, which subsumes the family of Random Utility Maximization models and is capable of capturing halo effects. Specifically, we show how to use partially-ranked preferences to efficiently model rational and irrational customer types from transaction data. Our estimation procedure is based on column generation, where relevant customer types are efficiently extracted by expanding a tree-like data structure containing the customer behaviors. {\color{black} Further, we propose a new dominance rule among customer types whose effect is to prioritize low orders of interactions among products.} An extensive set of experiments assesses the predictive accuracy of the proposed approach. {\color{black} Our results show that accounting for irrational preferences can boost predictive accuracy by 12.5% on average, when tested on a real-world dataset from a large chain of grocery and drug stores.}
}
\KEYWORDS{Choice Modeling, Halo effects, Substitution effects, Rank-based model}
{\color{black} Accurately forecasting the demand of certain products or services is of crucial importance in the context of supply-chain optimization and retail operations.} Most often, a predictive model must be learned from historical data representing the choice behavior of an agent faced with a discrete set of alternatives, called the offer set. A common assumption when dealing with demand estimation is to consider product demands as independent from each other, resulting in the independent demand model strauss2018review, Talluri2004a. However, it is well known that this assumption does not hold in many real-life scenarios and that product demands interact through substitution and halo effects. In general, we consider alternative $x$ a substitute of alternative $y$ if the presence of $x$ in the offer set decreases the probability of $y$ being chosen. On the contrary, we refer to an halo effect if the presence of $x$ in the offer set increases the attractiveness of $y$, and thus its likelihood of being chosen.
Discrete choice models have been widely adopted to model substitution. Among them, the family of choice models that received the most attention in the literature is undoubtedly the one of Random Utility Maximization (RUM) models thurstone1927RUM, block1959random, Luce1959. Choice models belonging to the RUM family assume that a random utility is assigned to every alternative. Utilities are modeled as random variables, and different choices about their distribution lead to different choice models. When faced with an offer set, the decision maker samples a vector of utilities and picks the option with the highest one, so as to maximize her expected payoff.
{\color{black} The standard theory of rational choice assumes the relative preference between two alternatives does not depend on the other products in the offer set. Hence, if alternative $x$ is preferred to alternative $y$ in a given offer set $S$, the same should hold for any other offer set $S' \neq S$. Starting from this assumption, known as Independence of Irrelevant Alternatives (IIA), Luce1959 derived the Multinomial Logit (MNL) model, which is arguably the most famous RUM choice model.} Its popularity stems from the facts that it can be efficiently estimated, it is interpretable and, when used for decision making, it allows to benefit from appealing theoretical and computational properties. The Multinomial Logit model lacks, however, flexibility{\color{black} , imposing specific patterns of substitutions among alternatives. In particular, the logit formula implies that the ratio between the choice probabilities of two alternatives does not depend on the other (irrelevant) alternatives in the offer set. In response, many models have been proposed to overcome such limitations, so as to capture more complex patterns of substitutions. In the Nested Logit model, for example, this is achieved by assuming IIA holds only among groups of similar alternatives. In the Mixed Multinomial logit (MMNL) and Rank-Based farias13 choice models, instead, violations of the IIA assumption are captured by aggregating several IIA-consistent classes of customers. Notably, some of these models, such as the MMNL, the Rank-Based and the Markov Chain Blanchet2016 choice models, can theoretically approximate any RUM choice model and therefore capture arbitrarily complex substitution effects. We refer the interested reader to the computational study of comparativeBerbeglia for a deeper overview on RUM choice models and their generalization performances.}
All models that belong to the RUM family obey the so-called Regularity assumption, which states that the introduction of an option in the offer set cannot increase the probability of another alternative being chosen. Hence, they cannot capture halo effects. Nevertheless, many studies in the literature of behavioral economics corroborated the reproducibility and robustness of this type of choice behaviors attreffect1_simonson1989choice, attreffect2_huber1982adding, incompatible with the theory of utility maximization and therefore referred to as irrational. {\color{black} In the remainder of this paper, we therefore refer to rational behavior as one that can be captured by RUM models, and to irrational behavior as one that cannot. In order to better illustrate the kind of choice scenario in which violations of the Regularity assumption may arise, we report below the results of a choice experiment from the seminal work of simonson1992choice_exp.}
{\color{black} The choice phenomena reported in Table (ref) is an example of the so-called compromise effect, where middle (i.e., compromise) options in terms of price and quality are preferred to extreme ones.} {\color{black} One may be tempted to handcraft an utility function based on price and quality features in order to explain the observed choice outcomes. However, this cannot be done without considering the assortment-dependent effects on the attractiveness of products, which is inconsistent with the theory of rational choice.}
{\color{black} Violations of the regularity assumption may be induced by other cognitive biases as well. For example, in the context of grocery shopping, when two complementary products (e.g., pasta and tomato sauce) are present in the assortment, the perceived attractiveness of both is likely to increase. One may also observe asymmetric, or decoy effects decoy_puto when the addition of an option (the decoy) to the offer set increases the choice probability of another alternative perceived as better. This choice phenomena was popularized a choice experiment reported in ariely2008predictably, in which a group of students was asked to choose among three possible subscription plans to “The Economist” magazine. For the sake of brevity, we report this experiment in Appendix (ref), where we also show how the GSP model (see Section (ref)) can explain the related choice outcomes. We refer the interested reader to gsp-berbeglia2018 for more examples on the topic. }
Such observations motivated a recent interest in more general choice models, capable of overcoming the limitations of the RUM framework. Unfortunately, many of these choice models lack efficient estimation schemes, and their performance on non-RUM instances has not been well understood yet LoR-jagabathula. Also, the minimal assumptions these models make about the distribution of choice probabilities may increase the risk of capturing spurious patterns from data, i.e., overfit.\footnote{\textcolor{black}{Mostly a concern in Statistics and Machine Learning, overfitting refers to the situation when a model is too tailored to a specific data set (typically, the training data), and as such fails to generalize well to other data sets (e.g., the test data). Overfitting typically occurs either when the model is too general, or when the training data is not sufficiently representative for the ground truth. As a consequence, an overfit model may not yield accurate predictions on other data sets.}} {\color{black} This may be observed in the form of a model experiencing high variance in predictive accuracy when estimated on little amount of training data.} Finding the delicate balance between flexibility and predictive accuracy is therefore of crucial importance for the practical utility of such models. The Generalized Stochastic Preference (GSP) choice model, an extension of rank-based choice models introduced by gsp-berbeglia2018 to capture halo effects, is one of the recently proposed models that fits into this stream of literature. Despite being theoretically attractive, the estimation of the GSP choice model poses significant challenges both from the computational and predictive points of view. The authors suggest that estimation procedures originally developed for rational rank-based choice models farias13, Vulcano-marketDiscovery, bertsimas16-local_search may be adapted to their irrational choice model. Nevertheless, no empirical study has been reported in order to assess the estimation efficiency and predictive accuracy of the GSP choice model.
{\color{black} Next to computational challenges to estimate such model, its flexibility also comes at the price of an increased risk of overfitting.} {\color{black} Even in the case of rational behaviors, it is known comparativeBerbeglia,jena2020partially that the estimation of general RUM models on little amounts of transactions data tends to be prone to overfitting. In the same line, on real-world data, HaloMNL came to a similar conclusion. When estimated on small amounts of training data, their model, extending the MNL model to allow for pairwise interactions among products, did not outperform a simpler MNL. Hence, particular care should be taken to such issue for effectively estimating the GSP choice model, which can account for even higher orders of interactions among products.}
\paragraph{Contributions.}
In this work, we propose an estimation method for the GSP choice model. Specifically, we show how to use partially-ranked preferences to model irrational customer behaviors, and how to efficiently estimate them from choice data by adapting the column generation approach proposed by jena2020partially. Partially-ranked preferences allow us to circumvent several difficulties regarding the adaption of estimation methods for strictly ranked preferences. In particular, our objective is to train the choice model so as to maximize its predictive accuracy. This is different from farias13, who focus on worst-case revenue prediction for a given assortment of items. Also, our estimation method can easily handle both rational and irrational customer behaviors. In contrast, it is not clear how the Mixed Integer Programming (MIP) formulation of the Market Discovery subproblem from Vulcano-marketDiscovery should be adapted to allow for the discovery of irrational preferences. \textcolor{black}{Finally, the Growing Preference Tree (GPT) algorithm of jena2020partially provides a strong computational advantage in terms of scalability, especially important when dealing with irrational customer behaviors (discussed in the following) and generalizes well to unseen offer sets when tested on RUM instances.} The application of partially-ranked preferences for tackling the estimation of generalized stochastic preferences thus looks promising. An appealing property of our approach stems from the fact that the irrationality, and thus the flexibility of the choice model is increased in an adaptive, data-driven way. By increasing the set of possible customer behaviors only when required to better explain the given data, we may limit the risk of overfitting and speed up the estimation procedure. {\color{black} To further reduce the risk of capturing spurious, high order interactions among products, we propose a new dominance rule among entering columns, prioritizing customer types with a small number of strictly ranked products and large indifference sets.}
We run an extensive set of experiments to assess the predictive performance of the proposed choice model. Using the methodology delineated by LoR-jagabathula, we characterize the rationality loss of both generated and real instances. This allows us to observe that irrational customer types can significantly improve predictive accuracy on instances presenting halo effects among alternatives. {\color{black} We further show that our new criteria for discovering customer types can provide a further boost in predictive accuracy. Notably, our algorithm outperforms, on average, two baselines from the literature on irrational choice modeling, the Halo-MNL HaloMNL and the Pairwise Choice Markov Chain (PCMC) PCMC, when tested on real-world data. }
\paragraph{Organization of the paper.} In Section (ref), we review the literature on irrational choice models. In Section (ref), we introduce the GSP choice model from gsp-berbeglia2018 and our corresponding partially-ranked representation. We show how to estimate the proposed choice model in Section (ref). The numerical results of our experiments on both synthetic and real instances are reported in Section (ref). Finally, concluding remarks are reported in Section (ref).
{\color{black} Our work spans several areas of research. In the following, we first review the literature from Psychology and Marketing, where several descriptive models, with little applicability from the predictive point of view, have been proposed to overcome the limitations of the RUM framework. We then survey the works from the Machine Learning and Operation Management communities, where discrete choice models of various levels of generality have been proposed.}
\paragraph{Descriptive theories of choice. } In order to define the notion of a rational agent, most economists rely on a set of consistency principles of rationality, which includes, among others, the aforementioned Regularity assumption and the more famous axiom of Independence of Irrelavant alternatives (IIA). This set of assumptions aims at describing how a rational agent is supposed to make her decisions across different offer sets. However, a vast body of literature has provided strong empirical evidence of choice behaviors incompatible with the theory of rational choice (we refer to Rieskamp2006 for an excellent overview on the topic). The RUM framework is flexible enough to explain most of these choice behaviors, but cannot account for violations of the Regularity assumption. To overcome such limitation, more general theories of choices have been developed in psychology, such as Decision Field theory Busemeyer1993, Roe2001 and the Leaky competing accumulator model Usher2004a. These models belong to the broader class of Sequential Sampling models, which mimic the evolution of the decision-making process over time, and can account for violations of the rationality principles, including the Regularity one. They lack, however, practical estimation algorithms, and are usually adopted from a descriptive point of view more than a predictive one. Other works, such as Tversky1993 and Rooderkerk2011, embed alternatives into an attribute space, where context-dependent features are computed in order to determine the utility of each of the alternatives. These approaches have usually been applied to small, controlled experiments, and rely on the existence of two metric features, along which customer preferences are supposed to monotonically increase or decrease. This is a key difference with respect to our approach, where no item feature is supposed to be given.
\paragraph{Discrete choice models escaping RUM. } Decomposing the utility into two components, item-specific and context-dependent, is also the starting point of HaloMNL and CDM, who propose a second-order extension of the MNL model in order to capture pairwise product interactions. However, these models do not subsume the RUM framework and thus, as pointed out by LoR-jagabathula, are not guaranteed to provide a better fit than RUM methods, even when applied to irrational instances. The same limitation holds for other models such as the General Attraction Model from GAM, the Perception-adjusted choice model percp-adjusted-luce and the General Luce Model echenique2015general. Feng2017 propose a welfare-based framework, which subsumes the RUM framework and can be used to obtain choice models able to capture violations of the regularity assumption. The estimation of these choice models, however, is left by the authors as an open research question. Another general approach for which no empirical result has been reported is the Generalized Stochastic Preference choice model gsp-berbeglia2018, an extension of rank-based choice models farias13, Vulcano-marketDiscovery that allows for irrational customer behaviors. This model subsumes the RUM family of models and generalizes the non-RUM approach from KleinbergMU17 by allowing for heterogeneity in customer preferences. Despite its flexibility, the GSP choice model imposes some structure on the choice probabilities, and some examples are provided by the authors describing choice behaviors that do not belong to the GSP class. PCMC propose the Pairwise Choice Markov Chain model, where each alternative is represented as a node of a continuos time Markov Chain. Given an offer set, the choice probabilities are given by the stationary distribution of the sub-chain consisting of the nodes indexed by the available alternatives. Although the PCMC choice model is able to capture both substitution and halo effects, it obeys the axiom of uniform expansion introduced by yellott1977uniformExpansion. The authors argue that such property may be desirable in the context of discrete choice modeling.
\paragraph{Universal discrete choice models. } Some more general choice models have been proposed in the literature, which are able to represent any discrete choice function. In particular, osogami-rbm propose an extension of the MNL model aming at capturing high-order product interactions. They show that the resulting model can be represented as a Restricted Boltzman Machine (RBM), a probabilistic graphical model whose units are divided into two groups, visible and hidden. Visible units are used to encode a binary representation of the offer set and of a given choice, while hidden units learn a latent representation of the input. Given enough hidden units, these models can represent any sort of irrational behavior. An approach based on tree ensembles has recently been proposed by both DecisionForest-gallego and DecisionForest-misic, who show that any discrete choice model can be represented as a distribution over decision trees.
As previously mentioned, choice models with rather flexible structures pose some crucial challenges, whose solution greatly impacts the predictive accuracy of the trained choice models. In particular, one needs to balance between flexibility of the choice model, tractability of its estimation procedure, and risk of overfitting when limited amount of data is available. {\color{black} In this regard, it should be noted that our estimation procedure is non-parametric. Compared to the approach from osogami-rbm, our model can adaptively increase the number of parameters in a data-driven way, as more data becomes available. This may help avoiding overfitting issues when only limited amounts of data, since a a model with a relatively small number of parameters will be learned in this case. The results from comparativeBerbeglia seems to confirm this claim, showing Rank-Based choice models are relatively data-efficient, offering good generalization even with limited amounts of transactions data. Also, our algorithm allows to include both rational and irrational behaviors in the estimation process, thus providing a general method, well suited to a wide range of real case studies. The same is not true for other irrational models such as osogami-rbm, which should be used with care on datasets where it is reasonable to assume that customers do act rationally.}
DecisionForest-misic and DecisionForest-gallego tackle both the computational and generalization aspects by proposing regularization methods whose effect is to restrict the search space in a principled way. It may be argued, nevertheless, that less general choice models may be more effective in exploring search spaces that are smaller by definition, and that imposing some structure on the choice probabilities may provide important inductive bias to improve generalization over unseen offer sets when limited amount of data is available. This observation motivates the focus of this paper. In particular, we propose an estimation method for the Generalized Stochastic Preference choice model, which is flexible enough to subsume the RUM family of models and to capture halo effects, but still imposes some structure on the choice probabilities.
We conclude this section by mentioning an interesting line of work from the machine learning community, proposing general approaches based on Neural Networks to approximate the complex, high-order interactions among alternatives FATE, rosenfeld2019predicting, PointerNet. Despite their flexibility, however, these models have only been applied to settings with product features and large number of training offer sets. Their adaptation to a setting close to ours, where no item featurization is given and the amount of offer sets seen at training time is relatively small, has not been explored yet and does not seem trivial.
\textcolor{black}{In this section, we review the Generalized Stochastic Preference model gsp-berbeglia2018 and extend it by allowing for partial ordering and indifference sets.} Consider a set of products $\mathcal{N}=\{0,...,N-1\}$, with label 0 representing the no-purchase option. {\color{black} With a slight abuse of notation}, let then $\sigma$ denote both a subset of products in $\mathcal{N}$ and a linear order defined over such products, so that the rank (or position) of product $j$ according to $\sigma$ is given by $\sigma(j) \geq 1$.
Specifically, when faced with an offer set $S \subseteq \mathcal{N}$, {\color{black} a customer of type $k$, also referred to as $C_k(\sigma_k,i_k)$}, picks the alternative ranked $i^{th}$ in its subsequence $\sigma_k$ that only contains items also available in $S$. {\color{black} Further, we define $\sigma_{k,S} \subseteq \sigma$ as} the sequence of products obtained by removing from {\color{black} $\sigma_k$} every product $j \notin S$. The customer will then choose product $j^*$ so that $\sigma_{k,S}(j^*)=i$. If $|\sigma_{k,S}| < i$, the customer will leave without any purchase. The particular case of $i=1$ corresponds to customers who always pick their favorite (i.e., highest ranked) product among the available ones. For this reason, we refer to customers $C(\sigma, 1)$ as rational behaviors, and to the index $i$ of a generalized stochastic preference as its irrationality level. The GSP choice model is then defined by a probability distribution $\pmb{\lambda} \in \mathbb{R}^K$ over $K$ customer types $\{C_k(\sigma_k,i_k)\}_{k=1}^K$, {\color{black} so that the probability of choosing item $j$ from assortment $S$ is given by
}
It should be noticed that, since every RUM choice model can be equivalently represented as a distribution over rational stochastic preferences block1959random, the GSP choice model naturally subsumes the RUM family of models.
{\color{black} KleinbergMU17 theoretically justify the use of “irrational”, rank-based behaviors\footnote{In the work of KleinbergMU17, the authors refer to position-selecting choice functions, whose definition is essentially equivalent to the one of (irrational) customer behaviors from gsp-berbeglia2018.} in order to capture compromise effects. In particular, the authors assume alternatives can be mapped to a one-dimensional embedding (i.e., utility) representing the alternatives overall evaluation by the decision-maker. Such embeddings can be given by their price or by a possibly complex function of their features. Alternatives can then be ranked in this embedding space according to their evaluation. Then, choosing the best “compromise” corresponds to selecting the option with rank $2 \leq i \leq |S|-1 $, where $S$ is the set of available alternatives. To better illustrate the practical implications of this argument, Table (ref) exemplifies gsp-berbeglia2018 how the GSP model can explain the results of the experiment from simonson1992choice_exp in Example (ref).}
{\color{black} When only products $\{1,2\}$ are offered, customer $k=4$ chooses the cheapest one, i.e., option $(1)$. According to the rational theory of choice, this would imply that option $(1)$ has to be preferred to option $(2)$ independently of the other products in the offer set. This, however, would be in contradiction with the data at hand. Irrational choice behaviors, on the other hand, can account for assortment-dependent effects. By introducing option $(3)$ in the assortment, the same customer ends up choosing option $(2)$, thus implying that $(2)$ is preferred to $(1)$ in this case.} {\color{black} We refer to Appendix (ref) and gsp-berbeglia2018 for more examples showing how the GSP choice model can reproduce several experiments from the literature on behavioral economics showing evidence of irrational choice behaviors.}
From a modeling perspective, we note that including the 0 (i.e., no-purchase) option among the ranked alternatives has a useful implication in practice. In particular, contrary to the original formulation in gsp-berbeglia2018, this allows us to capture violations of the regularity assumption also for the no-purchase option (we refer to Appendix (ref) for more details). Several studies, indeed, have shown that customers' willingness to purchase and overall satisfaction may decrease in the presence of too many alternatives among which a choice has to be made Iyengar2000, ParadoxOfChoice.
The estimation of the GSP choice model poses significant computational challenges, given that the space of rational customer types alone is factorially large. Estimation procedures developed for rational, rank-based models such as those from Vulcano-marketDiscovery and bertsimas16-local_search cannot be easily adapted to account for learning irrational preferences, nor does their scalability look promising to tackle the even bigger search space implied by the presence of irrational behaviors comparativeBerbeglia, jena2020partially. For these reasons, we decided to adopt the framework if partially-ranked preference sequences from jena2020partially to represent generalized stochastic preferences. Besides providing a more intuitive, behavioral representation of an agent's decision process, partially-ranked preferences allow for fast estimation schemes and have been shown to generalize well on unseen offer sets. Starting from the observation that, for rational customer behaviors, low-ranked alternatives have a relatively low impact in explaining choice data, jena2020partially propose to strictly rank only few, relevant alternatives for each preference list, while allowing for ties among the rest of them. Alternatives with the same rank may then be grouped into so-called indifference sets. We thus provide the following definition:
{\color{black} It follows from Definition (ref) that a certain customer has no particular preference for products in $I(\sigma)$, which all have the same rank. Hence, we refer to $I(\sigma)$ as the indifference set of that customer type.} {\color{black} Note, also, that the irrationality level of a partially-ranked preference is limited by $i \leq |P(\sigma)| + 1$, since alternatives in the indifference sets all have the same rank. } For ease of notation, let $P_S(\sigma) = P(\sigma) \cap S$ and $I_S(\sigma) = I(\sigma) \cap S$ denote the strictly ranked preference list and the indifference set, respectively, obtained after removing from $\sigma$ every product not available in a given offer set $S$. A customer $C(P(\sigma), I(\sigma), i)$ will then pick the alternative ranked $i^{th}$ in $P_S(\sigma)$ if $i \leq |P_S(\sigma)|$, or an alternative chosen uniformly at random in $I_S(\sigma)$ when $ |P_S(\sigma)| < i \leq |P_S(\sigma) \cup I_S(\sigma)|$. When $i > |P_S(\sigma) \cup I_S(\sigma) |$, the customer leaves without any purchase.
{\color{black} While Section (ref) elaborates on how to estimate such preference sequences from transaction data, } Table (ref) gives an example of the choice behavior of two hypothetical customers $C_1\big((2,3,5),\{1,4\},1\big)$ and $C_2\big((2,3,5),\{1,4\},2\big)$, who differ only by their irrationality level. As a consequence, for each offer set $S$, we have that $P_S(\sigma_1) = P_S(\sigma_2)$ and $I_S(\sigma_1) = I_S(\sigma_2)$. {\color{black} Specifically, the first row of Table (ref) corresponds to the case where $i_1=1 \leq 2 = |P_S(\sigma_1)|$ and $i_2=2 \leq 2 = |P_S(\sigma_2)|$. The two customers will then select the items $j_1=2$ and $j_2=5$ with ranks 1 and 2, respectively, in $|P_S(\sigma)|$. For all the other assortments, however, we have that $i_2 = 2 > 1 \geq |P_S(\sigma)|$, hence Customer 2 will either pick an item uniformly at random from the indifference set (assortments $S_2$ and $S_4$) or leave without any purchase (assortment $S_3$). The same reasoning can be applied to obtain the choice of Customer 1 in the remaining assortments.}
jena2020partially have shown that rational, partially-ranked preferences can be efficiently learned from data, using a Growing Preference Tree (GPT) algorithm. {\color{black} In this section, we first review the GPT estimation framework, and then show how to extend the algorithm to additionally handle partially-ranked preferences with irrationality.}
We assume that training data is available in the form of $T$ observations $\mathcal{T}=\{(S_t, c_t)\}_{t=1}^T$ with $S_t$ and $c_t$ representing the offer set and the choice, respectively, that have been observed in period $t$. Let $\mathcal{S}_{train}=\{S_1,...,S_M\}$ denote the collection of $M$ offer sets over which choice data is available. We can further preprocess dataset $\mathcal{T}$ in order to obtain a vector of empirical probabilities $\pmb{v} \in \mathbb{R}^{N \cdot M}$ so that, for each $j \in \mathcal{N}$ and $S \in \mathcal{S}_{train}$, the probability of item $j$ being chosen from offer set $S$ is given by
The GPT algorithm fits into the general column-generation framework proposed for the estimation of a general class of nonparametric choice models by Vulcano-marketDiscovery. In line with this framework, customer behaviors are represented as a choice matrix $\pmb{A} \in \mathbb{R}^{(N\cdot M) \times K}$, encoding $K$ behaviors for $M$ offer sets, whose elements give the probability of customers choosing an item from a given offer set. In particular, based on the choice behaviors of a partially-ranked list with irrationality $i$ defined in Section (ref), the elements of the matrix $\pmb{A}$ may be computed as follows:
Given a distribution $\pmb{\lambda} \in R^K$ over the customer types, the predicted probability $x_{j,m}$ of a random customer choosing alternative $j$ from the offer set $S_m$ is then given by $x_{j,m} = \sum_k A^k_{j,m} \lambda_k$. One can thus define the best distribution $\pmb{\lambda}$, that is, the one for which the predicted probabilities are the closest to the observed ones, and obtain $\pmb{\lambda}$ by solving the following optimization problem:
Here, $\mathcal{L}(\pmb{x}, \pmb{v})$ can be any convex loss function measuring the distance between the predicted probabilities $\pmb{x}$ and the observed ones $\pmb{v}$. For example, one may minimize the $L_1$ error between the two probability distributions, in which case we have
Minimizing the $L_1$ error generally leads to sparse models. Further, objective function ((ref)) can be easily linearized bertsimas16-local_search and is therefore computationally amenable.
Another popular measure of the distance between two probability distributions is the Kullback-Leibler. It is strictly convex and leads to the same solution as Maximum Likelihood Estimation LoR-jagabathula. It is computed as
where $T_S$ is the number of samples showing $S$ as offer set.
{\color{black} Solving problem ((ref)) over the factorially large set of all possible customer types is not tractable. Hence, the master problem ((ref)) is first initialized with a restricted set of customer behaviors and is solved to find the corresponding probability distribution $\pmb{\lambda}$ that best fits the training data. In each further iteration, new relevant behaviors are discovered by solving a subproblem and added to the master problem, which then adjusts the probability distribution $\pmb{\lambda}$ over the new set of behaviors. The algorithm terminates once a predefined stopping criteria is met.}
In particular, let $\pmb{\alpha} \in \mathbb{R}^{N\cdot M}$ and $\nu \in \mathbb{R}$ denote the dual variables associated with constraints ((ref)) and ((ref)), respectively. The customers (i.e., preference sequences) worth adding to the model in order to improve its fit of the data are those whose corresponding choice vector $\pmb{a}$ {\color{black} (column of A)}, computed as in ((ref)), has a {\color{black} negative (reduced) cost $c(\sigma)= -\pmb{\alpha}^T\pmb{a} - \nu$}. While finding new preference sequences with {\color{black} negative costs} generally tends to be computationally expensive, the GPT algorithm exploits the structure of partially-ranked preferences to efficiently identify such columns. Indeed, partially-ranked preferences allow for using an efficient tree-like data structure, where deeper levels correspond to behaviors with more refined ranked lists. {\color{black} Specifically, any sequence of products obtained from such a tree by traversing the path from the root to a given node, corresponds to the preference sequence $P(\sigma_k)$ of a certain customer $C_k$. It then follows that a behavior $C_j$ is considered a sub-behavior of $C_k$, if $P(\sigma_j) = (P(\sigma_k),\ell)$ with $\ell \in I(\sigma_k)$. When searching for new customer behaviors, one may thus restrict the search for relevant customer types among the sub-behaviors of $\{C_1,...,C_K\}$, at any given iteration.}
{\color{black} To better illustrate how the search-tree is gradually explored during the GPT procedure, we report in Figure (ref) the tree resulting from the initialization step, followed by one iteration of the GPT algorithm on a toy example, where the universe of products consists of four alternatives, i.e., $\mathcal{N}=\{1,2,3,4\}$. The algorithm starts by initializing the tree with $N$ rational customer types $C_1, \dots, C_N$ such that $P(\sigma_k)=k$ and $I(\sigma_k)=\mathcal{N} \setminus \{k\}$. We then solve the restricted master problem ((ref)) over this initial set of behaviors, in order to obtain a first distribution $\pmb{\lambda}$ over the $N$ customer types, and the values of the dual variables $\pmb{\alpha}$ and $\nu$. After the initialization, the generation of new candidate behaviors to include in the master problem at each future iteration requires three steps:}
{\color{black}
}
{\color{black} Identifying relevant customer behaviors based solely on their reduced costs may not be robust in general when dealing with irrational customer behaviors. We elaborate more on the topic in Section (ref) where, based on behavioral considerations, we propose a superior selection criteria for the identification of relevant customer types.}
Observe that customers that differ only in their irrationality level (such as $C_5$ and $C_6$ in our example) generate the same sets of sub-behaviors. {\color{black} Hence, only one of these nodes (either $C_5$ or $C_6$ in our example) has to be considered to evaluate and generate further sub-behaviours.} We therefore consider only one node among the set of behaviors $\mathcal{C}_{P(\sigma),I(\sigma)} = \{ C_k(P(\sigma_k), I(\sigma_k), i_k): P(\sigma_k) = P(\sigma) \text{ and } I(\sigma_k)=I(\sigma), k=1,...,K \}$, with probability $\tilde{\lambda}_{P(\sigma),I(\sigma)} = \sum_{k : C_k \in \mathcal{C}_{P(\sigma),I(\sigma)}} \lambda_k$. {\color{black} Considering the example in Figure (ref), at the second iteration the preference list $((2,3), \{1,4\})$ would then be sampled with probability $\tilde{\lambda}_{((2,3)\{1,4\})} = \lambda_5 + \lambda_6=0.4$.}
We highlight two major advantages of the exploration strategy employed by the GPT algorithm:
{\color{black} \paragraph{Computational complexity. } As described above, each iteration of the GPT procedure involves sampling $\gamma$ behaviors $C_k(P(\sigma_k),I(\sigma_k),i_k)$ and, for each them, generating $|I(\sigma_k)| \cdot (|P(\sigma_k)|+1)$ sub-behaviors, i.e., one for each item $j \in I(\sigma_k)$ and irrationality level $i$, with $1 \leq i \leq |P(\sigma_k)|+1 $. The reduced cost $c(\sigma)$ of a sub-behaviour $\sigma$ can be obtained in $O(M)$ jena2020partially from the reduced cost of its parent node. Therefore, computing the reduced costs of all rational and irrational candidate sub-behaviors at a given iteration has a complexity of $O(N^2M)$ (compared to $O(NM)$ for the rational approach). While this is the theortical worst-case complexity, our experiments in Appendix (ref) show that the GPT tends to produce relatively short preference lists $P(\sigma)$, ranking as few as 3 products, on average. Further, jena2020partially showed that even on large (rational) instances with up to 1,000 products, the length of the produced strict preference lists tends to be similarly small, and rather independent from the number of products. The computational burden of each GPT iteration is therefore significantly mitigated in practice, since is tends to generate few irrational behaviors. }
{\color{black} In this section, we elaborate on how to identify new customer behaviors that improve the fit to the training data and are more likely to generalize well on test data. The de facto scoring method in column generation, and therefore for evaluating the quality of candidate behaviors in the GPT estimation procedure, is exclusively based on their reduced costs $c(\sigma)$. This is based on the hypothesis that a parsimonious model tends to generalize well on unseen offer sets, which is widely adopted in the literature Vulcano-marketDiscovery,bertsimas16-local_search,jena2020partially.} {\color{black} However, when dealing with irrational behaviors, such criterion may lead to capturing an excessive number of spurious interactions among products, especially in the case of scarce data availability.
}
{\color{black} In the following, we argue that the use of customer behaviors with small numbers of strictly ranked products, and, as a consequence, larger indifference sets, may drastically reduce the risk of overfitting. Using rational behaviors only, this is naturally achieved by the design of the GPT algorithm, which starts by generating behaviors with small numbers of strictly ranked products. While, in the rational case, strictly ranking only a few products with respect to the total number of existing ones (e.g., 5 out of 100 products) may be sufficient to reduce the risk of overfitting, this may not be the case when considering irrational behaviors. In fact, here, the added risk of overfitting increases quickly with the number of possible interactions within the sequence of strictly ranked products. }
{\color{black} As an example, consider the case in which we aim to capture the positive relation of item $1$ on item $2$ in a total universe of $N=5$ products (for simplicity, we here do not use the no-purchase option in the preference sequences or the assortments), based on the observed choices of product 3 from assortment $S_1=\{2,3\}$ and product 2 from assortment $S_2=\{1,2,3\}$. When estimating the choice model, several irrational preference sequences may fit these transactions, for example, either $C\big((1,2),\{3,4,5\}), 2\big)$ or $C\big((1,2,3,4,5),\{\}, 2\big)$. The former (with few strictly ranked products) is clearly the more precise one, and is less prone to overfitting, while the latter is an example of a more general one, prone to a higher risk of overfitting. While the latter sequence seems to have unnecessarily many strictly ranked products, in practice, when dealing with limited transaction data, such sequences may be selected due to their lower reduced costs. A choice model using such a sequence may, depending on the unseen offer sets, extrapolate up to $|P|\cdot(|P|-1)/2$ possible pairwise interactions, which are illustrated in Table (ref). Note that all except for one of these interactions are spurious and therefore overfit the training data. In contrast, the former sequence with only two strictly ranked products “deactivates” the influence of product 1 on any product other than 2.
While it is, of course, not possible to know beforehand which products really do interact which each other, it becomes immediate that, in an effort of reducing the risk of overfitting, it is desirable to prioritize behaviors with a small number of strictly ranked products. }
{\color{black} The number of spurious interactions to which an irrational customer behavior may lead to can be quantified exactly, as demonstrated in the following observation.
Proof: see Appendix (ref). }
{\color{black} Observation (ref) implies that the number of spurious interactions, leading to potential overfitting, does not necessarily grow with a higher level of irrationality, but rather with the number of strictly ranked products. We note that this observation is not limited to our definition of partially-ranked preference sequences, but generally applies to the case of behaviors defined by the Generalized Stochastic Preference model from gsp-berbeglia2018. }
{\color{black} We now propose a new dominance rule to select the candidate behaviors to be included in the master problem ((ref)). The rule aims at striking a delicate balance between the number of strictly ranked products and the reduced costs of a candidate behavior:
As will be shown in Section (ref), the use of this selection rule improves the predictive performance of the irrational GPT algorithm, particularly on the real-world data set. }
{\color{black} Table (ref) exemplifies the selection process according to each of the two possible selection criteria for seven candidate behaviors. The first four lines show, respectively, the behavior id, the number of strictly ranked products, the cost of each behavior and the resulting ranking $\pi$. Using cost $c(\sigma)$ as selection critera would lead to selecting customers with smallest cost $c(\sigma)$, namely $C_1, C_4$ and $C_7$. However, notice that customer $C_7$ strictly ranks a relatively high number of products and, based on Observation (ref), may imply a high number of spurious interactions among products. By using our proposed selection criterion, instead, we select behaviors with only two strictly ranked products. In particular, assuming $\delta=3$, we have \underbar{$\pi$}$=2$ and will select behaviors $C_1, C_4$ and $C_5$.}
{\color{black} We conclude this section highlighting connections between our proposed dominance rule and consideration sets, a well known concept in the Marketing literature hauser2010considreview. This concept refers to the fact that consumers usually pay attention to only a small subset of all existing items (either due to a limited attention budget or to avoid the cognitive burden of searching through a possibly very large set of products), and will select an item from this subset. }
{\color{black} While the estimation of consideration sets is object of a separate branch of literature aouad2015assortment, jagabathula2019inferring, our notion of strictly ranked sets approximate consideration sets, while still attributing a non-zero probability to products in the indifference set. It has also been shown in the literature on brand choice that the size of consideration sets tends to be relatively small, usually consisting of 2 to 5 brands hauser1990evaluation. This suggests, from a behavioral point of view, that prioritizing behaviors with a small number of strictly ranked products (and therefore lower orders of interactions among products) may provide good inductive bias for generalizing well on unseen offer sets.}
In this section, we report the results of our experiments on both synthetic and real datasets. The goal is to understand whether irrational, partially-ranked behaviors can improve predictive accuracy on new offer sets. In all our experiments, we compare three variants of the partially-ranked choice model estimated using GPT, namely GPT-R, {\color{black} which corresponds to the approach of jena2020partially, thus restricting the space of customer behaviors to the rational ones only, and its extensions GPT-I and GPT-IC, which include irrational behaviors in the estimation process. Of these, the former selects customer behaviors based solely on their costs, while the latter use the dominance rule proposed in this work, aiming at prioritizing customer behaviors with small consideration sets, i.e., with a small number of strictly ranked products, and thus focusing on sparse, low-order interactions among products}. We further compare the GPT-based approaches with three benchmarks: the enumerative rank-based choice model (RB-R) with fully-ranked lists, obtained by enumerating all possible preferences (i.e., permutations over products) \footnote{Let $m$ denote the maximum number of products missing from any assortment. As noted in LoR-jagabathula and Honhon2012, only $O(N^m)$ permutations of $m+1$ products need to be generated, since products with rank greater than $m+1$ will never be chosen. } , the pairwise choice markov chain (PCMC) proposed by PCMC, and the Halo-MNL choice model from HaloMNL. Section (ref) focuses on the generalization performances of the various approaches on a set of synthetic instances. In Section (ref), {\color{black} we test the models on the IRI Academic dataset bodea2009data, consisting of transaction data from a large grocery store chain}.
\paragraph{Estimation of the choice models.} Following LoR-jagabathula, we train RB-R by minimizing the average Kullback-Leibler (KL) divergence ((ref)) between predicted probability distributions and the empirical ones over training offer sets. All the other approaches are trained by Maximum Likelihood Estimation. As already observed, it is well known that minimizing the KL divergence is equivalent to maximum likelihood estimation in terms of optimal solution retrieved LoR-jagabathula. For the GPT-based approaches, we stop the training procedure when the difference in the log-likelihood of the data at two consecutive iterations is statistically insignificant, as proposed by Vulcano-marketDiscovery \footnote{Let $\mathcal{L}^k$ and $\chi^2(\beta)$ denote the log-likelihood at iteration $k$ and the critical value of the chi-squared distribution with $\beta$ degrees of freedom, respectively. We stop the GPT-procedure when $-2(\mathcal{L}^k - \mathcal{L}^{k+1}) < \chi^2(\beta)$, where $\beta$ is replaced by the difference in the number of parameters (i.e., behaviors) between the two iterations.} , or when no negative cost column has been found at a given iteration. {\color{black} Further, we set the hyperparameters $\gamma=10$, and $\delta=20$ (as in jena2020partially), which denote the number of behaviors to sample and the number of best ones to add to the master problem at each iteration, respectively.} For the estimaton of PCMC, we used the code provided by the authors\footnote{Code available at https://github.com/sragain/pcmc-nips.}. We refer the reader to Appendix (ref) for more details on the implementation of the PCMC choice model.
{\color{black} We start this section by describing our data generation procedure. We then proceed by characterizing the irrationality level of the generated instances, and by reporting the generalization performance of the various approaches on such instances.}
We generate choice data samples according to two ground-truth models, specifically the Halo-MNL model proposed by HaloMNL and the GSP model. Both of them allow us to control the amount of irrationality resulting in the generated instances and to investigate its impacts on the performance of the various approaches. For each ground truth model, instances were generated as follows:
In all the experiments reported in this section, we used a number of products $N=10$, one of which represents the no-purchase option. For each ground-truth model, we generate either $3,000$ or $50,000$ transactions, for a total of 10, 20 or 50 training offer sets. This simulates different amounts and diversity of training data. When using 50,000 transactions, in particular, the goal is to simulate the scenario in which we train the models based on empirical probabilities that are close to the true ones (i.e., those from the ground-truth model), and the effect of any sampling noise becomes negligible. This corresponds to the setting already used, for example, in bertsimas16-local_search and DecisionForest-misic, where choice models are trained on ground truth probabilities. We further assume that the number of transactions is equally distributed among the training offer sets, which all have dimension $|S| \geq 3$ and contain the no-purchase option.
We first investigate the level of irrationality present in the generated instances. In line with the methodology proposed by LoR-jagabathula, we fit the enumerative rank-based choice model, RB, to all our training instances. It is well known that any RUM choice model can be equivalently represented as a probability distribution over rankings of alternatives block1959random. Thus, by fitting such model to a given instance, the resulting objective function indicates what the authors define as the Loss of rationality (LoR) of that instance, which can be interpreted as a measure of the minimum amount of choice data that cannot be explained by using any choice model belonging to the RUM family. Figure (ref) reports the LoR value distributions over instances grouped by category (Rational and Irrational), ground-truth models (Halo-MNL and GSP) and number of customer types (in parenthesis). As already mentioned, rational instances for Halo-MNL(1) and Halo-MNL(10) correspond to instances generated under MNL and MMNL ground-truth models, respectively. Also, rational GSP ground-truth models are equivalent to Rank-Based models with the same number of preference lists.
It is interesting to note that the aggregation of a high number of irrational customer types seems to result into a rational choice behavior at the population level (see Halo-MNL(10) and GSP(100) in Figure (ref)), {\color{black} given that the individual, complex buying behavior becomes less apparent, and the collective (aggregated) transactions are easier approximated by simple choice rules. This is also connected to what comparativeBerbeglia refers to as degree of consistency. Instances with many customer types are said to be “less consistent”, since the probability of being of a certain customer type is relatively low, and have been found to generalize better. }
Figure (ref) also reports a red dashed line, corresponding to a Loss of rationality of 0.008, which visually separates the generated instances based on their irrationality level. Essentially, rationally-generated instances tend to fall below this threshold, but also the irrationally-generated ones in which many customer types are aggregated. In the following, we interpret this value as a threshold to understand whether an instance contains significant amount of irrational choice behaviors. In Appendix (ref), we further show that the LoR of a given instance can be impacted by other factors as well, such as the number of choice samples and offer sets available for training.
We now focus on the generalization performance of the various approaches when tested on new offer sets. This has been measured in terms of average $L_1$ error between the predicted probability distribution $\pmb{x}$ and the ground-truth probability distribution $\pmb{v}$ on new offer sets, and has been computed as
where $\mathcal{S}_{test}$ is the collection of all possible offer sets that have not been used for training\footnote{The total number of offer sets with dimension $3 \leq |S| \leq 10$ and containing the no-purchase option is equal to $502$. Hence, given $M=10, 20$ or $50$, $|\mathcal{S}_{test}| = 502- M$.}. As noted in PCMC, equation ((ref)) can be interpreted as the expected $L_1$ prediction error given a randomly drawn offer set.
Table (ref) reports the $L_1$ test errors of each approach on sets of instances grouped by ground-truth models and number of customers types, indicated in parenthesis.
{\color{black} We first focus on the set of irrational instances. It is possible to observe how the performance of the rational choice models, RB-R and GPT-R, deteriorates as the Loss of Rationality increases. Specifically, this is the case for Halo-MNL(1) and GSP(10) instances where, among the rank-based approaches, GPT-IC and GPT-I offer the best predictive accuracy, respectively. GPT-IC favourably compares also to the Halo-MNL for small enough percentage of positive, pairwise interactions among products. On average, however, the Halo-MNL choice model manages to well approximate the data-generating process on Halo-MNL(1) instances, therefore outperforming all other approaches. We notice that GPT-IC tends to outperform GPT-I on all classes of instances, with the exception of those in GSP(10). On these instances, GPT-IC does actually not improve over GPT-R, unless there is a high percentage of irrational behaviors. Such results are in line with the behavioral assumption intrinsic to GPT-IC, which we proposed to explicitly prioritize sparse, low-order interactions among products, and may thus fail to generalize well on those scenarios where customers consistently (i.e., with high probability) show high orders of substitution and halo effects among products. However, we deem such interactions less likely to happen in practice. Our results on real-world data (see Section (ref)) seem to confirm this claim. The good median and maximum test errors of GPT-IC further confirm the robustness of the underlying selection criterion to identify customer behaviors that tend to generalize well.}
{\color{black} We now discuss the results for rational instances, where the flexibility of irrational approaches may increase the risk of overfitting (see also Appendix (ref)) when compared to GPT-R. \sout{This also} All GPT-based algorithms favorably compare with RB-R, confirming the results of jena2020partially on the generalization power of partially-ranked lists and that enumerating all possible fully-ranked preferences for training the RB model increases the risk of overfitting the training set Vulcano-marketDiscovery. This supports the hypothesis that adding only relevant types to the estimated choice model is crucial for its generalization performance. Also note that the same relative performance between GPT-I and GPT-IC observed on irrational instances can be noticed in the rational case as well. Specifically, GPT-IC outperforms GPT-I, on average, on all instances with the exception of RB(10) ones, i.e., those where customers consistently exhibit high order of substitutions among products. Finally, we emphasize that both irrational GPT variants significantly outperform the PCMC and Halo-MNL models on such rational instances. }
\paragraph{Impact of the amount of available data} {\color{black} We now test the robustness of the various approaches under different amounts of training data. In particular, Figure (ref) and Figure (ref) report, for each approach, the corresponding average test error over irrational and rational instances, respectively, under different data-regime settings “$T$-$M$”, where $T$ represents the number of transactions and $M$ the number of assortments available for training. Each plot also reports, on the top axis, the best performing model under each data-regime scenario.}
{\color{black} Both figures exhibit common trends in the the relative performance of the approaches. In particular, the Halo-MNL model tends to require significant amounts of data in order to become competitive with (or outperform) the rank-based approaches. These, in contrast, show relative stable performance and steadily improve with more available training data. They also consistently outperform the PCMC model.}
{\color{black} Among the rank-based approaches, in line with our discussion of Table (ref), we observe that GPT-IC tends to perform the best on Halo-MNL instances. Also, while being competitive on GSP(100) and RB(100) instances, it is generally outperformed by other rank-based approaches on GSP(10) and RB(10) instances, which are characterized by higher orders of interactions among products.}
{\color{black} We conclude this section by referring the interested reader to Appendix (ref) for additional numerical results. In particular, Appendix (ref) provides statistics describing the choice models learned by GPT-based approaches on classes of instances characterized by different levels of irrationality. The results therein also highlight the computational effectiveness of GPT-based approaches, which can be estimated in less than two seconds, on average, on our synthetic instances. In Appendix (ref), we provide a more refined view of the impact of the irrationality level of GSP customer types on the predictive accuracy of the various approaches. Finally, Appendix (ref) investigates the generalization performance of the implemented algorithms on Halo-MNL instances separated by type of positive interaction, i.e., symmetric or asymmetric, in the ground-truth model.}
In this section, we test all approaches on the IRI Academic data-set bodea2009data, a real-world data-set from the retail sector. The data consists of transactions from grocery and drug store chains located in 47 markets in the USA. We consider transactions corresponding to 29 product categories in total, which we report in Table (ref).
{\color{black} Each transaction record in the dataset contains informations regarding the week and store in which the transaction occured, and the purchased item, uniquely identified by its Universal Product Code (UPC).} {\color{black} In order to tackle both the sparsity and large volume of the data, we follow the same pre-processing steps outlined in LoR-jagabathula. Specifically, we start by considering the subset of transactions corresponding to the first two weeks of year 2007. We then aggregate products by their UPC-vendor code. In other words, transactions where items with the same UPC-vendor code were bought, are attributed to the same vendor-item. This kind of aggregation is common in the marketing literature in order to reduce the sparsity of the data bronnenberg2004market. We then proceed by considering the nine most popular vendor-items, and further aggregate the remaining ones into a no-purchase option, therefore obtaining ten alternatives in total.}
{\color{black} The assortment of products shown to the customer at the moment a transaction occurred is not given in the data. Hence, for each transaction $t=1,\dots,T$ occurring in week $w_t$ at the store $s_t$, where product $j_t$ was bought, we assume the assortment shown to the customer consists of the set products sold at least once in that store-week combination, i.e., $S_t = \bigcup_{t'=1}^T\{j_{t'} : w_{t'}=w_t, z_{t'}=z_t\}$. At the end of this step we obtain a final list of transactions $\mathcal{T}=\{(S_t, j_t)\}_{t=1}^T$. }
{\color{black}
Following the experimental setup of DecisionForest-misic, we separately test the various approach on each of the 29 product categories using 5-folds cross validation. In particular, after considering a product category with transactions data spanning a collection $\mathcal{S}=\{S_1, \dots S_M\}$ of $M$ unique assortments, we partition $\mathcal{S}$ into five (approximately) equally sized collections of assortments $\mathcal{S}_1, \dots \mathcal{S}_5$. For each set $\mathcal{S}_i, i=1,\dots 5$, let $\mathcal{T}_i$ denote the set of transactions where an assortment belonging to $\mathcal{S}_i$ was shown to the customers, i.e.,$ \mathcal{T}_i=\{(S_t, j_t) : S_t \in \mathcal{S}_i\}$ . We then run 5 separate experiments where transactions $\mathcal{T}_{train} = \mathcal{T}\setminus \mathcal{T}_i$ are used for training while transactions $\mathcal{T}_i$ are used for testing the predictive accuracy of the algorithms on new assortments. }
{\color{black} We measure the predictive accuracy in terms of expected $L_1$ error, over unseen assortments. We modify equation ((ref)) to account for the fact that each test assortment is now associated to a certain number of transactions $T_S=\sum_{t=1}^T \mathbbm{1}[S_t=S]$. We thus compute the test error as follows:}
{\color{black} Table (ref) reports the average test errors of the various approaches on each product category. Columns $M$ and $T$ indicate the total number of unique assortments and transactions, respectively, available for each product category. We further report for each approach the mean, median and maximum test error over $all$ experiments. The row “GPT-IC Improvement” reports the percentage improvement of GPT-IC over each approach, while “Nb Best” denotes the number of product categories in which the corresponding approach achieves the best average predictive accuracy.}
{\color{black} We observe that GPT-IC significantly outperforms all other approaches according to all metrics on this dataset. Such results confirm that prioritizing customer behaviors with a relatively small number of relevant, strictly ranked products, may enhance predictive accuracy in practice. Specifically, GPT-IC achieves a 7.2% improvement in predictive accuracy with respect to GPT-I, on average, and a 12.4% improvement with respect to GPT-R, the best RUM baseline.} {\color{black} In this context, one may wonder whether the predictive accuracy of GPT-R can be improved by adopting the new customer selection rule of GPT-IC (see Section (ref)). We therefore tested such a configuration on the IRI data-set. However, our experiments did not show any improved test errors, confirming that the new dominance rule is indeed helpful only when aiming at estimating irrational customer preference sequences.}
{\color{black} Figure (ref) provides a clearer picture of the improvement one may achieve by going beyond RUM on each product category. In particular, for each category we compare GPT-IC with the best performing RUM baseline, namely RB-R and GPT-R, and then report the average percentage improvement in predictive accuracy. Notably, such improvements can be as high as 48% for the category of cigarettes, and close to 40% for the beer and coffee product categories. We also note that for those product categories where the decrease in accuracy is the most significant, such as frozen dinner, laundry and detergent, mayonnaise, salty snacks and soup, none of the irrational baseline we tested was able to outperform the RUM ones. This shows that either such products categories do not contain significant levels of irrationality, or not enough data is available to learn such complex product interactions.}
\paragraph{Impact of the amount of available data. } {\color{black} In this section we investigate how the performance of the various approaches is affected by the amount of data available for training. In particular, Figure (ref) reports the average test error over all products categories when different amount of transactions are used for training. Specifically, for each of product category, we perform 5-fold cross validations as described above and, for each experiment $i=1,\dots,5$, we select 10%, 25%, 50%, 75% and 100% of the transactions in $\mathcal{T}_{train}$, respectively.}
{\color{black} In line with our results on synthetic instances (see Section (ref)), Halo-MNL needs significant amounts of data to be competitive with rank-based approaches, only outperforming GPT-R when 75% or more of the available transactions are used for training. In contrast, the GPT-based approaches seem to be quite data-efficient, with relatively stable performances even for the case where only 10% of the transactions are used for training. Interestingly, the performance of GPT-I slightly deteriorates when moving from 25% to 50% of the transaction being used. This may be due to the fact that, for several product categories, most of the transactions concern a relatively small number of assortments. Hence, cases with only 10% of training transactions tend to exclude “noisy” assortments for which only few transactions (as few as one or two) are available, and which may cause GPT-I to infer spurious product interactions. GPT-IC, on the other hand, does not seem to suffer from such issue, since it prioritizes low-order interactions, which require less data to be learned effectively.}
{\color{black} In this paper, we have proposed a discrete choice-model that is sufficiently flexible to capture rational and irrational choice-behavior, together with a computationally- and data-efficient estimation method. The resulting models have been shown to overfit less and generalize well when compared to existing benchmarks.
In particular, we extend the Generalized Stochastic Preference choice model introduced by gsp-berbeglia2018 by adapting partially-ranked preference sequences jena2020partially, which enables us to estimate the model via column generation. In an effort to prevent additional overfitting induced by the more general irrational preference sequences, and linked to the concept of consideration sets from the marketing literature, we propose a new criterion to select relevant customer types, which are more likely to generalize well in practice.
Our experiments on a popular and extensive set of real-world data has shown that our proposed models have a variety of advantages. First, the use of the new selection rule further improves the generalization accuracy of our irrational choice-model on unseen offer sets by 7.2%, on average. In contrast, using this selection rule in the context of the purely rational choice-model did not result in improvements, confirming that this selection rule is indeed a contribution particular to the irrational case. } {\color{black} Second, with respect to the rational baseline models, our irrational model boosts predictive accuracy by 12.4%, on average, and for some categories up to 48%. On (synthetic) rational RUM instances, our irrational choice-models provide stable results, only slightly inferior to the rational baseline models, while the irrational baseline models showed significantly worse performance. Third, our models have shown to be data-efficient, providing a higher predictive accuracy then the benchmarks when little training data is available.
Finally, an appealing feature of our approach is that, within the same framework, it is possible to exploit the explanatory power of (i) partially-ranked preference lists farias13 and (ii) irrational behaviors, which can significantly enhance accuracy on irrational instances. Using the new selection rule, our approach is thus capable of providing accurate estimates of product demands on both rational and irrational instances, circumventing the need for effective model selection criteria. }
\ACKNOWLEDGMENT{We would like to acknowledge the Wharton Customer Analytics (WCA) research group and the Majid Al Futtaim (MAF) data & analytics team for the insightful discussions.}