Sponsored search program in online marketplaces is routinely ofered to sellers allowing them the opportunity to enhance the visibility and performance of their items. Optimizing for diferent goals such are clicks or conversions, advertisers can run campaigns provided a budget constraint. However, without any control on the spend, campaigns with smaller budgets can run too briefly, failing to reach regions of high quality trafic. Moreover, the same lack of spending control can benefit a few dominating sellers, inducing a lack of competition that negatively afects the majority of sellers, the marketplaces' revenue, and users experience. Budget pacing technique is a common tool used to control spend of ads campaigns that can tackle aforementioned challenges in a principled manner providing benefits to sellers, the online marketplace and users. In this paper we propose a simulation test bed based on real trafic of sponsored search program at eBay for accurate and safe evaluation of diferent budget pacing algorithms. We study several simple budget pacing algorithms, characterizing their efect under complex environmental constraints. As an important contribution, we describe an eficient test bed for ofline simulations and propose a new simple and eficient budget pacing algorithm based on the campaigns' remaining budget which can achieve improvements in many business metrics compared to the production benchmark.
how the campaigns’ budget is being depleted throughout
the day. Most common implementation of budget
pacitems through an optimized exposure or user
engageitems. This in turn enhances performance of sponsored budgets to be spent) are also common.
Many online marketplaces ofer advertising programs to ing optimizes for uniform spending throughout the day
their sellers, with the most notable one being sponsored [
common target historically being pay-per-click (PPC1)][.
ment, depending on seller’s strategies, with the most ule may span: 1) an unhealthy competition as higher bid
to define daily budgets, organize items into groups for
In order to run sponsored search campaigns, sellers need sulting in lower clearing prices and user engagement, and
ads may not have enough budget left later in the day,
re2) advertisers would miss out on good ad opportunities
that builds trust and partnership 2[], notably,
smoothwhich they specify targeting, and target and/or maxi-later in the day. On the other hand, introducing a budget
mum bids. Allocating small budgets, or high maximum pacing module fosters: 1) healthy ad competition that
bids can cause campaigns to deplete their budget too fast results in higher yield for the ad platform, 2) advertisers’
and stop early. Moreover, the spending pattern of the ROAS as more ads can be shown where users are more
campaigns’ money is an important signal to advertiserslikely to engage and 3) user retention is higher as they
ness and/or repeating patterns of budget depletion may have a profound efect on the entire advertising program.
be key indicators for advertisers 3[]. Thus, advertising
platforms may ofer tools such as budget pacing [
Simple budget pacing techniques have proven to be other advertisements may join the ads auction creating very efective at tackling the control over the spending
an additional, external, competition which creates an
[
provided bid and response probability (in our case
Finally, testing the eficiency of budget pacing tech- click-through-rate pCTR) as = × . We simulate niques can be very expensive and risky if they are ex- item allocation with a multi-slot generalized second-price posed to real-word trafic, as the sponsored search is
auction for allocating items across the search result page
highly nonlinear program in terms of interactions of its[
pacing test bed which acts as our domain analysis framew-ill be charged clearing price based on second-price work where a range of budget pacing techniques can beauction mechanism using the ad expected value of the evaluated quickly and safely, and hyperparameter fine- first lower ( + 1 ) ranked item : tuning can be done.
Summarizing the key contributions of this work with respect to above discussed questions and challenges to build practical working budget pacing system in a is listed as follows: = +1 = +1 ×
+1 , (1) bed.
on throttling-based budget pacing approaches, noting that approaches discussed could easily be implemented as bid altering approaches as well.
Another important aspect that new ad program cope we evaluate practical budget pacing algorithms and propose reasonable extensions which allow us to achieve key business goals. • These budget pacing algorithms are implemented
online advertisement is presented. • Based on the real trafic of sponsored search pro• A detailed construction framework of test bed of the budget after each user response, and if the budget is logically capped so tha t ≤ . Ad campaigns would run throughout the day given their budgets ’s, deplete completely depleted stop whenever that happens.
Interesting observation is that no pacing may be a good terized and evaluated. gram at eBay, a test bed is implemented, charac-solution when the ads competition is high enough as it always guarantees that for a search query the highest as an important design approach and based on it,auction, thus maximizing the revenue. • Given the constraints of environment, we explain and second highest ranking sponsored items among notthe importance of greedy budget pacing strategies yet-depleted budget campaigns are always present in the 2.2. Related work on budget pacing
methodologies
partite graph allocation methodologies5[
In this study we propose a general sponsored search test pacing or throttling (preventing an ad to be allocated)
bed of high integrity, which makes generic assumptions and soft budget pacing (altering bid value for an ad used
that are common in the domain, and requires a distribu-for the allocation). In practice, throttling is a more
aption of users’ search requests as its main input. Given pealing approach for young ad platforms as its efect is
the main application being eBay’s sponsored search pro-clearly distinct which better supports system triage and
gram, we describe it first in this section. Following, we
discuss related work in budget pacing techniques that fer throttling approaches over bid altering approaches in
were considered for experimentation in the designed test sponsored search [
Each approach makes slightly diferent assumptions order. on the ad opportunity trafic that makes it dificult to Simulating click behavior of users. We simulate the evaluate them without exposing them to the real trafic click behavior of users using click value generator (elabwhich is expensive and risky. To enable safe and eficient orated in Section3.2) that is based on the concept of testing of budget pacing solutions we design and present counterfactual modelling. a trafic-based sponsored search test bed below. Evaluation metrics. In order to characterize the quality of the test bed we focus on smoothness of spend throughout the day, but also on other key performance metrics: 3. Test bed the number of impressions, the number of clicks, CTR, total ad revenue and cost-per-click (CPC).
In this section, based on above described sponsored search implementation flow, we explain the implementation of the test bed based on the real trafic collected 3.2. Probabilistic click value generation from logs. The test bed runs on real daily logs utilizing Opposed to a naive random click generation strategy, we historical information of ad opportunities, thus allowing exploit the fact that the log of each search query contains us to simulate budget pacing algorithms with high in-the information about the and click values of tegrity. As such, the test bed is suitable for a diferent sponsored items shown at a given slot. We declare this types of ad programs such as display/native platforms or information as 1 and click value 1, while the gensmall ad exchanges. erator will use 2 from a newly generated ranking to produce click value 2 in a manner described below.
Case 1. 2 < 1 and 1 = 1.
• Generate a random numbe r in [
Data Model. The budgets of sponsored search cam- 2/
paigns are typically reset once a day. We, thus, focus
on simulating 1-day trafic by partitioning it into 1440
1-minute datasets where each dataset contains all searchCase 2. 2 < 1 and 1 = 0. 2 is assigned to 0.
requests eligible for displaying sponsored items. This ap- Case 3. 2 > 1 and 1 = 1. 2 is assigned to 1.
proach can be applied to any other budget reset strategy. Case 4. 2 > 1 and 1 = 0.
Achieving a real time budget pacing signal estimation is • Generate a random numbe r in [
Targeting-based retrieval. In practice, retrieval based 3.3. Quality of the test bed on targeting input is a complex and time consuming process involving sorting by relevance and other important In this section, we evaluate the quality of the test bed values. To simulate the targeting-based retrieval task, for of sponsored search ads by computing the number of each search query, we build its own targeting set from impressions, the number of clicks, CTR, spending and logged recall sets. cost-per-click for the whole day when we run the simuThe bid value. One item in a campaign may have difer- lator without any treatment algorithms, accounting for ent bid values depending on its targeting (i.e. keywords) natural noisiness of the system and any external compestrategy, where keywords may overlap. Therefore, to tition. Another run of the simulator, with a naive click calculatead expected value, we prioritize largest bid ad value generation (based on estimated pCTR) is generated group similarly as production system. to show the advantages of the proposed solution. These The pCTR. In practice, sponsored items would have results are then compared to historical data to gives us pCTR calculated depending on the context, however, dur- an idea about the quality of the test bed. ing simulation this process can be very time consuming. The global evaluation of test bed is provided in Tabl1e. In order to address the challenges of computing pCTR A key property of the simulator is that the overall bescores for less frequent items and sponsored items from havior of simulated trafic should match the real trafic.
While the gaps in the simulation results compared to the 20 0 20 40
techniques greedy strategies may be preferable, which we discuss below. Finally, campaigns with small budgets may not benefit much from a duration improvement.
A large volume of papers discuss about the budget
pacreal trafic can come as artifacts from the approximations ing algorithms [
We noted that “no pacing” simulation, called reset time may account for all such scenarios and their variations, at 0-th interval ( 0), has the same trend as the original even including fine tailored policies for specific camtrafic for all curves. Using these time series, we validated paigns when needed. We discuss budget pacing algothe test bed by calculating the relative diference between rithms suitable for implementation through a framework 0 and real trafic, shown in the aforementioned fig- given in Algorithm1 in the following context used for ures, and discovered that the diference is acceptably eBays sponsored search program. small. Most importantly, the simulated 0 is used as the baseline for all approaches tested, amortizing any discrepancy created due to the test bed artifacts.
The proposed simulator is designed to test diferent use cases a sponsored search program can face such as having external competition, working in an environment with diferent budget reset strategies, using budget pacing or no pacing as control, and other. In the experiments we present in this study, we simulate scenario of applying budget pacing techniques on the system that previously did not control budget spend, while having a competition from an external advertising program. This particular scenario has a caveat of a potential reduction of total impressions. Moreover, throttling campaigns for some ad opportunities does not mean that there will be more opportunities in the future, so for simple budget pacing • Most campaigns have small budgets or get small number of clicks in practice due to high competition of the environment. • The budgets are reset once per day – no pacing.
The algorithms in line are calle d where x is
the reset time considered and is equal to 0 or 750
in this study.
• First group of budget pacing techniques
considers only the remaining budget of a campaign. We
discuss this scenario in Section4.2, and call
approaches in this paper.
• Second group of budget pacing techniques
considers information about campaigns’ remaining
budgets and the remaining time. We discuss
this scenario in Section4.3, and call approaches
in this paper.
• Third group of budget pacing techniques
considers information about campaigns’ remaining
budgets and predicted information about the
remaining spending opportunity. The predicted
information about the spending opportunity is pacing rate . We modify the vanilla budget pacing
alcalculated based on historical data. We discussgorithm proposed in [
in this paper. know anything about the environment except the fact factor that the competition is very high and they want to collect enough (i.e., always join the auctions whenever they can. as many clicks as possible, then the best strategy is just any more by setting it to a small value0.001. The main which is smaller than 1. When is small
), then we do not want to reduce it
budget , the target total spend of the campaign up to is the duration the campaign wants to complete its budget.
Therefore, if
is larger than 1, then the campaign is overspending (spend more than what it should at time ), and should be slowed down by multiplying with the motivation is that we still adopt greedy strategy, the campaigns do not completely stop spending. Given our ofline experimentation, we set = 0.8 and = 0.01. When is smaller than 1, it implies the campaign interest and this is one of program’s high priorities, then
If getting as many clicks as possible is the majority’s the moment is described by × , = 0, … , 1439 , where it seems the optimal pacing strategy is greedy one, i.e., try to let the campaigns join the auctions whenever they can. The reason is as follows. If the campaigns do not
daily reset algorithm also maximizes CPC (greedy rev- the time. enue maximization) when second auction logic is used Daily budget reset strategy is typically the first budget control strategy implemented in advertising programs, is under-spending, the pacing rate= 1 , as we want it to thus, in our study it serves as the main baseline. This op- join auctions immediately. Based on the simulated logs tion is referred to as
0. As we discussed in Section3.4, this approach is a good option because all campaigns canthe campaign . The closer guarantee maximum number of impressions. Moreover, pacing algorithm in terms of spreading the spend over and , the better for that campaign, we can calculate the true spend of as no support is being throttled. The negative point of 4.4. Remaining click opportunity based this approach is that it does not attempt to smoothen the budget depletion, but maximizes the competition at the time of reset, which, due to early budget depletion results in an unhealthy competition across the day.
ness goals, we may search for the optimal reset time.
750) sponse curve of sponsored search program and its busi- as described in Algorithm1. pacing algorithm
train a model based on historical data of campaigns’ campaigns in case campaigns have no budget restrictions. provided good results in the number of clicks, total rev- spends to predict the possible remaining spend of each enue, CTR and CPC.
Below, we discuss several solutions for throttling- The eficiency of the algorithm really depends on quality based budget pacing where they would, for each ad call, of the forecasting model. Training standard forecastgenerate the throttling signal that will provide a proba-ing models such as autoregressive logistic regression or bility of item joining the ads auction.
This algorithm only uses remaining budget to pace the
spend. Motivated by the budget pacing algorithm pro- the campaigns have no budget restriction. In this case,
posed in [
ing budget and remaining time in day with the current
ARIMA [
and /( × ) if ℎ ==
As described above, the test bed consists of 1440 diferent
queries with the eligible ad slots. Before working with the -th dataset, the information of the campaigns’ initial and remaining budgets, and the remaining time are obtained for the -th dataset. The budget pacing throttling threshold is calculated by algorithms described in
auction for the -th dataset. After the -th dataset simulation, the remaining budgets of campaigns are updated based on the simulated spend.
There are three groups of budget pacing strategies considered: 1) greedy ( time, (
and opportunities ( comparison purpose.
). 0, 750), 2) based on budget and ) and 3) based on forecasted 0 is chosen as benchmark for
rithms we measure key business metrics discussed in
system-level spend pacing error (PE) (measuring smoothness of spend over a day) metric defined as:
PE = (1/1440) ×∑ 1440 | − | =1 with and as the fraction of total spend and trafic in -th interval. Moreover, we also measure campaignweighted Weighted Pacing Error (WPE): =
1440 ∑ ( ∑ (| , − × =1 =1
1440 |) × ) , where , , and are the accumulated spend of a campaign up to -interval, the total spend of campaign, and the total spend of the whole system in one day, respecValues of all metrics are reported as changes relative 0 strategy, and are presented in Table2. tively. to
750 vs 0
This pacing is not used to smooth out the spends of campaigns. Precisely, the campaigns join any auction as long as their budget is not empty. spendacumlation 500 feublaRyoNuonPdaNceinwgRestingTime_750 ideal 400 300 200 100 0 0 20 40 60 interval=1mins 80 10 120 140 (a) 1( 750 vs 0)
spendacumlation
The reset time is at 750-th minute gives us the best cording to the Table2 we can see that the algorithm results in terms of number of clicks, revenue and CTR. has a strong impact on the CPC program, where in This means the environment ofers a very good spending terms of business metrics, from the non-greedy spendtime for all campaigns. Moreover, the campaigns have aing approaches considered in this paper, the proposed full budget at 750-th minute and thus, we see a high peak shows best results. of impressions and clicks at that moment. Given the fact The best pacing error results imply tha t that most CPC campaigns have a small amount of clicks,method variant can smooth out the spend throughout they quickly deplete their budgets after a few hours. the day efectively. The error curves of top-1 campaign
The result of 0 and 750 shown in Table2 con- shown in Figure2c show that the proposed algorithms ifrms that if the environment has high competition and work very well, i.e., the error curves of top-1 campaigns many CPC campaigns with small budgets, then greedy of the budget pacing algorithms nearly match the ideal strategy seems to be a good one. ones.
To understand the impact o f 0 and 750 on the
spreading of the spend of CPC campaigns, we focus on ClkOp vs 0 This pacing is based on the remaining
top-1 campaigns which have highest number of clicks budget information of campaigns and estimated
remainwhen working with 0 (benchmark). Figure2a shows ing spend opportunities of campaigns. In the situation
the pacing error curves of the top-1 campaign when where ads competition is not very large, this algorithm
working with 0 (blue lines) and 750 (orange lines). may appear very similar to 0 in terms of results (see
The ideal spending curve (green line) is the benchmark.Table 2 and Figure2d). The reason for this is the bias
Clearly, the error curves of 750 is much worse than of the predictions towards dominating campaigns that
0 or the campaigns spend much quicker when they have had plenty of ad opportunities during the day,
sufwork with 750. focating smaller campaigns for whom the prediction of
ad opportunities would be underpredicted. The success
Budget vs 0 This pacing method is based on the of approaches, thus, heavily depends on the high
remaining budget information of campaigns. Given thevolume of competition [
If the campaigns have big budgets, then the ratio should slowly decrease. But the behavior of wInotrhkisopfasipmerp,lweebduetsecficriiebnedt taesdtetbaeidlefdocrobnusdtrguecttpioancifnragmesmall budget campaigns does not much change too much,algorithms. We study some simple yet eficient budget i.e., their budgets will still be quickly depleted. Combined pacing algorithms for online advertising program with efect, of the two types of campaigns will result in the a competitive environment with plenty small budgets lack of competition and a faster budget depletion of large campaigns. Our theory analysis and experiments show campaigns, whose behavior will look similar to the one that greedy strategy is quite a good option which led to without any budget pacing applied. This is clearly seen an exploration of simple budget pacing algorithms given in pacing error curve of the top campaign shown in Fig-such environment. Finally, with our empirical experiure 2b. ments and characterization of the system, we proposed an approach we calle d that achieved the best BudgetTime vs 0 This pacing is based on the re- balance in terms of pacing error and business metrics maining budget and time information of campaigns. Aci-mpact.