Simple Objectives Work Better, Groupon

Explanation of the paper

Abhay Shukla
May 8 · 7 min read

Can a simpler formulation of objective function achieve better results for online marketplaces? Online marketplaces like Groupon have multiple stakeholders and require addressing objectives of each stakeholder. Researchers at Groupon found that simplifying their objective function improved Conversion Rate by 1.56% and Operational Value of their business by 1.43%.

In this post, we will first cover what multi-objective recommendations in multi-stakeholder systems is and then delve into the contents of the paper.

Multi-stakeholder Systems and Multi-Objective Recommendations

Online Marketplace: Online marketplaces are platforms where merchants and customers meet and make a transaction online which mutually benefits both. Depending on the business there can also be other stakeholders of the system along with customers and merchants. Amazon, Instacart, E-bay are the familiar examples of marketplaces.

Single and Multi-Objective Recommendation: Most popular recommendation methods, e.g. collaborative filtering, focus only on user relevance by optimizing items for clicks or conversions. Single-objective recommendation is a narrow view of the problem in multi-stakeholder systems since it focuses only on customer, ignoring other stakeholders. Obviously, this is not healthy for the system in long term.

An intuitive and popular approach to address objectives of other stakeholders is to take score from user relevance model and modify it to suit the needs of other stakeholders. As a result you get a new relevance score which addresses multiple objectives. To make it concrete take the example where you want to take revenue into consideration when recommending items to users on e-commerce platform. You can modify the user relevance score of an item as,

Where u is user, i is item and betas are the tuning parameters. These parameters can also be thought as levers to control the contribution of each component in calculation of the multi-objective score.

Now we have sufficient background to proceed and discuss the paper Simple Objectives Work Better.

Recommendations in Groupon

Groupon’s search and recommendation engine is called Relevance and it is responsible for finding best deals for customers while satisfying objectives of all its stakeholders. The current multi-objective scorer combines weighted factors, each factor representing some stakeholder. In the paper they describe current objective function and the simplification which gave lift in conversion and operational value.

Ranking Pipeline

The ranking pipeline of Groupon is shown in Figure 1. It consists of two modules or stages:

  1. Response Prediction: An ML model which predicts relevance of a deal to user in terms of probability of click or probability of conversion/purchase.
  2. Optimization: This module takes output by Response Prediction module and modifies this score to make it multi-objective aware using Multi-Objective Scorer. Finally, diversity and fairness of predictions is taken care of by Diversity Management. However, methods involving diversity and fairness are not described in the paper.
Figure 1: Ranking pipeline of Groupon

Usually, diversity in recommendations ensures different relevant options to users while fairness ensures that recommendations are not lopsided towards only a few popular merchants, ignoring the rest.

Visual Algo Treatments are not described in the paper but I assume it could be some kind of dashboard which allows tweaking of levers in recommendations.

ML models used for ranking/predictions (in context of the paper) are Gradient Boosting Machines (GBM).

Current Multi-Objective Scorer

Current Multi-objective scorer in Groupon computes weighted sum of eCVR, Estimated Bookings and Estimated Value.

score = a * eCVR + b * eBooking + c * eValue

where,

eBooking = eCVR * price^{priceExponent}

eValue = eCVR * marginPercentage * price^{priceExponent}

The terms of the scorer are,

eCVR: Estimated conversion rate of a deal for a user.

eBooking: Adjusted expected booking value of deal in $.

eValue: Adjusted expected operational value of deal in $.

The adjustments above are with respect to exponent of price to reduce overpowering effect of high priced deals. a, b and c are the parameters which give relative importance to each component. The paper mentions these values are normalized so its likely that 0 <= a, b, c <= 1 and a + b + c = 1. For new and anonymous users b = c = 0 and therefore the focus is entirely on conversions.

Disadvantages of this objective function: While this approach is flexible and gives levers to tweak scores but according to authors it lacks mathematical rigor and requires one to make complex decisions on selecting correct values to the parameters a, b and c. This is complex because trade-offs between different choices of parameters are difficult to measure.

Simplified Formulation

Simplified formulation estimates bid value or expected gain for each deal as a weighted combination of value contributed towards individual goals. The weights are probabilities of achieving the goal. More concretely, the simplified formulation of objective function is,

