## History

Prior to 1998, many advertisements were charged by impression, as it was the easiest metric to calculate. In 1998, GoTo.com, Inc debuted a pay-per-click charging system, with pricing and slot placement determined by an auction. GoTo used a first price auction, where bidders were placed according to their bids and charged their bids when they won. GoTo faced bidders who were constantly changing their bid in response to new information and changing information from other bidders.

Currently, charging per action is a common pricing scheme in affiliate networks, such as the Amazon Associates Program.

In 2002, Google AdWords began using a second price auction to sell the single advertisement slot. Shortly thereafter, pages had multiple advertisements slots, which were allocated and sold via generalized second-price auction (GSP) auction, the natural generalization of a second price, single item, multi bidder auction.[1]

## Auction Mechanisms

### Generalized Second Price Auction

Generalized second-price auction (GSP) is the most commonly used auction mechanism for sponsored search.

#### Untruthfulness

An issue with GSP is that it's not a truthful auction and it is not the optimal strategy. To illustrate this, consider the following example.

There are three bidders with only two possible slots. The values of each bidders 1, 2, and 3 are $10,$5, and $3 respectively. Suppose that the first slot click through rate (CTR) is 300 and the second slot CTR is 290. If bidder 1 is truthful, he would have to pay ${\displaystyle p_{1}=\5(300)=\1500}$ for a utility of ${\displaystyle u_{1}=\10(300)-\1500=\1500}$. However, if bidder 1 decides to lie and reports a value of$4 instead then his utility would be ${\displaystyle u_{2}=\10(290)-\3(290)=\2030}$. Notice that ${\displaystyle u_{2}>u_{1}}$ which makes GSP untruthful and bidders have an incentive to lie.

#### Quality Variant

Google assigns a numeric “quality” score ${\displaystyle \gamma _{i}}$ to each bidder ${\displaystyle i}$. Bidders, rather than being ordered purely by their bid, are instead ordered by rank, which is the product of their bid and quality score ${\displaystyle \gamma _{1}b_{1}\geq \gamma _{2}b_{2}\geq \dots \geq \gamma _{n}b_{n}}$ . Slots are still assigned in decreasing rank order. Bidders are charged, rather than the bid of the bidder one rank lower (${\displaystyle p_{i}(b_{i},b_{-i})=b_{i+1}}$), are charged the minimum price for which, if it was their bid, would keep them in their current rank: ${\displaystyle p_{i}(b_{i},b_{-i})={\frac {\gamma _{i+1}b_{i+1}}{\gamma _{i}}}}$