{'fraction_non_alphanumeric': 0.027355478244292998, 'fraction_numerical': 0.009674498403469475, 'mean_word_length': 4.76800439802089, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic Reserve Price Design for Lazada Sponsored Search

In ecommerce platform, users will be less likely to use organic search if sponsored search shows them unexpected advertising items, which will be a hidden cost for the platform. In order to incorporate the hidden cost into auction mechanism which helps create positive growth for the platform, we turn to a reserve price design to decide whether we sell the traffic, as well as build healthy relationships between revenue and user experience. We propose a dynamic reserve price design framework to sell traffic more efficiently with minimal cost of user experience while keeping long term incentives to the advertisers to reveal their valuations truthfully. A distributed algorithm is also proposed to compute the reserve price with billion scale data in the production environment. Experiments with offline evaluations and online AB testing demonstrate that it is a simple and efficient method to be suitably used in industrial production. It has already been fully deployed in the production of Lazada sponsored search.


INTRODUCTION
Advertising takes an important role in Internet companies like Google and Meta, and it's also the most efficient strategy of monetization in e-commerce platforms such as Amazon, Taobao and Lazada. As we know, building the flywheel to make an e-commerce platform continually grows is to build up a closed-loop among monetization, user growth, and platform traffic & Gross Merchandise Volume (GMV), which shows in figure 1. When money made by ads is invested into user growth, the new or retained users' contribution to GMV can make the platform more valuable to sellers. However, people agree that search ads will hurt user experience and GMV. The first reason for this is the different targets monetization team and organic search team set, the former tries to optimize cost per mille (CPM) while the latter focus on optimizing GMV per mille (GPM). The second reason is that ad items are far less than what are in organic search. But if we keep filling more, the marginal value of ads will decrease, which will finally do harm to the platform. Therefore, building relationship between user experience and revenue when we fill ads is necessary and important. Furthermore, methods that fill ads dynamically are a better way to boost revenue with little loss of user experience. Auction mechanisms, such as reserve price design, can be used to achieve the purpose.
Usually, conversion rate (CVR) or click-through rate (CTR) threshold is used to decide whether we sell the traffic, but it will impose a negative impact on advertisers especially when they are new or put new commodities on shelf because of the uncertainty of estimation. Under the mechanism, no matter how much advertisers raise their bid price, they will not get the traffic and finally quit the campaign. Other methods like [28] try to design a mechanism that encourages advertisers to create an experience for users that maximizes efficiency, but it doesn't work well when ad supply is not sufficient in some traffic because poor quality ads with low bids still have the opportunity for impression. In this paper, we design a framework that generates dynamic reserve price to build the relationship among revenue, user experience, and monetization ratio 1 from the aspect of traffic while keeping the incentive-compatible as well. To compute the reserved price on a large scale of data, we propose distributed algorithm, which can also be used in different problems with the same form.
From the perspective of reserve price design, to maximize the revenue earned in a general second price auction (GSP), the platform can set reserve price and not make any allocations when the bids are low [22]. Lots of work have done to find the optimal reserve price to improve platform revenue from the perspective of advertiser and keep the incentive ability to prevent bid shading issues. A widely used method is based on advertiser's history behavior [14]. In order to estimate the value distribution, the idea is to use advertiser's history of the bids. However, there are two drawbacks of this kind of method, one is that it uses advertisers' original bid to calculate the reserve price, which makes us more careful about the incentive problems. Another one is, for an e-commerce platform, what we sell to the advertisers is the user at different times, which have very different values. It's scarcely possible to estimate the optimal reserve price in practice due to the data sparsity issue. In 1 Monetization ratio defines how much traffic we used to do advertising Figure 1: The flywheel to make e-commerce platform continually grow arXiv:2206.10295v1 [cs.GT] 21 Jun 2022 our proposed method, we rethink the reserve price design from a traffic perspective, and we can prove it's the near-optimal choice to maximize expected cost per mille (ECPM) under different kinds of platform constraints. Moreover, it's also very easy to prove the incentive compatibility property.
Our contributions can be summarized as follows: 1) We design dynamic reserve price to build the relationship between user experience and revenue to make the most of the traffic with incentive compatibility. 2) We proposed distributed algorithm to handle the scalability issues, and it can also be used in problems with the same form. 3) We conducted offline and online experiments to evaluate the effectiveness of the method. In conclusion, it's a very useful method to decide whether we should reserve the traffic to deal with the hidden cost of sponsored search.

