Optimizing Multiple Performance Metrics with Deep GSP Auctions for E-commerce Advertising

As shown in Fig. 1, we describe a typical ad platform architecture in e-commerce advertising. There are $N$ advertisers compete for $K\leq N$ ad slots, which are incurred by an ad request from the user. Each advertiser $i$ submits bid $b_{i}$ to participate in the auction, usually based on her private valuation $v_{i}$. We note that $b_{i}$ does not necessarily equal to $v_{i}$. We use vector $\mathbf{b}=(b_{i},\mathbf{b}_{-i})$ to represent the bids of all the advertisers, where $\mathbf{b}_{-i}$ represents the bids from all the advertisers except $i$. The response prediction module predicts the user response probabilities (e.g., $pCTR$, $pCVR$, etc.) on the candidate ads. These predictions, together with the bids $b$, could be used by the auction mechanism module, denoted by $\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle$, for top-$K$ ads selection and payment calculation. We use $\mathcal{R}_{i}(b_{i},\mathbf{b}_{-i})=k$ to denote that the advertiser $i$ wins the $k$-$th$ ad slot, while $\mathcal{R}_{i}(b_{i},\mathbf{b}_{-i})=0$ represents the advertiser loses the auction. The $K$ winning ads would be displayed to the user. The auction mechanism module further calculates the payment for the winning ads following a payment rule $\mathcal{P}$. Let $\mathcal{P}_{i}$ be the payment charged to advertiser $i$, and thus her utility is $u_{i}=v_{i}-\mathcal{P}_{i}$. Finally, the performance metrics can be obtained from the payments of the displayed ads and the responses from users after seeing the ads. In this paper, we focus on designing an ad auction mechanism to optimize $L$ performance metrics, which can be expressed as functions ${\{f_{j}(\mathbf{b};\mathcal{M})\}}_{1}^{L}$. We explicitly show the performance metrics depend on the bidding profile and the deployed auction mechanism.

Based on the concepts discussed above, we formulate the considered problem as multiple performance metrics optimization in the competitive advertising environments. Given bid vector b from all the advertisers and $L$ ad performance metric functions ${\{f_{j}(\mathbf{b};\mathcal{M})\}}_{1}^{L}$, we aim to design an ad auction mechanism $\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle$, such that

where $\mathcal{D}$ is the advertisers’ bid distribution based on which bidding vectors $\mathbf{b}$ are drawn. The objective is to maximize a linear combination of the multiple performance metrics $\{f_{j}\}^{L}_{1}$ with preference parameters. By choosing different $w_{j}$’s, we can design auction mechanisms to make various trade-offs among performance metrics. In this paper, we assume $w_{j}$’s are the inputs in the problem formulation, and focus on the ad auction mechanism design. There are extensive related works on how to determine $w_{j}$’s and derive Pareto-efficient solutions (Lin et al., 2019; Chen et al., 2017). We consider some desirable properties, i.e. Game Equilibrium and Smooth Transition, when designing an ad auction mechanism. There are several equilibrium concepts from game theory for auction design, e.g., Nash Equilibrium (NE) (Varian, 2007) and Incentive Compatibility (IC) (Myerson, 1981). IC is a desired economic property for auction design in competitive environments. Intuitively, an ad auction mechanism is IC, if all the bidders truthfully reveal their private valuations. The IC mechanism would remove the burden of considering bidders’ strategic behaviors, leading to reliable and predictable inputs for ad performance optimization. Therefore, the IC auction mechanisms could promote the long-term prosperity of the advertising ecosystem (Hammond, 1979).

The most well-known sufficient condition for an IC auction mechanism is the classical Myerson Theorem (Myerson, 1981). We first present this condition in the context of single slot ad auction.

For the multi-slot case, we turn to a widely used solution concept in the ad industry: Symmetric Nash Equilibrium (SNE).

Another desirable property we want to achieve is Smooth Transition (ST). As discussed in Section 1, the performance objectives of the ad platform may vary due to the change of the business logic. If the new optimization objective is quite different from the previous one, the resulting auction mechanism would significantly affect the advertisers’ utilities  (Bachrach et al., 2014). This introduces the chaos of the auction environment. To stabilize advertisers’ utility change under different mechanisms, we choose a benchmark mechanism $\mathcal{M}_{0}$, and require advertisers’ utility under the new mechanism should not be less than $1-\epsilon$ of that under $\mathcal{M}_{0}$. The benchmark mechanism $\mathcal{M}_{0}$ could be the currently deployed mechanism. Specifically, we define the Smooth Transition constraint as follows:

