Cost-Control in Display Advertising: Theory vs PracticeAnoop R Katti

Rui C. Gonçalves

Rinchin Iakovlev

anoop.katti@zalando.deZalando SE
Berlin, Germany

rui.goncalves@zalando.deZalando SE
Berlin, Germany

rinchin.iakovlev@zalando.deZalando SE
Berlin, Germany

ABSTRACTIn display advertising, advertisers want to achieve a marketing
objective with constraints on budget and cost-per-outcome. This is
usually formulated as an optimization problem that maximizes thetotal utility under constraints. The optimization is carried out inan online fashion in the dual space – for an incoming Ad auction, abid is placed using an optimal bidding formula, assuming optimalvalues for the dual variables; based on the outcome of the previous
auctions, the dual variables are updated in an online fashion. While
this approach is theoretically sound, in practice, the dual variables
are not optimal from the beginning, but rather converge over time.
Specifically, for the cost-constraint, the convergence is asymptotic.
As a result, we find that cost-control is ineffective. In this work,
we analyse the shortcomings of the optimal bidding formula andpropose a modification that deviates from the theoretical derivation.
We simulate various practical scenarios and study the cost-control
behaviors of the two algorithms. Through a large-scale evaluationon the real-word data, we show that the proposed modification
reduces the cost violations by 50%, thereby achieving a better costcontrol than the theoretical bidding formula.

CCS CONCEPTS• Information systems → Display advertising; Sponsoredsearch advertising; Content match advertising.

KEYWORDS
Display advertising, Real-time bidding, Online optimization, Budget constraint, Cost control, Optimal bidding, Dual online mirror
descent
ACM Reference Format:
Anoop R Katti, Rui C. Gonçalves, and Rinchin Iakovlev. 2024. Cost-Control
in Display Advertising: Theory vs Practice. In Proceedings of AdKDD ’24.
ACM, New York, NY, USA, 6 pages. https://doi.org/XXXXXXX.XXXXXXX

1INTRODUCTION

In online display advertising, advertisers run Ad campaigns witha goal of achieving some marketing objectives, e.g. increasing theawareness/engagement of their brand, boosting sales, etc. Online
Ads are often sold using auction mechanisms where the competing Ads place a bid and are charged for a user view or a click.
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
AdKDD ’24, August 25, 2024, Barcelona, Spain© 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-XXXX-X/18/06
https://doi.org/XXXXXXX.XXXXXXX

Advertisers have a certain advertising budget that they wish tospend in a specific period of time and they wish to control the costper-outcome (e.g. cost-per-view, cost-per-click). While the budget
represents the total volume of Ad spend, cost-per-outcome represents the efficiency with which the outcome is achieved. In fact, it
is not uncommon for advertisers to set up campaigns with high advertising budgets and steer them on cost-per-outcome. This makes
it important to meet both the budget and the cost constraints.
In this paper, we consider a scenario where advertisers run amarketing campaign for a fixed period of time to achieve a marketing objective while keeping the total advertising spend withina specified budget and the cost-per-view under a specified targetcost. Such a scenario has been widely studied in the literature of
Real-time Bidding [9, 11, 16]. A common way to approach it is toformulate it as an optimization problem that maximizes the advertiser utility (cost-adjusted value) under constraints. Each incoming
Ad opportunity is supposed to have an expected value to the advertiser. The constraints capture the upper bound on the total Ad
spend and the cost-per-outcome. Note that when competing forthe current Ad opportunity, we do not have access to the future
Ad opportunities. Consequently, based on the historical outcomes,
the optimization is carried out in an online fashion and in the dual
space [3]. Assuming the current values of the dual variables (computed from the online optimization) are optimal, an optimal bidding
formula is derived that maximizes the advertiser utility for each
Ad opportunity, accounting for the current violation of constraints.
Based on the outcomes of the historical auctions, the dual variables
associated with the constraints are updated towards their optimalvalues in an online fashion.
This approach is theoretically sound. However, the values of thedual variables are not optimal from the beginning. In fact, they
converge to the optimal value over time. In particular, the dual
variable associated with the cost-constraint converges asymptotically. As a result, we find that in practice, cost-control is ineffective.
Furthermore, say the dual variable associated with cost-control has(almost) converged to the optimal value. If the market conditions
change or if the campaign settings are modified by the advertisers,
the algorithm would take a very long time to stabilise again to thenew optimal value. In the rest of the paper, we analyse the optimal
bidding formula and highlight its shortcomings when applied in an
online setting. Based on the analysis, we propose a change to thebidding formula that deviates from the theoretical derivation. We
simulate several practical scenarios and compare the cost-control
behaviors of the two algorithms. Lastly, through a large-scale evaluation on the real-world data, we demonstrate that the proposed
modification violates cost constraints on 50% fewer campaigns ascompared to the theoretical bidding formula.

