document: General auction mechanism for search advertising In sponsored search , a number of advertising slots is available on a search results page , and have to be allocated among a set of advertisers competing to display an ad on the page . This gives rise to a bipartite matching market that is typically cleared by the way of an automated auction . Several auction mechanisms have been proposed , with variants of the Generalized Second Price ( GSP ) being widely used in practice . There is a rich body of work on bipartite matching markets that builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik . This line of research offers deep insights into the structure of stable outcomes in such markets and their incentive properties . In this paper , we model advertising auctions in terms of an assignment model with linear utilities , extended with bidder and item specific maximum and minimum prices . Auction mechanisms like the commonly used GSP or the well-known Vickrey-Clarke-Groves ( VCG ) can be interpreted as simply computing a bidder-optimal stable matching in this model , for a suitably defined set of bidder preferences , but our model includes much richer bidders and preferences . We prove that in our model the existence of a stable matching is guaranteed , and under a non-degeneracy assumption a bidder-optimal stable matching exists as well . We give an algorithm to find such matching in polynomial time , and use it to design truthful mechanism that generalizes GSP , is truthful for profit-maximizing bidders , correctly implements features like bidder-specific minimum prices and position-specific bids , and works for rich mixtures of bidders and preferences . Our main technical contributions are the existence of bidder-optimal matchings and strategyproofness of the resulting mechanism , and are proved by induction on the progress of the matching algorithm .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O