Auctioning online advertisement space

Contents

Introduction

1 Account one: Edelman et al. (2005): “Internet Advertising and the Generalized Second-Price Auction: Selling Bil-lions of Dollars Worth of Keywords”

2 Account two: Hal A. Varian (2007): “Position auctions”

3 Account three: Fukuda et al. (2010): “Theoretical and exper- imental investigations of the performance of keyword auction mechanisms”

4 Critical discussion

5 Conclusion

Appendix

References

List of Figures

1 Distribution of mean absolute deviations (source: Varian (2007), p.1176)

2 Comparison of the average revenues of the auctioneer across periods (source: Fukuda (2010), p. 12)

3 Summary statitics of the bidding behavior per treatment and value (source: Fukuda (2010), p. 19)

Introduction

This termpaper gives a critical synthesis of three scientific contributions dealing with optimal models of charging payments for Internet advertising, an import- ant market of the new economy of the digital era. The theoretical context is game theory. The mentioned papers aim at finding the most efficient form of allocation, that is, a form of allocation which satisfies clients who invest in online advertising as well as search engine companies who offer advertising positions relating to keywords on websites visited by users: Every client should agree with the recent advertisement, and the search engine company should receive the best payment possible. This state of things is called an equilibrium in these papers.

But concerning ways to achieve this aim, the papers to discuss here differ in perspective and complexity. To scrutinize those papers, we begin by giving an account of each of the papers containing the main theses, explaining them, and outlining the string of argumentation.

To realize this, two pages will be devoted to each paper. Afterwards this termpaper continues with a critical discussion, outlining the main issues of the considered models and experiments respectively.

The references of the papers to each other will be taken into account but also stances expressed in other material dealing with the same problems. A short conclusion will close this termpaper.

Avoiding mathematical formulas up to an extent, interesting results were out- sourced to the Appendix.

1 Account one: Edelman et al. (2005): “Inter- net Advertising and the Generalized Second- Price Auction: Selling Bil-lions of Dollars Worth of Keywords”

Dating back to 2005, the paper by Edelman et al. is deeply marked by the beginning of online advertising. This form of commercials was already bil- lions of dollars worth, but Google started the program Google Ad Words just three years ago, and Yahoo was still to be considered as a potent and serious competitor in the market of selling advertising related to keywords on web sites.

Edelman et al. focus on the analysis of the so-called generalized second price (GSP) auction. At least in principle, it is used by search engines to choose customers for buying advertising positions on web sites. The method replaced the older approach to get paid off for a certain amount of ad-impressions (cf. Eldeman et al., 2005, p. 245). Different positions are offered, but the top one is the most valuable because the probability of actual clicks and therefore the possibility for the client to purchase his or her goods is the highest. To get the top position or any other one, clients have to enter an auction. The one with the highest bid wins the position in question but has only to pay the second best bid.

Edelman et al. hold up the thesis that GSP shows some similarities with the so-called Vickrey-Clark-Groves (VCG) mechanism and the Generalized English auction but has the advantage to offer multiple positions and the disadvantage that the dominant strategies lack an equilibrium, especially that of truth-telling (cf. Edelman et al., 2005, p. 242). The latter means that the advertising clients can pay less and profit more if they do not bid as high as the value of the click for them, that is regarding the worth of the purchase which can be realized (cf. Edelman et al., 2005, pp 248-249). Although not a dominant strategy, in view of Edelman et al., even according to the GSP-model, equilibrium is possible nevertheless. The authors speak of a locally envy-free equilibrium (cf. Edelman et al., 2005, p. 250).

The similarity between GSP and VCG consists in the fact that according to both models payment for advertising is based on differences in bids. But in contrast to GSP, first, VCG only offers one position per web page instead of a multitude, and, second, as a consequence, customers are charged on the basis of the externality of the other clients whose bids were too low. That means that the payment will be the difference between the aggregate clicks without the auction winning client and the aggregated value with the winning client implied. Last but not least the VCG offers smaller revenues than GSP1 (cf. Edelman et al., 2005, p. 247).