where we set a lower bound for advertiser $i$’s utility ${u}_{i}$ when selecting a new auction mechanism $\mathcal{M}$. The lower bound $\bar{u}(\mathcal{M}_{0})$ could be set as the average utility over a certain period under the benchmark mechanism $\mathcal{M}_{0}$. The parameter $\epsilon$ is a tolerant utility loss ratio for advertisers ($0\leq\epsilon\leq 1$). By choosing an appropriate $\epsilon$, the advertiser’s utility would not fluctuate too much when the auction mechanism is switched towards optimizing another objective.

Classical approaches from mechanism design usually resort to the reliable prediction model for performance metrics, and search for the solutions by simply maximizing the expected performance objective (Bachrach et al., 2014). However, precise predictions are intractable, especially when some performance metrics are related to the long sequential user interactive behaviors.

We follow the design rationale of the classical GSP auction mechanism (Lahaie and Pennock, 2007), where the allocation scheme is to rank advertisers according to their rank scores with a non-increasing order, and the payment rule is to charge the winning advertiser with the minimum bid required to maintain the allocated rank position. The rank score of the classical GSP auction is the product of the bid and the ad quality, which can only optimize certain performance metrics, such as social welfare or revenue. To optimize multiple ad performance metrics, we leverage the deep learning technique to design a new rank score and integrate it into the GSP auction framework. We call this new mechanism Deep GSP auction. Specifically, we design a deep neural network to map advertiser’s bid to a rank score, with the consideration of various related information, such as ad features (ads category, $pCTR$, and $pCVR$), user profile (gender, age, and income) and advertiser preference (budget, marketing demands). We use $r_{i}=R_{\theta}(b_{i},\textbf{x}_{i})$ to denote this new rank score, where $\textbf{x}_{i}$ represents the related features except the bid. The training of this deep rank score model is under the guideline of the optimization objective in problem (1). In order to satisfy the game equilibrium constraint, we also require the mapping function $R_{\theta}(b_{i},\textbf{x}_{i})$ to be monotone with respect to the bid $b_{i}$. We would discuss how to train the model to satisfy this property later.

With this new rank score, the allocation scheme and payment rule in Deep GSP auction can be summarized as follows:

• •

  Allocation Scheme $\mathcal{R}$: Advertisers are sorted in a non-increasing order of new rank score $r_{i}=R_{\theta}(b_{i},\textbf{x}_{i})$:

  $$r_{1}\geq r_{2}\geq\cdots\geq r_{N}.$$

  The advertisers with the top-K scores would win this auction. Ties are broken arbitrarily.

• •

  Pricing Rule $\mathcal{P}$. The payment for the winning advertiser $i$ is calculated by the formula:

  (6)

  $$p_{i}=R_{\theta}^{-1}(r_{i+1},\textbf{x}_{i}),$$

  where $r_{i+1}$ is the rank score of the next highest advertiser, and $R_{\theta}^{-1}(\cdot,\textbf{x}_{i})$ is the inversion function of $R_{\theta}(\cdot,\textbf{x}_{i})$.

The remaining question is how to train the deep neural network model with the monotone property, and how to efficiently calculate the inverse operation in payment rule.

As introduced in Section 2.2, some performance metrics are not feasible to have rigorous mathematical analyses, and we can only evaluate these metrics via actual feedback from the system after deploying the auction mechanism. This phenomenon is similar to the exploration process in reinforcement learning, where we need to conduct actions to observe the actual reward. With this connection, we formulate the training of the deep rank score model as a reinforcement learning problem and solve it via model-free policy optimization. As shown in Fig. 2, we introduce a concrete optimization framework to implement the Deep GSP auction and illustrate the detailed procedure. Given bid vector b of all the advertisers drawn from $\mathcal{D}$, we define the concepts of state, action, reward, and transition.

• •

  State: The state $s_{i}$ would reflect the quality of ad opportunity and the status of auction environments. We consider the following information to represent state: 1) Ad information, such as bid, $pCTR$, $pCVR$, and ad category. 2) Advertisers’ information, like the current budget, the price of products, and marketing intent. 3) User features, such as gender, age, income level, shopping preferences, and etc. Concretely, for ad $i$, $s_{i}$ equals to $(b_{i},\mathbf{x_{i}})$, which is defined in Section 3.1.