PRELIMINARIES
A typical description for auction pipeline shows as figure 2, there're advertisers in sponsored search scenario to compete for traffic. Due to the intention expressed by the user through a search query, only ≤ suitable advertisers can participate in one traffic competition. And for each traffic , ∀ ∈ [ ], using a second price auction, we allocate the traffic to the advertiser who has the highest . we can estimate the to define the potential revenue we can get, where is in cost per click (CPC) model and is the winner advertiser's bid for traffic , more specifically, the entire revenue can be denoted as where is the decision variable to decide whether we reserve the traffic, = 1 denotes sell otherwise we reserve it. And if there's no other control strategy, the traffic will be filled by ads as much as possible. However, more ads fill means greater potential for compromising the user experience, because the marginal value of ads will decrease.

Problem Formulation
As we discuss above, we need to figure out the relation between revenue, user experience, and monetization ratio, so global platform constraints have been added as equation [3][4][5]. We assume that all estimated value is accurate enough to reflect the true probability, which means the CTR can represent the true probability of click-through rate, and the others are similar. We only discuss the reserve price mechanism design without considering the estimation uncertainty. Consider the problem as an optimization problem with platform metrics constraint, such that where , means the lower bound of CTR and GPM respectively, which denote user experience constraints, and is the upper bound of ads impression that can also be used to control the user experience. The most important part of the ads platform is the monetization ratio, which is / and needs to be controlled very cautiously. It's the basic 3 platform constraints, at the same time, we can also add other constraints if it can be written in a linear form.

Lagrangian Duality
The traffic is very large in sponsored search scenario generally. The scale of the problems we aim to solve should give the solution with distributed cluster rather than a single machine. In this part, we introduce the form of reserve price design with derivation, at first. and then describe the distributed solution.
We rewrite the problem above in a more general form where denotes the constraint size, usually, the constraint is less than 10 in practice. Using the Lagrangian decomposition [16], We define so we have the Lagrangian relax form and the Lagrange multipliers . corresponding to the inequality constraints =1 are restricted to be non-negative, .
based on the KKT condition [18], the optimal solution for the above problem satisfy So, to maximize ( ; ) with a fixed , we only need to select the positive adjust-cost by the decision variable , which can be interpreted as therefore, bringing the problem defined in section 2.1 into equation 18, the dynamic reserve price can be interpreted as follow where 1 , 2 and 3 is the Lagrangian multiplier 2 for constraint 3-5 respectively

Distributed Algorithm for Dynamic
Reserve Price 2.3.1 Dual Descent Dynamic Reserve Price (D3RP). First, we consider the dual descent algorithm [21]. According to the decomposability of the Lagrangian dual problem, we can get the solution of the traffic level decision variable parallelly. By using the dual descent algorithm, which is an iterative procedure based on the decomposability of the dual, we can get more optimal Lagrangian multipliers. After we calculate using equation 18, the Lagrangian multipliers can be updated as follow: where is the learning rate for each iteration, and ∈ [0, ] denotes the iteration step, where is the maximum iterations. In algorithm 1, we introduce a distributed version of dual descent to calculate the dynamic reserve price. Particularly, in each iteration. 1) first we use map op in Spark to calculate independently for each traffic, and then we can get the traffic gradient coefficient for each Lagrangian multiplier. 2) we use reduce op to sum all gradient coefficients and collect to the driver to update using dual descent as equation 20. 2 can be interpreted as the shadow price or marginal utility of the metrics we want to control. . we can see that the algorithm above is simple and efficient enough, however, it requires setting the learning rate manually, which would be many and diverse. especially, if we try several settings of hyperparameter in computationally intensive scenarios with a large scale of data, it will waste lots of calculation resources. So we propose a method using coordinate descent algorithm [20] to calculate the reserve price, which updated one multiplier and keeps the other fixed. To avoid the setting of the learning rate, our method prepares an ordered collection of firstly and then selects the minimal , which can make the primal problem feasible. We reorganized the subproblem, and write it in the form of a coordinated update as follows let ( ′ ) = + =1, ≠ ′ + ′ ′ , ∀ ∈ [ ], according to equation 18, the decision variable is only related to the sign of the coefficient function ( ′ ), the interaction with the horizontal axis can make the decision variable change, so the ordered set of can be defined as and we can see that is a number of billion-scale, the candidate set of is the same order of magnitude as . So search algorithm with time complexity ( ) is unacceptable. We can design dual binary search (DBS) to find the temporary optimal if the primal problem is feasible.
More specifically, the procedure of the algorithm 2 shows below: 1) we calculate sorted candidates of Λ by equation 23 in parallel, 2) use binary search to find the minimum threshold to guarantee the constraint not less than and then update .