Where, g is goal, lambda is the probability of achieving goal g and nu is the value of the goal in $.

Examples of goals are activation, conversion, value and engagement.

While conversion, value and engagement are well known terms; activation is an interesting one. If you have a new user one of the most important goal is to help user make its first transaction or get activated on the platform. However activation could also mean driving conversion of customers who have been dormant on the platform for some period of time.

The interesting thing about simplified formulation is that,

  1. Bid value gives expected value of every deal, while considering value contribution of different objectives weighted by likelihood of achieving them. If there is a trade-off between likelihoods of achieving different objectives, it will be reflected directly on the bid value. However, one must ensure that one objective does not overpower the others and this trade-off actually exists. The authors do not talk about it though.
  2. Components of the simplified objectives are predicted by ML models. So essentially the simplified objective is an ensemble of models combined non-linearly. (Nonlinear because of product terms)

Predicting Components of Simplified Formulation

Probabilities of achieving the goal (lambda’s)

Lambda’s are models predicting probability of achieving a goal. This is in fact straightforward. If the objective is click or purchase then its a binary classification model. The paper mentions these ML models are GBM’s.

This leaves us with goal values.

Value of Goal

The value of goal is estimated by Operational Value.

Operational Value = Unit Selling Price * Quantity + Fees — Open Discount — Closed Discount — Shipping Costs — Transactional Costs

Open discounts are discounts available to users on the platform and closed discounts are discounts available to only some users. I think its fair too assume closed discounts to be targeted discounts sent to users via email or notifications.

Authors mention that Open Discount and Closed Discount are the moving parts in this calculation of Operational Value which need to be estimated from ML models. As a result they train ML models to predict for every deal every day,

  1. % of open discount orders of deal
  2. % of closed discount orders of deal

Using this expected open discount and expected closed discount per deal can be easily calculated as,

OD per deal = min(cost_to_user * OD %, OD$ cap) * OD orders / Total orders
CD per unit = cost_to_user * CD %

Where CD% = closed discount amount / Total amount

The boldfaced percentages are the ones predicted by ML models. The features of the models include:

  1. Lags (past behavior)
  2. Vertical
  3. Vertical sub-category
  4. OD day or not
  5. Day of the week
  6. Week number

For training GBM models data was split into Train (70%), validation (15%), and test (15%) datasets.

Results

Offline Results for OD% and CD%

Baseline model is estimates of OD% and CD% from historical data. A comparison of baseline and ML model on test set for different verticals is shown in Table 1.

Table 1: Comparison of Baseline model and ML model

It is not very clear in that paper whether this table combines results of OD% and CD% models? If it only included one of them, then its more likely that it is for OD% based on Mean of actual % numbers. Whatever is the case, it can be clearly observed that ML model gives better results comparatively.

A/B Experiment Results

A/B experiment was done with 50% population for each variant. The variants were Current Multi-Objective Scorer and Simplified Formulation. The goal for existing customers was only based on operational value maximization and for conversion/activation maximization for new users. The results are,

  • Conversion Lift: 1.56%
  • OV Lift: 1.43%

Summary and Concluding Remarks

The main idea in this paper is to simplify the current Multi-objective Scorer function which uses sum of weighted factors and includes parameters such as a, b, c and priceExponent needing judgement from user of the ranking system.

score = a * eCVR + b * eBooking + c * eValue
[current multi-objective scoring function]

The simplified scoring function is again a weighted sum of factors. However the weights (which are probabilities of achieving a goal) and factors (which are values of goals) are both derived from ML models, thus reducing human judgement and tuning efforts.

simplified scoring function

The paper also talks about future directions at length which I have omitted here.

There is a lot of interesting literature in the domain of Multi-Stakeholder Recommendations and Multi-Objective Optimization in Recommendations. The approach used in this paper an ensemble of models. Principled techniques in this domain use constrained optimization for computing score for (customer, item) pairs. For further reading Click Shaping to Optimize Multiple Objectives is a highly recommended paper.

Nerd For Tech

From Confusion to Clarification

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

Abhay Shukla

Written by

Lead Data Scientist@Airtel X Labs https://www.linkedin.com/in/shuklaabhay/ #DataScience #ML #AI #Statistics #Reading #Music #Running

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store