However, as Edelman et al point out, the revenues thanks to GSP could be higher if truth-telling was a dominant strategy. In VCG, it is. The bids are matched to the click values assigned to them by the customers (cf. Edelman et al., p. 249). The reason is that only one position is offered in the auction. The offering of multiple positions as in GSP implies the possibility that one bidder can get a better position by just slightly elevating a bid that therefore does not reflect the click value but allows higher gains (cf. Edelman et al., 2005, p. 249). Nevertheless, the search engine company receives hardly anything the higher gains. A significant accompanying circumstance is the instability of bids in GSP because it seems to be attractive to elevate the bid in order to take a higher position.

Moreover stable assignments of bids are even possible in GSP. The precondition is that there are fewer positions than bidders or bids (cf. Edelman, 2005, p. 250). In this respect a trait of VCG occuring in this model based on the fact that there are less positions (exactly: one) than bidders. If stable assignment of bids is given, an equilibrium is set in. According to Edelman et al., this equilibrium can be characterized as locally envy-free equilibrium. It is achieved when bidders located there cannot enhance their payoff by changing bidding position with a higher ranked bidder (cf. Edelman et al., 2005, p. 250).

The authors find the same given by the generalized English auction. This functions by the mechanism that bidders drop out one by one at a certain price until only one of them is left. Like VCG, the guiding principles are only one ➫s own values instead of beliefs and ever changing bids.

¹ for a detailed proof, see Appendix A.

2 Account two: Hal A. Varian (2007): “Posi- tion auctions”

Compared to Edelman et al. (2005), the paper by Varian can be regarded as a continuation on slightly different grounds. The author looks more closely at the structure of the equilibrium identified in advertising auctions by Edelman et al. but also by other scientific contributors. Varian holds the thesis that equilibrium belongs to “basic properties of the prices observed in Google’s ad auction” ( cf. Varian 2007, p. 1163). Using a different terminology in his approach than Edelman et al. (2005), Varians aim is threefold. First, he tracks back phenomenons of equilibrium to the so-called general nash equilibrium (NE) and the more specific symmetric nash equilibrium. Second, Varian checks attractiveness of bidding at the higher or at the lower bounds. Three, he tries to provide empirical data to prove that equilibrium is a quite common phenomenon of advertising auctions.

Instead of positions, Varian speaks of slots for advertisings (cf. Varian 2007, p. 1164). Far more than Edelman et al, Varia uses formulas in his main text. The different agents, that is customers who act as advertisers, are expressed by a = 1 , . . . , A, the different slots are expressed by s = 1 , . . . , S (cf. Varian 2007, p.1164). Varian conceives a ➫ s expected valuation for slot s in the formula

Abbildung in dieser Leseprobe nicht enthalten

where v a > 0 can be interpreted as the expected profit per click. It also indicates the expected profit for the agent, that is the advertiser. As far as the value hierarchy of slots is concerned, x 1 > x 2 > . . . > x s. The value of x s equals 0 for all s > S. Furthermore, Varian holds up two premises we know from Edelman et al. (2005). First, it is assumed that there are more agents respectively bidders than slots. Second, it is set like in GSP that the winner of a slot has to pay the second best bid to obtain the slot he or her aims at. Varian expresses the price to pay for the desired slot as

Abbildung in dieser Leseprobe nicht enthalten

The expected net profit can be regarded as

Abbildung in dieser Leseprobe nicht enthalten

(cf. Varian 2007, p. 1164)

According to Varian, the Nash equilibrium is achieved when each agent prefers his current own slot to “any other slot”. Varians mathematical definition where the price of the current slot is p t = b t + 1 is the following:

Abbildung in dieser Leseprobe nicht enthalten

(cf. Varian 2007, p. 1165)

Varian also identifies a subset of Nash equilibrium, that is Symmetric Nash Equilibrium. We find such kind of equilibrium if all players use the same strategy (cf. Slantchev 2005, p. 27). Varian’s definition is

Abbildung in dieser Leseprobe nicht enthalten

(cf. Varian 2007, p. 1165)

The remark for all t and s is decisive because it hints to the circumstance that all slots at any time are optimal. Varian shows that the inequalities are solvable (cf. Varian 2007, pp. 1165-1168). Henceforth, Varian checks lower and upper bounds concerning their attractiveness of bid changing. On the one hand, moving one position upwards can, but must not alter the profit. For moving upwards and at least keeping the profit, Varian has the formula

Abbildung in dieser Leseprobe nicht enthalten