AdKDD ’24, August 25, 2024, Barcelona, Spain

Katti et al.

to the literature [9, 16], we derive the optimal bidding formula forparticipating in Ad auctions. We then share a practical issue withcost-control and propose a modification that deviates from thetheoretical derivation, but works in practice.

3.1

Figure 1: Bid variation with 𝜇 – Theoretical (blue), Proposed(orange, green); solid and dashed lines indicate 𝛼 = 1 and 0.

Optimal Bidding

Consider a single Ad campaign with an advertising budget of 𝐵 anda target cost-per-view of 𝐶 view . Let the campaign participate in 𝑁
Ad opportunities (i.e. Ad auctions). For the 𝑖 𝑡ℎ Ad opportunity, letbid𝑖 be the bid placed by this Ad campaign in the auction, 𝑥𝑖bid𝑖 be
the resulting probability of a user view, 𝑣𝑖 be the value of the viewto the advertiser and 𝑐𝑖 denote the cost of the view. We define theÍ𝑁 bid𝑖
optimization objective as 𝑖=1
𝑥𝑖 · (𝑣𝑖 −𝛼 ·𝑐𝑖 ), where 0 ≤ 𝛼 ≤ 1 isthe fraction of cost considered in the objective. If 𝛼 = 1, we optimize
for utility and if 𝛼 = 0, we optimize for value. The optimization
problem is formulated as:max

2

RELATED WORK

Real-time Bidding has been extensively studied in the scientific
literature [5, 17, 18]. Several of the existing works in real-time bidding address the topic of bidding in repeated auctions with budget
constraints [1, 2, 6, 8, 10, 14]. The approaches can be grouped inthree categories: (i) solving an online optimization using dual online
mirror descent [3, 9], (ii) using a Proportional–Integral–Derivative(PID) controller to control the spend-rate around some target [15–17], and (iii) maximizing the total reward using reinforcementlearning in either the primal [5] or the dual space [11]. In fact,in [4], the authors prove that dual-based PI controllers are the same
as solving the dual optimization using online mirror descent with
momentum.
We consider not just the budget constraints, but also the costper-outcome constraints. Two studies that are close to the problem
we consider are from LinkedIn [9] and Alibaba [16]. Similar to theworks on budget constraints, they formulate and solve an optimization problem to derive the optimal bidding formula that captures
both the budget and the cost constraints and optimize the dual
variables using either the online mirror descent [9] or a PID controller [16]. We base our work primarily on these two studies.
The bidding formula is optimal only if the dual variables have
converged to their optimal values. However, in practice, the dual
variables are not optimal from the beginning. Specifically, the dual
variable associated with cost-control converges only asymptotically.
In this work, we propose a modification to the bidding formula thatdeviates from the theoretical derivation and show that in practice,
it is more effective than the optimal bidding formula. To the best of
our knowledge, there is no previous work that studies this topic.
Other relevant literature in the field include building auction
simulators [12, 13] and handling more extensive constraints suchas achieving a certain distribution of users [7].

3𝑥 bid ∈ [0,1] 𝑁

METHOD

We consider the problem of maximizing the total advertiser utility(cost-adjusted value) given a target budget and a target cost-perview. Ad opportunities are sold using an auction mechanism. Similar

subject to

𝑁
∑︁
𝑖=1
𝑁
∑︁
𝑖=1
𝑁
∑︁
𝑖=1

