??? University of Maryland College Park USA University of Maryland College
Park USA

# Analysis of a Learning Based Algorithm for Budget Pacing

MohammadTaghi Hajiaghayi<EMAIL_ADDRESS>and  Max Springer<EMAIL_ADDRESS>
###### Abstract.

In this paper, we analyze a natural learning algorithm for uniform pacing of
advertising budgets, equipped to adapt to varying ad sale platform conditions.
On the demand side, advertisers face a fundamental technical challenge in
automating bidding in a way that spreads their allotted budget across a given
campaign subject to hidden, and potentially dynamic, cost functions. This
automation and calculation must be done in runtime, implying a necessarily low
computational cost for the high frequency auction rate. Advertisers are
additionally expected to exhaust nearly all of their sub-interval (by the hour
or minute) budgets to maintain budgeting quotas in the long run. To resolve
this challenge, our study analyzes a simple learning algorithm that adapts to
the latent cost function of the market and learns the optimal average bidding
value for a period of auctions in a small fraction of the total campaign time,
allowing for smooth budget pacing in real-time. We prove our algorithm is
robust to changes in the auction mechanism, and exhibits a fast convergence to
a stable average bidding strategy. The algorithm not only guarantees that
budgets are nearly spent in their entirety, but also smoothly paces bidding to
prevent early exit from the campaign and a loss of the opportunity to bid on
potentially lucrative impressions later in the period.

In addition to the theoretical guarantees, we validate our algorithm with
experimental results from open source data on real advertising campaigns to
further demonstrate the effectiveness of our proposed approach.

###### Key words and phrases:

budget pacing, auction systems, mechanism design, learning algorithm

##  1\. Introduction

Ad impressions sold through real-time bidding (RTB) auctions are responsible
for an ever-increasing portion of company expenditures as well as the revenue
of large ad providers like Google, Facebook, Amazon, Microsoft, and Yahoo!.
Google alone is responsible for upwards of 50 billion ad impressions on
average per day Tunuguntla and Hoban (2021), with a corresponding revenue on
the order of $100 million. While companies bidding in these advertising
campaigns do not participate in every auction throughout the day, they are
often required to participate enough to spend their allotted budget in this
time. Thus, great interest is placed on adequately pacing budgets throughout
the day so as to not spend too hastily at the beginning of a day and miss out
on better impressions, or spend too frugally until the close of day.

We here take the perspective of a demand-side platform (DSP), an intermediary
serving as the interface connecting advertisers with ad-exchanges and offering
customized bid strategies in online auctions. Our model of a DSP is given a
users budget and target spent amount, and is asked to uniformly pace spending
so as to exhaust this amount.

In optimizing bids within an RTB, an advertiser hopes to maximize key
performance indicators, such as cost per conversion (CPC) or click through
rate (CTR), for an ad campaign subject to the budgeting constraints for each
time period Cai et al. (2017); Jauvion and Grislain (2020); Lobos et al.
(2018); Zhang et al. (2014). By smoothly spreading a budget across the
duration of a campaign, an advertiser can ensure sustained influence across
the broad spectrum of ad impressions with which they interact. We can
summarize the objective of an advertiser using a DSP as follows:

  * •

Achieve performance goals: in an advertising campaign, performance goals are
typically meant to ensure a broad audience is reached while maintaining a low
CPC, ie. the investment required to acquire new customers is relatively small.

  * •

Optimally pace the budget: an advertiser hopes to have a sustained influence
in an ad campaign, smoothly rolling out their advertisements to ensure impact
on users. This budget pacing can be uniform (equal representation throughout a
campaign) or potentially more sophisticated so as to maximize the number of
users reached during certain times of the day, while placing less priority on
other periods.

In spite of the ever increasing prevalence of online advertising in modern
society and the clear value of optimizing the above objectives in practice,
the research literature on the problem instance of optimally spending budgets
in their entirety is limited. The bulk of the work either excludes
comprehensive analysis of the stability of a proper budget pacing mechanism in
favor of simulating these results Cai et al. (2017); Lee et al. (2013); Xu et
al. (2015), or does not impose the realistic constraints that are met in the
advertising economy Fernandez-Tapia (2015); Lobos et al. (2018). As such, we
bring an analytic approach in combination with simulated results on real
datasets of our pacing mechanism to bridge this gap in the literature.

###  1.1. Main Ideas

In this paper, we present an online approach to smoothly and uniformly pacing
an advertiser’s budget over a fixed-length advertising campaign. Our approach
invokes an iterative control feedback mechanism to estimate the proper
_average_ bid to submit over each time period, which is later manipulated by a
mechanism (potentially hidden to the bidder) to compute an “actual spent
amount” for that period so that the total budget is approximately spent in a
uniform fashion throughout the campaign. The algorithm relies on simplistic
scaling of bids in response to learning of this latent mechanism in a
naturalistic way, and is currently in implementation at two major companies
with which the authors were previously affiliated. Specifically, we
analytically derive the stability and convergence time of this natural
learning algorithm that has analogously appeared in other online bidding
literature Lee et al. (2013); Zhang et al. (2014). Though simple, this
algorithm exhibits low convergence times for the problem of budget pacing and
possesses interesting dynamics in accordance with other one-dimensional
mappings like the logistic map. We summarize our main results informally:

  * •

Develop an iterative control feedback algorithm for smart pacing of an
advertisers budget through an ad campaign.

  * •

Analytically derive the efficiency of this algorithm in quickly converging to
an optimal bid strategy to ensure budgeting quotas are met.

  * •

Implement our algorithm with extensive simulations on real ad campaigns from
Yahoo! to demonstrate its feasibility in practice.

The remainder of the paper is organized as follows. In Section 2, we discuss
the budgeting problem on a high level and previous work in the field. In
Section 3, we describe our model and give a comprehensive analysis of the
convergence dynamics exhibited. We discuss extensions of our algorithm to
account for other realistic budgeting schemes to be implemented by a DSP in
Section 4, and finally present simulations of our algorithm on real datasets
in Section 5 to demonstrate its utility in practice. We conclude with a
discussion of our methodology, its limitations, and where future work will be
directed.

##  2\. Background and Related Work

In this section, we discuss the problem of budget pacing with the joint
problem of bid optimization, and subsequently discuss the related work, noting
where these results fall short of the reality of RTB schemes.

###  2.1. Problem Statement

We consider _online bid optimization_ in the following framework: there are
$T$ auction periods ordered by an index $t\in\\{1,...,T\\}$. At the start of
an auction period, an individual advertiser must make a decision as to how
much to bid for desired ads within this period, denoted by $b_{t}$.
Advertisers further have a total daily budget $B\in\mathbb{R}$ that limits the
amount that can be spent within the day. Typically, advertisers would like to
have smooth budget delivery Agarwal et al. (2014); Avadhanula et al. (2021);
Balseiro and Gur (2017); Balseiro et al. (2021); Conitzer et al. (2018); Lee
et al. (2013); Xu et al. (2015), expressed as not buying more than a set
fraction of the impressions before a given time in order to ensure that:

  1. (1)

budgets are not prematurely expended, thus resulting in missed opportunities
later in the day

  2. (2)

spending does not fluctuate substantially for ease of analysis.

