Mechanism Design for Mixed Ads

We propose a hybrid auction mechanism for sponsored search, where bidders can be truthful or not, and are accordingly treated differently. Our class of hybrid mechanisms give incentives for non-truthful bidders to bid truthfully, while behaving as a non-truthful auction if no bidders are truthful. Our motivation is that the Generalized Second Price (GSP) auction (the current mechanism of choice) has appealing properties when ads are simple (text based and identical in size). But GSP does not generalize to richer ad settings, whereas truthful mechanisms, such as VCG do. Hence there are incentives for search platforms to migrate to truthful mechanisms, but a straight switch from GSP to VCG either requires all bidders instantly bid truthfully or incurs significant revenue loss. We introduce a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss. The mechanism is equivalent to GSP when nobody has updated their bid, is equivalent to VCG when everybody has updated, and it has the same allocation and payments of the original GSP if bids were in the minimum symmetric Nash equilibrium. In settings where both GSP ads and truthful (TF) ads exist, it is easier to propose a payment function than an allocation function. We give a general framework for these settings to characterize payment functions which guarantee incentive compatibility of truthful ads, by requiring that the payment functions satisfy two properties. Finally, we compare the revenue of our transitional mechanism with revenues of GSP and VCG mechanisms when run on a sample of Bing data.