Advertisement allocation for generalized second-pricing schemes

作者：Goel Ashish; Mahdian Mohammad; Nazerzadeh Hamid^*; Saberi Amin

来源：Operations Research Letters, 2010, 38(6): 571-576.

DOI：10.1016/j.orl.2010.09.002

• Sponsored search
• Generalized second-pricing scheme
• Throttling policies
• Greedy algorithms

Recently, there has been a surge of interest in algorithms that allocate advertisement space in an online revenue-competitive manner. Most such algorithms, however, assume a pay-as-you-bid pricing scheme. In this paper, we study the query allocation problem where the ad space is priced using the well-known and widely used generalized second-price (GSP) scheme. We observe that the previous algorithms fail to achieve a bounded competitive ratio under the GSP scheme. On the positive side, we present online constant-competitive algorithms for the problem.

• 出版日期2010-11
• 单位Microsoft