Introduction 1.Recommender Systems

Recommender Systems (RS) have proven successful almost everywhere in the digital economy, as they are a crucial component of the engines that run digital advertising, e-commerce websites, digital media, music and video providers and social networks. For the last few years, there has been a growing effort -partially inspired by economic theory-in providing a principled way to design these systems. We contribute to this research effort by providing a proof of concept that recommender systems used by e-tailer and advertisers could be welfare maximizers. To do so, we leverage a user behavioural model summarized in Figure 1, and which will be formalized in Section 4.

Shortcomings of current approaches

Most reward-optimized recommendation systems measure an abstract form of user utility and not an actual monetary value. This situation likely stems from the preponderance of clicks as immediate reward feedback in real-world systems. But as the field and the industry mature, we need consistent and rigorous approaches for conversion-optimized recommendation systems. The apparent similarity of conversions and clicks from the point of the merchant/advertiser is misleading, and the current click-optimization approaches are conceptually lacking when it comes to conversion modelling. The three main differences are:

• While clicks are free for the users, conversions cost real money, and therefore the item price should play a big role in the utility computation within the Recommender System. In other words, the price of an item is a disincentive to buy, but not to click. • Due to finite budgets, users have to make choices and items serving the same need are mainly in competition in the user shopping process. This is much better modelled as a Categorical distribution over the choices, instead of the standard Bernoulli used for click modelling.

Figure 1:

The model of the user as a rational decision-maker with a limited awareness set. At time t1 and t2, the user observes different models of phones, with their prices. At time t3, they decide whether to buy one of the two phones, or to leave the website empty-handed. This decision is the output of a rational process of utility maximization that takes into account both the features and the prices of the two phones. The novelty of our framework is that we make explicit the difference between what the user knows (the awareness set) and the entire catalog.

• While clicks are conditioned on existing recommendation systems policies (they are bandit feedback by nature), conversions are in a large part organic and therefore less sensitive to changes in recommendation policy.

