WWW 2008 / Poster Paper

April 21-25, 2008 · Beijing, China

GSP-ExR: GSP Protocol with an Exclusive Right for Keyword Auctions
Yuko Sakurai , Atsushi Iwasaki, Yasumasa Saito, and Makoto Yokoo
Graduate School of Information Science and Electrical Engineering Kyushu University, Fukuoka, 819-0395 Japan


{sakurai, saito}@agent.is.kyushu-u.ac.jp {iwasaki, yokoo}@is.kyushu-u.ac.jp ABSTRACT
We prop ose a keyword auction protocol called the Generalized Second Price with an Exclusive Right (GSP-ExR). In existing keyword auctions, the numb er of displayed advertisements is determined in advance. Thus, we consider adjusting the numb er of advertisements dynamically based on bids. In the GSP-ExR, the numb er of slots can b e either 1 or K . When K slots are displayed, the protocol is identical to the GSP. If the value p er click of the highest ranked bidder is large enough, then this bidder can exclusively display her advertisement by paying a premium. Thus, this pricing scheme is relatively simple and seller revenue is at least as good as the GSP. Also, in the GSP-ExR, the highest ranked bidder has no incentive to change the numb er of slots by over/under-bidding as long as she retains the top p osition. Categories and Sub ject Descriptors: I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence General Terms: Economics, Theory Keywords: Electronic Commerce, Mechanism design, Keyword auction, Web advertising our keyword auction setting, one serious limitation for using the VCG is that seller's revenue can b e lower than the GSP, which would discourage search engines from introducing the VCG. Also, bidders have difficulty understanding this protocol, since determining the VCG payment is also quite complicated and not intuitive. Thus, we develop a new auction protocol called the GSP with an Exclusive Right (GSP-ExR). The GSP-ExR can choose the optimal numb er of slots, either 1 or K . When K slots are displayed, the protocol is identical to the GSP. If the bid amount of the highest ranked bidder is large enough, then this bidder can exclusively display her advertisement by paying a premium. Therefore, this pricing scheme is relatively simple. Also, the amount of the premium is determined so that the highest ranked bidder has no incentive to change the numb er of slots by over/under-bidding. Our simulation results show that the GSP-ExR can improve b oth social surplus and seller's revenue. 1

2. MODEL
First, we illustrate a keyword auction model as follows. Assume a set of K slots on a sp ecific keyword and a set of bidders N = {1, 2, . . . , n} where n  K . In a keyword auction, each bidder submits a value p er click on the advertisement for a keyword. We assume the value p er click is indep endent of the rank of the slots. Formally, let vi denote bidder i's value p er click, which is a private valuation for bidder i. Search engine ranks the bidders in decreasing order based on the product of each bid and a click-through-rate (CTR). In advance the auctioneer determines each bidder's CTR, which is hidden from bidders. Many previously conducted studies on keyword auctions have assumed a separable CTR [1, 3, 5]. In this pap er, we also use this assumption. Let C T Ri (k, j ) denote the probability that bidder i's advertisement is clicked on the j -th highest slot among k slots. CTR is separable if we can represent it as follows: C T Ri (k, j ) = Ck,j qi . Here, qi is a factor related to the quality of bidder i's advertisement, estimated by the auctioneer. Ck,j dep ends only on p osition (k, j ), while qi is associated with bidder i. Naturally, we assume Ck,j b ecomes larger when the p osition j is closer to the top: k, j, Ck,j  Ck,j +1 . The numb er of slots can b e either 1 or K in the GSP-ExR. We assume that the following conditions hold: C1,1 > CK,1 and
1 Due to space limitation, we omit the simulation results in this pap er.

1.

INTRODUCTION

Recently, billions of dollars are sp ent on keyword auctions run by search engines such as Google and Yahoo! [2, 4, 5]. In current keyword auctions, the numb er of displayed advertisements is determined in advance. In this pap er, we consider adjusting the numb er of slots dynamically based on the bids. For example, if one bidder has a very high valuation p er click compared to other bidders, this bidder is allowed to exclusively display her advertisement as long as she is willing to pay a premium. In this case, we can simultaneously obtain b etter social surplus as well as b etter revenue for the seller (search engine). When we apply the GSP protocol which is actually used as a keyword auction protocol, the highest ranked bidder can increase her utility by over-bidding to obtain the exclusive right, since she does not need to pay the premium. On the other hand, we can apply the well-known VCG protocol, which is guaranteed to satisfy strategy-proofness and Pareto efficiency. However, in Y. Sakurai also works as a JSPS Research Fellow.
Copyright is held by the author/owner(s). WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04.

1089


WWW 2008 / Poster Paper
PK C1,1 < j =1 CK,j . Most existing keyword auctions introduce reservation price r , i.e., a bidder's bid is considered only when qi bi  r holds. We assume that a bidder has a quasi-linear utility, which is calculated by the difference b etween bidder i's true value p er click and her payment. Furthermore, we define social surplus P Sk when allocating k slots: Sk = k=1 Ck,j q(j ) b(j ) . Here, j we refer q(j ) b(j ) to the j -th highest product. The optimal numb er of slots to maximize the obtained social surplus can b e determined as follows: k = arg maxk{1,K } Sk .

