طراحی مکانیزم مبتنی بر تکامل مشترک برای تبلیغات جستجویی حمایت شده

Sponsored search advertising (SSA), the primary revenue source of Web search engine companies, has become the dominant form of online advertising. Search engine companies, such as Google and Baidu, are naturally interested in SSA mechanism design with the aim to improve the overall effectiveness and profitability of SSA ecosystems. Due to model intractability, however, traditional game theory and mechanism design frameworks provide only limited help as to the design and evaluation of practical SSA mechanisms. In this paper, we propose a niche-based co-evolutionary simulation approach, aiming at computationally evaluating SSA auction mechanisms based on advertisers’ equilibrium bidding behavior generated through co-evolution of their bidding strategies. Using this approach, we evaluate and compare key performance measures of several practical SSA auction mechanisms, including the generalized first and second price auction, the Vickrey–Clarke–Groves mechanism, and a novel hybrid mechanism adopted by sogou.com, a major search engine in China.

In sponsored search advertising (SSA), online advertisers bid for keyword-specific advertisements to appear alongside the organic search results on Web search result pages. With the promise of precise and in-context customer targeting, SSA provides an effective way of monetizing Web search queries. Within a decade, it has evolved into the dominant form of online advertising and becomes an industry on its own. In 2010, SSA constituted the largest category share (46%) of the $26 billion online advertisement spending in the U.S. markets, far exceeding the share of display advertisement, the second largest category, 24%.1 SSA is also the primary revenue source of Web search engine companies. In recent years, it accounted for more than 96% and 99.9% of Google and Baidu’s international revenues, respectively.2 The basic economic institution behind most SSA platforms, such as Google’s AdWords and Baidu’s Phoenix Nest, is keyword-based position auction. In this type of auction, advertisers selling similar products or services bid for the same keywords on an SSA platform. Once a relevant search query arrives, an auction will be conducted to determine the rank position and the associated payment of winning advertisements. When a user clicks on an advertisement, she will be sent to the landing page on the website of the corresponding advertiser, who in turn pays the search engine.

This paper focuses on SSA mechanism design and evaluation. To address the limitations of the analytical mechanism design framework, we propose a niche-based co-evolutionary simulation approach for SSA mechanism design, aiming at computationally analyzing advertisers’ equilibrium bidding behavior, and deriving the key performance measures of various kinds of SSA auction mechanisms. Our approach has the following managerial implications. For online advertisers, our work can help generate the optimal equilibrium bids. For Web search engine companies, it can help better understand advertisers’ bidding behavior and dynamics through analyzing the equilibrium continuum of SSA auctions. It can also be used to evaluate key performance of alternative SSA auction mechanisms. Our research has two major limitations. First, the proposed approach can only be used to evolve advertisers’ equilibrium bidding behavior in SSA scenarios where advertisers have complete information, or reliable estimations about all advertisers’ per-click values and CTRs for all slots. Second, co-evolutionary simulations for SSA auctions with a large number of advertisers will impose major computational overhead. In the future work, we plan to extend our approach to handle incomplete information settings through maintaining a hybrid strategy population for each advertiser according to her Bayesian beliefs of the competitors’ private per-click values. To deal with the computational overhead, we are working on parallelizing the key simulation algorithm. We also plan to conduct formal analysis of the co-evolutionary simulation framework through replicator dynamics theory.