𝑥𝑖bid𝑖 · (𝑣𝑖 − 𝛼 · 𝑐𝑖 )(1a)𝑥𝑖bid𝑖 · 𝑐𝑖 ≤ 𝐵,

(1b)

𝑥𝑖bid𝑖 · 𝑐𝑖 ≤ 𝐶 view𝑁∑︁𝑥𝑖bid𝑖 .

(1c)

𝑖=1

For second-price auctions, solving the above optimization problem results in the following optimal bidding formula [9, 16]:
𝑣𝑖 + 𝜇 · 𝐶 viewbid𝑖 =,(2)
𝛼 +𝜆+𝜇where 𝜆 > 0 and 𝜇 > 0 are dual variables associated with the budget
and the cost-per-view constraints respectively.
Eq 2 assumes that the dual variables are at their optimal values,
𝜆 ∗ and 𝜇 ∗ . However, 𝜆 ∗ and 𝜇 ∗ are not known from the beginning.
Rather, the dual variables are updated towards their optimal values
in an online-fashion. Concretely, after each mini-batch of 𝑛 auctions,𝑖 𝑡 : 𝑖 𝑡 +1 , the 𝑥𝑖 ’s materialise into binary outcomes, i.e. viewed or not
viewed. Let 𝜖𝜆 and 𝜖 𝜇 be the learning rates for the online updates.
Then 𝜆 and 𝜇 are updated as 1 :
𝑖 𝑡 +1 𝜖 ∑︁𝐵©
ª𝜆𝑡 +1 = max ­𝜆𝑡 + 𝜆
𝑥𝑖 · 𝑐 𝑖 −
, 0®
𝑛 𝑡
𝑁
𝑖
«
¬
𝑖 𝑡 +1∑︁𝜖𝜇©
ª𝜇𝑡 +1 = max ­𝜇𝑡 + Í 𝑡 +1
𝑥𝑖 (𝑐𝑖 − 𝐶 view ) , 0®
𝑖
𝑥
𝑡
𝑖
𝑡
𝑖
𝑖
«
¬

3.2

(3a)

(3b)

Practical Issue with Cost-control

In this section, we analyse the optimal bidding formula. Suppose
budget is not an active constraint, i.e. 𝐵 is sufficiently high. In thiscase, 𝜆𝑡 = 𝜆 ∗ = 0. Say, advertisers want a return on Ad-spend of
𝑅 > 1. Then, the expected value, 𝐸 [𝑣] = 𝑅 · 𝐶 view and the (average)
1 For spend-control, we use the Model Predictive Control version as in [9]. For cost-

control, we use momentum in order to be robust against outliers; this is particularly
important when the overall cost-per-view is lower than the target, i.e. the constraint
is inactive and a single outlier can activate the constraint and reduce the bid.

Cost-Control in Display Advertising: Theory vs Practice

AdKDD ’24, August 25, 2024, Barcelona, Spain

𝑅+𝜇bid = 𝐶 view · 𝛼+𝜇 . Fig 1 shows how bid varies with 𝜇 for 𝑅 = 5,
𝐶 view = 1 and 𝛼 = 1 (solid blue). We can see that bid ≥ 𝐶 view .
In fact, the equality, bid∗ = 𝐶 view , happens at the optimal value,𝜇 ∗ = ∞. With 𝛼 = 0 (dashed blue in Fig 1), the lower-bound on bid
still holds.
In an online optimization setting, the algorithm starts with a
𝜇 < ∞ and reaches the optimal value asymptotically over a long
period of time. As discussed in Sec 4.1, due to several factors that areoutside the control of the algorithm, the cost-per-view may exceed
the specified target, 𝐶 view . If the bid does not drop below 𝐶 view ,then in such cases, it may be infeasible to meet the cost constraint.
Consequently, the bidding algorithm does not achieve an effective
cost-control.

3.3

Improving Cost-control