As a simple example, assume that each $t$ denotes a 2 minute ad period on a
streaming website. Within this time frame, advertiser $A$ may choose to bid
with value $b_{t}$ in auctions against all advertisers interested in showing
an ad to a given subset of users. Within a split-second, the highest bidder
for each user is chosen and $A$ must pay for the auctions they won, incurring
some cost

$c_{t}=b_{t}\times\text{ (number of auctions won)}.$

Following observation of this incurred cost, the advertiser $A$ invokes an
algorithm to adjust their bidding in an effort to ensure a smooth depletion of
their budget throughout the day.

We note that for each impression, the base bid $b_{t}$ can be rescaled in a
manner corresponding to the value of the impression for that advertiser. For
example: as formulated in Perlich et al. (2012), the bid value of the $i$-th
impression is rescaled by the probability of its conversion $p_{i}$, divided
by the average conversion (denoted $\overline{p}$). This is often done for
individual impressions of great interest to an advertiser, however, in our
formulation, $b_{t}$ is submitted on average in each auction period.

The added complication of the smooth delivery problem we focus on in the
present study is that oftentimes, when an advertiser submits a bid in an
auction, this may not be the true value they pay for that impression. As
demonstrated in the simple example above, although $A$ submits a bid $b_{t}$,
they actually incur a cost that is potentially much larger (proportional to
the number of auctions won).

In response, the pacing of an advertiser’s budget relies on learning the
actual cost of submitted bids to adequately scale bid values to meet desired
spending goals in each period.

We can now formally frame the budget pacing problems as:

minimize $\displaystyle B-\sum_{t=1}^{T}c_{t}$ (1) subject to
$\displaystyle\left|\frac{B}{T}-c_{t}\right|\leq\epsilon$ (2)

for some $\epsilon\ll 1$ and where the optimization is framed using the
information for all the auctions, however, the problem itself is online. As a
result, it is clear we need an algorithm that quickly learns the latent cost
function, $f(b_{t})=c_{t}$, in a small portion of the total number of auctions
and subsequently uniformly paces their bidding for the duration of the
campaign. Of crucial importance, we note that the cost function in each period
implicitly contains information on the number of impressions won and overall
surplus generated based on the value of impressions won, subject to the
payment rules of whichever auction mechanism is implemented for those
impressions.

Lastly, it is important to note that the cost function, $f$, is _subject to
change_ at different times in a campaign and can be adjusted by the advertiser
when manipulating their target spend amount for different times. For example,
if the algorithm is being utilized to exhaust a daily budget, the advertiser
may emphasize impressions in the morning and input a higher target spend
amount for that portion of the day, while reducing this target for later times
in the day. With slight modifications of our algorithm we can further capture
these instances (see Section 4).

###  2.2. Related Work

Real-time bidding strategies have an expansive literature Celli et al. (2021);
Feng et al. (2018); Geyik et al. (2015); Karaca et al. (2019); Nedelec et al.
(2019); Weed et al. (2016), however the field of optimal budget pacing is
relatively new and, as such, the literature thus far is often limited in scope
Agarwal et al. (2014); Balseiro and Gur (2017); Balseiro et al. (2021); Borgs
et al. (2007). We here examine the methodologies of a select number of other
studies whose work closely aligns with our own, the aspects of real-time
bidding they encompass, and where they fall short.

Most closely related to our work is that of Lee et al. Lee et al. (2013),
which devises a comparable algorithm for pacing the budget while also
maximizing the performance indicators of impressions. In particular, their
algorithm scales bids between successive rounds to ensure smooth delivery of
the budget without early exit. However, this paper maximizes impression value
by estimating a threshold for advertisers to begin bidding. As a result, the
algorithm bids more highly on the valuable impressions, but risks overspending
and early exit from the campaign in these instances. Our algorithm instead
ensures that agents are present throughout the entire campaign so that no
impression is missed out on and guarantees sustained presence in an ad space.
Additionally, the work of Lee et al. does not account for the real-world
quotas that advertisers must meet, forcing them to spend their budgets in
close to their entirety. Our algorithm accounts for this constraint and
utilizes it in the scaling of bid values.

The work done by Xu et al. Xu et al. (2015) also aligns well with our study,
emphasizing smooth delivery of budget and minimizing the probability of early
exit from a campaign to ensure a sustained presence for advertisers. When
omitting performance goals, their algorithm is comparable to ours as it
optimizes bidding by scaling bids based on the discrepancy between desired
spending amount and the actuality. Additionally, they optimize over a fixed
penalty function, similar to our latent cost function. However, their
algorithm is not robust to changes in this penalty over time and fails to
provide analytic results on the convergence and stability of this algorithm.
Our study attempts to bridge the gap between the analytic and computational
studies on optimal budget pacing. Lastly, this paper fails to consider the
real-world constraint of budgeting quotas.

Fernandez-Tapia Fernandez-Tapia (2015) examines the pacing problem from
different perspective to the above, deriving analytical results through
variational calculus techniques. This work compares the optimal bidding
strategy when RTBs occur at a linear rate (fixed spacing between bids) and
nonlinear. As most papers, including our own, make the simplifying assumption
that auctions occur at such a high rate that we need not consider unequal
arrival of the impressions to bid on, this more technical study highlights a
more complex and realistic setting of auctions. However, while impressions may
arrive in this more complicated fashion, advertisers do not in practice base
their strategies around this assumption. As such, our algorithm is better
suited for real-world implementation.

The problem of finding an optimal bidding strategy for an advertiser who does
not know their own valuation, subject to budgeting constraints, has also been
studied as an extension of the multi-armed bandit problem as in Avadhanula et
al. (2021). Avadhanula et al. provide bidding schemes over discrete and
continuous bid spaces for $m$ platforms simultaneously with regret lower
bounds of $\Omega\left(\sqrt{mOPT}\right)$ and
$\Omega\left(m^{1/3}B^{2/3}\right)$ – where $B$ is the budget and $OPT$ the
performance of the optimal bidding strategy. This model however is limited in
that the auction format is restricted to a second-price auction payout
mechanism, whereas our approach provides a more general framework which can be
applied to any auction mechanism.

##  3\. Optimal Bidding

In this section, we detail the algorithm for learning the latent cost function
and uniformly pacing an advertiser’s budget throughout an advertising
campaign. We first present the algorithm with the intuition behind its
definition and proceed by analyzing the convergent dynamics and efficiency. We
emphasize uniformly pacing an advertiser’s budget, or target spend amount, so
that all auction periods are weighted equally. The primary concern is to spend
the entirety of their budget while staying active in the campaign for as long
as possible.

We define the metrics by which a budget pacing algorithm should be measured in
order to assess its overall effectiveness in online real-time bidding systems.

  1. (1)

Fast convergence to a stable bidding strategy relative to the overall campaign
duration.

  2. (2)

Adaptive capacity for changes in the display auction mechanism (manipulated on
the supplier end).

Ensuring good performance metrics is complex in the online market due to the
speed and frequency that impressions are sold, yet we prove in this section
that our natural learning algorithm performs well due in large part to its
simplicity and efficient computation.

###  3.1. Pacing Algorithm

