E cient Collusion in Sponsored Search Auctions
Transcript Of E cient Collusion in Sponsored Search Auctions
Efficient Collusion in Sponsored Search Auctions
Diploma Thesis in Economics Diplomarbeit
zur Erlangung des Grades eines Diplom-Volkswirtes
by
Kai Becker
Student ID: 508369
Humboldt Universit¨at zu Berlin School of Business and Economics
Supervisor: Prof. Dr. Elmar Wolfstetter June 1, 2009
The challenge of innovation is that we are all boxed in by what we know, by our assumptions about how things work. Innovation is right in front of us—we just need to see past our own assumptions. Forget what you know.
—Scott Karp on Google’s Adwords Select—
Contents
1 Introduction
4
2 Position Auctions
8
2.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Model Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Payment Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Tie-breaking rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Analysis of Equilibria
16
3.1 Complete Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Incomplete Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Mediators in Position Auctions
28
4.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 A Mediator for the Generalized Second-Price Auction . . . . . . . . . . . 34
5 Collusion in a Generalized Second-Price Auction
39
5.1 A Collusive Mediator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 The Case of Incomplete Information . . . . . . . . . . . . . . . . . . . . . 42
5.3 Collusion with Side Payments . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4 Repeated Play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6 Variations
56
6.1 Asymmetric Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2 Mediators in General Position Auctions . . . . . . . . . . . . . . . . . . . 57
6.3 Position Auctions with Quality Factors . . . . . . . . . . . . . . . . . . . 60
6.4 Utility Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Conclusion
64
1 Introduction
The online advertisement market is one of the most blossoming and rapidly growing markets today and billions of dollars worth of keywords are sold every year. The revenue of the major player in the market, Google, added up to about $ 4.226 billion in 2008. On the Forbes Global 20001, a list of the 2000 largest companies in the world, Google was ranked in position 155. In order to demonstrate the immense dimensions of the Internet advertisement market, it is found in an earlier version of (Edelman, Ostrovsky, Schwarz [2007]) from October 2005:
“The combined market capitalization of Google and Yahoo! is over $ 125 billion. In comparison, the combined market capitalization of all US airlines is about $ 20 billion.”
Today, the market capitalization of Google alone is about $ 125.3 billion. The dominant part of sales in the Internet advertising market is organized by an auction mechanism, the so-called generalized second-price auction (GSP), that was introduced in its current version not earlier than February 2002 by Google. This mechanism is subject of our study. We will investigate the strategic implications of this mechanism, i.e. we will investigate the set of Nash equilibria; introduce the notion of mediators and question whether it is vulnerable to collusion by bidders who use a mediation device in order to do so.
The mechanism works as follows: Whenever an Internet user enters a query, she will be redirected to a page of results, on which she finds a list of so-called sponsored links next to the list of results, which are clearly distinguishable from the ordinary search
1http://www.forbes.com/lists/2009/18/global-09_The-Global-2000_Rank_print.html
4
1 Introduction
results. These sponsored links are paid advertisements, targeted to the specific keywords that users enter. When a user clicks on a link, she will be redirected to the respective advertiser’s page. The search engine charges a certain amount of money from each advertiser for every click on his advertisement depending on the keyword’s popularity, as well as for the position in which he is shown. In particular, there is a limited number of ads that can be shown on a page, and links that are shown on a higher position on the screen are likely to be clicked more often. Advertisers submit one-dimensional bids for each keyword they are interested in and, finally, they are shown in decreasing order of their bids whenever the respective keyword is entered by a user. The auction is highly dynamic, since bidders can adjust their bids at any point in time, and different links are shown for different keywords. Each advertiser has to pay the amount of the bid that the advertiser has submitted that is allocated to the position directly below him plus a minimal increment. The auction is called a generalized second-price auction since it is an intuitive extension of the principle of the well known single-item second-price auction. If there were only one position, the mechanism would be strategically equivalent to the famous Vickrey-Clarke-Groves (VCG) auction. However, since there is, in general, more than one position, GSP is no longer equivalent to the VCG auction. It lacks some of the desirable properties such as incentive-compatibility, i.e. truth-telling is a weakly dominant strategy for every bidder. In addition, it does not possess an equilibrium in dominant strategies neither.
In particular, we will analyze the set of Nash equilibria of the game induced by the generalized second-price auction. It can be shown that multiple equilibria exist, and among the set of symmetric Nash equilibria, an equilibrium exists with the same outcome as if the auction were designed according to the rules of VCG. Players are ranked according to their true valuations and they are charged VCG payments. This is the socially optimal outcome for the bidders and the worst outcome for the search engine, which is somewhat surprising, since, the opposite is true of general multiple object auctions, see for example (Krishna [2002]):
“Among all mechanisms for allocating multiple objects that are efficient, in-
5
1 Introduction
centive compatible and individually rational, the VCG mechanism maximizes the expected payment of each agent.”
We will derive our results by following two different approaches—those of (Varian [2007]), who analyzes bounds of equilibrium bids in a symmetric Nash equilibrium, and of (Edelman, Ostrovsky, Schwarz [2007]), who develop the concept of locally envy-free equilibria. In a locally envy-free equilibrium, every bidder prefers his current position to the position of the player directly above him. In fact, we will show that both equilibrium concepts deliver the same results since they are strategically equivalent.
However, as there are multiple equilibria, and from the perspective of the bidders, the VCG equivalent outcome is socially optimal, bidders can improve their utility by coordinating to the VCG equilibrium over any other equilibrium of the game. (Edelman, Ostrovsky, Schwarz [2007]) show by means of a generalized English auction (that corresponds strategically to the generalized second-price auction) that bidders may emerge to coordinate with the VCG outcome in a dynamic framework through simple strategies, i.e. by raising their bids incrementally until it is no longer profitable. Another way to attain the VCG equivalent equilibrium is by the use of a mediator. In the thesis at hand, we will focus on mediators in terms of (Ashlagi et al. [2008]):
“A mediator for a given game is a reliable entity that can interact with the players and perform actions on their behalf. However, a mediator cannot enforce behavior.”
Every player is free to use the service of the mediator or participate in the game directly. (Ashlagi et al. [2008]) design a mediator that implements the VCG equivalent outcome such that it is an ex post equilibrium for every bidder to use the service of the mediator and report his valuation truthfully. We will present their results in some detail in Chapter 4. While a mediator that implements the VCG equivalent outcome may already be regarded as a form of collusive behavior on the part of the bidders, since it coordinates on the best social equilibrium for the bidders and the worst for the search engine, we examine if a mediator exists that is able to coordinate the bidders to achieve
6
1 Introduction even more profitable, collusive outcomes. Our focus is on efficient collusion, i.e. collusive agreements that implement an allocation of players and positions that is consistent with the order of players’ true valuations. We find that no such mediator in the fashion of (Ashlagi et al. [2008]) is able to do so. Furthermore, we question if collusion becomes feasible by equipping the mediator with the additional ability to facilitate transfer payments among bidders. In our analysis, we allow for static as well as repeated play.
In Chapter 2 we give a short review on the evolution of sponsored search auctions and introduce a formal model of position auctions, as we will say in place of sponsored search auctions in the remainder of this thesis, since it more accurately depicts the nature of the auctions, i.e. assigning players to positions on a screen. Chapter 3 analyzes equilibrium behavior and outcomes in such a framework. Chapter 4 introduces the concept of mediators and applies it to the context of position auctions. A mediator is presented that implements VCG in a generalized second-price auction. Chapter 5 investigates GSP’s vulnerability to collusion. In Chapter 6, we present some variations of our model. Chapter 7 concludes.
7
2 Position Auctions
2.1 Evolution
The story of Internet advertising began around the year 1994. In the early days of Internet advertising, the predominant format of advertisements was the so-called banner ads. These were sold on a CPM (cost per thousand impressions) basis, i.e. advertisers paid a fixed amount of money for a fixed number of times their ad was shown, typically one thousand impressions. Single contracts were negotiated on a case-by-case basis, market dynamics were at most moderate and revenues were insignificant compared to what would follow some years later. But in 1997, the Internet advertisement market was revolutionized by GoTo, which was renamed to Overture some time later and was finally acquired by Yahoo!. A completely new way of selling advertisements on the web was created. Not only did advertisers no longer have to pay for a fixed number of impressions anymore, but they were also charged a price per click, i.e. for every time a user was redirected from a search engine to their respective web site. Furthermore, advertisements became targeted. Each visitor to a web site was no longer shown the same banner, advertisements were now shown to a user whenever she entered an appropriate keyword into a search query. Despite these remarkable features, the new mechanism brought considerable innovation in many more ways. First, it served as a compromise in terms of what was essentially sold. Advertisers are in fact interested in attracting customers who finally purchase a product, while the search engine’s goal is to maximize the profit for every query that is performed by a user. While the former suggests a pricing model in which a payment has to be made only if a customer actually purchases
8
2 Position Auctions
a product, the latter suggest cost per impression pricing. Furthermore, the mechanism overcame manual, cost-intensive negotiations for each advertisement by introducing a kind of automated self-serve interface on an auction basis. Until the first years of the new millennium, Overture, which implemented pay-per-click advertisement for other web sites, significantly outperformed Google in terms of revenue by an amount of $ 288 million in 2001, while Google earned about $ 86.4 million in the same year. The initial auction format by Overture was a first-price format, i.e. bidders were charged to pay the bid they submitted on a per-click basis. But this pricing rule turned out to be inefficient. Due to the dynamic nature of ad auctions, bidder’s are free to change their bid whenever they want to, it occurred that bidders adjusted their bids frequently in response to other bidders’ behavior. In particular, as shown e.g. in (Edelman, Ostrovsky [2005]), the first-price format used by Overture did not possess a stable equilibrium, and “cycling” bids were observed in practice. Bidders subsequently raised their bids by an increment above competitor’s bids until it was no longer profitable and then dropped back to the minimum bid, which yielded inefficiency for both the search engine and the bidders. Inefficiency from the perspective of the bidders, since the bidder with the highest valuation did not obtain the highest position over the whole period of time, and inefficiency for the search engine, since bids were below equilibrium bids of alternative pricing mechanisms over considerable periods of time. Hence the mechanism caused inefficient allocations, created volatile prices and offered incentives to invest in automated robots and other software that would offer bidders advantages over other bidders who could not react as quickly on changing bids. Clearly, such investments are socially inefficient. Finally, in February 2002, Google introduced a new version of its ad program AdWords, that initially sold ads on CPM basis. AdWords Select came along with a considerable number of innovations that were destined to once more change the market fundamentally. In order to overcome the inefficiencies due to cycling bids, Google introduced a second-price format which was less susceptible to gaming. Another seminal innovation was the introduction of relevance. Whenever bidders are ranked according to their bid only, a bidder can obtain the top position on the screen simply by submitting
9
2 Position Auctions
the highest bid. However, if some bidders attract more users than others to click on a link and thus generate higher profits for the search engine, but are assigned to lower positions or not shown at all, this is clearly inefficient. Hence, Google included these bidder dependent probabilities of being clicked by multiplying each bidders bid with its estimated click-through rate and ranked the bidders accordingly. While Google remains true to this model to this day, Yahoo! switched to the second-price format shortly after it was introduced by Google, but still ranks bidders purely by their bids. Today, Google earns a revenue of approximately $ 22 billion, mostly from selling ads. Revenue of Yahoo! aggregates to about $ 7.2 billion annually.1
We will introduce a formal model of position auctions in the following chapter. We will assume the estimated click-through rates to be identical for each bidder, in which case both models are equivalent. In Chapter 6 we will relax this assumption and allow for varying click-through rates and show that most of our forthcoming findings will emerge to hold in adjusted versions.
2.2 Model Environment
In the existing literature, position auctions were modeled as games of complete information by (Edelman, Ostrovsky, Schwarz [2007]) and (Varian [2007]) as well as games of incomplete information, see for example (Ashlagi et al. [2008]) or (Lahaie [2006]). Independent of the information setting that will be applied, position auctions share an identical basic environment EP .
For a specific keyword, there is a finite number of positions j ∈ K = {1, . . . , m}, i.e. positions on the screen where ads related to the keyword can be displayed. There is a finite number of bidders i ∈ N = {1, . . . , n}, and without loss of generality, there are more bidders than slots, n > k. For each position j ∈ K, there exists a positive number αj > 0, the click-through rate of position j. In the following, it is assumed
1Revenue numbers are taken from www.wolframalpha.com, which emerges to be an exciting new competitor of established search engines.
10
Diploma Thesis in Economics Diplomarbeit
zur Erlangung des Grades eines Diplom-Volkswirtes
by
Kai Becker
Student ID: 508369
Humboldt Universit¨at zu Berlin School of Business and Economics
Supervisor: Prof. Dr. Elmar Wolfstetter June 1, 2009
The challenge of innovation is that we are all boxed in by what we know, by our assumptions about how things work. Innovation is right in front of us—we just need to see past our own assumptions. Forget what you know.
—Scott Karp on Google’s Adwords Select—
Contents
1 Introduction
4
2 Position Auctions
8
2.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Model Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Payment Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Tie-breaking rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Analysis of Equilibria
16
3.1 Complete Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Incomplete Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Mediators in Position Auctions
28
4.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 A Mediator for the Generalized Second-Price Auction . . . . . . . . . . . 34
5 Collusion in a Generalized Second-Price Auction
39
5.1 A Collusive Mediator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 The Case of Incomplete Information . . . . . . . . . . . . . . . . . . . . . 42
5.3 Collusion with Side Payments . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4 Repeated Play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6 Variations
56
6.1 Asymmetric Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2 Mediators in General Position Auctions . . . . . . . . . . . . . . . . . . . 57
6.3 Position Auctions with Quality Factors . . . . . . . . . . . . . . . . . . . 60
6.4 Utility Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Conclusion
64
1 Introduction
The online advertisement market is one of the most blossoming and rapidly growing markets today and billions of dollars worth of keywords are sold every year. The revenue of the major player in the market, Google, added up to about $ 4.226 billion in 2008. On the Forbes Global 20001, a list of the 2000 largest companies in the world, Google was ranked in position 155. In order to demonstrate the immense dimensions of the Internet advertisement market, it is found in an earlier version of (Edelman, Ostrovsky, Schwarz [2007]) from October 2005:
“The combined market capitalization of Google and Yahoo! is over $ 125 billion. In comparison, the combined market capitalization of all US airlines is about $ 20 billion.”
Today, the market capitalization of Google alone is about $ 125.3 billion. The dominant part of sales in the Internet advertising market is organized by an auction mechanism, the so-called generalized second-price auction (GSP), that was introduced in its current version not earlier than February 2002 by Google. This mechanism is subject of our study. We will investigate the strategic implications of this mechanism, i.e. we will investigate the set of Nash equilibria; introduce the notion of mediators and question whether it is vulnerable to collusion by bidders who use a mediation device in order to do so.
The mechanism works as follows: Whenever an Internet user enters a query, she will be redirected to a page of results, on which she finds a list of so-called sponsored links next to the list of results, which are clearly distinguishable from the ordinary search
1http://www.forbes.com/lists/2009/18/global-09_The-Global-2000_Rank_print.html
4
1 Introduction
results. These sponsored links are paid advertisements, targeted to the specific keywords that users enter. When a user clicks on a link, she will be redirected to the respective advertiser’s page. The search engine charges a certain amount of money from each advertiser for every click on his advertisement depending on the keyword’s popularity, as well as for the position in which he is shown. In particular, there is a limited number of ads that can be shown on a page, and links that are shown on a higher position on the screen are likely to be clicked more often. Advertisers submit one-dimensional bids for each keyword they are interested in and, finally, they are shown in decreasing order of their bids whenever the respective keyword is entered by a user. The auction is highly dynamic, since bidders can adjust their bids at any point in time, and different links are shown for different keywords. Each advertiser has to pay the amount of the bid that the advertiser has submitted that is allocated to the position directly below him plus a minimal increment. The auction is called a generalized second-price auction since it is an intuitive extension of the principle of the well known single-item second-price auction. If there were only one position, the mechanism would be strategically equivalent to the famous Vickrey-Clarke-Groves (VCG) auction. However, since there is, in general, more than one position, GSP is no longer equivalent to the VCG auction. It lacks some of the desirable properties such as incentive-compatibility, i.e. truth-telling is a weakly dominant strategy for every bidder. In addition, it does not possess an equilibrium in dominant strategies neither.
In particular, we will analyze the set of Nash equilibria of the game induced by the generalized second-price auction. It can be shown that multiple equilibria exist, and among the set of symmetric Nash equilibria, an equilibrium exists with the same outcome as if the auction were designed according to the rules of VCG. Players are ranked according to their true valuations and they are charged VCG payments. This is the socially optimal outcome for the bidders and the worst outcome for the search engine, which is somewhat surprising, since, the opposite is true of general multiple object auctions, see for example (Krishna [2002]):
“Among all mechanisms for allocating multiple objects that are efficient, in-
5
1 Introduction
centive compatible and individually rational, the VCG mechanism maximizes the expected payment of each agent.”
We will derive our results by following two different approaches—those of (Varian [2007]), who analyzes bounds of equilibrium bids in a symmetric Nash equilibrium, and of (Edelman, Ostrovsky, Schwarz [2007]), who develop the concept of locally envy-free equilibria. In a locally envy-free equilibrium, every bidder prefers his current position to the position of the player directly above him. In fact, we will show that both equilibrium concepts deliver the same results since they are strategically equivalent.
However, as there are multiple equilibria, and from the perspective of the bidders, the VCG equivalent outcome is socially optimal, bidders can improve their utility by coordinating to the VCG equilibrium over any other equilibrium of the game. (Edelman, Ostrovsky, Schwarz [2007]) show by means of a generalized English auction (that corresponds strategically to the generalized second-price auction) that bidders may emerge to coordinate with the VCG outcome in a dynamic framework through simple strategies, i.e. by raising their bids incrementally until it is no longer profitable. Another way to attain the VCG equivalent equilibrium is by the use of a mediator. In the thesis at hand, we will focus on mediators in terms of (Ashlagi et al. [2008]):
“A mediator for a given game is a reliable entity that can interact with the players and perform actions on their behalf. However, a mediator cannot enforce behavior.”
Every player is free to use the service of the mediator or participate in the game directly. (Ashlagi et al. [2008]) design a mediator that implements the VCG equivalent outcome such that it is an ex post equilibrium for every bidder to use the service of the mediator and report his valuation truthfully. We will present their results in some detail in Chapter 4. While a mediator that implements the VCG equivalent outcome may already be regarded as a form of collusive behavior on the part of the bidders, since it coordinates on the best social equilibrium for the bidders and the worst for the search engine, we examine if a mediator exists that is able to coordinate the bidders to achieve
6
1 Introduction even more profitable, collusive outcomes. Our focus is on efficient collusion, i.e. collusive agreements that implement an allocation of players and positions that is consistent with the order of players’ true valuations. We find that no such mediator in the fashion of (Ashlagi et al. [2008]) is able to do so. Furthermore, we question if collusion becomes feasible by equipping the mediator with the additional ability to facilitate transfer payments among bidders. In our analysis, we allow for static as well as repeated play.
In Chapter 2 we give a short review on the evolution of sponsored search auctions and introduce a formal model of position auctions, as we will say in place of sponsored search auctions in the remainder of this thesis, since it more accurately depicts the nature of the auctions, i.e. assigning players to positions on a screen. Chapter 3 analyzes equilibrium behavior and outcomes in such a framework. Chapter 4 introduces the concept of mediators and applies it to the context of position auctions. A mediator is presented that implements VCG in a generalized second-price auction. Chapter 5 investigates GSP’s vulnerability to collusion. In Chapter 6, we present some variations of our model. Chapter 7 concludes.
7
2 Position Auctions
2.1 Evolution
The story of Internet advertising began around the year 1994. In the early days of Internet advertising, the predominant format of advertisements was the so-called banner ads. These were sold on a CPM (cost per thousand impressions) basis, i.e. advertisers paid a fixed amount of money for a fixed number of times their ad was shown, typically one thousand impressions. Single contracts were negotiated on a case-by-case basis, market dynamics were at most moderate and revenues were insignificant compared to what would follow some years later. But in 1997, the Internet advertisement market was revolutionized by GoTo, which was renamed to Overture some time later and was finally acquired by Yahoo!. A completely new way of selling advertisements on the web was created. Not only did advertisers no longer have to pay for a fixed number of impressions anymore, but they were also charged a price per click, i.e. for every time a user was redirected from a search engine to their respective web site. Furthermore, advertisements became targeted. Each visitor to a web site was no longer shown the same banner, advertisements were now shown to a user whenever she entered an appropriate keyword into a search query. Despite these remarkable features, the new mechanism brought considerable innovation in many more ways. First, it served as a compromise in terms of what was essentially sold. Advertisers are in fact interested in attracting customers who finally purchase a product, while the search engine’s goal is to maximize the profit for every query that is performed by a user. While the former suggests a pricing model in which a payment has to be made only if a customer actually purchases
8
2 Position Auctions
a product, the latter suggest cost per impression pricing. Furthermore, the mechanism overcame manual, cost-intensive negotiations for each advertisement by introducing a kind of automated self-serve interface on an auction basis. Until the first years of the new millennium, Overture, which implemented pay-per-click advertisement for other web sites, significantly outperformed Google in terms of revenue by an amount of $ 288 million in 2001, while Google earned about $ 86.4 million in the same year. The initial auction format by Overture was a first-price format, i.e. bidders were charged to pay the bid they submitted on a per-click basis. But this pricing rule turned out to be inefficient. Due to the dynamic nature of ad auctions, bidder’s are free to change their bid whenever they want to, it occurred that bidders adjusted their bids frequently in response to other bidders’ behavior. In particular, as shown e.g. in (Edelman, Ostrovsky [2005]), the first-price format used by Overture did not possess a stable equilibrium, and “cycling” bids were observed in practice. Bidders subsequently raised their bids by an increment above competitor’s bids until it was no longer profitable and then dropped back to the minimum bid, which yielded inefficiency for both the search engine and the bidders. Inefficiency from the perspective of the bidders, since the bidder with the highest valuation did not obtain the highest position over the whole period of time, and inefficiency for the search engine, since bids were below equilibrium bids of alternative pricing mechanisms over considerable periods of time. Hence the mechanism caused inefficient allocations, created volatile prices and offered incentives to invest in automated robots and other software that would offer bidders advantages over other bidders who could not react as quickly on changing bids. Clearly, such investments are socially inefficient. Finally, in February 2002, Google introduced a new version of its ad program AdWords, that initially sold ads on CPM basis. AdWords Select came along with a considerable number of innovations that were destined to once more change the market fundamentally. In order to overcome the inefficiencies due to cycling bids, Google introduced a second-price format which was less susceptible to gaming. Another seminal innovation was the introduction of relevance. Whenever bidders are ranked according to their bid only, a bidder can obtain the top position on the screen simply by submitting
9
2 Position Auctions
the highest bid. However, if some bidders attract more users than others to click on a link and thus generate higher profits for the search engine, but are assigned to lower positions or not shown at all, this is clearly inefficient. Hence, Google included these bidder dependent probabilities of being clicked by multiplying each bidders bid with its estimated click-through rate and ranked the bidders accordingly. While Google remains true to this model to this day, Yahoo! switched to the second-price format shortly after it was introduced by Google, but still ranks bidders purely by their bids. Today, Google earns a revenue of approximately $ 22 billion, mostly from selling ads. Revenue of Yahoo! aggregates to about $ 7.2 billion annually.1
We will introduce a formal model of position auctions in the following chapter. We will assume the estimated click-through rates to be identical for each bidder, in which case both models are equivalent. In Chapter 6 we will relax this assumption and allow for varying click-through rates and show that most of our forthcoming findings will emerge to hold in adjusted versions.
2.2 Model Environment
In the existing literature, position auctions were modeled as games of complete information by (Edelman, Ostrovsky, Schwarz [2007]) and (Varian [2007]) as well as games of incomplete information, see for example (Ashlagi et al. [2008]) or (Lahaie [2006]). Independent of the information setting that will be applied, position auctions share an identical basic environment EP .
For a specific keyword, there is a finite number of positions j ∈ K = {1, . . . , m}, i.e. positions on the screen where ads related to the keyword can be displayed. There is a finite number of bidders i ∈ N = {1, . . . , n}, and without loss of generality, there are more bidders than slots, n > k. For each position j ∈ K, there exists a positive number αj > 0, the click-through rate of position j. In the following, it is assumed
1Revenue numbers are taken from www.wolframalpha.com, which emerges to be an exciting new competitor of established search engines.
10