As before, suppose budget is sufficiently high and is, therefore,
not an active constraint. Intuitively, if the current cost-per-view isgreater than 𝐶 view , 𝜇 should increase over some 𝜇 ′ < ∞, bid shoulddrop below 𝐶 view and the cost-per-view should gradually decrease
to 𝐶 view . Further, once the cost is under control, i.e. cost-per-view
equals 𝐶 view , 𝜇 should stabilise at 𝜇 ′ . Let’s consider introducing′
an artificially discounted 𝐶 view
= 𝛽 · 𝐶 view , 𝛽 ∈ [0, 1) in the original optimization (Eq 1c). With this change, the bid can now go
below 𝐶 view and this happens at some 𝜇 ′ < ∞. However, even after
the cost-per-view decreases to 𝐶 view , the (average) error in Eq 3b
continues to remain positive (as the errors are computed against′
𝐶 view). Consequently, 𝜇 will not stabilise at 𝜇 ′ , but instead keeps
increasing (asymptotically) to ∞. This unnecessarily pushes thecost-per-view below the real target, 𝐶 view and negatively impacts
the value generated to the advertiser.
Based on this intuition, we propose the following change that
does not conform to the theory, but takes the best of both worlds:
modify the bidding formula as if there is a discounted target costper-view and leave the online updates in Eq 3a and Eq 3b unchanged.
This results in the alternative bidding formula shown below:
bid𝑖 =

𝑣𝑖 + 𝜇 · 𝛽 · 𝐶 view
𝛼 +𝜆+𝜇(4)

Fig 1 visualises how bid varies with 𝜇 for 𝑅 = 5, 𝐶 view = 1, 𝛼 = 1
and for two different values of 𝛽 (solid orange: 𝛽 = 0.5, solid green:
𝑅+𝜇·𝛽
𝛽 = 0). We can see that the (average) bid = 𝐶 view · 𝛼+𝜇 ≥ 𝛽 ·𝐶 view .
This lower-bound also holds for 𝛼 = 0 (dashed orange and dashedgreen in Fig 1). This allows the bid to go below 𝐶 view , thereby,
bringing down the cost when necessary. Once the cost reaches thetarget, 𝐶 view , the (average) error in Eq 3b goes to zero, 𝜇 stabilises
and the cost remains at the target. While this modification deviatesfrom the theory, we argue that in an online optimization setting, it
enables the bidding algorithm to achieve effective cost-control.

4

EVALUATIONIn this section, we will first analyse the cost-control behaviors of
the two bidding algorithms in different practical scenarios – thetheoretically derived bidding formula and the proposed bidding
formula. Then, we will perform quantitative comparison on largescale real-world Ad opportunities and campaigns.

(a) View-rate vs Bid

4.1(b) Simulation Traffic distribution

Simulations on Synthetic Data

The goal of the simulations is to qualitatively study the cost-control
behaviors of the algorithms in different scenarios that are relevantin practice.
4.1.1 Set-up: We consider a single campaign with 𝐵 as the budget
for one day and 𝐶 view as the target cost-per-view. For simplicity
of simulation, we choose the awareness objective, i.e. obtain user
views; however, the analysis on cost-control should generalise toother marketing objectives such as engagement (i.e. clicks) andpurchase (i.e. sales). In our simulations, we maximise utility, i.e.
𝛼 = 1. The value of a view is set to, 𝑣𝑖 = 𝑅 · 𝐶 view , where 𝑅 > 1 is aconstant representing the advertisers’ return on Ad spend. Fromreal auctions, we have constructed a relationship between bid andview-rate. This is a property of the market. This relationship isvisualised in Fig 2a. Notice that as bid increases, view-rate increases(polynomial with a degree 4). The price per view is 95% of thebid to emulate a second-price auction. We consider O (106 ) Ad
opportunities and that they are distributed as shown in Fig 2b to
mimic the real traffic distribution. The dual variables, 𝜆 and 𝜇, areinitialised such that the initial bid is 𝐶 view (and 𝜆 = 𝜇). Further, they
are updated every 1 minute with learning rate recommended in [9].
4.1.2

