Automated Bidding in a Repeated Bidding Game

An automated bidding agent is a software used for buying ad impressions on behalf of an advertiser. An advertiser specifies aggregate objectives and constraints, and a dynamic bidding algorithm tunes the bids of an ad campaign to meet those objectives. Automated bidding agents are now standard in online advertising auctions.

Online ad impressions are sold by repeated auctions. Bids to those actions are specified through advertiser campaigns and can vary by keyword, user demographic, etc. The campaign will also specify a budget that will constrain the total spend over many instances of the bids.

There are many advantages of having campaigns instead of companies purchasing the advertisements directly, but the down side is that campaign management is a complex task. Auction details may vary from one to another, especially when there are different ad formats and a single campaign needs to manage them all. In addition, due to budget constraints, even second-price auction is not truthful, so allocating budget across time is not a simple task. Complexity of campaign managers ultimately led to development of automated bid managers, which are now used to manage auctions.

Automated bidders are extremely popular up to the point that some online advertisement platforms don't even support manual bidding any more.

Model: Value-Maximizing Auto-bidders

The automated bidders act on behalf of the advertisers. They are fed with high-level preferences, constraints and a bidding algorithm that dynamically adjusts the campaign details:

Bidding is done in $T$ rounds, one impression auctioned off each round.

There are $n$ advertisers, each with an associated auto-bidder.

Input: advertiser $i$ specifies a budget $B_{i}$ and values (max bids) $v_{it}$ for every round $t$.

In each round, the values $(v_{1t},...,v_{nt})$ (that are i.i.d. over time) are drawn from a known distribution $F$ (no correlation across advertisers in each round).

An auto-bidder for advertiser $i$ observes $v_{it}$ and places bid $b_{it}\leq v_{it}$.

Output: the auction outcome, i.e. an allocation $x_{it}\in [0,1]$ and payment $p_{it}$ (that depends on the type of auction being held).

Goal: to maximize $\sum x_{it}v_{it}$, subject to $\sum p_{it}\leq B_{i}$.

Budget Pacing

There are numerous ways for the auto-bidders to divide their budget between the rounds.

Multiplicative Budget Pacing

The advertiser specifies budget $B_{i}$ and maximum bids $v_{it}$.

The auto-bidders maintain a shading factor $\mu _{t}\geq 1$.

In round $t$, an auto-bidder bids $v_{it}/\mu _{t}$ and selects $\mu _{t+1}$ adaptively, based on the observed history.

When the auction is second-price, there exists a pure Nash equilibrium $(\mu _{1},...,\mu _{n})$ of the multiplicative pacing game.

Note: Finding a Nash equilibrium is PPAD-hard.

Known Results

It was shown that at any equilibrium, the resulting allocation obtains at least half of the optimal liquid welfare (optimized willingness to pay), where liquid welfare is defined as a

maximal willingness to spend for the goods received: ${\underset {i}{\sum }}min{\bigg \{}B_{i},{\underset {t}{\sum }}x_{t}v_{t}{\bigg \}}$

In addition, if a single-round auction is truthful, then there is a choice of $\mu ^{*}$ such that bidding $v_{it}/\mu ^{*}$ in every auction instance is optimal in hindsight.

Adaptive Pacing

Using an adaptive algorithm presented below will achieve good results for a broad class of auctions (including First-price, Second-price, GSP auctions).

Adaptive Multiplicative Pacing Algorithm

1. Initialize $\mu _{1}=1$

2. In each round $t$:

2.1. Bid $b_{t}=v_{t}/\mu _{t}$.

2.2. Observe payment $p_{t}$.

2.3. $\mu _{t+1}\leftarrow \mu _{t}+\epsilon \times (\rho -p_{t})$ (If $\mu _{t+1}<1$ then set $\mu _{t+1}=1$) where $\rho =B/T$ and learning rate $\epsilon ={\frac {1}{\sqrt {T}}}$ If we spend more then $\rho$, reduce bid next round If we spend less then $\rho$, increase bid next round.

Note: A bid $b_{t}$ can be at most the remaining budget, so if we exhaust the budget early, all the following bids will be 0.

Class of Auctions

The algorithm yields good results for auctions satisfying the following conditions:

Input: bids $b_{1},...,b_{n}$

Output: allocation $x_{1},...,x_{n}$ and payments $p_{1},...,p_{n}$

Condition 1: Core Auction

1. Payments are at most bids: $p_{i}\leq x_{i}b_{i}$.
2. For any subset of bidders $A$, and any feasible allocation $y$, ${\underset {i\in A}{\sum }}x_{i}b_{i}+{\underset {i\in A}{\sum }}p_{i}\geq {\underset {i\in A}{\sum }}y_{i}b_{i}$. Intuition: If we take $A=\{1,...,n\}$, then the auction maximizes declared welfare, and if $A=[n]-\{i\}$, then the payments are at least the VCG payments.

Condition 2: Monotone Bang-Per-Buck

1. $x_{i}/p_{i}$ is weakly decreasing as $b_{i}$ increases.

As mentioned above, first-price, second-price and GSP auctions are all in this class.