We begin by assuming an advertiser has two pieces of information: its budget,
$B$, and the number of auction periods in the campaign, $T$ (ie. auction
periods per day). Intuitively, the advertiser who is trying to uniformly pace
their budget will initially bid its average budget for the corresponding
number of auctions, $b_{0}=\frac{B}{nT}$ (where $n$ is the number of auctions
per period). However, in general, the actual cost is much larger than the
input bid and the convergence time remains low regardless of this initial bid
selection, so any choice suffices. Once an initial average bid is set, it is
utilized for the first period ($t=0$), once again being scaled for each
impression in accordance with their value, and the agent incurs cost $c_{0}$
throughout this time.

Following the initial bid, an advertiser now has the information of how much
was spent in the first period and can assess the discrepancy between the
_desired_ amount to be spent and the _actual_ amount. Let $B_{r}^{t}$ denote
the remaining budget after period $t$, and $c_{t}$ be the incurred cost in
this period, then we can define the scaling factor
$\frac{B_{r}^{t}}{T-t}\cdot\frac{1}{c_{t}}$ as the ratio of the amount the
advertiser wants to spend on average in each remaining auction period to how
much it spent on the previous. Using this ratio as a budget pacing factor, we
have the following iterative scheme:

$\displaystyle b_{t+1}=\frac{B_{r}^{t}}{c_{t}(T-t)}\cdot b_{t}$

Algorithm 1 Budget Smoothing

1: Input: $B,T,t,b_{t},(c_{0},...,c_{t})$

2: Output: $b_{t+1}$

3: $B_{r}^{t}=B-\sum_{i=0}^{t}c_{i}$ {remaining budget after time $t$}

4: $c_{\text{opt}}=\frac{B_{r}^{t}}{T-t}$ {optimal spend amount}

5: $c_{\text{act}}=c_{t}$ {actual spend amount}

6: $\alpha=\frac{c_{\text{opt}}}{c_{\text{act}}}$

7: return $\alpha\cdot b_{t}$

Algorithm 1 takes as input the budget ($B$), number of periods in a campaign
($T$), current period ($t$), the most recent bid value ($b_{t}$), and the
history of previously spent amounts ($\\{c_{i}\\}_{i=0}^{t}$), outputting a
new average bid value scaled based on this information. Note that each $c_{i}$
is equal to $f(b_{i})$, however the algorithm is trying to _learn_ $f$, so we
use the former notation.

As we will see in Section 3, this intuitive update algorithm converges to a
fixed point that uniformly paces an advertisers budget within a small fraction
of the total auction time, as well as undergoing interesting bifurcations when
parameters of the system are tuned. A brief summary of the results for latent
cost functions in the family $f(b_{t})=C\cdot b_{t}^{k}$, where
$k\in\mathbb{R}$ and $C\in\mathbb{R}_{+}$, are provided in Table 1.

Parameter Range | Dynamics
---|---
$k\leq 0$ | Unstable fixed point
$k\in(0,1)$ | Stable fixed point with convergence time $\propto\frac{\ln(k)}{\ln(1-k)}$
$k=1$ | Stable fixed point with convergence in one iterations
$k\in(1,2)$ | Stable fixed point with convergence time $\propto\frac{\ln(2-k)}{\ln(k-1)}$
$k\geq 2$ | Instability requiring guard rails on spending
Table 1. Summary of convergence results for cost functions of the form
$f(b_{t})=C\cdot b_{t}^{k}$.

In analyzing the efficiency of this learning algorithm, we consider various
reasonable actual cost functions $f(b_{t})=c_{t}$ and their divergent or
convergent behavior to an optimal strategy. In the following analysis we
consider only continuous cost functions, and as such simplify our analysis by
examining polynomial functions which can approximate any such function – a
consequence of the Stone-Weierstrass theorem Rudin (1976).

###  3.2. Linear and Semi-Linear Cost Function

As a warm-up, we first consider the most simplistic form of the latent cost
function: a linear cost. We assume that $f(b_{t})=C\cdot b_{t}$ for some
$C>0$: the situation in which the agent running the ad sale simply scales
incoming bids by a fixed constant factor. We reiterate that such a simple
scaling can effectively capture the dynamics of a repeated first auction
system wherein the actual amount spend by a bidder is proportional to the
number of auctions won in a given period.

In this elementary case, we see that, for any initial bid placed an advertiser
adapts to the latent cost function in exactly one iteration, bidding the
optimal uniform amount for the remainder of the campaign.

######  Theorem 3.1.

For a linear cost function, $f(b_{t})=C\cdot b_{t}$ where $C>0$, and initial
bid $b_{0}$, Algorithm 1 converges to a fixed point bid value in exactly one
iteration.

In many practical instances, it is also important to consider a semi-linear
cost function. We define the semi-linear cost function as
$f(b_{t})=\min\\{C\cdot b_{t},M\\}$111Additionally, if we use the semi-linear
function with a maximum rather than minimum, we see identical convergence
rates. where both $C,M>0$. This is analogous to when the administration of the
ad sales both scale an advertisers bids by a fixed constant factor and also
instate ”guard rails” on the spending: requiring the amount spent to be no
greater than $M$. This is meant to protect against over excessive spending by
an advertiser. Despite this limitation on bids, we see that the semi-linear
function converges in one iteration when $M>\frac{B}{cT}$.

######  Theorem 3.2.

For a semi-linear cost function, $f(b_{t})=\min\\{C\cdot b,M\\}$ where $C>0$,
initial bid $b_{0}<M$, and $M>\frac{B}{CT}$ Algorithm 1 converges to a fixed
point average bid value in exactly one iteration.

Additionally, for $M\gg 1$, the semi-linear function is identical to the
linear case. As a result, proving Theorem 3.2 encompasses the result of
Theorem 3.1.

###### Theorem 3.2.

Assume $b_{0}\neq b^{*}$:

$\displaystyle b_{1}$ $\displaystyle=\text{{Algorithm} 1}(B,T,1,b_{0},c_{0})$
$\displaystyle=\frac{B-\min\\{Cb_{0},M\\}}{\min\\{Cb_{0},M\\}T}\cdot b_{0}$
$\displaystyle=\frac{B-Cb_{0}}{cT}$ $\displaystyle b_{2}$
$\displaystyle=\text{{Algorithm} 1}(B,T,2,b_{1},(c_{0},c_{1}))$
$\displaystyle=\frac{B-\min\\{Cb_{0},M\\}-\min\\{cb_{1},M\\}}{\min\\{cb_{1},M\\}(T-1)}\cdot
b_{1}$
$\displaystyle=\frac{B-Cb_{0}-\min\\{C\cdot\frac{B-Cb_{0}}{CT},M\\}}{\min\\{C\cdot\frac{B-Cb_{0}}{cT},M\\}(T-1)}\cdot\frac{B-Cb_{0}}{CT}$
$\displaystyle=\frac{B-Cb_{0}}{CT}$ $\displaystyle=b_{1}$

∎

###### Theorem 3.1.

Using the result of Theorem 3.2 we take the limit as $M\rightarrow\infty$,
thus giving $\min\\{cb,M\\}=cb$ with convergence in one iteration. ∎

Before proceeding to give theoretical bounds on the convergence times of our
algorithm for the cases where we do not see one iteration convergence, we must
first define the “general cost function” and assess the fixed points of our
system.

###  3.3. General Cost Function

