The Markov User Model Under The Generalized Second Price Auction

Sponsored search auction is used by most search engines to find ads showing on the web page of search results. The income of this targeted advertising business is a big part of the revenue of most search engines. The most widely used approach is called Generalized Second Price (GSP) auction. Most previous works about GSP auction are based on the separation assumption:the probability a user will click on an ad is com-posed by two independent parts:a quality factor of the ad itself and a position factor of the slot of the ad. This previous model does not include the externality a higher ad may bring to the ads below it.We study a GSP auction in a Markovian user model where the externality is in-cluded by modeling a user's probability behavior of scanning 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 sim-ulation. We compare our results with social optimum and previous approaches. Com-parison shows that our results approximate the social optimum and improve previous approaches under various circumstances.