GSP with General Independent Click-through-Rates

DOI10.1007/978-3-319-13129-0_32MaRDI QIDQ2937002zbMATH OpenOpenAlexFDO

Authors Ruggiero Cavallo, Christopher A. Wilkens

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3048

zbMATH Keywords

generalized second price auctiontwo-slot setting

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: The popular generalized second price (GSP) auction for sponsored search is built upon a separable model of click-through-rates that decomposes the likelihood of a click into the product of a "slot effect" and an "advertiser effect" --- if the first slot is twice as good as the second for some bidder, then it is twice as good for everyone. Though appealing in its simplicity, this model is quite suspect in practice. A wide variety of factors including externalities and budgets have been studied that can and do cause it to be violated. In this paper we adopt a view of GSP as an iterated second price auction (see, e.g., Milgrom 2010) and study how the most basic violation of separability --- position dependent, arbitrary public click-through-rates that do not decompose --- affects results from the foundational analysis of GSP (Varian 2007, Edelman et al. 2007). For the two-slot setting we prove that for arbitrary click-through-rates, for arbitrary bidder values, an efficient pure-strategy equilibrium always exists; however, without separability there always exist values such that the VCG outcome and payments cannot be realized by any bids, in equilibrium or otherwise. The separability assumption is therefore necessary in the two-slot case to match the payments of VCG but not for efficiency. We moreover show that without separability, generic existence of efficient equilibria is sensitive to the choice of tie-breaking rule, and when there are more than two slots, no (bid-independent) tie-breaking rule yields the positive result. In light of this we suggest alternative mechanisms that trade the simplicity of GSP for better equilibrium properties when there are three or more slots.

Recommendations

• On the solution of GSPN reward models
• Generalizing the GSVD
• On the Gittins index for multiarmed bandits
• A generalized Gittins index for a class of multiarmed bandits with general resource requirements

Cited in

(12)

• Generalized second price auctions over a network
• Hybrid mechanisms for Vickrey-Clarke-Groves and generalized second-price bids
• Bayes-Nash equilibria of the generalized second-price auction
• Bounding the inefficiency of outcomes in generalized second price auctions
• Revenue guarantees in sponsored search auctions
• Equilibria of GSP for range auction
• An experimental study of sponsored-search auctions
• Adopting the cascade model in ad auctions: efficiency bounds and truthful algorithmic mechanisms
• Individually-fair auctions for multi-slot sponsored search
• Nontruthful position auctions are more robust to misspecification
• Arbitrage opportunities across sponsored search markets
• Simplified mechanisms with an application to sponsored-search auctions

This page was built for publication: GSP with General Independent Click-through-Rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937002)