Variants: We consider three variants(i) Max-cap: here, we apply a hard cap on the bid, where the cap
is the target cost-per-view; specifically, bid𝑖 = min(𝑣𝑖 /(1 +𝜆), 𝐶 view ).
(ii) Cost-control-theoretical: here, we employ the bidding formulafrom Eq 2 to achieve the target cost-per-view.
(iii) Cost-control-practical: here, we employ the proposed bidding
formula from Eq 4 to achieve the target cost-per-view. We set
𝛽 = 0 as this provides the most flexibility to the algorithm todrop the bid all the way to 0, if necessary.
4.1.3 Metrics: We visualize the evolution of the dual variables, 𝜆and 𝜇, the actual and target cost-per-view and the actual and target
spend.
4.1.4 Practical Scenario 1: Budget is the active constraint. Consider
a scenario where budget is the active constraint, i.e. target cost-perview is set to some high value. In this case, the optimal values forthe dual variables are: (𝑅 − 1) < 𝜆 ∗ < ∞ for all variants and 𝜇 ∗ = 0
for variants (ii) and (iii) (variant-(i) does not have 𝜇). We find thatafter a few iterations, all three variants converge to the optimalvalues. This is visualised in Fig 3.
4.1.5 Practical Scenario 2: Cost is the active constraint. Consider ascenario where cost-per-view is the active constraint, i.e. budget

AdKDD ’24, August 25, 2024, Barcelona, Spain

Figure 3: Scenario 1 – Budget is the active constraint

Katti et al.

Figure 6: Scenario 4 – Cost is the active constraint and advertiser moves the budget to a different channel

Figure 4: Scenario 2 – Cost is the active constraint
Figure 7: Scenario 5 – Cost is the active constraint and thetraffic becomes 2x

variables are 𝜆 ∗ = 0 for all variants; variant-(i) does not have 𝜇; forvariant-(ii), 𝜇 ∗ = ∞; for variant-(iii), 𝜇 ∗ = 𝑅 − 1.
We find that variants-(i) and (iii) converge to their optimal values
after a few iterations; variant-(ii) converges to 𝜆𝑡 = 0, but, as
expected, 𝜇𝑡 keeps growing. More importantly, in variant-(ii), since𝜇𝑡 never reaches to its optimal value, the cost-per-view is always
higher than the target. On the other hand, Max-cap and Cost-controlpractical reach the target cost-per-view. This is shown in Fig 4.

Figure 5: Scenario 3 – Budget is the active constraint and acost-sensitive advertiser decreases the target cost-per-view

is sufficiently high. In this case, the optimal values for the dual

4.1.6 Practical Scenario 3: Budget is the active constraint and a costsensitive advertiser decreases the target cost-per-view. Consider ascenario where the advertiser is highly sensitive to the costs (andultimately, return on Ad spend). At the beginning of the campaign,
budget is the active constraint. However, the advertiser realises
during the campaign that they are not achieving the desired returnon Ad spend and decreases the target cost-per-view. Now the cost
becomes the active constraint and 𝜇𝑡 should go from 𝜇 ∗ = 0 to
𝜇 ∗ = ∞ in the case of variant-(ii). This takes a long time and it leads

Cost-Control in Display Advertising: Theory vs Practice

AdKDD ’24, August 25, 2024, Barcelona, Spainfor it. Scenarios 5 and 6 demonstrate the dynamic nature of theenvironment and they may be important for designing the algorithm. Moreover, the simulation, here, is simplistic (e.g. all views areequally valuable, view-rate increases smoothly with increasing bid,etc.). In the real-world, the actual impact from different scenarios
may be different. This is presented in the next section.

4.2

Large-scale Evaluation on Real-world Data

The goal of the large-scale evaluation is to observe to what extent
the target costs will be achieved on real-world campaign data andreal-world Ad opportunities at scale. Additionally, we also want toobserve the utility (cost-adjusted value) generated to the advertisers.

