Ad Auctions and Other Stories by

There is a growing research tradition in the interface between Economics and Computer Science: Economic insights and questions about incentives inform the design of systems, while concepts from the theory of computation help illuminate classical Economics problems. This dissertation presents results in both directions of the intellectual exchange. Originally designed by industry engineers, the sponsored search auction has raised many interesting questions and spurred much research in auction design. For example, early auc-tions were based on a first-price payment model and proved to be highly unstable — this dissertation explores how improvements in the bidding language could restore stability. We also show that a first-price auction offers substantially better performance guarantees when a single advertiser may benefit from multiple ads. Another interesting problem arises because sponsored search auctions must operate with limited information about a user’s behavior — we show how sampling can maintain incentive compatibility even when the auctioneer incorrectly predicts the user’s behavior. Computational tools also offer novel ways to understand the limits of complex economic systems. For example, a fundamental observation in this intellectual exchange is that peo