Greedy Bidding Strategies for Keyword Auctions

How should players bid in keyword auctions such as those used by Google, Yahoo! and MSN? We consider greedy bidding strategies for a repeated auction on a single keyword, where in each round, each player chooses some optimal bid for the next round, assuming that the other players merely repeat their previous bid. We study the revenue, convergence and robustness properties of such strategies. Most interesting among these is a strategy we call the balanced bidding strategy (BB): it is known that BB has a unique fixed point with payments identical to those of the VCG mechanism. We show that if all players use the BB strategy and update each round, BB converges when the number of slots is at most 2, but does not always converge for 3 or more slots. On the other hand, we present, a simple variant which is guaranteed to converge to the same fixed point for any number of slots. In a model in which only one randomly chosen player updates each round according to the BB strategy, we prove that convergence occurs with probability 1. We complement our theoretical results with empirical studies.