How much do a moose’s antlers weigh? Not a moose, but a moose’s antlers. Finding the answer takes less than 10 seconds thanks to our favorite search engine, Google. Even more impressive than how heavy moose antlers are (about 40 pounds or 18 kg: thanks, Google) is that we can find the answer to this, or almost any other question, for free.
In 2015, Google’s parent company, Alphabet, posted over 75 billion dollars in revenue and is projected to bring in over 80 billion dollars in revenue in 2016. Google brings in approximately 99% of Alphabet’s total revenue; so Google makes a ton of money. Yet a large portion of Google’s products are free to users. How does a company so integrated into our society, producing so much revenue, not charge its users? Easy, ads.
Over 75% of Google’s total revenue in 2015 (that’s around 55 million for those keeping score) came from advertisements on Google’s own pages through their advertising service AdWords. When a search is entered into Google, advertisement links may pop up based on which keywords were entered. Advertisers pay Google to have their links show up front and center on your screen. There are a few different services which AdWords offers: cost per click advertising (the advertiser only pays Google if the link is clicked), cost per impression advertising (the advertiser pays to have their ad shown), etc. These ads can get extremely pricey based on the demand surrounding the keyword. In the cost per click advertising system, clicks can be as much as $50 for competitive phrases such as “insurance” or “bank”.
So, how does Google determine whether Nexxus or L’Oréal Paris is the top link when you search for “hair shampoo”? Google holds an auction. The results of these auctions are ever changing: one minute Nexxus will be the top result, but refresh the page in 10 minutes and it’ll be L’Oréal Paris.
Most people are familiar with the classic example of an auction: there’s an old man speaking very quickly, yelling the increasing price to a room full of people, and the participants wave a numbered marker to indicate they bid at the current price. This is an English auction (open ascending bid auction). There are n bidders, 1 item for sale, and each bidder has some value on the item. The bidders place increasingly higher bids on the item, and the price of the item is the highest bid currently on the table. A bidder stops placing bids when the price has exceeded their value. The auction ends when no one will bid any higher on the item, or equivalently, when the price has exceeded every bidder’s value except for the last bidder standing, the winner of the auction.
In a more general setting, auctions are arrangements which allocate items among bidders based on a set of rules. The rules determine who gets what and how much people have to pay. There are many types of auctions, and the design for different auctions accommodate various settings (multiple items for sale, bidders know each other’s values, etc.) and achieve certain results (maximize revenue, encourage truthful bidding, etc.).
Generalized second price (GSP) auctions
Every time you search on Google, an auction runs, and the results of the auction decide which ads appear on your search results screen and in what order the ads appear. Google takes the search, and categorizes it based on the keywords entered. Separately, advertisers match keywords to ads. Google matches your search’s keywords to the set of advertisers with associated keywords; then the auction begins among that set of advertisers.
Google uses (or at least claims to use) a generalized sealed-bid second-price auction. Advertisers, privately submit bids to Google, then they’re assigned an Ad Rank. A bidder’s Ad Rank determines whether their ad will show up on the page, and where their ad will show up. An advertiser’s ad rank is primarily based on their bid and their ad’s Quality Score, a value assigned based on how relevant the ad is to the search’s keywords, how likely the ad is to get clicked (expected clickthrough rate), and how well the ad matches what the searcher wanted (landing page experience). Basically, it’s not just how much an advertiser bids, but also how good the ad is.
So if there are m slots available to advertisers after some search, the advertiser with the highest Ad Rank wins slot 1 at the price of the second highest bid plus $0.01, the advertiser with the second highest Ad Rank wins slot 2 at the price of the third highest bid plus $0.01, and so on for all m slots. In some generalized sealed-bid second-price auctions, this extra $0.01 is ignored, so the advertiser with the highest Ad Rank wins slot 1 at the price of the second highest bid, and so on down the line.
Desirable properties in auctions
Auctions are studied with the goal of designing “good” ways to allocate resources in various settings. So, what’s a good allocation, what’s a bad allocation? That depends on the objective of the person designing the auction. A few properties desirable in auctions are revenue maximization, truthful bidders, and social welfare maximization.
For the sake of using some more formal notation in an easy to understand manner, let’s watch an auction between our buds Alice, Bob, and Carol (Normally Alice and Bob like to send private private messages to each other, but today they’re making friends with Carol). Suppose Alice, Bob, and Carol are all bidding for two ad spots, with probabilities of being clicked .8 and .5. They value the ad at $10, $6, and $2 respectively, and spots are sold with the cost per click advertising system. Assume the bidder who wins the first slot pays the second highest bid, and the bidder who wins the second slot pays the third highest bid. In this round, all participants bid their true value.
An auction maximizes revenue if, you guessed it, the auction maximizes how much revenue the seller expects to receive. So there’s no other allocation which makes the seller more revenue. Google makes $ on slot i if the link in that slot is clicked and $0 otherwise. Summing over all the slots, the expected revenue from Google’s auction is , where is the bidder who won to slot i$.
In an auction, every bidder is trying to maximize their utility, which can just be thought of as a value that measures how “well off” someone is. In Google’s auction for an ad, the bidder has utility $0 if their link is not clicked on, since they don’t pay anything and don’t receive any benefit. If their link is clicked on, the bidder’s utility is how much they valued their link being clicked minus the cost of the click. So the expected utility of bidder j being given slot i is . If bidder j is not given a slot, their expected utility is 0. An auction where bidders maximize their utility by bidding according to their true values is incentive compatible, or is said to encourage truthfulness.
In some auctions, bidders can be better off (have a higher utility) by lying about how much they value items. Let’s consider the same example with Alice, Bob, and Carol, except we’ll change the amount Alice bids. If Alice bids her true value, $10, then her utility is .8($10-$6)=$3.2. But if she’s sneaky, and bids $5, then her utility is .5($10-$2)=$4, making her better off than when she bid her true value.
Social welfare maximization
Social welfare measures how desirable a situation is for society. Social welfare maximization is a popular objective for any allocation; for instance, most any government auction would want to maximize social welfare. Companies also choose auctions which maximize social welfare, otherwise a competitor would do it and steal customers.
In the GSP model, a bidder whose link is not clicked gains nothing, so their social welfare is 0, but a bidder whose link is clicked gains however much they valued that click. So the expected social welfare of a GSP auction is , where is the bidder who won to slot i. Moving away from the definition though, social welfare is an interesting concept here.
The definition doesn’t fully encapsulate “how desirable” the allocation is, since it doesn’t take into account the quality of the ad being advertised. The main motivation behind Ad Rank being dependent on more than just the advertiser’s bid is to ensure that Google-goers end up seeing well placed, relevant ads. It seems the definition of social welfare in this auction, at least in the case of Google’s ads, should somehow take quality into account.
How GSP stacks up
GSP auctions are not incentive compatible (the example above, where Alice was better off bidding below her true value, is a GSP auction). Potentially advertisers can develop some type of strategy to increase their expected utility from how much it would be from bidding their true value. Developing this kind of strategy seems doable since most advertisers are among the same set of competitors in each auction. Gleaning information about competitors’ preferences let’s an advertiser better predict their actions in auctions. In our example above, if Alice predicted that Bob would bid $6 because she’s been in auctions with him before, then she would know that she’s better off bidding $5 as opposed to $10.
If all participants in a GSP auction know each others values, then the auction leads to an allocation which maximizes social welfare. So no other allocation could make social welfare higher than the allocation found through the GSP auction. This does not remain the case when participants have either partial information or no information about each others’ values.
It turns out that designing auctions that maximize revenue is difficult without complete information about bidders’ values. GSP is no exception here and it does not maximize revenue.
Interestingly, there is another auction (the Vickrey-Clarke-Groves auction) which could be used to sell advertisement links in Google’s situation and could perform better with respect to these three properties. The allocation produced from the VCG auction is incentive compatible, socially optimal, and capable of achieving as high as double the revenue of a GSP auction when partial or no information among participants is known (the setting most common to Google advertisers). It’s very likely that Google only publicly claims to use a GSP auction, but that the actual process varies in order to attain higher revenue, or other desirable properties for the company or its users.