An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the Web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction - generalized second price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity.