- Posted by Intent Media 16 Jun
- 0 Comments
When deciding on ranking rules for display ads, be it the ads alongside search engine results or sponsored search ads on e-commerce sites, one needs to choose the auction strategies that are best for the publishers and advertisers involved. Anyone who browses the web is familiar with ad units that have multiple slots ranked by varying “desirability” or click-through-rates. Advertisers place their bids to have their ads displayed in these slots and pay only if the ad is clicked. The auction designer’s job is to determine the ranking, and how much each displayed advertiser pays, that will yield the highest expected revenue. In this post, I will discuss how to approach this problem and some related concepts that we found interesting. Note that the display ad setting requires discussion of multi-item auctions. While revenue optimization of single-item auctions has been a well-researched area, our auction setting is interesting in its own merit, not only because of the the exciting, ongoing research, but also due to the massive revenue impact: one small optimization can make a million dollar impact to your annual revenue, or a $500 million impact if you are Google! We, at Intent Media, addressed the auction design problem as we were launching a new ad product for OTAs and hotel suppliers. When a user searches for hotels, we power a series of prices from competitor websites that show up alongside each hotel property in the search results. The prices themselves are advertisements that compete to be shown in a real-time auction.
I will try my best to keep this post easy-to-read to the best of my abilities by giving some background, whenever I feel it is necessary. But some familiarity of Mechanism Design, especially Generalized Second Price (GSP) auctions can help navigate the ideas further and beyond this post. If that sounds daunting, Google Chief Economist Hal Varian has made a video that can get any new student of online advertising ecosystem up and going in 9 minutes and 12 seconds.
A series of challenging problems
Beyond all the $$$ that is involved, why is this an interesting problem for Data Scientists, Statisticians, Applied Mathematicians and the like? Let us dive into an example to demonstrate the types of decisions we need to make about the auction design. Typically, to decide which is the best ranking for each instance of the auction, we need to consider the advertiser bids, as well as the probability of each of the competing ads being clicked on if displayed on any of the slots. Let denote the bid of advertiser and be the corresponding ad’s click-through rate (normalized over all available slots). Then we rank the ads by non-increasing order of , where . The right choice of can be a difficult decision to make. Take two keyword auctions that have been publicized broadly. Google started with , otherwise known as the “rank by revenue”, while Yahoo! started with , i.e. “rank by bid only”, according to literature and media posts. The models have become more complex over time [citations for Google, Yahoo! and Bing]. The value of q that is optimal for your auction may lie somewhere in between and landing on it could require a combination of game theory chops, business intuition, data exploration and live testing.
Why auction simulation is the answer
While it is possible to close in on the optimal value of the exponent by testing different values online using controlled randomized testing (e.g., A/B testing or multivariate testing), it is often not the best course of action given business rules and other constraints. A change in auction dynamics means advertisers will have to adjust their bidding strategies. Hence frequently changing the value of can be detrimental to advertiser relations. At the same time, it can be critical to start with a near-optimal value. Also, such auctions have many so moving pieces that it is hard, and often dangerous, to intuitively surmise what could happen if even a single parameter is changed. Some form of testing is must and testing on live traffic has its costs. Luckily for us, as Varian notes, due to the special structure of these ad auction an equilibrium (in terms of advertiser bidding behavior) can be calculated explicitly and we can get a read on the revenue under different sets of parameters at that equilibrium. In other words, we “simulate” the auction and compute expected revenue, instead of having to run expensive A/B tests live. In the remainder of the post we will give some overviews of the decisions we need to make and what aspects of the auction we need to simulate.
What are the big decisions?
One of the the first things in our mind would be to choose between first price and second price auctions. If you are not familiar with how first vs second price auctions work, resources can be found online or in any game theory textbook. A good auction design should ensure that –
- the bidder who values the commodity most will win, and
- the commodity is sold only when that “highest value” is higher than the seller’s valuation.
Note that, in case of ad auction seller’s actual valuation of a slot may be difficult to determine, but the seller obviously wants to maximize revenue regardless. Let us assume, for now, that the first condition is satisfied. Even then neither a first- or second-price auction is guaranteed the second condition. In case of a first-price auction, even if the highest of the true valuations of the buyers is higher than the seller’s valuation, the corresponding bid may be lower due to “bid shading.” For more information on that, you can start by reading about “winner’s curse.” In case of a second-price auction, the highest bid is usually same as the highest of the buyer valuations, but the actual price paid is discounted to match the second-highest bid, which can be arbitrarily smaller than the highest bid. We can implement reserve prices that can be used somewhat dubiously to force the second condition (discussed later) – but it has its own problems. Since neither auction is a clear winner at all times, we resorted to simulation results, which favored a second-price auction for our particular case.
The exponent on the predicted click through rate (otherwise known as quality score) is an important parameter that affects revenue. We already discussed some of the implications above. It has been shown that the correlation of bids to the valuations determines whether a value closer to 0 or 1 is optimal for a given auction. There could however be other “unknowns” weighing in on the optimality of a given exponent. Our simulations yielded best results for a quality score exponent between 0 and 1.
The minimum bid is the minimum allowed bid an advertiser needs to place to get in the auction. This is another parameter that has substantial impact on the overall revenue. We have seen that raising the minimum bid can raise the revenue. However, raising the minimum bid reduces advertiser utility and hence can be counterproductive to the health of the auction. This tool, however tempting it may be, should be used carefully as it can hurt advertiser utility and possibly affect total revenue negatively. Sometimes it is a sensible solution to set the different minimum bids for commodities with different demand level or even per-bidder minimum bids, instead of a single, global minimum bid. This is important for us, as we do serve ads for hotel properties with varying degrees of advertiser competition – consider a famous Las Vegas hotel, where all advertisers have lucrative margins, as opposed to a two star hotel in a small market. We have set a global minimum bid for now, based on the results of auction simulations and a set of business rules, while we research other, more granular minimum bid strategies.
A reserve price is a price set by the seller or auction designer below which the commodity will not be sold. One can think of reserve price to be a “fake” or “phantom” bid to drive the bids up. In case of a second price auction, a high reserve price reduces the discount that the highest bidder ought to have gotten and hence reduce advertiser utility. Reserve prices can have remarkable effect on auction dynamics and are a highly discussed and debated topic in auction discussions. One of the most impressive properties of them is probably the fact that of all dominant-strategy incentive-compatible (DSIC) mechanisms, a GSP with reserve prices yield maximum revenue. The reserve price that maximizes revenue under our equilibrium assumptions has been derived here. Our current state of auction simulation suggests that overall revenue is optimized if the reserve price is not increased any higher than the minimum bid.
There is another class of auction attributes that are generally not thought of as “parameters” of the auction, but they are also an important part of auction design and considered “big decisions” to be made. For example, how many commodities (in this context, ad positions or slots) do we want to sell at a time? How much motivation can we create for a bidder to move up from one position to a higher position? How much of the mechanism can be disclosed to advertiser in terms of reporting and to help them with their strategies, while protecting the information on other advertisers?
One advantage of the simulation approach is the ability to set up any “virtual” click gradient (and test its effect on revenue) without actually designing a new display unit, which is often time and resource consuming. A steeper click gradient encourages advertisers to bid higher by increasing the incremental potential click through rate to the slot above. But the effectiveness of this tool is limited by the highest valuation of the top spot. Hence, like the theme has been in this post, this is another “how far to go” question one must answer.
Number of slots
One does not always have the liberty to increase or decrease the number of slots at will. Again, simulation allows us to make a case to add or reduce an ad slot without adding it in production. Adding a slot can be beneficial by bringing in extra revenue for that slot, or can reduce overall revenue by reducing advertiser motivation to increase bids. This becomes particularly interesting when the overall click gradient (or the advertiser’s click gradient) is flat, which means advertiser may be motivated to bid just enough to be displayed at the bottom slot. Yet another uncertainty and, as kids these days say, auction simulation FTW!
In this post I described how we approached the problem of designing an optimal auction for an online advertising product and why we resorted to auction simulation. If you had fun reading it, keep an eye on this space for Part II of this post, where I will describe our simulation (i.e. what we actually simulated) and some of the challenges we needed to overcome. This involved data sampling, analysis and solving some interesting applied statistics problems. If you are into this stuff, hope you don’t miss it!
Saurav Pandit is a Data Scientist at Intent Media. He likes to use game theory and machine learning to solve life’s everyday problems – from house hunting to potty training. Between doing data science and spending time with family and friends, he doesn’t get to share as many thoughts or tweets as he’d like to.