关键词：经济学；计算机科学；广告；拍卖；支付
摘 要：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 auctions were based on a rst-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 rst-price auction oers substantially better performance guarantees when a single advertiser may benet 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.