Incentive Compatibility Discussion
Incentive compatibility is the most important feature for reserve price design, as the bid of an advertiser may determine the price he pays in future auctions, if we don't design the reserve price with incentive compatibility, it may lead the advertisers to shade their bids and finally result in a loss in revenue for the platform. In this part, we prove the incentive compatibility of our design of reserve price. Consider one advertiser in an auction of traffic , ∀ ∈ [ ] and assume that the other advertiser will be truthful. for each ∈ [ ] do 4: compute sorted candidate set Λ ( ) by eq 23 in parallel 5: search optimal ( ) and We can see that for each advertiser , the dynamic reserve price and her prices to win the traffic do not depend on 's own bids at all. Hence, the bid of the advertiser does not affect his utility in future rounds and myopically maximizing utility in each round is optimal for maximizing the long-term utility. Since truthful bidding is myopically a dominant strategy in each round, being truthful is the best choice, and all advertiser following the always truthful strategy constitutes an equilibrium status. = is a weakly dominant strategy, which can lead to a truthfully bidding, so this kind of dynamic reserve price design is incentive compatibility.

Convergence and Optimality Discussion
In general, when the algorithm converges to a result, that jointly satisfies the optimality condition of equation [15][16][17], and is the optimal solution to the primal problem. However, the Lagrangean techniques can not guarantee to get an optimal solution to the primal integer programming (IP) problem, because a duality gap occurs due to the LP relaxation [27]. However, the solution computed from 12-14 is optimal for any IP problems derived from 15-17, when is replaced by − [16], where is non-negative variables, which satisfy for any > 0 such that is 0. But we can still analyze the gap between optimal and our algorithm empirically, the result in table 2 shows that it can achieve a nearly optimal solution. In particular, the optimality gap decreases as the number of traffic increases. Generally, the data scale is quite large in the e-commerce scenario, which means we can get the near-optimal solution in general.

EXPERIMENTAL EVALUATIONS
we do the test on both artificial data and Lazada sponsored search scenario data. For artificial setting, we generate and the coefficient of global constraint using two uniformly distribution in [0, 1] respectively, at the same time, without losing generality, we set the constraint between 0 and , and make it has a feasible solution. For a real scenario on a large dataset, is replaced by = , and we test three constraints as described in section 2.1. The optimality is evaluated by duality gap [29], which can quantify the discrepancy between the objective value computed by a current feasible but suboptimal solution of the primal problem and the value calculated by the dual problem.

Optimality Testing
First, we evaluate the optimality ratio, which is defined as the ratio of objective value solving by SCIP 3 [15] to that using our distributed algorithm. Because it's difficult to find any solver that can solve billion-scale IP problems, therefore, we only test the optimality under medium-scale problems using artificial data generated as described above. The experiment results show in figure 3, which demonstrate that the optimality ratio is above 0.995 with = 2000, and above 0.998 with = 10000 under all scenarios of local constraints for all experiment cases. More details, we compare the two algorithms described above across the different number of constraints, where 1 ≤ ≤ 20 and all coefficients generated by the uniform distribution. We draw the average optimality ratio curve with 20 times test as we vary , the result shows in Figure 1. The optimality gap increases while increases, at the same time, decreases while increases. In practice in industry, we usually have small but large , so it proves empirically we can get a near-optimal solution.

