Auctions and mechanisms in keyword-based advertising

Today most of search engines’ profits come from advertising, and in particular from sponsored search. In sponsored search, advertisement slots next to search results are sold. When a query is made, besides processing the query results themselves, the search engine selects ads relevant to that query. Two of the main characteristics of this form of advertising are that advertisers are billed only when a click on their ad is made, and that prices are computed using an auction. In this thesis we consider some generalizations of the sponsored search auction model presented in the literature. In particular we account for the fact that the search engines have a great control over the order in which advertisers are ranked. In fact search engines assign quality scores to each advertiser, and, prior to sorting, scale all bids by such factors. We show how this changes the main properties of the equilibria in these auctions, and that in particular, the efficiency directly depends on how the search engine sets the quality scores. We then analyze some strategic behaviors in this environment, showing how their properties can differ from other classical auction models. In a second part of this thesis we present some experimental results. These were obtained with a large scale sponsored search simulator developed for this thesis. To realistically simulate such environments new algorithms and techniques were developed that partially overcome the lack of publicly available information, by effectively estimating many hidden parameters, such as click through rates. The experimental results presented focus on the global effects on the market when a fraction of the advertising agents engage in strategic behaviors. In particular we focus on two cases. In the first agents start to optimize their set of keywords using a custom build set of available synonyms. The second behavior we consider is one in which an agent changes his bid, with the objective of increasing costs for his opponents. Interestingly we show that this technique is not always profitable. The fact that, in sponsored search, agents might not have access to all the necessary information to compute their optimal bids, marks a significant departure from the theoretical models, that instead assume full knowledge of the environment. The field that studies models in which agents’ capabilities are limited is called bounded rationality. The final chapters of this thesis are dedicated to work done by the author during his visiting period at Northwestern University, Evanston U.S.A., under the supervision of prof. Lance Fortnow. The focus is on bounded rationality, and two problem that directly expose the role of computational limitations in game theory are analyzed.