  Many popular search engines run an auction to determine the placement of
advertisements next to search results. Current auctions at Google and Yahoo!
let advertisers specify a single amount as their bid in the auction. This bid
is interpreted as the maximum amount the advertiser is willing to pay per click
on its ad. When search queries arrive, the bids are used to rank the ads
linearly on the search result page. The advertisers pay for each user who
clicks on their ad, and the amount charged depends on the bids of all the
advertisers participating in the auction. In order to be effective, advertisers
seek to be as high on the list as their budget permits, subject to the market.
  We study the problem of ranking ads and associated pricing mechanisms when
the advertisers not only specify a bid, but additionally express their
preference for positions in the list of ads. In particular, we study "prefix
position auctions" where advertiser $i$ can specify that she is interested only
in the top $b_i$ positions.
  We present a simple allocation and pricing mechanism that generalizes the
desirable properties of current auctions that do not have position constraints.
In addition, we show that our auction has an "envy-free" or "symmetric" Nash
equilibrium with the same outcome in allocation and pricing as the well-known
truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this
equilibrium is the best such equilibrium for the advertisers in terms of the
profit made by each advertiser. We also discuss other position-based auctions.
