Groupon is a dynamic two-sided marketplace where millions of deals organized in three different lines of businesses or verticals: Local, Goods and Getaways, using various taxonomies, are matched with customers' demand across 15 countries around the world. Customers discover deals by directly entering the search query or browsing on the mobile or desktop devices. Relevance is Groupon's homegrown search and recommendation engine, tasked to find the best deals for its users while ensuring the business objectives are also met at the same time. Hence the objective function is designed to calibrate the score to meet the needs of multiple stakeholders. Currently, the function is comprised of multiple weighted factors that are combined to satisfy the needs of the respective stakeholders in the multi-objective scorer, a key component of Groupon's ranking pipeline. The purpose of this paper is to describe various techniques explored by Groupon's Relevance team to improve various parts of Search and Ranking algorithms specifically related to the multi-objective scorer. It is for research only, and it does not reflect the views, plans, policy or practices of Groupon. The main contributions of this paper are in the areas of factorization of the different abstract objectives and the simplification of the objective function to capture the essence of short, mid and long term benefits while preserving fairness and moving users forward in the customer lifecycle.
•Information systems → Recommender systems; Retrieval
effectiveness; Computing methodologies; Applied computing →
Electronic commerce
1 This work was done while the author was at Groupon
* © Copyright 2019 for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
1.
Groupon is a large global e-commerce company, operating via the
web and the popular Groupon Mobile App. Currently serving 15
countries and more than 100 million monthly active users
worldwide, Groupon is the place you start when you want to buy
just about anything, anytime, anywhere. Groupon offers physical
merchandise through their Goods business, travel deals through its
Getaways business, and is the market leader in Local e-commerce.
Groupon is trying to develop a robust marketplace, and as such,
needs to understand at an individual level the supply and service
needed to develop a daily habit for the company’s customers.
How does featuring the local burger place down the block
compare to featuring a big chain when it comes to increasing a
user’s future spending? Given the number of local choices, a
customer has, how many Groupon options are provided to
promote a daily habit? When is it appropriate to recommend a
product over a trip? In essence, what are the underlying objectives
and forces that power Relevance, the company’s search and
recommendation ranking engine?
An objective function is a mathematical expression which
implicitly reflects certain tradeoffs for outcomes. The design of an
objective function must take into consideration three important
points. The first is that, as a mathematical object, the outcomes
that one includes must be capable of being quantified. The second
observation is that these outcomes, in addition to being
quantifiable, must also be observable and in certain cases
predictable. The third is that, insofar as an objective function
determines decision making, care must be taken as to which
outcomes are included in light of Goodhart’s Law [
These considerations lead naturally to constraints on the types of factors that can and ought to be included in an objective function and bear on all approaches to designing and iterating on objective functions in concrete ways. 2.
So far all of this is abstract and unlikely to be new to anyone reading this paper, but it is important to get the trivial things out of the way.
Now we consider how these abstractions impact the actual situation faced by Groupon. As a two-sided marketplace, the terms that might naturally exist in any overarching objective function are not hard to conceptualize at a high level: Groupon must please its users, please its merchants, and make a profit. Following the abstractions described in the previous section, such an objective function must take into consideration how these objectives can be quantified, the level of accuracy at which they can be quantified both retrospectively and in prediction, and what distortions these quantifications may introduce to the market’s behavior.
The objective function’s rubber meets the road when it comes to deciding how to allocate limited resources to meet those objectives. In the case of ranking deals, the limited resources are chiefly impressions: we want to allocate these in the most efficient way possible, where the meaning of “efficiency” is more or less defined by optimizing an objective function.
Furthermore, determining relevant deals for a given user at a given time introduces novel constraints on an objective function. In particular, computing such an objective function must be efficient and fast when applied to all eligible deals per user with thousands of requests occurring every second, and furthermore, there must be some mechanism for predicting some terms of an objective function before being able to measure such terms. For instance, we naturally want to weigh the financial benefit of a deal being purchased into a deal’s score. Financial benefit can be easily quantified after the fact. However, predicting a deal’s financial benefit, even assuming it is purchased, can be tricky there are often multiple prices for a given deal, depending on quantity sold, the day of the week you wish to reserve a hotel, different options etc.
So an objective function for ranking deals ought to only include quantities that we can (i) quantify in a clearly defined way and (ii) predict in a clearly defined and accurate way.
The art & science of recommending deals that delight customers is one exercised throughout different touch points on Gorupon’s web and mobile apps. As shown in Figure 1, there are multiple use cases. Whether it's personalized recommendations in the home feed, keyword search, browse or upsell/cross-sell opportunities, ranking deals and other items (e.g query autocomplete) is at the front and center of the user experience and is what Relevance does. While traditional recommender systems generally aim at solving the low-intent “surprise me” recommendation use case, we see the ranking problem as something to solve in multiple places throughout the purchasing funnel continuum. To capture the different aspects of ranking in a multi-stakeholder environment we have modeled the ranking problem as a multi-stage pipeline that combines machine learning (learning to rank or LTR [2]) based predictions with the objective function.
Groupon has a sophisticated real-time ranking pipeline that includes query understanding for search and both response prediction and optimization phases for generating a per-item score, as shown in Figure 2 below, to form a ranked list of deals presented to the user. For a particular set of deals (i.e. the candidate set), a customer and a given context, the output of the response prediction phase is a list of per-deal likelihoods that the customer will view or purchase (i.e. respond to or take action on) the deal that is offered, under that specific context. This likelihood or probability is then used as an input to the optimization stage, which computes a final score that considers multiple stakeholders’ goals in the Multi-Objective Scorer followed by Diversity Management that ensures diversity and fairness.
User response prediction is a central problem in the computational advertising and e-commerce domains. Quantifying user intent allows advertisers and merchants to target offers towards the right users. This leads to a judicious use of marketing dollars and also renders a pleasant user experience.
We believe it is important to highlight how computational advertising, and in particular, response prediction relates to the evolution of recommender systems.
Despite recent advances in context-aware recommender systems [3], traditional item-based and user-based collaborative filtering approaches to recommender systems fail to factor in context, such as time-of-day, geo-location or session-based information to generate more accurate recommendations. Moreover, they also fail to recognize that recommendations don't happen in a vacuum 2 Illustrative only; Groupon may consider different factors. and as such may require the evaluation of business constraints and objectives. With the advent of learning to rank (LTR) and the application of other shallow and deep machine learning techniques to recommender systems, the world of recommender systems, advertising and e-commerce has finally converged [4][5]. In order to produce meaningful features used as input to an online response prediction model, we developed and deployed ML models used to generate offline deal features, such as Deal Quality Score (DQS), a prior computed for each new deal, distance and customer-gender triple, as well as Customer-Deal Interaction models that use more traditional Collaborative Filtering (Matrix Factorization [6]) techniques to establish deal-category propensity used as customer features. More recently, we have been experimenting with deep learning and the implementation of an embedding framework to generate item (deal, user, context and combined) embeddings similar to those developed at Pinterest [7] and Twitter [8].
As shown in Figure 2, the final response prediction scores are computed using a shallow, low-latency oriented Gradient Boosting Machine (GBM) [9] that takes in a few raw and some engineered Context, Deal and Customer features and produces an online score per each qualified deal in a LTR plugin we developed and use in Groupon’s ElasticSearch deal catalog cluster.
Simply put, the multi-objective scorer is implemented as a weighted average of all the different factors signifying the needs of each of the stakeholders. The factors considered in the objective function are: 1.
eCVR (estimated Conversion Rate): This score is Groupon’s prediction for the likelihood of a transaction of this deal by this user. The score is the output of all relevance machine learned models that includes multiple features.
Estimated Bookings: The estimated booking is factored in to solve for the business objective of optimizing bookings in addition to conversion. This factor is calculated using the price of the deal and the estimated conversion to evaluate the likely amount of booking $.
Estimated Value: Similar to estimated booking, estimated value is also a business objective that aims to incorporate net value into the mix. This factor is calculated using a predicted $ operational value (OV) for each deal adjusted by the estimated conversion to evaluate which deals have the highest potential to contribute to company goals. It is important to note that the scope of the scorer is to determine which deals are more likely to contribute to company goals relative to other deals, and not as a tool to forecast actual impact to those goals.
The function as implemented is defined below where ● ● score = a * eCV R + b * eBooking + c * eV alue eBooking = eCV R * priceprice_exponent eV alue = eCV R * margin% * priceprice_exponent ● ● ● ● ● ● b = bid value/expected gain , g = goal/action , λg = probability of achieving goal/action happening , vg = value/gain f rom achieving goal/action happening (in $ amount) Examples of such goals include, but are not limited to:
Activation: The meaning of activation varies according to user segments. It can be defined as a sign-up action for anonymous users, first purchase for new users who have already signed up and first purchase after 365 days of inactivity for reactivatable users. We definitely want Groupon users to perform the activation action associated with their respective segments.
An alternative/normalized Form of Objective Function:
score = eCV R * ( a + priceprice_exponent * ( b + c * margin%)) Here are a few key points to highlight about the various factors: These values of these components are context specific to provide flexibility to match specific goals for each context.
Price used in the calculation above is adjusted with an price_exponent to reduce its overpowering effect for high priced deals.
The price and margin for the deals are calculated based on the nuances within each channel or vertical.
The constants used as weights (a,b and c in the equation above) are normalized and represent the post-normalized relative importance given by the business to orders/purchase velocity (conversion), revenue for the merchant (bookings) and revenue for company (margins%). In this paper, we do not use any other business metrics and/or constraints used to optimally compute these values.
For new and anonymous visitors, the emphasis is entirely on conversion in order to drive activations.
While this approach provides the necessary levers to adjust the scores for different use-cases and scenarios, it is complex, requires interpretation of the input price and margin data, it lacks the mathematical rigor that clearly states the measurable trade-offs and allows for optimizing the objectives of multiple stakeholders. 5.
A more simple and principled formulation of Groupon’s objective function, used in computational advertising, is to produce a bid or score that represents the expected gain (in $ amount) for each deal-impression based on goals/actions and the probability of achieving the goals:
Considering that these are goals that we will consider for our v0 version, we need to define λg and vg for each goal g.
Given the simplified formulation, the challenge can be divided into two: a) build a model to estimate the probability of the action/goal occurring and b) build a separate model to estimate the actual value of the action/goal, should it occur. Going back to the original multi-objective formulation, price and margin are used for margin value estimation, whereas a machine learning model trained on impression and purchase data is used to predict the likelihood of a customer buying a deal. However, there are many factors, other than price and margin, that may affect the true value of the transaction. For example, there are additional processing/booking fees, marketing costs (i.e. discounts) and variable considerations that can affect the value of a transaction and are vertical dependent.
To deal with value estimation, we utilize the concept of Operational Value or OV. The table below contains the main assumptions and components of OV:
OD stands for Open Discount, which is available on Groupon.com via promo code for all the users on a given day, and CD stands for Closed Discount, which is available through marketing/targeting the customers based on marketing strategies, and it is available only for certain set of customers not everybody.
While most of the variables to OV are direct inputs calculated per their definition on aggregated and historical data, OD and CD need to be predicted as there is no way to know beforehand whether a customer will use a promo code or will be targeted for additional marketing discounts. 3 Operational Gross Revenue, Operational Net Revenue, and Operational Value are not financial measures under GAAP and are not intended as a substitute for revenue or other financial metrics reported in accordance with GAAP. ● ● ● ● ● ●
Percent of orders that will use an open discount (when available) ○
OD orders pct = orders with open discount/ total orders ○ OD per unit = min(cost_to_user * OD %, OD
$ cap) * OD orders pct Closed discount as a percent of the Sell Price (applicable for all days) ○ CD pct = closed discount amount/ total
amount ○ CD per unit = cost_to_user * CD pct For this, the data is aggregated at deal level and day level for OD and CD separately. We then constructed this problem as a
OV can be easily calculated in hindsight. However, during the scoring time, not all data is statically available. The predictive OV model predicts tomorrow’s OV per unit for each active deal option factoring known business changes (e.g. discount campaigns) and uploads the data for relevance to use in tomorrow’s live ranking of deals.
This data aims to replace both financial components of the objective function (margin and sell price) as Predicted OV better approximates a deal’s potential value to Groupon.
In the overall OV calculation, the predictive components are only OD amount and CD amount. Our target variables for the ML model are OD orders percent and CD percent.
The model calculates as many values as possible by inputting data points specific to each deal from standard data sources and only predicts values when no standard data sources are available (e.g. Open Discounts).
A primary factor that impacts a deal’s OV from one day to the next is discounting.
The ML model used for predicting the percentage of orders that will use an OD code and the average CD percent is also a GBM. Important features are found to include, among others, the following: time-series regression problem with historical information as independent variables. As data we considered the sample of 1.2M data points out of around 20M data points. The population dataset is for 1 year of data. Split the data into Train (70%), validation (15%), and test (15%) datasets.
We used a GBM model to train the data and performed regularization to generalize the model using a validation set Finally, all the metrics shown in the presentation are as per the performance on hold out (test) dataset
As a baseline, we used a model that calculates the percentage of OD orders and CD based on the average of the past behavior. Overall average OD orders percentage is 29% per deal (average % of entire data).
R2 = 2.5% RMSE = 39%
MAE = 28% For deals with avg total orders per day >= 5, R2 = 41%, RMSE = 21%, MAE = 14% (around 16% of test data) (actual mean = 24%) For deals with avg total orders per day >= 15, R2 = 56%, RMSE = 14%, MAE = 8% (around 4.5% of test data) (actual mean = 16%)
R2 = -16%, Adjusted R2 = -16% (n = 230k, k = 6) RMSE = 8%
MAE = 3% For deals with avg total orders per day >= 30 (actual mean = 1.2%), R2 = 4.5%, RMSE = 2.77%, MAE = 1.39% While our primary metrics are MAE and RMSE, we are using R2 to track model fit and it’s especially useful for comparing category level model fit. The R2 values are low (or negative) as the straight line average method based on historical data is a very poor fit.
For predicted OD orders percent (actual mean of the entire test data = 29.6% per deal)
R2 = 22% RMSE = 35%
MAE = 27% For deals with avg total orders per day >= 5, R2 = 50%, RMSE = 19%, MAE = 13% (around 16% of test data) (actual mean = 24%) For deals with avg total orders per day >= 15, R2 = 65%, RMSE = 13%, MAE = 7% (around 4.5% of test data) (actual mean = 16%) We can observe that, prediction accuracy increases as avg total orders per day increases. 4 To do the evaluation we used standard statistical metrics for regressions, such as Root Mean Squared Error (RMSE), Mean Averaged Precision (MAE) and Coefficient of Determination (R2).
For Predict CD percent (actual mean of the entire test set = 1.69% per deal) ● ● ●
R2 = 8.5% RMSE = 7.3%
MAE = 2.7% For deals with avg total orders per day >= 30, (actual mean = 1.2%), (around 1.7% of the test data), R2 = 30.1%, RMSE = 2.2%, MAE = 1.1%. As seen in Table 4, the ML Model improved the baseline model in all the metrics (RMSE, MAE and R2 ), especially for the Getaways vertical where discounts typically have a higher impact on the bottom line.
We also conducted a full A/B tests at 50/50 split of customer sessions on web and mobile traffic where we substituted the previous multi-objective scorer with the simplified objective function based only on value maximization for registered users (existing customers) and conversion/activation maximization for non-registered (new users). This resulted in improvement for all verticals with an overall statistically significant lift of: ● ●
OV Lift: 1.43% We believe that these results stem from improved financial estimates used for this experiment as well as the use of a simpler optimization function that has less moving pieces but is more in line with clear goals and objectives.
In this section, we discuss various future directions we will be investigating. 9.1 Moving Users Through the Customer Lifecycle Let’s first identify the stage at which a user currently is, in their customer lifecycle. Then, identify the event (quantifiable) that would push the user to the next stage. Finally, consider this event as an objective and optimize for it. In other words, use a different objective for a different cohort of users based on where they are currently in their customer lifecycle. One of the main advantages of this approach is that it eliminates the manual procedure of determining the weights present in our base approach. Once the objective is clear for each cohort of users, we can use the simplified formulation to combine multiple objectives according to the goals that correspond to the given cohort.
Amongst the challenges, we need to create cohorts representing stages of customer lifecycle like that shown in Fig. 2 and we need to figure out a quantifiable objective for each cohort. As seen above in Table 5, multiple different objectives can be applied to a different cohort of users to move them through the customer lifecycle. 9.2
We can think of objective as some parametric function of multiple objectives e.g. Financial Value, Repurchase Tendency, Expected Margin, etc. Our task is to find a set of parameters that maximize the value gained from ranking produced by this function subject to a constraint that the distance between the list ranked purely by e-CVR and the one ranked by the output of this function is less than some acceptable value.
This is similar to the approach presented in Multiple Objective
Optimization in Recommender Systems [
The form of objective would something similar to the following: max AGk[ f (E[P rof it], E[M argin], ..., α, β, γ, ...) ] s.t. N DCG[ f (E[P rof it], E[M argin], ...), f (eCV R)] > Δ 1 AGk(f ) = |queries| |queries| ∑ q=1
k 1k ∑ f (q, πi(f , q)) i=1 where π(f , q) is ranked list produced for user q by ranking function f .
Given this form, we can make the constraint Δ stricter or relaxed for different user segments based on what kind of treatment we envision for these segments.
We can re-use our offline evaluation framework to measure the
distance between two ranked lists (e.g. MAP[
In addition to estimated CVR (e-CVR) and estimated Value (eValue) which we have already optimized for, we could also consider the following factors as goals/estimates in Groupon’s objective function: ● ● ● ●
Estimated CTR (e-CTR): An estimate of the click through rate that can be a proxy to measure customer engagement. However, we need to evaluate if it is redundant or adds valuable information along with e-CVR.
Affinity to Cause Revisit: A measure of the capability of a deal to create a likeability towards the company which causes the user to come back.
Price: Absolute Price/Price Range is a measure of revenue. Moreover, at a user segment level, there could be certain segments whose behavior is highly correlated to price changes while some segments which are more agnostic to price changes. How the learned weight on this factor plays out for different user segments could be insightful.
Merchant ROI: In addition to increasing sales and other reasons, merchants sign up with Groupon to a) bring in ● ● more new customers and b) to have customers come back again and again...
Available Merchant Inventory: Groupon might not want good deals to sell out fast to maintain a rich inventory of good deals at all times. Groupon might also want to reserve these good deals to activate/reactivate users by limiting their exposure to power users. Some measure which represents the selling rate/inventory left.
Exposure to categories: A combination of a user’s affinity to explore and exploration level in the deal’s category. We might want to do more exploration for power users to gain more confidence in a deal’s performance but not so much for less active users. 10. Conclusion In this paper, we first described considerations we took at Groupon when defining an objective function designed to calibrate the score to meet the needs of multiple stakeholders in the company’s two-sided deal marketplace. We then described the logic behind the multi-objective scorer which is part of Groupon’s current ranking pipeline. Subsequently, we provided a simplified formulation of the objective function, making more principled and centered around the concept of expected gain. To optimize the outputted ranked list of deals-impressions the function produces a per-deal bid/score that represents the expected gain (in $ amount) for each deal-impression based on given goals/actions and the probability of achieving such goals.
Focusing first on maximizing conversion and financial value we went ahead and defined Operational Value (OV) as a unified calculation of value per deal to be plugged into the simplified objective function. We then trained, built and evaluated a separate machine learned Gradient Boosted Machine (GBM) model to estimate the percentage of users exposed to open/closed discounts, a key component in the OV estimation.
Finally, we reported experimental results and discussed future directions.
This paper has been kept intentionally broad and does not describe in detail any specific product feature nor does it promise the delivery of one. It bears no direct influence on the Relevance development roadmap or any other Groupon products for that matter. It is a research paper, exploratory in nature, that represents the discussions and ideas solely attributed to the authors and does not represent the views, plans, policies or practices of Groupon. As used herein, “we” and “our” means the authors of this paper and not Groupon or any of its subsidiaries. [12] Normalized Discounted Cumulative Gain (NDCG) [https://en.wikipedia.org/wiki/Discounted_cumulative_gain#Normalized_DCG ]