In the most complex case, we consider a general cost function of the form
$f(b_{t})=C\cdot b_{t}^{k}$ where $k\neq 1$. In this case, we here identify
the fixed point of the system and assess its stability.

######  Theorem 3.3.

For $k\in(0,2)$, Algorithm 1 has exactly one stable fixed point for cost
functions of the form $f(b_{t})=C\cdot b_{t}^{k}$ where $C>0$.

###### Proof.

The fixed point of our system occurs when the output of Algorithm 1 is equal
to the input $b_{t}$. Solving this equation yields:

$\displaystyle
b^{*}=\left(\frac{B-\sum_{i=0}^{t-1}Cb_{i}^{k}}{c(T-t+1)}\right)^{1/k}$
(3.3.1)

Noting that in general, if $b_{0}$ is not a fixed point, then the fixed point
for period $t$ is defined as the above. If instead $b_{0}$ is a fixed point,
the system will thus bid this value on average for the entire campaign and the
point has the more simplistic formula derived by the following:

$\displaystyle b^{*}=\left(\frac{B}{C(T+1)}\right)^{1/k}$ (3.3.2)

which is the special case of (3.3.1) where $t=0$. As such it suffices to
examine the more general formula to encompass all results.

In order to prove stability of the above fixed points, we linearize around the
point $b^{*}$ and assess whether the point is attracting or repelling by
examining the derivative at that point Strogatz (2000). Informally, if we let
$|f^{\prime}(b^{*})|=|\lambda|$, then we have linear stability when
$|\lambda|<1$ and instability when $|\lambda|>1$. Now we can analyze our
system’s fixed point. First we differentiate the function in Algorithm 1 to
get the following:

$\displaystyle\frac{d}{db_{t}}\left(\frac{B-\sum_{i=1}^{t}Cb_{i}^{k}}{Cb_{t}^{k}(T-t)}\cdot
b_{t}\right)$
$\displaystyle=\frac{-C+(1-k)b_{t}^{-k}(B-\sum_{i=1}^{t-1}Cb_{i}^{k})}{C(T-t)}$
(3.3.3)

Plugging in the fixed point from (3.3.1) gives the following stability
estimate respectively

$\displaystyle|\lambda|=\left|1-k\left(\frac{T-t+1}{T-t}\right)\right|\approx|1-k|\text{
for }t\ll T$ (3.3.4)

Thus for $0<k<2$, the system is in general attracted to the fixed point
defined in (3.3.1), and the point is unstable outside of this parameter range.
∎

###  3.4. Convergence Time Bound

The crucial result of this paper comes from the minimal convergence time for
Algorithm 1. In contrast to recent papers examining optimal online budget
pacing schemes, none have analytically derived an estimate for convergence
times to these optimal strategies Lee et al. (2013).

######  Theorem 3.4.

For $|1-k|<1$, Algorithm 1 has a bounded distance from the stable bid value at
time $t$ defined by:

$\displaystyle\epsilon:=|b_{t}-b^{*}|\leq\gamma^{-1/k}\cdot\frac{|1-k|^{t-1+\frac{1}{k}}}{1-|1-k|}$

where $\gamma=\frac{CT}{B}$. Subsequently, we have a convergence time,
$t^{*}$, to the stable bid value bounded as:

$\displaystyle
t^{*}\leq\frac{k-1}{k}+\frac{\ln\left|\epsilon\gamma^{1/k}(1-|1-k|)\right|}{\ln|1-k|}$
(3.4.1)

We can see that the convergence time is dependent upon the parameters of our
RTB campaign, namely the budget, length, and degree of the latent cost
function. In order to prove the theorem, we first need a crucial lemma from
the theory of metric spaces, proven in Andrzej Grana (2003).

######  Lemma 3.5 (Banach Fixed Point Theorem).

Assume that $\Omega\subset\mathbb{R}^{n}$ is closed, and that
$G:\Omega\mapsto\Omega$ is a contraction, that is, there exists $0\leq L<1$
such that

$\displaystyle\|G(x)-G(y)\|\leq L\|x-y\|,$

for all $x,y\in\Omega$, where $\|\cdot\|$ is any norm on $\mathbb{R}^{n}$.
Then the function $G$ has a unique fixed point $x^{*}\in\Omega$. Additionally,
let $x_{0}\in\Omega$ be arbitrary and define the sequence
$\\{x_{t}\\}_{t=1}^{\infty}\subset\Omega$ by $x_{t}=G(x_{t-1})$. Then we have
the estimate

$\displaystyle\|x_{t}-x^{*}\|$
$\displaystyle\leq\frac{L^{t}}{1-L}\|x_{1}-x_{0}\|$

In particular the sequence $\\{x_{t}\\}_{t=1}^{\infty}$ converges to $x^{*}$

Invoking this well studied result from Banach requires only that the mapping
is contractive. We henceforth proceed in proving the theorem by demonstrating
this crucial property of Algorithm 1, and applying Lemma 3.5.

###### Theorem 3.4.

To invoke Lemma 3.5 we need to estimate an adequate Lipschitz constant $L$ and
put a proper bound on the distance between two points in the sequence defined
by our algorithm. We first note that

$\displaystyle|G(x)-G(y)|\leq L|x-y|$
$\displaystyle\Rightarrow\frac{|G(x)-G(y)|}{|x-y|}\leq
L\leq|G^{\prime}(x^{*})|$

where $x^{*}\in(x,y)$ gives us an easily computable bound the sequence when
$|G^{\prime}(x)|<1$. Note that we now use the absolute value rather than other
norms since our algorithm uses scalar valued functions.

Stemming from our analysis in Section 3.3, a Lipschitz bound for the dynamics
when $0<k<2$ is $L=|1-k|$. The remaining component needed to apply Lemma 3.5
is a bound on the distance $|b_{1}-b_{0}|$. For any $b_{0}$ that is not the
fixed point, we can look for the maximal distance to $b_{0}$ by taking the
derivative of $b_{1}-b_{0}$ and setting it equal to 0. Assume without loss of
generality that $b_{1}-b_{0}>0$.

$\displaystyle\frac{d}{db_{0}}|b_{1}-b_{0}|$
$\displaystyle=\frac{d}{db_{0}}\left|\frac{B-Cb_{0}^{k}}{Cb_{0}^{k}(T-1)}\cdot
b_{0}-b_{0}\right|$ $\displaystyle=\frac{-C+|1-k|b_{0}^{-k}B}{C(T-1)}-1$

Setting the derivative equal to 0 and finding the maximal $b_{0}$

$\displaystyle b_{0}=\left(\frac{B|1-k|}{CT}\right)^{1/k}$

which gives the distance value

$\displaystyle|b_{1}-b_{0}|=\left|\frac{T-|1-k|}{|1-k|\cdot(T-1)}\cdot\left(\frac{B|1-k|}{CT}\right)^{1/k}\right|$
(3.4.2)

Now plugging in our Lipschitz constant and maximal distance from (3.4.2) to
the estimate from Lemma 3.5 yields

$\displaystyle|b_{t}-b^{*}|$
$\displaystyle\leq\frac{|1-k|^{t-1}}{1-|1-k|}\cdot\left|\frac{T-|1-k|}{T-1}\cdot\left(\frac{B|1-k|}{CT}\right)^{1/k}\right|$
$\displaystyle\approx\frac{|1-k|^{t-1}}{1-|1-k|}\cdot\left|\left(\frac{B|1-k|}{CT}\right)^{1/k}\right|$

