Computer Science – Computer Science and Game Theory
Scientific paper
2008-07-08
Computer Science
Computer Science and Game Theory
Scientific paper
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. A rich body of work on bipartite matching markets builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik. We apply insights from this line of research into the structure of stable outcomes and their incentive properties to advertising auctions. 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) are interpreted as simply computing a \emph{bidder-optimal stable matching} in this model, for a suitably defined set of bidder preferences. 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, implements features like bidder-specific minimum prices and position-specific bids, and works for rich mixtures of bidders and preferences.
Aggarwal Gagan
Muthukrishnan Siddharth
Pal David
Pal Martin
No associations
LandOfFree
General Auction Mechanism for Search Advertising does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with General Auction Mechanism for Search Advertising, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General Auction Mechanism for Search Advertising will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-269133