改善關鍵字拍賣中廣義二級價格的穩健度

Improving the Robustness of the Generalized Second Price in Sponsored Search Auctions

欉振坤(Chen-Kun Tsung)

指導教授 ： 李新林

國立中正大學/工學院/資訊工程學系/博士(2014年)

摘要

搭配廣義二級價格的贊助商搜尋拍賣(Sponsored Search Auction, SSA)結合了搜尋引擎與廣告的服務，是目前最熱門的線上廣告服務。搜尋引擎提供者(Search Engine Provider, SEP)藉由考慮拍賣參與者的各個面向以提升拍賣機制的穩健度。本論文首先針對以英式拍賣為基礎的SSA，提出有效降低計算得標者時間的拍賣機制。提出的拍賣機制不但保有英式拍賣的實做簡易性，更能提供SEP可預期的獲利保證。接著，研究廣告商與SEP同時滿意的平衡結果。我們首先研究雙方參與者對於評價拍賣結果的相關因素、定義平衡的拍賣結果並分析實現平衡結果的必要條件。最後，我們分析報復型廣告商對於拍賣結果的影響，並且提出拍賣機制，以有效的偵測與矯正報復型投標行為，進而降低報復型投標所造成的負面影響。以目前的SSA架構下，本研究考慮上述面向以提高拍賣機制的穩健度，提供網路瀏覽者更好的使用體驗，並且增進廣告商對於拍賣結果的接受度，對於日後的SSA發展十分重要。

關鍵字

穩健度 ； 廣義二級價格 ； 贊助商搜尋拍賣 ； 均衡 ； 惡意投標

並列摘要

In the current online advertising industry, the sponsored search auction (SSA) with the generalized second price (GSP) strategy is the most popular advertising application. The SSA combines Internet search with advertising service to recommend advertisements interested by the Internet users. To enhance the robustness of the SSA, we take into account the following issues: 1) the computation efficiency in determining winners as the advertisers have various valuations, 2) the outcome satisfaction between the SSA participants, and 3) the outcome fairness for advertisers with different bidding strategies. First, we apply the rank-by-bid principle to the English auction-based SSA to improve the computation time in determining winners. The proposed mechanism not only maintains the easy implementation of the English auction, but also provides the lower bound of revenue for the search engine provider (SEP). Next, we study the balance outcome that is accepted by the SEP and advertisers simultaneously. We investigate six factors to formulate the outcome satisfaction for the SEP and advertisers. Then, five similarity/distance measurement approaches are applied to estimate the way of realizing balance outcomes. In the end of this study, we measure the negative effects resulted from the vindictive bidding, and provide an auction mechanism to detect and correct vindictive bidding behaviors. From our theoretical analysis and simulation experiment, the proposed mechanisms provide efficient process for determining winners, balance outcomes accepted by the SEP and advertisers simultaneously, and fair and stable outcomes. This study is important in the implementation consideration since the proposed mechanisms take advantage of the properties applied in the real world environment.

並列關鍵字

Robustness ； Generalized Second Price ； Sponsored Search Auction ； Equilibrium ； Vindictive Bidding

參考文獻

[THL14-a] Chen-Kun Tsung, Hann-Jang Ho, and Sing-Ling Lee, "A Game Theoretical Approach for Solving Winner Determination Problems," Journal of Applied Mathematics, vol. 2014, Article ID 845071, 10 pages.

[APR13] Marjan Abdeyazdan, Saeed Parsa, and Amir Masoud Rahmani, "Task Graph Prescheduling, Using Nash Equilibrium in Game Theory," The Journal of Supercomputing, Vol. 64(1), pp. 177-203, 2013.

[BB01] Deepak Bansal and Hari Balakrishnan, "Binomial Congestion Control Algorithms," IEEE International Conference on Computer Communications, pp. 1-10, 2001.

[BC12] Julien Bringer and Herve Chabanne, "Embedding Edit Distance to Enable Private Keyword Search," Human-centric Computing and Information Sciences, Vol. 2(2), 2012.

[BDQ08] Tian-Ming Bu, Xiaotie Deng, and Qi Qi, "Forward Looking Nash Equilibrium for Keyword Auction," Information Processing Letters, Vol. 105(2), pp. 41-46, 2008.