Figure 8: Scenario 6 – Budget is the active constraint and thetraffic drops to 0.5x
to a higher violation of the cost-per-view constraint as comparedto other variants. This is visualised in Fig 5.
4.1.7 Practical Scenario 4: Cost is the active constraint and advertiser
moves the budget to a different channel. Consider a scenario wherecost is the active constraint and that Cost-control-theoretical has
reached a very high value asymptotically converging to the optimal,
i.e. 𝜇𝑡 ≫ 0. Imagine the advertiser realises that they could move thebudget to, say, a different marketing channel where they are able tospend the budget. Suddenly, budget becomes the active constraint.
Now, 𝜇𝑡 should go from 𝜇𝑡 ≫ 0 to 𝜇𝑡 = 0, which takes a long time.
This results in a less efficient behavior from variant-(ii), which ends
with a higher cost-per-view. This is shown in Fig 6.
4.1.8 Practical Scenario 5: Cost is the active constraint and the traffic
becomes 2x. Consider a scenario where cost is the active constraint
and that Cost-control-theoretical has reached a very high value
asymptotically converging to the optimal, i.e. 𝜇𝑡 ≫ 0. Assume thetraffic on the platform dynamically doubles – this could be becauseof the traffic variation during the day or due to some special event
like a sale. Suddenly, budget becomes the active constraint. As
before, 𝜇𝑡 should go from 𝜇𝑡 ≫ 0 to 𝜇𝑡 = 0, which takes a long time.
This results in a less efficient behavior from variant-(ii), which ends
with a slightly higher cost-per-view. This is shown in Fig 7.
4.1.9 Practical Scenario 6: Budget is the active constraint and thetraffic drops to 0.5x. Consider a scenario where budget is the active
constraint and 𝜇𝑡 = 𝜇 ∗ = 0 for variants (ii) and (iii). Now consider
that the traffic on the platform halves – this could happen due tothe traffic variations within a day or a more drastic event like asystem failure. Suddenly, cost becomes the active constraint. For
Cost-control-theoretical, 𝜇 ∗ ≫ 0 and the algorithm has to movetowards this optimal value. This takes a long time, which leads toa higher violation of the cost-per-view constraint as compared toother variants. This can be observed in Fig 8.
4.1.10 Summary: We consider six different practical scenarios. Scenarios 1 and 2 are the most frequent ones. Scenarios 3 and 4, although less frequent, might be critical for a single advertiser whocares about costs (ultimately, return on Ad spend) and is optimizing

4.2.1 Set-up: For large-scale evaluation, we choose a click objective (engagement campaigns) as this differentiates the valuation ofviews based on their probability to convert to a click. We maximise
utility, i.e. 𝛼 = 1. We consider O (107 ) Ad opportunities and O (103 )Ad campaigns. Each campaign participates in only a fraction of
auctions due to targeting. The ads compete with organic content
for user views (with organic content effectively acting as floors).
For a given page, all variants receive the same number of views(regardless of the ranking of the content). If a page has 𝐾 views,
then they go to the top-K contents on the page. The clicks for eachviewed content is sampled from the predicted click-through-rate.
This assumes that the user behavior changes only after viewing
the content, not before. The auction pricing is second-price. The
payment event is view and the advertisers specify a target cost-perview. The dual variables are updated every 1 minute with learning
rate as recommended in [9].
4.2.2 Variants: We test six variants: (i) Max-cap, (ii) Cost-controltheoretical, (iii)-(vi) Cost-control-practical with 𝛽 = 0.8, 0.5, 0.2, 0.0.
𝑗4.2.3 Metrics: Let 𝑀 be the number of campaigns and let 𝐶 view𝑗and 𝑐 view be the target and actual cost-per-view of the 𝑗 th campaign.

Then, we measure the number of campaigns for which the cost-perview constraint is violated by more than 5% of the target cost. That
is,
!
𝑗
𝑗
𝑀
𝑐 view − 𝐶 view
1 ∑︁𝑀violations =1> 0.05(5)𝑗
𝑀 𝑗=1
𝐶 view
Additionally, let 𝑢 𝑗 be the utility accrued by the 𝑗 th campaign. We
define Max-cap as the baseline variant and measure the relative
uplift in the utility. That is,𝑗𝑗

1 ∑︁ (𝑢 variant − 𝑢 baseline )
𝑗
𝑀 𝑗=1
𝑢
𝑀