The first part of the equation covers “worst case profit moving up”, the second one the “profit now” (cf. Varian 2007, p. 1168). On the other hand, reducing one’s bid can be advantageous but should not be so extensive that the agent below oneself wants to go up and take one➫s position. Varian gives the equation

Abbildung in dieser Leseprobe nicht enthalten

The first half of the equation renders “his profit now”, the second one “how much he would make in my position” (cf. Varian 2007, p. 1168). Finally, Varian turns to real auctions as empirical data. He finds out that in more than 2400 (2425) auctions, with at least 5 ads, satisfy the SNE inequalities with a small mean absolute error (cf. Varian 2007, p.1176).

Abbildung in dieser Leseprobe nicht enthalten

Figure 1: Distribution of mean absolute deviations (source: Varian (2007), p.1176).

3 Account three: Fukuda et al. (2010): “The- oretical and experimental investigations of the performance of keyword auction mech- anisms”

On the basic of the assumption of a “dominant strategy equilibrium” (cf. Fukuda et al., 2010, p. 2) in VCG, Fukuda et al. (2010) pose the thesis that the so-called “locally envy-free Nash Equlibrium” (LEFE), shows in VCG as well as in GSP a) to be efficient and b) to allow the coincidence of upper and lower bounds of the auctioneer➫s as well as advertisers➫ revenues in both mechanisms of advertising auctions. The authors claim to have confirmed their thesis both theoretically and experimentally. They point out three main res- ults. First, they state that all LEFNE in VCG are characterized by efficiency of advertising allocations. Second, the authors underline that in VCG, the dominant strategy equilibrium is identical with LEFNE generating minimal revenue among all LEFNE. Third, the maximum revenue of all LEFNE in VCG is equal to that in GSP (Fukuda et al., 2010, p. 3).

From these results, the authors draw the conclusion that VCG and GSP are similar in efficiency and profitability (cf. Fukuda et al., 2010, p. 3). By efficiency, the ranking of bids in correlation to their values is understood

(cf. Fukuda, 2010, p.15). Profitability concerns both the advertisers and the auctioneers.

The theoretical part of the confirmation of the thesis is mainly based on the propositions of Edelman et al. (2007) and Varian (2007). Among them count the propositions that the auctioneer➫s revenue in GSP is greater than or equal to VCG, that in GSP the LEFNE stands for efficiency, that the truth-telling equilibrium in VCG is a LEFNE, and that LEFNE in VCG is marked by over- bidding and submitting by clients except the bidder with the highest bid. In addition to formalizing the lower and upper bound in their own terminology, Fukuda et al. (2010) try to prove the above-mentioned propositions mathem- atically (cf. Fukuda et al. 2010, pp. 6-8).

Nevertheless, they inspire confidence in the experimental way of confirming their thesis. Because they see in experiments the advantage to check even mechanisms which do not exist in practice (which is the case for VCG) as well as to analyze the frequency of equilibria and efficiency (cf. Fukuda et al. 2010, p. 4). For these reasons, the authors undertook the first experiment on keyword auction (cf. Fukuda et al. 2010, p. 4).

The experimental design is based on two treatments for each mechanism, that are VCG and GSP. The goal is to achieve a high gain on bidding for advertising positions in correlation of certain values. Out of 90 undergrad students of a Japanese university who are extensively briefed and questioned afterwards to be sure they understand their task (cf. Fukuda et al. 2010, p. 10), nine groups of five players are formed who bid for five advertising positions over 100 rounds. The effort of the participants is rewarded in correlation to their success by an average payment of 25 US-dollars (cf. Fukuda et al. 2010, p. 11).

To the above-mentioned results, some further observations stemming from the experiment can be added. For instance, revenues for advertisers become stable after round 50. In this stadium, the average revenues lie between 20600 and 24800 yen, and they are closer to the lower than the upper bound both for advertisers and auctioneers (cf. Fukuda 2010 et al., pp. 12-15).

Abbildung in dieser Leseprobe nicht enthalten

Figure 2: Comparison of the average revenues of the auctioneer across periods

(source: Fukuda (2010), p. 12)

Abbildung in dieser Leseprobe nicht enthalten

Figure 3: Summary statitics of the bidding behavior per treatment and value

(source: Fukuda (2010), p. 19)

[...]