TY - GEN
T1 - A new ranking scheme of the GSP mechanism with Markovian users
AU - Deng, Xiaotie
AU - Yu, Jiajin
PY - 2009
Y1 - 2009
N2 - Sponsored search auction is used by most search engines to select ads to display on the web page of a search result, according to advertisers' bidding prices. The income of this targeted advertising business is a big part of the revenue of most search engines. The most widely used approach to choose ads is the Generalized Second Price (GSP) auction, choosing the i-th highest bidder to display at the i-th most favorable position and charging the (i+1)-st highest bidding price. Most previous works about GSP auction are based on the separation assumption: the probability a user will click on an ad is composed of two independent parts: a quality factor of the ad itself and a position factor of the slot of the ad. The previous model does not include the externality an ad may bring to the other ads. We study a GSP auction in a Markovian user model where the externality is considered by modeling a user's probability behavior when he reads ad list. In particular, we propose a new ranking scheme for the bidders. We prove Nash equilibrium always exists in the auction and study the efficiency of the auction by theoretical analysis and simulation. We compare our results with social optimum and previous approaches. Comparison shows that our scheme approximates the social optimum and improves previous approaches under various circumstances. © 2009 Springer-Verlag Berlin Heidelberg.
AB - Sponsored search auction is used by most search engines to select ads to display on the web page of a search result, according to advertisers' bidding prices. The income of this targeted advertising business is a big part of the revenue of most search engines. The most widely used approach to choose ads is the Generalized Second Price (GSP) auction, choosing the i-th highest bidder to display at the i-th most favorable position and charging the (i+1)-st highest bidding price. Most previous works about GSP auction are based on the separation assumption: the probability a user will click on an ad is composed of two independent parts: a quality factor of the ad itself and a position factor of the slot of the ad. The previous model does not include the externality an ad may bring to the other ads. We study a GSP auction in a Markovian user model where the externality is considered by modeling a user's probability behavior when he reads ad list. In particular, we propose a new ranking scheme for the bidders. We prove Nash equilibrium always exists in the auction and study the efficiency of the auction by theoretical analysis and simulation. We compare our results with social optimum and previous approaches. Comparison shows that our scheme approximates the social optimum and improves previous approaches under various circumstances. © 2009 Springer-Verlag Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/76649141546
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-76649141546&origin=recordpage
U2 - 10.1007/978-3-642-10841-9_59
DO - 10.1007/978-3-642-10841-9_59
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3642108407
SN - 9783642108402
VL - 5929 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 583
EP - 590
BT - Internet and Network Economics
PB - Springer Verlag
T2 - 5th International Workshop on Internet and Network Economics, WINE 2009
Y2 - 14 December 2009 through 18 December 2009
ER -