𝑈 advertiser =(6)baseline

We find that the number of views for some campaigns can be very
low and the number of clicks can be even lower (usually, 2 ordersof magnitude smaller). This results in high variance in the above
metrics that are based on cost-per-view and advertiser value (i.e.
clicks). Therefore, we keep only those campaigns with more than
300 views and at least, 1 click in the baseline, still leaving O (103 )Ad campaigns, and we report the metrics on those campaigns.
4.2.4 Results: We show the results in Tab 1. From the table, we cansee that Max-cap has zero violations on the target cost-per-view,

AdKDD ’24, August 25, 2024, Barcelona, Spain

Katti et al.

Table 1: Large-scale evaluation results
𝑀𝑣𝑖𝑜𝑙𝑎𝑡𝑖𝑜𝑛𝑠

𝑈𝑎𝑑𝑣𝑒𝑟𝑡𝑖𝑠𝑒𝑟

0%
8.15%
4.12%
5.13%
5.21%
5.46%

+22.09%+22.60%+25.84%+17.49%+11.68%Max-cap
Cost-control-theoretical
Cost-control-practical, 𝛽 = 0.8
Cost-control-practical, 𝛽 = 0.5
Cost-control-practical, 𝛽 = 0.2
Cost-control-practical, 𝛽 = 0.0

but generates the lowest utility to the advertisers. Cost-controltheoretical violates the target cost-per-view on 8.15% of campaigns,
but generates +22.09% uplift in utility compared to Max-cap. Costcontrol-practical with 𝛽 = 0.8, 0.5, 0.2, 0.0 violate the target cost-perview on only 4.12%, 5.13%, 5.21%, 5.46% of campaigns respectively
while generating +22.60%, +25.84%, +17.49%, +11.68% uplifts inutility over Max-cap respectively. Moreover, compared to Costcontrol-theoretical, Cost-control-practical reduces the cost violations
by 50% while generating the same utility, with 𝛽 = 0.8 making
the best trade-off. Based on the results, we also find that Costcontrol-practical provides a more reliable cost lever to advertisers forsteering their campaigns towards the desired volume and efficiency.

5

CONCLUDING REMARKS

Summary: We considered a scenario where advertisers run amarketing campaign to achieve a certain objective under budget
and cost-per-outcome constraints. We showed the ineffectivenessof the theoretically derived bidding formula in meeting the cost
constraints and proposed an adjusted bidding formula with a new
𝛽 parameter. Through simulations and large-scale evaluations, wedemonstrated that the proposed bidding formula reduces cost violations by 50%.
How to select 𝛽: The optimal value of 𝛽 depends on how close theprices are to the bids, which is a property of the market itself. If themarket competition is high, then prices (in second-price auctions)closely follow the winning bids. In this case, we need a lower 𝛽(say, 0.5) to push the bids and correspondingly, the prices down toachieve an effective cost control. On the other hand, if the market
competition is low, then prices are much lower than the winningbids. In this case, a 𝛽 slightly lower than 1 (say, 0.9) is alreadyenough to push the prices down and control costs. A 𝛽 close to 0 is
not recommended as it negatively impacts the utility generated tothe advertiser (as shown in Tab 1). Ultimately, 𝛽 should be viewed
as a hyperparameter that is tuned for the market.
Future work: While we proposed an alternative bidding formulaand proved its effectiveness in an empirical manner, it still lacks atheoretical justification. Moreover, it is also not clear if this modification is the most effective one. Future work will be to explore
and compare with other modifications and possibly arrive at atheoretical justification.

6

AUTHOR CONTRIBUTIONS

Anoop leads the bidding algorithm design and contributed to setting
up the problem, identifying the improvement, running simulations

on the synthetic data and producing the results for large-scale evaluation. Rui contributed to identifying the improvement, runningsimulations on the synthetic data and the engineering implementation. Rinchin contributed to the engineering implementation.

