Search queries reveal what users are interested in. This self-evident fact creates extremely profitable markets, one for each search keyword, where search engines sell advertising space to companies targeting an audience with specific interests. More details on sponsored search markets can be found in [Easley-Kleinberg, Chapter 15].

Like a newspaper, a TV or radio programme, any web page can potentially contain ads for commercial products.

Responses to web search queries are of particular value in this context, as they have been created in response to a user’s explicitly expressed interest. The user can thus be provided with ads relating directly to their current interest.

Search engines use their privileges as owners and creators of search engine results pages (SERPs) and respond to a search query with two types of results: organic results (as found by the search algorithm) and sponsored results (advertisements). Those keyword-based ads are sold on the basis of certain conventions.

Pay Per Click. A sponsored result contains a link to a company’s web site. The company pays for each user following that link. Such a user is likely to become a customer, having issued the query, noticed the ad, and is now visiting the company’s web site. The company is willing to pay a fee for this business opportunity, in proportion to the expected value of this customer.

Price Setting Auctions. Search engines determine the price of a particular advertising space through an auction procedure in which they solicit bids from the advertisers. Usually, for each keyword, there are multiple slots for displaying ads, and some are more valuable than others.

A practical solution of the price setting problem in this context needs to combine the ideas of single item auctions and matching markets, ideally in such a way that truthful bidding is encouraged. After describing advertising on SERPs as a matching market, we discuss two procedures in some detail: the Vickrey-Clarke-Groves mechanism (VCG), and the generalized second price auction (GSP).

## Advertising as a Matching Market

Clickthrough Rates. For each keyword, the search engine can offer several advertising slots on the response page. Users are more likely to click on slots higher up on the page. For this model, we assume that each slot has a known clickthrough rate, the number of clicks per hour that an ad in that slot will receive. Furthermore, we assume that:

• advertisers know the clickthrough rates,

• the rate depends only on the slot (and not on the actual content of the ad),

• the rate does not depend on the ads in the other slots.

Revenue per Click. On the advertiser’s side, we assume that each advertiser has a revenue per click: the expected amount of revenue it receives per user clicking on the ad. This value does not depend on the content of the page containing the link.
Once a slot for a keyword is chosen, the ad will be shown on each SERP relating to that keyword.

Matching Market. Recall the basic ingredients of a matching market:

• The participants consist of a set of buyers and a set of sellers.

• Each buyer $j$ has a valuation $v_{ij}$ for the item offered by seller $i$.

• Buyers are matched up with sellers in such a way that no buyer purchases more than one item, and no seller sells their item to more than one buyer.

Here, buyer $j$ corresponds to advertiser $j$ with a revenue per click of $v_j$. Seller $i$ corresponds to slot $i$ with a clickthrough rate of $r_i$. Advertiser $j$’s valuation $v_{ij}$ for slot $i$, the benefit they receive from being given that slot, is simply the product of the clickthrough rate $r_i$ and the revenue per click $v_j$:

This formula yields a situation where all buyers agree on their preferences, and the valuations of one buyer are simply a multiple of the valuations of any other buyer.

Example. A matching market for slots with clickthrough rates of $10, 5, 2$, respectively, and advertisers with revenues per click of $3, 2, 1$, respectively.

These data can now be used to find a set of market clearing prices, as before, provided one knows the actual valuations of the advertisers.

If the valuations are not known, an auction can be used to solicit valuations from potential advertisers.

## The VCG Principle

In the case of a single-item auction, using the second-price format, where the single item is awarded to the highest bidder at a price equal to the second highest bid, it turned out that truthful bidding is a dominant strategy, i.e., that it is at least as good as any other strategy, regardless of the strategies used by other participants.

The VCG mechanism generalizes single-item second prize auctions to multiple items, based on the following principle.

The VCG Principle. Each individual is charged the harm they cause to the rest of the world.

In other words, the price of an item awarded to a participant in a multiple-item auction is equal to the total amount everybody would be better off if this participant were not there.

In a single-item second-price auction, if the highest bidder had not participated the item would have gone to the second highest bidder, who values the item at $v_2$, say. For the remaining bidders, the outcome would not have been different. But collectively, they experience a total harm of $v_2$, the value that bidder 2 loses because bidder 1 wins the auction.

## The VCG Principle in a Matching Market

Assume that the buyer’s valuations in a matching market are private (not known to the other buyers) and independent (not depending on how the other items are allocated to the other buyers).

As before, items are assigned to buyers in a way that maximizes the total valuation. Then, the price that buyer $j$ should pay for their assigned item $i$ is the harm caused by this transaction to the remaining buyers.

Example. Let’s continue with the above example of a matching market with slots and advertisers.