Lastly, we can define $\gamma:=\frac{CT}{B}$ to get the simplified

$\displaystyle|b_{t}-b^{*}|\leq\gamma^{-1/k}\cdot\frac{|1-k|^{t-1+\frac{1}{k}}}{1-|1-k|}$

and finally, we can rearrange this inequality to give us a bound on the
convergence time:

$\displaystyle t$
$\displaystyle\leq\frac{k-1}{k}+\frac{\ln\left|\gamma^{-1/k}(1-|1-k|)|b_{t}-b^{*}|\right|}{\ln|1-k|}$
$\displaystyle=\frac{k-1}{k}+\frac{\ln\left|\epsilon\gamma^{1/k}(1-|1-k|)\right|}{\ln|1-k|}$

thus, we have the result. ∎

Lastly, it is important to note that up to this point, we have only considered
latent cost functions which are monomial (consisting of one term). This is a
simplifying assumption which is justified by bounding polynomial cost
functions with monomials, detailed in the following lemma (the proof can be
found in Appendix Analysis of a Learning Based Algorithm for Budget Pacing).

######  Lemma 3.6.

For a cost function defined using the general form
$c_{1}b^{k_{1}}+c_{2}b^{k_{2}}+...c_{m}b^{k_{m}}$ where
$k_{1}>k_{2}>...>k_{m}$ and $b>0$, the convergence time of Algorithm 1 is
bounded by that of monomial functions.

###  3.5. Loss of Stability

As noted in Section 3.3, when $k>2$ the fixed point for average bidding
becomes unstable. As a result, Algorithm 1 does not converge for a cost
function of quadratic or higher degree. In this instance however, we can once
again utilize guard rails on spending to obtain convergence to cyclic bidding
behavior. The following theorem, proven in Appendix Analysis of a Learning
Based Algorithm for Budget Pacing, demonstrates the importance of guard rails
on spending to ensure adequate budget pacing for advertisers adapting to the
RTB auction mechanism. The proof invokes the same strategy as Theorem 3.1,
where we now find $b_{0}$ which are fixed points of Algorithm 1 applied twice,
and can be found in the appendix.

######  Theorem 3.7.

For a cost function of the form min$\\{C\cdot b^{k},M\\}$ where $C>0$ and
$\frac{B}{CT}<M<B$, Algorithm 1 undergoes a period doubling bifurcation at
$k=2$, leading to oscillatory behavior between two average bid values for each
iteration $t$.

This period doubling is further indicative of a canonical path to chaos
Strogatz (2000) and as such a loss of stability for our system.

##  4\. Real-World Implementation

The algorithm presented is easy to implement and can be specifically tailored
to a wide range of applications. As noted previously, slight variants on the
presented algorithm are used at several companies which tailor the bidding to
tertiary interests that we discuss in this section. 222Variations of the bid
pacing algorithm presented in this paper are currently implemented at two
major companies with which an author was previously involved. Due to
proprietary data restrictions at these companies, we focus mainly on important
theoretical aspects of the algorithm along with simulations results in this
paper. We focus on two specific variations: fluctuating target spend amounts
and subthreshold budgets, however the simplicity of our algorithm allows for a
plethora of adjustments for specific needs.

###  4.1. Non-Uniform Pacing

While our main analysis demonstrates the stability of average bidding for the
desired goal of uniform pacing, the algorithm can be simply adapted to meet
changing target spend amounts throughout the campaign. For instance, if an
advertiser wants to decrease spending during the morning since the bulk of
their target market is not online, they may decrease their target spend amount
until later in the day. A variant of this form is easily achieved by adjusting
the submitted budget for any given time period(s). This is achieved by adding
another input parameter $\kappa_{t}\in(0,1]$ which scales the budget by the
multiplier at any given time point. Pseudocode for such a variation on our
algorithm is presented in Algorithm 2. We note that in spite of this tailoring
to a specific need, the convergence properties that were theoretically
justified remain, and will be further validated in Section 5.

Algorithm 2 Non-Uniform Pacing

1: Input: $B,T,t,b_{t},(c_{0},...,c_{t}),\kappa_{t}$

2: $B_{v}\leftarrow\kappa_{t}\cdot B$

3: $b_{t+1}=$ Algorithm 1($B_{v},T,t,b_{t},(c_{0},...,c_{t})$)

4: Output: $b_{t+1}$

Algorithm 3 Subthreshold Budget

1: Input: $B,T,b_{t},(s_{0},...,s_{t})$

2: if $B<\tau$ for some threshold $\tau$ then

3: $B_{v}\leftarrow\sigma\cdot B$ for some $\sigma>1$ fixed by the provider

4: $b_{t+1}=$ Algorithm 1($B_{v},T,b_{t},(s_{0},...,s_{t})$)

5: else

6: $b_{t+1}=$ Algorithm 1($B,T,b_{t},(s_{0},...,s_{t})$)

7: end if

8: Output: $b_{t+1}$

###  4.2. Subthreshold Budgets

In the instance where users submit a budget to the DSP that are too small for
meaningful uniform pacing, the provider can implement a variant on our
algorithm for forcibly exhausting a budget early in the campaign period, thus
resulting in the user needing to update with a larger budget for the next
campaign. 333We once again note that this is common practice at certain
companies, in an effort to force users to meet a minimum budget threshold.
This is achieved by implementing a “virtual budget” where the DSP simply
scales up the input budget and thus the algorithm establishes a higher average
bid than is feasible for the user’s actual budget, leading to early exit from
the campaign. While this outcome is counter to the presented practicality of
the algorithm, it is an effective means by which a provider can ensure that
advertisers are submitting a high enough budget to be competitive in the
market space. This variant’s pseudocode is presented in Algorithm 3. We
reiterate that although the _intent_ of this adapted algorithm is not in line
with the primary justification for our presented results, it nonetheless
retains the convergence properties of Section 3 and will be validated through
experimentation in Section 5.

##  5\. Simulation Results

In this section, we proceed to validate our theoretical results through
comprehensive simulations on both real and simulated data. We demonstrate the
discussed convergence dynamics of the bidding scheme as well as implement our
DSP within the context of a Yahoo! RTB auction system from publicly available
data. All codes for the presented results are available as supplementary
material to our paper.

###  5.1. Bid Dynamics

We here validate our model against simulated results for various different
parameter values. These experiments are meant to illustrate the empirical
behavior of our simplified model. We present the dynamics of bid values as a
function of time in Figure 1 for the three algorithms discussed above. Namely,
the first column plots the dynamics of Algorithm 1, with columns two and three
depicting Algorithms 2 and 3 respectively.

For the presented simulations, the advertisers is given an arbitrary initial
average bid for the first period, and subsequently bids based on the
corresponding algorithms. We henceforth set the budget for all simulations at
$B=50000$, $T=1000$, and an amount spent function defined as
$f(b)=\min\\{b_{t}^{k},100\\}$. Additionally, we once again make the
simplifying assumption that the spent functions are monomials, allowing us to
study the dynamics exclusively as a function of the degree $k$.