ACKNOWLEDGMENTS
Thanks to Lorenz Knies for building the tool that enabled thelarge-scale evaluation. Thanks to Grigorii Fadeev, Dmitry Volodin,
Benjamin Tanz, Mustafa Khandwawala and Amir Davari for thevaluable discussions. Thanks to the leadership team for sponsoring the work – Manuel Vanzetti, Evgeny Belov, Nicolas Guénon,Paul Gorman, Dinesh Deva. Thanks to Andrey Kashin and Tigran
Bagramyan for keeping us true to the customer requirements.
Thanks to the reviewers for their valuable feedback.

REFERENCES[1] Santiago Balseiro and Yonatan Gur. 2019. Learning in repeated auctions withbudgets: Regret minimization and equilibrium. Management Science 65, 9 (2019),
3952–3968.
[2] Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni.
2017. Budget management strategies in repeated auctions. In World Wide Web.
15–23.
[3] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2020. Dual mirror descentfor online allocation problems. In International Conference on Machine Learning.
PMLR, 613–628.
[4] Santiago R Balseiro, Haihao Lu, Vahab Mirrokni, and Balasubramanian Sivan.
2022. On Dual-Based PI Controllers for Online Allocation Problems. arXiv
preprint arXiv:2202.06152 (2022).
[5] Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, andDefeng Guo. 2017. Real-time bidding by reinforcement learning in display advertising. In Web search and data mining. 661–670.
[6] Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2022. Online learningwith knapsacks: the best of both worlds. In International Conference on Machine
Learning. PMLR, 2767–2783.
[7] Andrea Celli, Riccardo Colini-Baldeschi, Christian Kroer, and Eric Sodomka. 2022.
The parity ray regularizer for pacing in auction markets. In Web Conference.
162–172.
[8] Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. 2022.
Multiplicative pacing equilibria in auction markets. Operations Research 70, 2(2022), 963–989.
[9] Yuan Gao, Kaiyu Yang, Yuanlong Chen, Min Liu, and Noureddine El Karoui.
2022. Bidding agent design in the linkedin ad marketplace. arXiv preprint
arXiv:2202.12472 (2022).
[10] Sahin Cem Geyik, Luthfur Chowdhury, Florian Raudies, Wen Pu, and Jianqiang
Shen. 2020. Impression Pacing for Jobs Marketplace at LinkedIn. In Conferenceon Information & Knowledge Management. 2445–2452.
[11] Yue He, Xiujun Chen, Di Wu, Junwei Pan, Qing Tan, Chuan Yu, Jian Xu, andXiaoqiang Zhu. 2021. A unified solution to constrained bidding in online display
advertising. In Knowledge Discovery & Data Mining. 2993–3001.
[12] Olivier Jeunen, Sean Murphy, and Ben Allison. 2022. Learning to bid with
AuctionGym. (2022).
[13] Phuong Ha Nguyen, Djordje Gligorijevic, Arnab Borah, Gajanan Adalinge, andAbraham Bagherjeiran. 2023. Practical Budget Pacing Algorithms and Simulation
Test Bed for eBay Marketplace Sponsored Search. In AdKDD Workshop.
[14] Alessandro Nuara, Francesco Trovò, Nicola Gatti, and Marcello Restelli. 2022.
Online joint bid/daily budget optimization of internet advertising campaigns.
Artificial Intelligence 305 (2022), 103663.
[15] Michael Tashman, Jiayi Xie, John Hoffman, Lee Winikor, and Rouzbeh Gerami.
2020. Dynamic bidding strategies with multivariate feedback control for multiple
goals in display advertising. arXiv preprint arXiv:2007.00426 (2020).
[16] Xun Yang, Yasong Li, Hao Wang, Di Wu, Qing Tan, Jian Xu, and Kun Gai. 2019.
Bid optimization by multivariable control in display advertising. In Knowledge
discovery & data mining. 1966–1974.
[17] Weinan Zhang, Yifei Rong, Jun Wang, Tianchi Zhu, and Xiaofan Wang. 2016.
Feedback control of real-time display advertising. In Web Search and Data Mining.
407–416.
[18] Weinan Zhang, Shuai Yuan, and Jun Wang. 2014. Optimal real-time bidding for
display advertising. In Knowledge discovery and data mining. 1077–1086.