If $X$ would drop out, $Y$ would get slot $A$ instead of $B$ and so be better off by a value of $20-10 = 10$, and $Z$, getting slot $B$ instead of $C$ would be better off by $5-2 = 3$. The total harm caused by $X$ thus is $13$, which is the price they should be charged.

If $Y$ would drop out, that would make no difference for $X$, but $Z$, again, would be better off by $5-2 = 3$. The harm done by $Y$ this is $3$.

The absence of $Z$ would make no difference to either $X$ or $Y$, accounting for a total harm of $0$.

Formally, let $S$ denote the set of sellers, and $B$ the set of buyers. Denote by $V^S_B$ the maximum total valuation (over all possible perfect matchings between sellers and buyers).

Denote by $S - i$ the set resulting from removing seller $i$ from $S$, and similarly, by $B - j$ the set of all buyers except buyer $j$. If buyer $j$ receives item $i$ then $V^{S-i}_{B-j}$ is the best total valuation for the rest of the buyers. On the other hand, if buyer $j$ did not participate (and item $i$ was still available), the best total valuation for the rest of the buyers would be $V^S_{B-j}$. The harm caused by buyer $j$ acquiring item $i$ is the difference of those two values. Applying the VCG principle, the price $p_{ij}$, which buyer $j$ should pay for item $i$, is

## The VCG Price-Setting Mechanism

Assuming that there is a single price setting authority, who can collect information from buyers, assign items to them and charge prices, the VCG mechanism can now be described as a 3-step procedure:

2. Choose a socially optimal assignment of items to buyers (a perfect matching that maximizes the total valuation, based on the reported valuations).

3. Charge each buyer the VCG price determined as above.

This mechanism can be regarded as a game, where each buyer chooses a strategy (a set of valuations to report), and receives as their payoff the difference between the valuation and the price they pay. It turns out that in this game, as in a single-item second price auction, truthful bidding is a dominant strategy.

Note that VCG prices are personalized prices (they depend on both the item and the buyer), as opposed to the fixed market clearing prices.

## Truth-Telling as a Dominant Strategy

Claim. If items are assigned and prices are computed according to the VCG mechanism, then truthfully reporting valuations is a dominant strategy for each buyer, and the resulting assignment maximizes the total valuation of any perfect matching between buyers and sellers.

Clearly, if buyers truthfully report their valuations, then the assignment of items to buyers by the VCG mechanism is designed to maximize the total valuation.

Now suppose that buyer $j$ truthfully reports their valuations, and gets item $i$ assigned, for a payoff of $v_{ij} - p_{ij}$.

A deviation from truth-telling (that is: a lie) can only be beneficial for buyer $j$, if it affects which item they get assigned. Suppose that, by reporting false values, buyer $j$ gets item $h$ instead of item $i$ at a payoff of $v_{hj} - p_{hj}$. But

as the following argument shows. Expanding $p_{ij}$ and $p_{hj}$ yields an equivalent inequality

By construction, assigning item $i$ to buyer $j$ forms part of a socially optimal perfect matching, whence

which is the maximum total valuation over all possible perfect matchings. The quantity $v_{hj} + V^{S-h}_{B-j}$, however, is only the maximum total valuation over all perfect matchings that assign item $h$ to buyer $j$. Hence

as claimed.

## Generalized Second-Price Auctions.

In the case of keyword-based advertising, the VCG mechanism maximizes the total valuation obtained by advertisers. It is not clear whether at the same time the sellers’ revenue (which is what the search engines really care about) is maximized. For that reason, an alternative approach is used.

GSP is a generalization of a single-item second-price auction, which is easy to describe. In the GSP procedure, each advertiser $j$ announces a single bid $b_j$, the price they are willing to pay per click. The procedure the awards slot $i$ to the $i$th highest bidder, at a price per click equal to the $(i+1)$th highest bid.

GSP shares with single-item second-price auction the feature that the price to pay is lower than the bid. However, with this procedure, truthful bidding is not necessarily a dominant strategy, as the following simple example demonstrates.

Example. The ingredients for this matching market are:

• three advertisers, $X$, $Y$ and $Z$, with values per click of $7$, $6$ and $1$, respectively,

• two slots for advertisements, $A$ and $B$, with clickthrough rates of $10$ and $4$, respectively, plus a third (virtual) slot $C$ with a clickthrough rate of $0$, so as to have equal numbers of advertisers and slots.

This yields the following diagram of a matching market.

Under truthful bidding in GSP, $b_X = 7$ and $X$ gets the top slot at a price equal to the second highest bid, that’s a total price of $60$ against their valuation of $70$, for a payoff of $70 - 60 = 10$.

If $X$ would submit the lower bid of $b_X = 5$ per click (while $Y$ and $Z$ continue to bid truthfully), they would get slot $B$ at a total price of $4$, against their valuation of $28$, for a payoff of $28-4 = 24$, an improvement over truthful bidding.