Figure 1.  Bid values for different $k$ and algorithms. The first row plots
the bid dynamics of Algorithms 1, 2, 3 for $k=0.5$. The second and third rows
plot the dynamics for $k=1.4$ and $2.3$ respectively.

We first consider $k=0.5$, evaluating (3.4.1) with the given parameter set
gives a bound on the iterations to convergence of $t^{*}\leq 31$. In
simulating the model (row 1 of Figure 1) we see convergence within an error
tolerance $\epsilon=10^{-6}$ in 23 iterations for Algorithm 1, approximately
3% of the total auction period with 99.90% of the budget spent. Additionally,
in the non-uniform instance where we force the system to increase bidding as
the day progresses via Algorithm 2, we see that after each pacing increase the
algorithm quickly converges to a new stable state until the pacing is further
increased according to the advertiser’s request. Lastly, setting a budget
threshold of 75,000, we can use Algorithm 3 to force an early exit of the
advertiser after convergence to a stable bid that is not sustainable.

Increasing the cost function parameter to $k=1.4$, we predict the time to
convergence to be at most $t^{*}=19$ and in simulation (row 2 of Figure 1) we
see convergence in 18 iterations with 99.87% of the budget spent. Thus, our
theoretical results for the stable region are further validated in simulation.
Moreover, we once again exhibit convergence to increasing bid values in the
nonuniform budget pacing context, as well as successful campaign termination
by Algorithm 3.

We lastly show the interesting dynamics that arise when $k\geq 2$. At $k=2$ we
have the birth of 2-cycles in the dynamics, never converging on a singular
fixed point but remaining oscillatory (as discussed in Section 3.5). As we
further increase the parameter, higher order cycles emerge until the system
devolves into aperiodic behavior, more formally known as chaos Strogatz
(2000). The results of this parameter tuning align with the bifurcations
exhibited by the logistic map ($f(x)=rx(1-x)$) Strogatz (2000). The last row
of Figure 1 plots the bid dynamics for $k=2.3$ using the three algorithms. We
see that in all instances, the bid value oscillates about a bid strategy until
the campaign’s conclusion or budget exhaustion. However, even in this unstable
parameter region, our algorithm effectively mitigates this oscillatory
behavior and ensures that the advertisers stays in the ad campaign for its
total duration.

###  5.2. First Price Auction

To further demonstrate the efficacy of our budget pacing algorithm, we invoke
an agent running Algorithm 1 within a first-price auction mechanism as pitted
against advertisers from the Yahoo! real-time bidding dataset. This dataset
contains the bids over time of all advertisers participating in Yahoo! Search
Marketing auctions for the top 1000 search queries during the period from June
15, 2002, to June 14, 2003 (segregated into 15 minute time periods for each
day). We simulate the efficiency of our procedure by selecting a day at random
from the dataset and selecting bid values for arriving impressions within each
15 minute window via Algorithm 1. On each impression in this period, we
implement a first-price auction to decide on a winner and incurred cost (ie.
the highest bidder wins the impression and pays exactly what they bid). Thus,
for the submitted bid value by the algorithm, we observe cost $c_{t}$
(proportional to the number of auctions won) for a given 15 minute period and
update the bid value for the next period in an effort to uniformly pace the
budget expenditure. Figure 2 plots the proportion of budget spent throughout
the day as compared to a perfectly uniform pacing.

Figure 2.  Proportion of the total budget spent as a function of time for an
advertiser running Algorithm 1 in a repeated first-price auction format. The
orange curve indicates uniformly paced budget and blue indicates the
algorithms performance. Figure 3.  Proportion of the total budget spent as a
function of time for an advertiser running Algorithm 2 in a repeated first-
price auction format. The orange curve indicates nonuniformly paced budget and
blue indicates the algorithms _nonuniform_ performance.

We see that – even though the spent amount function is changing in each time
period by nature of the first-price auction, number of bidders, and impression
values – our algorithm successfully adjusts its bidding throughout the day and
maintains a near uniform pacing of the allotted daily budget.

Intuitively, the algorithm is here increasing its bid value for a 15 minute
window when it observes a cost for the prior period that indicates too few
auctions were won. In a symmetric manner, when bidding too high and more
spending occurs than desired, the algorithm lowers its bid value to win less
of the total auctions for a period. As a result, our very simplistic algorithm
manages to successfully pace its budget uniformly in the given realistic
framework.

We further implement Algorithm 2 within the repeated first price auction
setting, where we invoke multipliers that force minimal spending at the start
of the day which slowly increases until the end of day. Such a pacing may be
used for advertisers who are hoping to capture their market after the workday
or those who heavily use a given platform in the evening. Figure 3 plots the
proportion of budget spent throughout the day for this strategy as compared to
a perfectly uniform pacing.

##  6\. Conclusion

Bid optimization has become the central issue of budget pacing in online RTB
problems. Our work has presented and analyzed a natural learning algorithm
that ensures fast convergence times to optimal bids for uniform pacing of an
advertiser’s budget. The algorithm is additionally robust to fluctuations in
the underlying mechanism of the display ad sales, in the form of a latent cost
function. The efficiency of our algorithm is demonstrated both analytically
and numerically through simulations on real data, demonstrating the
feasibility of its implementation in real world systems. Additionally, we
highlight that the algorithm does not rely on a synthesis of neural learning
systems or more complex parameter estimation: it simply learns optimal
behavior by comparing performance in the current iteration to the previous
Perlich et al. (2012).

