.jpg)
The generalized first-price auction (GFP) is a non-truthful auction mechanism for sponsored search (a.k.a. position auctions).[1] In sponsored search n bidders compete for the assignment of k slots. Each slot has an associate click-through rate, the click-through rates are decreasing from top to bottom. The GFP mechanism asks each bidder for a bid. Then the highest bidder gets the first slot, the second-highest, the second slot and so on. On each click the highest bidder pays his bid on the first slot, the second highest bidder pays his bid on the second slot, and so on.
The GFP mechanism was the first mechanism to find application in sponsored search, replacing the "flat fee" and "per-impression" model that was the standard. Overture adopted the GFP mechanism in 1997, and provided service to Yahoo! and MSN. Although very successful initially, bidders quickly learned how to manipulate the mechanism. Bidding patterns exhibited a characteristic saw-tooth pattern,[2] and the mechanism need not possess a (pure) Nash equilibrium.[1] These deficiencies lead to the replacement of the GFP mechanism in practice, and the adoption of alternate auction designs.
Recent work by Hoy et al.[3] and Dütting et al.[4] shows that the deficiencies of the GFP mechanism can be ascribed to its bidding interface, and that adopting a more expressive bidding interface guarantees the existence of an efficient Nash equilibrium under complete information as well as an efficient Bayes-Nash equilibrium under incomplete information.