Duality Gap on Production Data
we test the algorithm with real search scenario data to measure the optimality of the solution. As it's difficult to find the solution to billion-scale problems, therefore, one of the choices is to calculate the duality gap combined with primal objective value , and if the relative duality gap defined as / is small enough, it means that we find the near-optimal solution. So, we use it to describe the level of optimization. As described above we test the two algorithms by real data with three constraints, table 2 shows the result of the relative duality gap after 15 iterations, which indicates we have already achieved a near-optimal solution. We can see the relative duality gap curve from figure 4, which shows that D3RP is sensitive to the learning rate while having a slower converge speed than CD2RP.

Solving Speed
The distributed implementation of our algorithm is using Spark, and in order to study the scalability, we try different scales of traffic sampled in real data with range from million-scale to billion-scale with fix = 3 (CTR, GPM and PVR), and we set 512 number of executors, where each one with 1 core and 2G memory. Experiment has been tested 3 times in the same setting to get more reliable results. Figure 5 shows the solving time with different scales of traffic. The optimization for 20 million-scale decision variables within ∈ {1, 3, 5, 7} global constraints can be able to converge to a near-optimal solution within an hour, which shows in figure 6.

Production Deployment
We present the online performance of the proposed dynamic reserve price design in Lazada sponsored search scenario, in which we consider not only efficiency, such as CTR and GPM, but also the relevance score 4 . We consider four metrics, i.e., Revenue, CTR, GPM, 4 Relevance score is a human evaluation metric defining whether the ads are relevant to the query. top query 5 relevance and mid query 6 relevance, and conduct online A/B testing with these metrics. We define the relevance score to be better than 85% in top query and 75% in mid query, at the same time, CTR and GPM gap of ad slot compared with pure organic bucket should be less than 20% and 30% respectively. Table 3 shows the relative improvements with 10% of production traffic during a week, and the benchmark is the traffic not using any traffic control strategy. From the experiments, dynamic reserve price can make it possible to get high performance of CTR, GPM and relevance with a low cost of revenue. At the same time, as the online platform contains millions of user requests every day, the results can prove stable. The distributed algorithm we developed in this paper has already been fully deployed in production.

RELATED WORK
In this section, we briefly discuss the work related to reserve price design for the application of online advertising. Most of the methods design the reserve price from the advertiser perspective using their history purchase, which differs from our work designing reserve price from the traffic perspective. the recent study on reserve price strategy is based on Myerson optimal auction [1] and tries to estimate the advertisers' unknown valuations to maximize platform revenue. In practice, Ostrovsky and Schwarz conducted an experiment on reserve prices for online auctions [2], which showed that it can significantly increase 5 Top query is the query with top 50% search request. 6 Mid query is the query with mid 10% search request. Figure 6: Time cost over different number of constraint on ten million scale decision variable using CD3RP the revenue of sponsored search. And a common insight, which is widely used in practice, is to estimate advertisers' valuation distributions using history bids. However, These methods can not bring long-term incentives to the advertisers. Because it may lead them to shade their bids and ultimately hurt platform revenue [6][7][8].
The rapid development of e-commerce technology in recent years [26], it renewed interest in reserve price design based on advertiser behavior, which is setting a personal reserve price for each advertiser based on their previous bid price to boost revenue [10][11][12][13][14]. Unfortunately, some designs of personalized reserve price still have incentive-compatibility issues, which have been discussed in [14].
Yash Kanoria al. [14] show how behavior base reserve price can be used to optimize reserve prices in an incentive-compatible way by appropriately learning from the previous bids. they propose an incentive-compatible mechanism that sets a personal reserve price for each advertiser based on the previous bids of other advertisers. However, all of these methods above potentially assume that all traffic value is similar to the advertiser, which may not be suitable for an e-commerce scenario.

CONCLUSION
We introduce the dynamic reserve price design framework for Lazada sponsored search, it can be used to define the relationship between revenue and user experience with incentive compatibility. We proposed distributed algorithms to solve the billion-scale problem with limited constraints, which can also be used to solve other similar problems in computational advertising. The proposed algorithm can be implemented not only using Spark but also using other distributed frameworks [17] such as MPI and Flink. The implementation in the production environment is simple to guarantee the stability of the whole advertising system.