## References

  * (1)
  * Agarwal et al. (2014) Deepak Agarwal, Souvik Ghosh, Kai Wei, and Siyu You. 2014\.  Budget Pacing for Targeted Online Advertisements at LinkedIn. In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (New York, New York, USA) _(KDD ’14)_. Association for Computing Machinery, New York, NY, USA, 1613–1619.  https://doi.org/10.1145/2623330.2623366
  * Andrzej Grana (2003) James Dugundji Andrzej Grana. 2003\.  _Fixed Point Theory_.  Springer, New York.
  * Avadhanula et al. (2021) Vashist Avadhanula, Riccardo Colini-Baldeschi, S. Leonardi, Karthik Abinav Sankararaman, and Okke Schrijvers. 2021.  Stochastic bandits for multi-platform budget optimization in online advertising.  _Proceedings of the Web Conference 2021_ (2021).
  * Balseiro and Gur (2017) S. Balseiro and Y. Gur. 2017.  Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.  _Proceedings of the 2017 ACM Conference on Economics and Computation_ (2017).
  * Balseiro et al. (2021) S. Balseiro, A. Kim, Mohammad Mahdian, and V. Mirrokni. 2021\.  Budget-Management Strategies in Repeated Auctions.  _Oper. Res._ 69 (2021), 859–876.
  * Borgs et al. (2007) C. Borgs, J. Chayes, Nicole Immorlica, K. Jain, O. Etesami, and Mohammad Mahdian. 2007\.  Dynamics of bid optimization in online advertisement auctions. In _WWW ’07_.
  * Cai et al. (2017) Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo. 2017.  Real-Time Bidding by Reinforcement Learning in Display Advertising.  _CoRR_ abs/1701.02490 (2017).  arXiv:1701.02490 http://arxiv.org/abs/1701.02490
  * Celli et al. (2021) A. Celli, Riccardo Colini-Baldeschi, Christian Kroer, and Eric Sodomka. 2021.  The Parity Ray Regularizer for Pacing in Auction Markets.  _ArXiv_ abs/2106.09503 (2021).
  * Conitzer et al. (2018) Vincent Conitzer, Christian Kroer, Eric Sodomka, and N. Stier-Moses. 2018.  Multiplicative Pacing Equilibria in Auction Markets. In _WINE_.
  * Feng et al. (2018) Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. 2018.  Learning to Bid Without Knowing your Value.  _Proceedings of the 2018 ACM Conference on Economics and Computation_ (2018).
  * Fernandez-Tapia (2015) Joaquin Fernandez-Tapia. 2015\.  An analytical solution to the budget-pacing problem in programmatic advertising.  _Journal of Information and Optimization Sciences_ 40 (November 2015).  https://doi.org/10.1080/02522667.2017.1303946
  * Geyik et al. (2015) Sahin Cem Geyik, Abhishek Saxena, and Ali Dasdan. 2015\.  Multi-Touch Attribution Based Budget Allocation in Online Advertising.  arXiv:1502.06657 [cs.AI]
  * Jauvion and Grislain (2020) Grégoire Jauvion and Nicolas Grislain. 2020.  Optimal Allocation of Real-Time-Bidding and Direct Campaigns.  _CoRR_ abs/2006.07070 (2020).  arXiv:2006.07070 https://arxiv.org/abs/2006.07070
  * Karaca et al. (2019) Orcun Karaca, Pier Giuseppe Sessa, A. Leidi, and M. Kamgarpour. 2019.  No-Regret Learning from Partially Observed Data in Repeated Auctions.  _ArXiv_ abs/1912.09905 (2019).
  * Lee et al. (2013) Kuang-Chih Lee, Ali Jalali, and Ali Dasdan. 2013\.  Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising.  _CoRR_ abs/1305.3011 (2013).  arXiv:1305.3011 http://arxiv.org/abs/1305.3011
  * Lobos et al. (2018) Alfonso Lobos, Paul Grigas, Zheng Wen, and Kuang chih Lee. 2018.  Optimal Bidding, Allocation and Budget Spending for a Demand Side Platform Under Many Auction Types.  arXiv:1805.11645 [math.OC]
  * Nedelec et al. (2019) Thomas Nedelec, Noureddine El Karoui, and Vianney Perchet. 2019.  Learning to bid in revenue-maximizing auctions.  _ArXiv_ abs/1902.10427 (2019).
  * Perlich et al. (2012) Claudia Perlich, Brian Dalessandro, Rod Hook, Ori Stitelman, Troy Raeder, and Foster Provost. 2012\.  Bid Optimizing and Inventory Scoring in Targeted Online Advertising. In _Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Beijing, China) _(KDD ’12)_. Association for Computing Machinery, New York, NY, USA, 804–812.  https://doi.org/10.1145/2339530.2339655
  * Rudin (1976) Walter Rudin. 1976\.  _Principles of mathematical analysis / Walter Rudin_ (3d ed. ed.).  McGraw-Hill New York.  http://www.loc.gov/catdir/toc/mh031/75017903.html
  * Strogatz (2000) Steven H. Strogatz. 2000\.  _Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry and Engineering_.  Westview Press.
  * Tunuguntla and Hoban (2021) Srinivas Tunuguntla and Paul R. Hoban. 2021.  A Near-Optimal Bidding Strategy for Real-Time Display Advertising Auctions.  _Journal of Marketing Research_ 58 (2021), p. 1–21.  https://doi.org/10.1177/0022243720968547 arXiv:https://doi.org/10.1177/0022243720968547
  * Weed et al. (2016) J. Weed, Vianney Perchet, and P. Rigollet. 2016.  Online learning in repeated auctions. In _COLT_.
  * Xu et al. (2015) Jian Xu, Kuang-chih Lee, Wentong Li, Hang Qi, and Quan Lu. 2015.  Smart Pacing for Effective Online Ad Campaign Optimization.  _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Aug 2015).  https://doi.org/10.1145/2783258.2788615
  * Zhang et al. (2014) Weinan Zhang, Shuai Yuan, and Jun Wang. 2014.  Optimal Real-Time Bidding for Display Advertising. In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (New York, New York, USA) _(KDD ’14)_. Association for Computing Machinery, New York, NY, USA, 1077–1086.  https://doi.org/10.1145/2623330.2623633

##  Appendix A Omitted Proofs

###  A.1. Proof of Lemma 3.6

We proceed by bounding the cost function. For $0<b<1$, we bound the function
using the minimal exponent

$\displaystyle
c_{1}b^{k_{m}}<c_{1}b^{k_{1}}+c_{2}b^{k_{2}}+...+c_{m}b^{k_{m}}<\tilde{C}b^{k_{m}}$

where $\tilde{C}:=\sum_{i}^{m}|c_{i}|$ and identically for $b\geq 1$, we bound
the function with the maximal exponent

$\displaystyle
c_{1}b^{k_{1}}<c_{1}b^{k_{1}}+c_{2}b^{k_{2}}+...+c_{m}b^{k_{m}}<\tilde{C}b^{k_{1}}$

For convenience, let $s(b):=c_{1}b^{k_{1}}+c_{2}b^{k_{2}}+...+c_{m}b^{k_{m}}$
and without loss of generality assume $b\geq 1$. Using the above we
demonstrate the following bounds on Algorithm 1 for the general cost function

$\displaystyle c_{1}b^{k_{m}}$ $\displaystyle<s(b)<\tilde{C}b^{k_{m}}$
$\displaystyle\frac{1}{c_{1}b^{k_{m}}}$
$\displaystyle>\frac{1}{s(b)}>\frac{1}{\tilde{C}b^{k_{m}}}$ $\displaystyle
b\cdot\left(\frac{B}{Tc_{1}b^{k_{m}}}-\frac{1}{T}\right)$
$\displaystyle>b\cdot\left(\frac{B}{Ts(b)}-\frac{1}{T}\right)$
$\displaystyle>b\cdot\left(\frac{B}{T\tilde{C}b^{k_{m}}}-\frac{1}{T}\right)$

which is equivalent to the output of Algorithm 1 with $t=0$. Thus, we have the
algorithm bound

$\displaystyle\text{Algorithm 1}(B,T,0,b_{0},c_{1}b_{0}^{k_{m}})$
$\displaystyle>\text{Algorithm 1}(B,T,0,b_{0},s(b_{0}))$
$\displaystyle>\text{Algorithm 1}(B,T,0,b_{0},\tilde{C}b_{0}^{k_{m}})$

Lastly, manipulating the result from Banach in Lemma 3.5 we have the
convergence time bound

$\displaystyle
t\geq\ln\left(\frac{(1-L)|b_{t}-b^{*}|}{|b_{1}-b_{0}|}\right)/\ln(L)$

substituting the output of Algorithm 1 for $b_{1}$, we thus define the
convergence time bound for a cost function $c$ as

$\displaystyle\tau_{s(b)}:=\ln\left(\frac{(1-L)|b_{t}-b^{*}|}{|\text{Algorithm
1}(B,T,0,b_{0},s(b_{0}))-b_{0}|}\right)/\ln(L)$ (A1.1)