Results

Using this algorithm on the defined class of auctions, the following outcomes can be observed:

1. Simultaneous Pacing: When auto-bidders run simultaneously, the expected liquid welfare is at least half of the expected optimum.
2. Stochastic Regret: The algorithm achieves vanishing regret for a single advertiser in a stochastic environment.

Simultaneous Pacing

Suppose that all agents use adaptive pacing simultaneously.

Recall that $x_{it}$ denote allocation of auto-bidder $i$ in round $t$ (a random variable). For any auction in the class, the expected liquid welfare of $x$ is at least half of the expected optimal liquid welfare in hindsight:

$E{\bigg [}\sum _{i}min{\bigg \{}B_{i},\sum _{t}x_{it}v_{it}{\bigg \}}{\bigg ]}\geq {\frac {1}{2}}E{\bigg [}{max}_{y}\sum _{i}min{\bigg \{}B_{i},\sum _{t}y_{it}v_{it}{\bigg \}}{\bigg ]}$

(left side of the equation is the expected liquid welfare of $x_{it}$ and right side is the expected optimal welfare)

Proof approach

Let's define Epoch to be a maximal interval $[t_{1},t_{2}]$ on which $\mu _{it}>1$ (where $t$ is taken from the interval).

Lemma 1. If $[t_{1},t_{2}]$ is an epoch, then $\sum _{t=t_{1}}^{t_{2}}p_{it}=\rho (t_{2}-t_{1})+O(\epsilon )$ (Average spend over an epoch $\approx \rho$ per round). Lemma 1 proof outline. If $\mu _{t+1}-\mu _{t}=\epsilon \times (\rho -p_{t})$, then using a telescopic sum we can conclude that $0=\mu _{t_{2}}-\mu _{t_{1}}\approx \epsilon \times (\rho |t_{2}-t_{1}|-[total\,\,spend])$.

If the expected number of rounds with $[\mu _{it}>1]$ is $\geq T/2$, then the expected spend is at least $B_{i}/2$, so this is a good approximation to the optimal liquid welfare.

Recalling the core auction property: for $A=\{i|\mu _{it}=1\}$, $\sum _{i\in A}x_{i}b_{i}+\sum _{i\not \in A}p_{i}\geq \sum _{i\in A}y_{i}b_{i}$.(Leftmost sum is the value obtained by agents with $\mu _{it}=1$, middle sum is the collected payment, and right sum is the maximal obtainable value for agents with $\mu _{it}=1$)

Note: When $\mu _{it}=1$ for some $t$, $v_{it}$ is high, but $x_{it}$ is low (e.g. a different auto-bidder wins instead), any lost value can be charged to payments received.

Stochastic Regret

For any auction in the previously mentioned class, the total expected value obtained by the adaptive pacing algorithm in a stochastic environment is $T*OPT-o(T)$.

(The expected per-round value of bidding $v_{t}/\mu ^{*}$, where $\mu ^{*}\geq 1$, sets expected per-round payment to $\rho$).

In a stochastic environment, on each round, the advertiser's value and the profile of competing bids are drawn i.i.d. (value and competing bids can be arbitrarily correlated).

Proof approach

Interpret update rule $\mu _{t+1}\leftarrow \mu _{t}+\epsilon (\rho -p_{t})$ as following a gradient, and consider adaptive pacing as Stochastic Gradient Descent.

If we take a $\delta$-neighborhood of $\rho$, and $S$ is a set that is a neighborhood of $\mu ^{*}$, the following claims will hold.

Claim 1. $\mu _{t}$ is nearly always in the set $S$.

Proof of Claim 1. Recall that $\mu _{t+1}\leftarrow \mu _{t}+\epsilon (\rho -p_{t})$, then $E[\mu _{t+1}-\mu _{t}\mid \mu _{t}]=\epsilon (\rho -E[spend(\mu _{t})])$.

This implies that if $\mu _{t}\not \in S$, then $\mu _{t+1}$ is $\epsilon \delta$-biased towards $\mu ^{*}$.

Furthermore,

Claim 2. For $\mu \in S$, bidding $v_{t}/\mu$ each round is $(1-O(\delta ))$-approximation.

Proof of Claim 2.

Case 1: $\mu _{t}<\mu ^{*}$ (overspend): only participate in $T(1-O(\delta ))$ rounds instead of $T$, but value is obtained per round is weakly higher.

Case 2: $\mu _{t}>\mu ^{*}$ (underspend): might win fewer impressions in expectation, but bang-per-buck (value per dollar spent) is weakly higher. This means that

[fraction of value lost] $\leq$ [fraction of budget unspent] $\leq O(\delta )$.

External Links

A Lecture on "Automated Bidding: Efficiency and Regret in a Repeated Bidding Game" by Brendan Lucier

References

This article "Automated Bidding in a Repeated Bidding Game" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Automated Bidding in a Repeated Bidding Game. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• List of Finance Companies in Jaipur
• Laured Kalari
• Automated bid managers
• Marijuana Stocks
• Ajaib
• International Productivity Monitor
• Microsoft Excel World Championship

---