Users interact with the web by visiting web sites and issuing queries to search engines. Showing advertisements (ads) to users during such interactions is a multi-billion dollar industry. The main goal is to match user visits to ads in a given context (web search, visiting a news site, checking e-mail, and so on). What makes this match making task different than other recommender problems like movie recommendation, content recommendation on a website, document recommendation in web search, product recommendation on a shopping site? The primary reason is due to the cost and utility functions
that are involved in matching ads-they are distinct from those used in other recommender problems. For instance, in web search and content recommendation, success of a matching algorithm is typically measured as improvement in user engagement metrics. In advertising since the ad links are sponsored by advertisers, publisher revenue and advertiser return on investment (ROI) are crucial for success. In fact, although most large-scale recommender problems can be abstractly formulated as algorithmically matching users to items in different contexts, constructing matching algorithms is an ill-posed problem in the absence of a well-defined notion of optimality that is quantified through some objective function. While the long-term objective is to maximize profit, online advertising systems typically depend on metrics that are measurable in the short term. For instance, although high-quality and topically relevant ads may not necessarily lead to significant improvements in click-rates, it may have favorable long-term impact like improving the return rate of users to web sites, which in turn leads to an increase in long-term revenue. Constructing objective functions that are based on short-term metrics involves identifying and appropriately quantifying various utilities and costs, and then striking a balance among several objectives, some of which may compete with each other. In this chapter we discuss the utilities and costs involved in one such algorithmic match making problem-online advertising. An effective matchmaking solution in such applications require strong interplay among various disciplines like computer science, economics, information retrieval, machine learning, optimization and statistics. This has given rise to a new scientific discipline that is now referred to as Computational Advertising [14, 12].