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.

## 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.

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 $s_i (v_j-p_j)$. 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 $\sum\limits_{i=1}^n s_i v_{\phi(i)}$, where $\phi(i)$ 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.

## Sold

There’s tons of examples of auctions in every day life! If you enjoyed reading about auctions, you might also like learning about matchings (one intro topic is the stable marriage problem).