Now combining with the algorithm bounds above gives

$\displaystyle\frac{(1-L)|b_{t}-b^{*}|}{|\text{Algorithm
1}(B,T,0,b_{0},c_{1}b_{0}^{k_{m}})-b_{0}|}$
$\displaystyle<\frac{(1-L)|b_{t}-b^{*}|}{|\text{Algorithm
1}(B,T,0,b_{0},s(b_{0}))-b_{0}|}$
$\displaystyle<\frac{(1-L)|b_{t}-b^{*}|}{|\text{Algorithm
1}(B,T,0,b_{0},\tilde{C}b_{0}^{k_{m}})-b_{0}|}$

which using definition (A1.1) equates to

$\displaystyle
L^{\tau_{c_{1}b^{k_{m}}}}<L^{\tau_{s}}<L^{\tau_{\tilde{C}b^{k_{m}}}}\Rightarrow\tau_{c_{1}b^{k_{m}}}<\tau_{s(b)}<\tau_{\tilde{C}b^{k_{m}}}$

bounding the general cost function’s convergence time with monomials.

###  A.2. Proof of Theorem 3.7

A 2-cycle for a function $f(x)$ exists if and only if there are two points
$x_{1},x_{2}$ such that $f(x_{1})=x_{2}$ and $f(x_{2})=x_{1}$. Equivalently,
these points must satisfy $f(f(x_{1}))=x_{1}$ and $f(f(x_{2}))=x_{2}$. We
proceed by finding the points that satisfy the latter condition, in our
context being the points which are fixed points when applying Algorithm 1
twice. Solving this relation amounts to the following problem

$\displaystyle b_{1}$ $\displaystyle=\text{Algorithm
1}(B,T,0,b_{0},\min\\{cb_{0}^{k},M\\})$
$\displaystyle=\frac{B-\min\\{cb_{0}^{k},M\\}}{\min\\{cb_{0}^{k},M\\}T}\cdot
b_{0}$ $\displaystyle b_{2}$ $\displaystyle=\text{Algorithm
1}(B,T,1,b_{1},(\min\\{cb_{0}^{k},M\\},\min\\{cb_{1}^{k},M\\}))$
$\displaystyle=\frac{B-\min\\{cb_{0}^{k},M\\}-\min\\{cb_{1}^{k},M\\}}{\min\\{cb_{1}^{k},M\\}(T-1)}\cdot
b_{1}$ $\displaystyle=$
$\displaystyle\frac{B-\min\\{cb_{0}^{k},M\\}-\min\\{c\left(\frac{B-\min\\{cb_{0}^{k},M\\}}{\min\\{cb_{0}^{k},M\\}T}\cdot
b_{0}\right)^{k},M\\}}{\min\\{c\left(\frac{B-\min\\{cb_{0}^{k},M\\}}{\min\\{cb_{0}^{k},M\\}T}\cdot
b_{0}\right)^{k},M\\}(T-1)}$
$\displaystyle\cdot\frac{B-\min\\{cb_{0}^{k},M\\}}{\min\\{cb_{0}^{k},M\\}T}\cdot
b_{0}$ (A2.1)

We now consider three unique cases for the value of the minimizations:
Case 1: $\min\\{cb_{0}^{k},M\\}=cb_{0}^{k},\min\\{cb_{1}^{k},M\\}=cb_{1}^{k}$
Setting (A2.1) $=b_{0}$ and solving gives us

$\displaystyle b_{0}=\left(\frac{B}{c(T+1)}\right)^{1/k}$

which is the original fixed point )3.3.1) from Section 3.3 that was proved to
now be unstable for $k>2$. As a result, the value of the bid will be repelled
from this point to the two points of our cycle. It is important to note that
any fixed point of a function $f$ satisfies $f(x)=x$ so we automatically have
$f(f(x))=f(x)=x$. We thus need not consider this trivial point in the 2 cycle,
as we are interested in the situation where $f(f(x))=x$ and $f(x)\neq x$.
Case 2: $\min\\{cb_{0}^{k},M\\}=cb_{0}^{k},\min\\{cb_{1}^{k},M\\}=M$
Once again solving (A2.1) $=b_{0}$ produces the following point

$\displaystyle b_{0}=2^{-1/k}(\sqrt{(-2B-MT^{2}+MT+M)^{2}+4B(M-B)}$
$\displaystyle+2B+MT^{2}-MT-M)^{1/k}$

for which we need to verify $b_{0}\in\mathbb{R}$. Real solutions exist for

$\displaystyle\sqrt{(-2B-MT^{2}+MT+M)^{2}+4B(M-B)}+2B+...$ $\displaystyle
MT^{2}-MT-M>0$ $\displaystyle\Rightarrow(-2B-MT^{2}+MT+M)^{2}+4B(M-B)$
$\displaystyle>(M+MT-2B-MT^{2})^{2}$ $\displaystyle M>B$

however this last inequality on M does not hold. Therefore
$b_{0}\in\mathbb{C}$ in this case and thus this is not one of our period two
points since our bid values are constrained to the real numbers.
Case 3: $\min\\{cb_{0}^{k},M\\}=M,\min\\{cb_{1}^{k},M\\}=cb_{1}^{k}$
Solving (A2.1) $=b_{0}$ once again yields

$\displaystyle b_{0}=\left(\frac{(B-M)^{2}}{c(B-M-MT+MT^{2})}\right)^{1/k}$

for which we once again need to verify $b_{0}\in\mathbb{R}$. It is clear that
$(B-M)^{2}>0$, so we need only check

$\displaystyle c(B-M-MT+MT^{2})>0$ $\displaystyle cM(T^{2}-T-1)>B$
$\displaystyle M>\frac{B}{c(T^{2}-T-1)}$

For $T>1$, $\frac{B}{cT}>\frac{B}{c(T^{2}-T-1)}$. Combining this with fact
that $M>\frac{B}{cT}$, verifies the above inequality and thus
$b_{0}\in\mathbb{R}$. Therefore, this is one of the points in our 2-period
cycle. Lastly, to find the second point of this cycle, we simply apply the
algorithm again. Let $b_{-}$ denote the first point. We once again have two
subcases which depend on the value of $c$. For
$\min\\{cb_{-}^{k},M\\}=cb_{-}^{k}$

$\displaystyle b_{+}$ $\displaystyle=\text{Algorithm
1}(B,T,0,b_{-},\min\\{b_{-}^{k},M\\})$
$\displaystyle=\frac{B-\min\\{b_{-}^{k},M\\}}{\min\\{b_{-}^{k},M\\}T}\cdot
b_{-}$ $\displaystyle=\frac{B-b_{-}^{k}}{b_{-}^{k}T}\cdot b_{-}$
$\displaystyle=\frac{MT}{B-M}\left(\frac{(B-M)^{2}}{c(B-M-
MT+MT^{2})}\right)^{1/k}$ $\displaystyle=\frac{MT}{B-M}\cdot b_{-}$

and for $\min\\{cb_{-}^{k},M\\}=M$

$\displaystyle b_{+}=\frac{B-M}{MT}\cdot b_{-}$

Therefore we have our two cycle producing oscillatory behavior between $b_{+}$
and $b_{-}$.