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 talk will present results in both directions of the intellectual exchange.
Originally designed by industry engineers, the sponsored search auction has raised many interesting questions in auction design. For example, early auctions were based on a first-price payment model and proved to be highly unstable --- we show 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, people cannot be expected to solve computationally intractable problems. We show that this insight engenders a new form of stability we call complexity equilibria: when production has economies of scale, markets may be stable because finding a good deviation is computationally intractable.