We study formally discrete bidding strategies for the game induced by the Generalized Second Price keyword auction mechanism. Such strategies have seen experimental evaluation in the recent literature as parts of iterative best response procedures, which have been shown not to converge. We give a detailed definition of iterative best response under these strategies and, under appropriate discretization of the players' strategy spaces we find that the discretized configurations space {\em contains} socially optimal pure Nash equilibria. We cast the strategies under a new light, by studying their performance for bidders that act based on local information; we prove bounds for the worst-case ratio of the social welfare of locally stable configurations, relative to the socially optimum welfare.
Logistics (theme 3)
Springer
A. Saberi
Lecture Notes in Computer Science
International Workshop on Internet and Network Economics
Networks and Optimization

Markakis, V, & Telelis, O. (2010). Discrete Strategies in Keyword Auctions and Their Inefficiency for Locally Aware Bidders. In A Saberi (Ed.), Proceedings of International Workshop on Internet And Network Economics 2010 (6) (pp. 523–530). Springer.