• •

  Action: The action $a_{i}$ is the outcome of the deep rank score model with the state $s_{i}$ as input, that is the rank score $r_{i}$ in Eq. (8).

• •

  Reward: After taking actions (obtaining rank scores), we run Deep GSP auction and observe performance metrics’ realization. We calculate the linear combination of these performance metrics and apply reward shaping strategy to incorporate the ST constraint into the reward, which is incurring a large penalty coefficient $\eta$ if this constraint is violated:

  (11)

  $$\quad\quad\quad re_{i}=F(\mathbf{b};\mathcal{M})-\eta\times\max(0,(1-\epsilon)\times\bar{u}_{i}(\mathcal{M}^{0})-u_{i}(\mathcal{M})),$$

  where $F(\mathbf{b};\mathcal{M})=\sum_{j}w_{j}\times f_{j}$ is the optimization objective, i.e. performance metrics defined in Eq. (1). We assume all the ads, no matter winning the auction or not, contribute to the auction outcome equally and share this global reward.

• •

  Transition: Since our model training is a single-step decision making problem, we can derive the policy without considering the transition dynamics.

The goal is to learn an optimal rank score policy $R_{\theta}^{*}$, which is defined in Eq. (8), that maximizes the expected reward, i.e.,

Since the optimization algorithm is orthogonal to our proposed Deep GSP auction, any continuous policy optimization method can be used. In this paper, we adopt an actor-critic based approach: Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015). In our context, the update rules of critic and actor model in DDPG are as follows:

where $\gamma$ is a hyperparameter that modulates the monotonicity constraint applied to the deep rank score model (i.e. actor model).

Our algorithm is different from the vanilla DDPG in two aspects. i) As we formulate the optimization of Deep GSP as a single-step decision making problem, the ground truth for critic $Q$ in Eq. (13) is the reward function solely, in contrast to the bootstrapping form of next state value estimation using target network (Lillicrap et al., 2015). This allows us to pre-train a critic model with log data simply by regression, which extremely improves the sample efficiency. ii) Besides the policy gradient, the actor model training also contains a point-wise monotonicity loss in Eq. (15). However, these variations do not prevent us from using the standard training pipeline of DDPG (Lillicrap et al., 2015).

We present the online performance of the proposed Deep GSP auction in Taobao ad platform. The deployment has the following details. (i) We use an open-source real-time log-processing framework, Flink (Carbone et al., 2015), to build the online stream process, which includes auction logs collection, real-time state construction, and metrics calculation. (ii) The critic and actor of the deep rank score model are trained on a Tensorflow-based distributed training framework. (iii) The exploration in policy optimization is done by deploying a separate online bucket, with random noise added on the actor output. (iv) In order to respond to the dynamic nature of the online auction environment more quickly, the deep rank score model will be updated every 15 minutes. (v) In the online engine, there are tens of thousands of traffic requests every second for the Deep GSP service, and each request contains an average of 400 ads. After the parallelization and calculation optimization, it takes about five milliseconds for each request to be processed.

We consider five metrics, i.e., RPM, CTR, ACR, CVR, GPM, and conduct online A/B tests with several combinations of these metrics. Table 4 shows the online A/B test with 1% of whole production traffic in August 1, 2020. We use GSP as the baseline, and present the relative improvements in the table. As the online platform contains millions of user requests every day, the results can prove stable. From Exp 1 - 5, Deep GSP makes it possible to get high performance of CTR, ACR, CVR, GPM at a low cost of RPM. From Exp 6, we find the platform’s revenue (RPM), the user experience (CTR, ACR, CVR), and overall GPM achieve a reciprocal win-win situation.

Next, we verify the effectiveness of smooth transition between auction mechanisms in the online production. We observe the influence on the advertisers’ utility when the mechanism switches from CTR objective to RPM objective by adjusting $\epsilon$ from $0.0$ to $1.0$. In Fig. 5, we find that the advertisers’ utility (blue line) moves downward gradually along with the increase of $\epsilon$. Therefore, Deep GSP can accommodate switching between even incompatible objectives, ensuring the advertisers’ performance will not immediately fluctuate too much.