Also, because the goal of recommendation is to facilitate two-party transactions, one needs to clearly state on whose behalf the Recommender System is operating (the buyer or the seller's side).

Our approach

To address all these shortcomings, we rely at learning time on the user's browsing history to infer the set of items over which the user is making the decision to buy or to leave ( Figure 1), and then we frame the problem of recommendation as the problem of finding the optimal enrichment of the user's awareness set (Figure 2). Also, we propose a novel recommendation objective: welfare maximization, moving the focus from ways of splitting the pie -which is the main focus of multi-stakeholder literature-to how to maximize the pie. This leads us to an objective based on the Willingness-To-Pay (WTP), which measures the maximum price that the user is willing to pay for an item. More precisely, it is the price point where the user is indifferent to buying or not the item [1]. To be able to maximize the WTP objective, we propose a simple algorithm which can be seen as an extension of the classical Matrix Factorization (MF) algorithm [2,3] that incorporates price and that can serve both as a user decision model and as a WTP estimator.

Paper contents

In Section 2, we cover the related work on recommendation with prices. In Section 3 we discuss potential applications of the Welfare objective for Recommendation. In Section 4, we introduce the user discrete choice model, and propose RUM-MF (random utility model via matrix factorization), a simple extension of existing MF algorithms. In Section A, we introduce our simulated environment and present our results against multiple performance-optimizing baselines on classical and welfare-based metrics. In Section 6, we conclude and outline future research directions. The role of recommendation in a limited information setup. Based on its knowledge of the user, the RS points the user to a new item that is likely to be useful. The value of RS is equal to the difference in utility between the user's decisions with or without the recommendation.

Related Work

Performance-optimized Recommendation

Performance-optimized Recommendation has a long history, with many initial works related to the problems of click-through rate (CTR) optimization for online advertising and search ranking. There are two categories of methods. The first relies on the label or reward given by the user, the second directly learns an order on the items.

The first class of methods was motivated by online advertising, and mostly relies on likelihood-based models. They are preferred due to their calibration properties, and range from the use of large-scale logistic regression with sparse features as in [4], Gradient Boosted Trees [5], Factorization and Fieldaware Factorization Machines [6,7], and more recently, Deep Neural Networks [8], Bayesian Methods [9], Variational Autoencoders [10], and Policy-based methods [8], leading to state-of-the-art results.

The second class of methods was motivated by search engine design and mostly relies on learning-torank models. This includes classical ranking methods such as SVM-Rank [11], Triplet Loss and Syamese Networks [12] and that have been more recently supplemented by Bayesian Personalized Ranking (BPR) [13,14].

Price in Recommendation

Moving to specialized approaches for conversion modelling and the use of price in recommendation, the literature is quite varied and ranges from full user shopping decision modelling via multiple objective matrix factorization of the shopping data as in [15], to ranking approaches that supplements user -item affinity measures with global and local budget preferences, as in [16]. More recently, [17] proposes a Graph Convolution Network-based method to infer category -specific price elasticity, and [18] explores several methods to compute item price bands and explicitly model user price affinity for various types of products.

Recommendation and Econometric Models

Probably the closest area of research is the existing body of work around the use of economic-inspired recommendation models. In [19], the authors outline the relationship between recommendation and surplus or welfare maximization and propose a way to estimate the personalized WTP based on the concavity of the utility function. In our paper, we extend their ideas to support what we think is the realistic case of limited awareness, and propose a different way to estimate the WTP that is closer to standard Matrix Factorization approaches. Similar limitations of the user decision set where already noted in the economic theory [20] literature.

In [21], the authors propose learning the WTP with auctions on mechanical turk, and using it for personalized promotion. In the follow-up paper [22], the authors propose Multiproduct Utility Maximization (MPUM) based on the complementarity property of some existing choices. In [16] the authors propose learning the in-session WTP using views and purchase decisions. More recently, in a series of papers [23,24] the authors propose two economic recommendation objectives, Marginal Utility per Dollar and Weighted Expected Utility. Unlike in our approach, the authors are only considering the user-side. On the vendor side, [25,26] both raise the point that the product prices have an impact on the seller's revenue and profit and propose alternative ways to incorporate this information in the final recommendation ranking function. In [27], the authors propose an extension to dynamic recommendation strategies that take into account demand saturation, and show that the problem is NP-complete and propose tractable heuristics.

Random Utility Models

Discrete Choice Theory is a classical branch of Economics, and Random Utility Models are one of the main tools of the discipline. Discrete Choice theory has its origins in the 60s with work such as [28]. Its use to answer marketing questions was pioneered by Daniel McFadden in [29]. He won a Nobel Prize for his work on Random Utility Models (RUM), and more precisely on Conditional Logit models [30]. Random Utility models (RUM) have been introduced in the 1970s, a time where the availability of user consumer data was scarce and the observability of the salient user and product features was reduced. However, in modern times, a lot of the user shopping activity moved online, therefore tremendously increasing the volume of available user shopping data and its granularity. Furthermore, it can be argued that in many cases, the modeller has access to a full view of the product information available to the consumer at the moment of the decision. That means that at learning time, we have total access to the full feature set used in the decision-making process, albeit in a raw form. For this reason, recent work has explored the possibility of applying RUM to consumer basket modelling and dynamic pricing (SHOPPER) [31]. However, though the authors drew parallels to existing recommendation models, the model was not used and benchmarked for recommendation.

Welfare and Recommendation

There are many ways to frame the problem of designing a Recommender System algorithm as a machine learning problem. For some, it is the question of guessing the most probable next item, or of matrix completion, for some others, it is an exploration-exploitation problem (bandit setting). A more recent line of approaches frames the problem of designing a Recommender System algorithm in terms of economic value maximization [19]. Our claim is that in the presence of sales data, recommendation algorithms can use the price information to directly optimize the welfare of the whole system (which is made of the advertisers and the users), instead of maximizing the probability of an action (click or conversion for instance). We use the simple but powerful idea that users convert when the price is below a stochastic threshold value, the Willingness-To-Pay (WTP) [1], and leverage a mature recommendation algorithm -Matrix Factorization (MF)-to learn the user decision process and the underlying WTP.

We concur with authors in [32] who wrote that "recommender systems serve multiple goals and that the purely user-centered approach found in most academic research does not allow all such goals to enter into their design and evaluation". In the case of online shopping, if the Recommender System is a user assistant, one has to raise the concern of contradictory objectives because on the one hand, the sellers might want to maximize their revenues or profit, and, on the other hand, the user is looking to maximize their utility.

The difference between what the user actually pays and the WTP can be seen as a surplus/utility that the user wants to maximize. On the seller side, we suppose the seller to be a revenue maximizer -we could equivalently suppose a profit maximizing criterion by taking into account the seller's procurement cost. We propose to maximize the total welfare of the system buyer+seller, defined as the sum of the utility of the buyer and the seller. If, when a sale occurs, the buyer's utility is their surplus (WTP -price) and the seller utility is the revenue generated by the sale (the price), then the sum of the two results in the system maximizing the expected WTP.

A shopper's behavioural model 4.1. User Decision Model

In this section, we present a simple model for the user behaviour. Such model can be understood by describing what happens between the moment the user reaches the e-tailer page, to the moment the user leaves or decides to buy something. In this description, we suppose that the user is looking for one specific category of product (for example, a pair of shoes or a mobile phone). By design, our model does not encompass the purchase of several goods, hence while not adapted for grocery shopping, we believe this encompasses a lot of the situations where Recommender Systems play a key role as shopping assistants.

Our main assumption is that while the user browses the e-tailer website -for example, looking for a new mobile phone -, they learn about the different alternatives proposed by the website. More precisely,we suppose that we can infer the awareness set over which the user decides to purchase something, or simply leave. For instance, in order to build the awareness set, one can take the browsing history and add the most popular items in the category, as well as the previous purchases.

By doing so, and assuming the user is rational and risk-neutral, we can define its decision process as choosing the item 𝑗 ⋆ that maximizes their utility over the associated awareness set at time t 𝐷 𝑖 (𝑡) , to which we add the no buy option (by definition, the no buy option brings 0 utility). More formally, we have that:

𝑗 ⋆ (𝑡) ∈ argmax 𝑗∈𝐷 𝑖 (𝑡) 𝑢 𝑖,𝑗 (𝑡),(1)

where 𝑢 𝑖,𝑗 (𝑡) is the total utility of user 𝑖 for item 𝑗:

𝑢 𝑖,𝑗 (𝑡) = 𝑤 𝑖,𝑗 − 𝑝 𝑗 (𝑡),(2)

computed as the surplus between the Willingness-To-Pay (WTP) 𝑤 𝑖,𝑗 and the price 𝑝 𝑗 (𝑡) of item 𝑗 at time 𝑡 . In our case, time 𝑡 is the index of the browsing session, to support the case where the user has performed multiple shopping trips.

Random Utility Maximization/ Matrix Factorization (RUM-MF)

Next, we introduce two additional assumptions that allow us to link the utility maximization to Matrix Factorization.

Gumbel noise

We extend the Equation ( 2) and connect our model with Random Utility Models: we suppose that there exists noise 𝜖 𝑖,𝑗 (𝑡) on the latent variable 𝑢 𝑖,𝑗 , such that at each decision time, the shopper makes their decision based on 𝑢 ˆ𝑖,𝑗 (𝑡) = 𝑢 𝑖,𝑗 + 𝜅 𝑖 𝜖 𝑖,𝑗 (𝑡),, where 𝜅 𝑖 is a positive, scalar model parameter. With this change, the shopper's decision -knowing 𝑖 and 𝑝 -, denoted 𝑥 𝑖 (𝑡) is now random. Also, we suppose the noise samples 𝜖 𝑖,𝑗 (𝑡) to be independent and follow a standard Gumbel distribution, which leads us to the classical softmax decision rule, for 𝑗 ∈ 𝐷 𝑖 (𝑡):

Pr(𝑥 𝑖 (𝑡) = 𝑗) = exp(𝑢 𝑖,𝑗 (𝑡)/𝜅 𝑖 ) ∑︀ 𝑗 ′ ∈𝐷 𝑖 (𝑡) exp(𝑢 𝑖,𝑗 ′ (𝑡)/𝜅 𝑖 ) .(3)

Factorizable form

We suppose there exists a dimension 𝑑, and a d-dimensional vectorial representation of the users 𝑋 𝑖 and of the items 𝑌 𝑗 such that 𝑤 𝑖,𝑗 = 𝑋 𝑖 • 𝑌 𝑗 , where • is the dot product. Such representation is very close to the Matrix Factorization, and can benefit from pre-existing user and/or item embeddings, that can be built for example using clicks, number of co-occurrences, user segmentation or catalog input. With these two assumptions, the decision model becomes

Pr(𝑥 𝑖 (𝑡) = 𝑗) = exp((𝑋 𝑖 • 𝑌 𝑗 − 𝑝 𝑗 (𝑡))/𝜅 𝑖 ) ∑︀ 𝑗 ′ ∈𝐷 𝑖 (𝑡) exp((𝑋 𝑖 • 𝑌 𝑗 ′ − 𝑝 𝑗 ′ (𝑡))/𝜅 𝑖 ) .(4)

It is classical but notable that in our formulation, we get a relation between the utility, and the odds ratio between two alternatives:

log Pr(𝑥 𝑖 (𝑡) = 𝑗|(𝑗, 𝑗 ′ ) ∈ 𝐷 𝑖 (𝑡)) Pr(𝑥 𝑖 (𝑡) = 𝑗 ′ |(𝑗, 𝑗 ′ ) ∈ 𝐷 𝑖 (𝑡)) = 𝑢 𝑖,𝑗 − 𝑢 𝑖,𝑗 ′ 𝜅 𝑖 .(5)

The interpretation of Equation 5is that the odd ratio between two alternatives is fully explained by the difference in utility the two alternatives provide to the user. So if 𝜅 𝑖 is known, we can relate the WTP, the prices, and the odd ratio between two alternatives.

Experiments

While many RecSys performance studies rely on datasets with logged partial feedback to back their claim, such methodology is not adapted to the problem at hand, since we cannot have access to the true WTP in real life datasets. For this reason, we build our own simulated environment in which we observe the behavior of our proposed method against existing state-of-the-art. For more discussion on the use of simulators in the analysis of Recommender Systems, see [33]. For space consideration, we only report here the main insights. The experiments detail as well as the tables of results can be found in the long version of this article as well as in the appendix, that contains an extended version of this section.

Our data generator takes as input the number of users and items, the number of sessions per user, the number of items seen in each session and the dimension 𝑑 of the latent space. It then generates two vectors from a 𝑑-dimensional Gaussian distribution. Those two vectors are then used as means for generating the users and items 𝑑-dimensional representations (by sampling from a Gaussian distribution). Each item's price is set to be revenue maximizing plus uniform noise. Once the items and the users are generated, we generate user sessions by exposing users to random sub-samples of items from the catalog and at the end of each session we run the utility computation to create the session outcome. We implemented our models in PyTorch and used Adam [34] to optimize over a 𝐿 2 -regularized cross-entropy loss.

To compute our metrics, we assume that our recommendations will be shown in slates of various sizes. We use a greedy approach to fill the banner using the top k products ranked by their expected Value per Sale (eVPS): 𝑒𝑉 𝑃 𝑆 𝑗|𝑖 = Pr(𝑢 ˆ𝑖,𝑗 > 0) × 𝑉 𝑎𝑙𝑢𝑒 𝑗 where 𝑉 𝑎𝑙𝑢𝑒 𝑗 is the value of the sale, which can be one of the four: volume (value equal to 1), user's utility, seller's revenue and overall welfare. While the greedy slate-filling approach is not optimal, it is by far the most popular approach and it has been shown in [35] to be a good approximation of the global maximum. To note, because of the greedy strategy, metrics that are not aligned with the user's utility, such as the seller's revenue, might not be monotonous in 𝑘.

We tested the following methods.

• Oracle Represents the best k products for each user, according to the true item features and true user preferences. We run experiments where we rank the products by their user's utility (Oracle-utility) or by the system welfare (Oracle-welfare). • BestOf Returns the k most popular products in the training data, sorted by number of sales.

• RUM-MF Returns the k most likely to be bought products according to the proposed model.

• MF-SM(Softmax) This is the same method as RUM-MF, but without using the price in the model training. As a note, we predict the WTP 𝑤 𝑖 by considering that the innerproduct between the user and item vectors is still approximating the utility 𝑢 𝑖 for the pair and adding the item price to it:

Pr(𝑥 𝑖 (𝑡) = 𝑗) 𝑀 𝐹 −𝑆𝑀 = exp(𝑋 𝑖 •𝑌 𝑗 ) ∑︀ 𝑗 ′ ∈𝐷 𝑖 (𝑡) exp(𝑋 𝑖 •𝑌 𝑗 ′ ) .

• MF-PCLICK Treats every conversion as an independent outcome, similar to Factorization Machine methods used for Click-through Rate Prediction [7]. Since the method is not recovering the willingness-to-pay, only two objectives are available for the slate generation, namely volume of sales and seller's revenue: Pr(𝑥 𝑖 (𝑡) = 𝑗) 𝑀 𝐹 −𝑃 𝐶𝐿𝐼𝐶𝐾 = 𝜎(𝑋 𝑖 • 𝑌 𝑗 ).

Findings

Optimizing for welfare leads to the best welfare output. As expected, optimizing for welfare works and it leads to the best welfare metric, RUM-MF-welfare, surpassing by more than 30% the performance matrix factorization methods (see long version for details).

We also observe that RUM-MF outperforms the other methods not only in Welfare metrics but also in classical Precision and Sales metrics, albeit by a smaller margin. The performance is maintained for slates with k>1 Switching to our formulation can lead to improvements even in the absence of prices. We observe that while not as competitive as RUM-MF, MF-SM outperforms clearly the MF-PCLICK approach. Indeed, even in the absence of prices, the categorical formulation of the problem and the presence of the no-buy option in the model leads to a better estimation of the user's utility vector.

Conclusion

We believe that as new algorithms tend to leverage the price information, welfare maximizing Recommender Systems are likely to become a reality in the near future. Because they will explicitly model the user's behaviour, this new class of RS will allow for a better understanding of the user interaction with the RS. The shift from click maximizer to welfare maximizer will permit a better control of the value sharing between the different stakeholders. Also, we implicitly relied on the classical Luce axiom of independence from irrelevant alternative, which might not be always satisfied. This is, however, a general problem in discrete choice theory that is not specific to our approach, so that one could investigate if the current approach could borrow, for instance, from nested decision models. Our goal was to provide a minimal working algorithm, but in practice such algorithm could be adapted to the available information. For example, if we have access to embedded representations of the user and/or the items (based on clicks or sales or browsing behaviours...), then we can use these representations as inputs in a neural network.