Strategic interaction in online advertisement

Printer-friendly version
Word cloud of (generated via
From theory to application
Sergei Izmalkov
Issue number: 
7 - May 2015
From Theory to Application
One of the most common online activities is search. Large companies, such as Google, Yahoo! or Microsoft, compete for people’s attention by constantly improving their services while financing them from selling ads. Notably, search platforms are market makers: they create their own rules and procedures of how advertisers are matched to customers. How to do this matching effectively is the main objective for practitioners and a fascinating problem for economic theorists.

Being the top search company in the world, Google processes more than 3 billion searches per day. Each time a person searches, an auction is conducted to determine which ads to show to her. In less than 20 years, online ads have grown to become the top advertising segment in the world with the volume of $175bln dollars (projected by for the end of 2015), roughly a half of it being sponsored search revenue.

The success of the online advertizing and of search platforms can be linked to three major innovations: contextual ads, auctions, and GSPA. A context is essentially anything that can differentiate customers: e.g., a search phrase, history of searches or purchases, contents of a page, a location and time of the search. Unlike  TV or billboard ads, contextual ads can target the desired audience with high precision: a florist can show his ad to anyone searching for flowers but not to those who look for cars or pizza. Auctioning ad positions achieves two goals for the search platforms: to generate high revenue and to satisfy customers by offering them relevant ads. Indeed, the firms who are willing to pay a lot for the best ad positions must be expecting a return on their ads coming from additional customers, but that, in turn, means that customers indeed find those ads attractive. Thus, the core of online advertisement and the main reason for its rapid growth is endogenous matching of advertisers and users achieved by bidding for relevant contexts and allocating the ads based on the bidding results.

GSPA or the generalized second price auction has been, until very recently, the prevalent format for ad allocations. In its simplest form, several advertising positions are allocated on the screen, typically 3 or 4 above the search results and a few more below. Firms submit bids for different keywords (phrases). When a user searches for something, e.g. “pizza margherita,” all bids for closely matched keywords, e.g. “pizza”, “margherita” and the query itself, are taken together and ranked. Then, the positions are allocated according to rank: the best position goes to the firm with the highest bid, the second-best position to the firm with the second-highest bid, and so on. Crucially, the price for the first position is the second-highest bid, for the second position is the third highest bid …; and firms pay per click – only when the customer actually responds to the ad.

A game theorist can now easily explain why this peculiar format became the industry standard. [EOS] and [V] were the first to model the GSP auction, offering a theoretical model and testing for its applicability for explaining actual bidding patterns. The main implication is that GSP auction has an equilibrium in which positions are allocated assortatively, which is also efficient: firms that obtain higher expected value from a customer also occupy higher positions. Payment per click rather than payment per ad shown or per transaction reduces the risk of adverse behavior by search platform and firms, since a click is the moment at which the customer is transferred from the search platform to the website of the firm.

However, the strongest argument in support of GSPA compared to the originally used generalized first-price auction (each firm pays its own bid) is that GSPA is dynamically stable (in game-theoretic language it “has an ex post equilibrium”), while GFPA is not. Since search queries come often (in fact, firms themselves can search and see auction results), firms can easily figure out the bids of the others. In GFPA, since firms pay what they bid, they would want to optimize their bids, which, when everyone does it, leads to a stream of requests of bid adjustments that puts a lot of strain on search platforms (and on efficiency/ revenue properties as well). In GSPA, since firms pay what their close competitor bids, there is no need to adjust bids often. By experimenting with bids, firms can also verify that search platforms behave by their rules and charge exactly the bid of the close competitor. This is astonishing for a theorist:  online , the second-price format wins, while, in contrast, second-price auctions for common goods are rarely used, mostly due to mistrust in the auctioneer (see [RTK]).

At present, the industry faces a conceptual challenge: how to improve on the existing auction format and how to offer new formats for new kinds of services. This is a daunting task, because the main process for having changes in practice is experimentation: you test a new idea on a small fraction of customers and implement it if your test shows a sizeable improvement relative to the control group. Search platforms constantly run such experiments. However, this does not work for auction rules. If the rules of the game change, the firms adjust their behavior, not only as a direct response to the changes but also in reaction to the responses of the other firms. An experiment on a fraction of a flow is unlikely to capture these strategic effects. This is a domain for a game theorist and a structural econometrician to make an impact: construct a model of the current strategic interaction, estimate its relevant parameters on existing data, then compute equilibria under the proposed new rules, or, perhaps, solve a general mechanism design problem searching for the optimal (in the appropriate sense) mechanism.

For a theorist, the main challenge is to find an appropriate model for the strategic interaction at hand. [Of course, later one would also need to convince practitioners that the model is appropriate and better than the existing and well-working format.] Most of the recent papers on online auctions, at least on the economics side, are tackling this challenge from various directions, focusing specifically on incorporating consumer clicking behavior into the model and  properly modeling and estimating individual firm’s decisions (notable contributions are [AE], [AN], and [JS]).

In our current project at CSDSI NES we focus on identifying the relevant scope for strategic interaction among firms. Existing models suppose that firms compete on keyword by keyword basis and treat different keywords separately. Reality is likely to be different. Firms, especially large ones, bid on thousands of keywords simultaneously, they might find it difficult or inefficient to pay a lot of attention to each specific keyword. Perhaps more importantly, firms may compete on related keywords, e.g. “pizza margherita” and “peperoni pizza,” which may significantly alter their strategic responses. Unlike an auction model for a single keyword, a firm may choose to lower its bid and bid more aggressively on the other keywords in response to increased bids by its competitors.

In the spirit of endogenous selection of quality ads via auctions, our idea is to identify who competes with whom and for what keywords directly from the actual data. And then use the identified structure as a reference for constructing theoretical models and for empirical estimation. The idea is to construct a bipartite network, that connects firms and keywords, for which they bid (normalized in a particular fashion to ensure that all firms whose ads are shown in response to a given query are actually competing for this keyword). Links are weighted by the amount of money actually paid, taking into account the intensity of searches and responses by users and the intensity of competition. Then, clusters in the constructed graph can represent different sub-markets and the relevant scope for strategic interaction of involved firms.

In collaboration with Yandex, the top search engine in Russian language, we have constructed such large graphs based on daily and weekly data for all sponsored search ads shown, and developed our own clusterization procedure to take into account various economic effects. Results are quite intriguing. Indeed, many identified clusters contain multiple keywords and firms, and have a complex structure (an example of a cluster is shown below: keywords are red, and firms are blue). We can also see immediately that the network structure of competition is likely to be highly important. For the general mechanism design approach in search of better ways to organize this and other online markets, we would need to take into account these network effects.





[EOS] Edelman, B., Ostrovsky, M. & Schwarz, M. (2007), `Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords', American Economic Review 97(1), 242--259.

[V] Varian, H. R. (2007), `Position auctions', International Journal of Industrial Organization 25(6), 1163--1178.

[RTK] Rothkopf, M. H., Teisberg, T. J. & Kahn, E. P. (1990), ‘Why are Vickrey auctions rare?’, Journal of Political Economy 98, 94—109.

[AE] Athey, S. & Ellison, G. (2011), `Position auctions with consumer search', The Quarterly Journal of Economics 126(3), pp. 1213--1270.



About the Author

Sergei Izmalkov obtained a PhD in Economics from Pennsylvania State University. He is currently an Associate Professor of Economics at the New Economic School, Moscow, and previously held a position at MIT. His main research interests are in Game Theory, Industrial Organization, and Mechanism Design, with focus on analysis and design of auctions, optimal selling schemes for an informed principal, analysis of online markets and economic networks. In 2013, Professor Izmalkov became the managing director of a newly established NES Center for the Study of Diversity and Social Interactions. CSDSI NES is supported by the Russian Ministry of Education and headed by Professor Shlomo Weber, it joined CTN in 2014.

Developed by Paolo Gittoi