Greedy Bidding Strategies for Keyword Auctions

Cary, Matthew, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna Karlin, Claire Mathieu, and Michael Schwarz. “Greedy Bidding Strategies for Keyword Auctions.” Proceedings of the International Conference on Electronic Commerce (2007): 262-271.

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.

Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions

Edelman, Benjamin, and Michael Schwarz. “Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions.” December 2006. Mimeo. (Revised and published as Optimal Auction Design and Equilibrium Selection in Sponsored Search Auctions, American Economic Review 100, no. 2 (May 2010): 597-602.)

We characterize the optimal (revenue maximizing) auction for sponsored search advertising. We show that a search engine’s optimal reserve price is independent of the number of bidders. Using simulations, we consider the changes that result from a search engine’s choice of reserve price and from changes in the number of participating advertisers.