April 21-25, 2008 · Beijing, China
Similarly, we can show that when the highest ranked bidder declares a true valuation and the total numb er of displayed slots is 1, then the bidder cannot increase her utility even if she changes from 1 to K slots. As a result, the highest ranked bidder cannot improve her utility by changing the numb er of displayed slots. In the GSP-ExR, we adjust the payment of the highest ranked bidder so that when S1 = SK , u(1) (1, 1) = u(1) (K, 1) holds, i.e., she is indifferent whether she gets the exclusive right. On the other hand, in the GSP, the highest ranked bidder can increase her utility by over-bidding to obtain the exclusive right, since she does not need to pay the premium. Note that when K slots are displayed, the highest ranked bidder might b e able to increase her utility by moving down on the rank of displayed p ositions. Such a manipulation is p ossible in the original GSP and the GSP-ExR inherits this problem. Example 1. Assume 2 slots and 2 bidders, 1 and 2. Suppose that each bidder has a value per click of v1 = 300 and v2 = 200. The advertisement quality's is identical, i.e., q1 = q2 = 1. A reservation price of r is set to 100. Suppose that the auctioneer determines Ck,j as fol lows: C1,1 = 0.5 and (C2,1 , C2,2 ) = (0.4, 0.2). Assume that bidder i submits her true value vi . We can calculate the social surplus of Sk as fol lows: S1 = 0.5×300 = 150 and S2 = 0.4×300+0.2×200 = 160. As a result, the optimal number of slots is k = 2. The top position goes to bidder 1 and she pays 200 per click and gets utility u1 (2, 1) = 0.4(300 - 200) = 40. On the other hand, if bidder 1 submits a bid of 1, 000, the total number of displayed slots becomes 1. Bidder 1 pays (C2,1 + C2,2 )b(2) /C1,1 = (0.4 + 0.2)200/0.5 = 240 and gets a utility of 0.5(300 - 240) = 30, which is smal ler than her original utility 40. Thus, bidder 1 cannot increase her utility by over-bidding to obtain the exclusive right.

3.

GSP WITH AN EXCLUSIVE RIGHT
· Each bidder submits a value p er click of bi . · The auctioneer sorts qi bi (that satisfies qi bi  r ) in decreasing order. Then the auctioneer determines the numb er of displayed slots (either 1 or K ) by comparing the obtained social surplus. ­ If SK  S1 , the optimal numb er of slots k b ecomes K and K slots are allocated. To calculate the payments, we apply the GSP payment. In the GSP, bidder i, who is allocated the j -th highest slot, will pay a price p er click of pi (K, j ), which is defined as follows: q(j +1) b(j +1) . (1) p i (K , j ) = qi ­ If S1 > SK , the optimal numb er of slots k b ecomes 1 and the highest ranked bidder has an exclusive right. Payment p(1) (1, 1) is calculated as follows: 1 (CK,1 q(2) b(2) p(1) (1, 1) = C1,1 q(1) +
K X j =2

We illustrate our new keyword auction protocol called the GSP-ExR. The GSP-ExR is defined as follows:

CK,j q(j ) b(j ) ).

(2)

4. CONCLUSIONS
We develop ed a new keyword auction protocol that dynamically adjust the numb er of slots, while in existing keyword auction protocols, the numb er of slots is determined in advance. Our newly develop ed GSP-ExR protocol, a modification of the GSP, simultaneously improves the obtained social surplus and the search engine revenue. One limitation of the GSP-ExR is that the numb er of slots is limited to 1 or K . Our future works include developing strategy-proof keyword auction protocols with simple payment calculation methods, in which the auctioneer can select the numb er of slots more flexibly.

Theorem 1. In the GSP-ExR, the highest ranked bidder has no incentive to change the number of displayed advertisements from either 1 or K as long as she retains the top position. Proof. For simplicity, assume that the quality of each bidder i's advertisement is identical, i.e., i, qi = 1. First, assume that when the highest ranked bidder declares a true valuation and the numb er of displayed slots is K , i.e., SK  S1 . Then, we show that the highest bidder cannot increase her utility by over-bidding, i.e., her utility when she gets the exclusive right (denoted as u(1) (1, 1)) is smaller than (or at most equal to) the utility when K slots are displayed (denoted as u(1) (K, 1)). u(1) (1, 1) = C1,1 (v1 -  CK,1 v1 +
K X 1 (CK,1 b(2) + C K,j b ( j ) ) ) C1,1 j =2 K X j =2

5. REFERENCES
[1] M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, A. R. Karlin, C. Mathieu, and M. Schwarz. Greedy bidding strategies for keyword auctions. In Proc. of ACM EC'07, pages 262­271, 2007. [2] B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97:242­259, 2007. [3] S. Lahaie and D. M. Penno ck. Revenue analysis of a family of ranking rules for keyword auctions. In Proc. of ACM EC'07, pages 50­56, 2007. [4] R. Matthew, R. Dominowska ,and R. Rob ert. Predicting clicks: Estimating the Click-Through Rate for New Ads. In Proc. of WWW2007, pages 521­529, 2007. [5] H. R. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163­1178, 2007.

C K,j b ( j )
K X j =2

-(CK,1 b(2) +

C K,j b ( j ) ) ) (  S K  S 1 )

= CK,1 (v1 - b(2) ) = u(1) (K, 1).

1090