Although bidding for online advertisements seems like a mundane task, it actually reveals very complex strategic decisions made by the various bidders. Here we explore the game theory aspects of online ad bidding.

The Generalized Second-Price Auction

Google auctions off all of their advertising slots (including hotel ads) in a mechanism known as the generalized second-price auction (GSP). In a basic sense, if there are two advertising slots for a keyword, then the top two bidders will have the right to display their ads. The price they pay, however, is not the price that they bid. Instead, each advertiser pays only what the person below them bid. The highest bidder will pay a price slightly above the bid of the second highest bidder, the second highest bidder will pay a bid price slightly above the bid of the third highest bidder, and so on. To illustrate, imagine Ann, Bob, and Charlie bidding for two advertising slots:

Understanding these types of auctions is critical for advertisers, since the nuances have implications for choosing the right bidding strategy. In particular, the founding theorists behind GSP state:

GSP generally does not have an equilibrium in dominant strategies, and truth-telling is not an equilibrium of GSP.

Let’s break it down.

Implication 1: Honesty is not the best policy.

If each click is worth $3 to an advertiser, it might not be in his best interests to bid $3. In fact, depending on the circumstances, it could be advantageous to bid higher or lower. In the above table, Bob can sneakily change his bid to $2.99:

Bob has dramatically increased his competitor Ann’s costs while paying the same price per click for his own ad. Such a strategy is known as an anti-social strategy. Telling the truth, i.e., bidding the true value of a click, is not advantageous.

Implication 2: Finding equilibrium is tricky.

A dominant strategy is optimal regardless of what other advertisers do. The optimal bid for an advertiser depends on other advertisers’ bids, and so dominant strategies do not lead to equilibrium. That doesn’t mean that equilibrium doesn’t exist, however. In fact, in any generalized second-price auction, there is guaranteed to be a local envy-free equilibrium.

The equilibrium occurs when each advertiser is content with being in their current position, i.e., it would not be advantageous for the advertiser to swap spots with any other advertiser. Hence, the situation is ‘envy-free’. Take the situation in the above table. Ann could retaliate by changing her bid to $2.98:

As it turns out, it might be preferable for Ann to occupy position 2 and reduce her price paid per click. If Bob is not happy with this arrangement, he could lower his bid to $2.97 and force Ann to respond. The bids will eventually converge to an equilibrium where none of the parties would gain anything by changing their bids.

There are many different equilibria that the situation could converge to, and it is hard to predict which will occur beforehand.

Implication 3: Finding optimal bidding strategies is really tricky.

Because of the lack of information about other bidders and the general bid instability of such auctions, finding optimal bidding strategies is currently an active area of research. Previous researchers have used techniques such as stochastic models and linear programming to try and find bidding strategies. One interesting approach is to model the problem of how much to bid for each keyword as a knapsack problem.

The knapsack problem states: if you have a set of items you want to fit in your knapsack but a limited amount of space, which items should you put in to maximize the value of the items in your knapsack? The answer will depend on the volume of each item as well as the value of each item.

Analogously, choosing how to allocate your budget for each keyword depends on the ROI of each keyword as well as the cost of the bid. When there are multiple constraints, the math becomes quite involved. An in-depth exposition of these techniques, however, will have to be the subject of another blog post.

Addendum: Note that Google uses a modified version of GSP, which includes other factors such as quality score into determining the price that the advertiser has to pay. Nevertheless, these implications will still hold true.