Mechanism Design for Mixed Bidders

The Generalized Second Price (GSP) auction has appealing properties
when ads are simple (text based and identical in size), but
does not generalize to richer ad settings, whereas truthful mechanisms
such as VCG do. However, a straight switch from GSP to
VCG incurs significant revenue loss for the search engine. We introduce
a transitional mechanism which encourages advertisers to
update their bids to their valuations, while mitigating revenue loss.
In this setting, it is easier to propose first a payment function rather
than an allocation function, so we give a general framework which
guarantees incentive compatibility by requiring that the payment
functions satisfy two specific properties. Finally, we analyze the
revenue impacts of our mechanism on a sample of Bing data.