# coupon_design_in_advertising_systems__63165d51.pdf

Coupon Design in Advertising Systems

Weiran Shen,1 Pingzhong Tang, 2 Xun Wang, 2 Yadong Xu, 2 Xiwang Yang 3

1 Renmin University of China 2 Tsinghua University 3 Byte Dance shenweiran@ruc.edu.cn, kenshinping@gmail.com, wxhelloworld@outlook.com, xuyd17@mails.tsinghua.edu.cn,yangxiwang@bytedance.com

Online platforms sell advertisements via auctions (e.g., VCG and GSP auction) and revenue maximization is one of the most important tasks for them. Many revenue increment methods are proposed, like reserve pricing, boosting, coupons and so on. The novelty of coupons rests on the fact that coupons are optional for advertisers while the others are compulsory. Recent studies on coupons have limited applications in advertising systems because they only focus on second price auctions and do not consider the combination with other methods. In this work, we study the coupon design problem for revenue maximization in the widely used VCG auction. Firstly, we examine the bidder strategies in the VCG auction with coupons. Secondly, we cast the coupon design problem into a learning framework and propose corresponding algorithms using the properties of VCG auction. Then we further study how to combine coupons with reserve pricing in our framework. Finally, extensive experiments are conducted to demonstrate the effectiveness of our algorithms based on both synthetic data and industrial data.

Introduction Online advertising has been one of the most important industry on the Internet. In the United States, its revenue has grown by 15.9 percent in 2019 compared to 2018, surpassing 124$ billion. 1 Advertising has become one of the key revenue sources for many Internet companies, such as Google, Facebook, Byte Dance. For example, more than 83.8 percent of Google s revenue comes from online advertising. And the market still shows no signs of slowing down. There are various types of online advertising, for example, social media advertising (e.g., Instagram and Facebook), paid search advertising (e.g., Google and Baidu), and native advertising (e.g., Buzz Feed and Tiktok), and so on. These advertisements are usually sold via auction mechanisms. The mechanisms determine which advertisements will be presented and how much the corresponding advertisers need to pay. There are two widely used auctions, i.e., the GSP auction (Edelman, Ostrovsky, and Schwarz 2007) (generalized second price) which is used by Google and Baidu, and the VCG auction (Vickrey 1961; Clarke 1971; Groves et al. 1973) which

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved. 1https://www.statista.com/statistics/183816/us-onlineadvertising-revenue-since-2000/

is used by Facebook and Bytedance. The difference between them is that the VCG auction is truthful, i.e., advertisers submit bids that truthfully reveal their valuations, while the GSP auction is not. However, it has been proved that the GSP auction has a Nash equilibrium whose outcome is equivalent to that of the VCG auction. Therefore, in this paper, we study how to maximize the revenue in the VCG auction. Coupons have been widely studied in economics (Bester and Petrakis 1996; Moraga-Gonz alez and Petrakis 1999; Kang et al. 2006; Board and Skrzypacz 2016). The most common arguments developed by economists to explain the use of coupons are twofold: 1) Coupons allow for price discrimination. 2) Coupons allow for peak-load pricing (Mckenzie 2008). In this work, coupons play the role of price discrimination. The intuition of revenue increment is that low-valued advertisers would spontaneously bid higher if they are provided with coupons, which in turn forces the high-valued advertisers to pay more when they win based on the payment rule of the VCG auction. In fact, many methods can be used to increase revenue, such as reserve price (Hartline and Roughgarden 2009), boosting (Golrezaei et al. 2017), squashing (Lahaie and Pennock 2007a), anchoring (Lahaie and Pennock 2007b). Coupons are signiﬁcantly different from them. As for coupons, advertisers hold the right to decide whether to use them. However, they cannot refuse to use the other methods, e.g., advertisers always want to remove the reserve price but they can not. In fact, sometimes reserve prices may have a negative effect on revenue (Ostrovsky and Schwarz 2011). Higher reserve prices make the auction less attractive which results in fewer participated advertisers. In this work, we generalize (Shen et al. 2020b) to the VCG auction, including the combination with reserve pricing. The intuition is that the VCG auction (with heterogeneous slots) can be decomposed into some tractable sub-VCG auctions (with homogeneous slots). Our contributions can be summarized as follows: 1) We generalize the application of coupons for revenue maximization in advertising systems to more realistic scenarios (i.e., VCG auctions). 2) We propose algorithms for coupon optimization using the properties of the VCG auction, along with the combination with reserve pricing. 3) Based on both synthetic data and industrial data, extensive experiments are conducted to demonstrate the effectiveness of our algorithms.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Related Works Our work is related to the revenue-maximizing mechanism design. Myerson (1981) studies the optimal auction where advertisers should be ranked in descending order of their virtual values. If nobody has positive virtual values, the item would not be sold to anyone. However, Roughgarden and Schrijvers (2016) argus that this setting relies heavily on the exact estimation of the advertisers value distribution and can be sensitive to estimation errors. Thus, simpler mechanisms are applied in industry, e.g., VCG and GSP auction. Many methods have been proposed to increase revenue in these auctions. Reserve pricing is one of the most widely studied methods: Hartline and Roughgarden (2009) presents how to use a reserve-price-based VCG auction to approximate the optimal one. Jin et al. (2019) proves a tight approximation ratio for anonymous reserve prices. Another method is boosting (Golrezaei et al. 2017) where the seller assigns a boost value to each advertiser which can transform his regular bid into a boosted one. Besides, squashing (Lahaie and Pennock 2007a) and anchoring (Lahaie and Pennock 2007b) are also widely used methods in industry (Chawla, Fu, and Karlin 2014; Huang, Mansour, and Roughgarden 2015; Tang and Wang 2016; Tang and Sandholm 2011). Our work is also related to automated mechanism design. Conitzer and Sandholm (2002) introduces the automated mechanism design approach, where the mechanism is computationally created for the speciﬁc problem instance at hand. Learning theory tools such as pseudo-dimension have been used to prove strong guarantees in auction settings (Morgenstern and Roughgarden 2015, 2016). In a similar direction, bounds on the sample complexity have also been developed (Hsu et al. 2016). Mohri and Medina (2014) uses DC programming to learn anonymous reserve price for the second-price auction. Duetting et al. (2019) uses deep learning to design revenue-maximizing mechanisms and deals with the incentive constraint via regret network. Shen, Tang, and Zuo (2019) also handles the same problem but can always return exactly incentive compatible mechanisms. Recently, Tang (2017) uses reinforcement learning to design and optimize mechanisms in dynamic industrial environments and has achieved success in industry (Cai et al. 2018a,b; Shen et al. 2020a).

Preliminaries In this section, the setting of VCG auction with coupons in advertising systems will be introduced ﬁrst. Then the formal problem of learning to design coupons will be deﬁned.

VCG Auction with Coupons in Advertising Systems There are n bidders [n] = {1, 2, . . . , n} and m slots (usually, n m). We will refer to ad i as the advertisement submitted by bidder i. Each bidder can occupy at most 1 slot and each slot can be allocated to at most 1 bidder. Let vi be the private value which quantiﬁes the value of a click for bidder i. And vi is drawn from a publicly known distribution Fi. For convenience, let v = (v1, . . . , vn) denote the value proﬁle, and let v i = (v1, . . . , vi 1, vi+1, . . . , vn) denote the

value proﬁle of all bidders except bidder i. Similarly, we can deﬁne the bid proﬁle b and b i. We only use αj [0, 1] to denote the click-through-rate of ad i when it is allocated to slot j as (Edelman, Ostrovsky, and Schwarz 2007) do, which implies that the number of times a particular slot is clicked does not depend on the ad in this slot. The reason is that the click-through-rate can be decomposed into position effect and ad effect while the ad effect can be taken into account in the private valuation. Besides, αj αj holds when j < j . In response to the bid proﬁle, VCG auction determines how to allocate each bidder and how much each bidder has to pay according to some allocation rule and payment rule. To be speciﬁc, the allocation rule is a function π that maps the bid proﬁle b to an n-dimensional vector indicating the quantity of clicks allocated to each bidder, i.e., π : Rn 7 [0, 1]n; The payment rule is a function p : Rn 7 Rn + that maps the bid proﬁle b to an n-dimensional non-negative vector specifying the payment for each bidder. For simplicity, we use π(b) and π, p(b) and p interchangeably. If bidder i is allocated to slot j, then πi = αj, and if bidder i does not win the auction, then πi = 0. These rules are speciﬁed as: Allocation rule: π(b) arg maxπ Pn i=1 π ibi. Payment rule: pi(b) = maxπ P i =i π i bi P i =i πi bi .

Coupons work as follows. Before submitting bids, each bidder i will be informed that he will be provided with a constant coupon ci 0. This coupon can get ci off the payment when he wins. Hence bidders would change their regular bids depending on their values and coupons, i.e., bi = bi(vi; ci). Therefore, the allocation rule and payment rule of VCG auction with coupons would be:

π(b) arg max π

pi(b) = max π X

i =i π i bi X

i =i πi bi πici. (1)

The utility of bidder i is ui(b) = πivi pi, and the revenue of platform would be:

Rev(v, c) =

i=1 pi. (2)

In what follows, let (i) denote the order of bidders satisfying if i < i , then [b(i) > b(i )] [(b(i) > b(i )) (c(i) c(i ))], that is, (i) denotes the bidder with the i-th highest bid (if there are more than one, then choose the bidder with the least coupon).

Learning Formulation There are two sets of data the training data and the testing data, containing features and bids. Both sets of data are generated by VCG auction without coupons. And our goal is to train a model which can provide coupons for bidders in each auction and maximize the revenue for platform. Since VCG auction is a truthful mechanism, in these sets of data, we can regard bids as bidders values. Let us deﬁne the problem formally. We consider a generic feature space X with the label space B = Rn + consisting

of the value proﬁle v. We regard (xt, vt) as a data instance where xt, vt denote the feature vector and value proﬁle in auction t, respectively. The hypothesis function h : X Rn + is used to set coupons ct = h(xt). Thus, the objective is to select a hypothesis function h out of some hypothesis set H to minimize the corresponding empirical loss:

t=1 Rev(vt; h(xt)). (3)

where S = ((x1, v1), . . . , (x T , v T )). Let αt j, pt i and πt i denote the corresponding notations in auction t. The goal is to learn the predictor which can work for any advertiser if corresponding features can be provided. For the sake of description, we use a new hypothesis function hi to set the coupon for bidder i as ct i = hi(xt i), where xt i denotes the feature for bidder i in auction t. For convenience, in what follows we will omit the superscript t when there is no confusion. It is worth noting that all proofs can be found in supplementary materials due to limited space.

Problem Analysis In this section, we will introduce the property of coupons and show the difﬁculty of coupon optimization ﬁrst. Then, the comparison with related work would be presented.

Proposition 1. In VCG auction with coupons, the dominant strategy of bidder i is using coupon ci and bidding vi + ci.

Proposition 1 denotes the dominant strategy of bidders in VCG auction with coupons. Therefore, we can use vi +ci to denote the bid of bidder i when he is provided with coupon ci in experiments. Thus we can deﬁne the revenue of VCG auction with coupons as Equation (4).

Rev(v; c) =

i=j αib(i+1)

i=j+1 αib(i) αjc(j)

h j (αj αj+1)(v(j+1) + c(j+1)) αjc(j) i

Deﬁnition 1 (No-feature case). In this case, features are not considered, and the coupon optimization problem is to minimize the following empirical loss:

t=1 Rev(vt; c), (5)

where c is an n dimensional vector specifying coupons which need to be optimized.

Proposition 2. In the no-feature case, the optimization of coupons in VCG auction (i.e., Equation (5)) is NP-hard.

Proposition 2 points out coupon optimization is hard, so we use the coordination descent method to optimize coupons. In this method, instead of optimizing coupons simultaneously, we optimize one of them while ﬁxing the others at each time step.

Comparison with Related Work As proposition 1 demonstrated, although coupons are optional for advertisers, they still accept and use all coupons in equilibrium. We will compare the difference between coupons and other involuntary discount mechanism, like boosting (Golrezaei et al. 2017) and bidding credits in squashing (Lahaie and Pennock 2007a). Boosting and bidding credits both multiply the submitted bids with a factor, i.e., ai bi. As for boosting, there is no restriction on ai. While for bidding credits, ai is between 0 and 1. Then in the VCG auction, there are two differences. When 0 ai < 1, advertiser i prefer not to accept boosting or bidding credits. However, as for coupons, advertisers dominant strategy would always be accepting them. Coupons can increase the revenue in some cases where boosting can not. For example, consider one slot and two bidders whose values are 0 and 1. Then, boosting can not increase the revenue since ai multiplies 0 still equals 0. While for coupons, this would not be a problem. Comparing with the second-price setting, several nontrivial technical issues are raised in the VCG setting. For example, Shen et al. (2020b) relies heavily on the fact that given value proﬁle v and coupons proﬁle c i, Rev(v; c) (as a function of ci) has at most one discontinuous point. Hence the surrogate loss function can be decomposed as a difference of two convex functions and DC programming can be applied. However, in the VCG setting, the revenue function is more complicated as Proposition 3 denotes. Proposition 3. In VCG auction with coupons, given value proﬁle v and the coupon proﬁle c i, Rev(v; c) (as a function of ci) is not continuous, and is neither convex nor concave. Actually, there can be m discontinuous points. We use Example 1 to demonstrate Proposition 3. As illustrated in Figure 1, Rev(v; c) (as a function of ci) is a piecewise function. There can be multiple discontinuous points. They divide the function into multiple line segments, which can have different slopes. Example 1. Let n = 6, m = 4, v = (5, 4, 3, 2, 1, 0) and α = (1.0, 0.4, 0.3, 0.1). When c 6 = 0, the value of revenue with respect to c6 is demonstrated in Figure 1.

Figure 1: The value of revenue w.r.t. c6

Furthermore, when reserve price is taken into consideration, the revenue function can be much more complicated, making the coupon optimization harder.

In this section, we will introduce a special case of VCG auction with coupons. As Proposition 4 denotes, we can extend the technique in (Mohri and Medina 2014; Shen et al. 2020b) to tackle the special case.

Deﬁnition 2 (Special case). In this case of VCG auction with coupons, the slots are homogeneous, i.e., α1 = α2 = = αm = α.

Let subscript (j) only represent the order of bids. We use b i,(j) = v i,(j) + c i,(j) to denote the j-th highest bid in bid proﬁle b i, that is, if j < l, then the order [b i,(j) > b i,(l)] [(b i,(j) = b i,(l)) (c i,(j) c i,(l))] is ensured. Let L(y; v, c i) = Rev(v; (y, c i)) be the negative number of the revenue as a function of ci = y, which can be rewritten as:

L(y; v, c i)

mαb i,(m+1) + α Pm j=1 c i,(j), y b i,(m+1) vi [ mαb i,(m) + α Pm j=1 c i,(j) α(c i,(m) y)+], y = b i,(m) vi αy mαb i,(m) + α Pm 1 j=1 c i,(j), y > b i,(m) vi mαy mαvi + α Pm j=1 c i,(j), otherwise (6)

Here x+ means max {x, 0}. As Proposition 4 states, L(y; v, c i) has at most one discontinuous point, which is a reduction of Proposition 3.

Proposition 4. In the special case, given the value proﬁle v and the coupon proﬁle c i, L(y; v, c i) has at most one discontinuous point at y = b i,(m) vi. When y < b i,(m) vi, L(y; v, c i) is non-increasing and concave. When y > b i,(m) vi, L(y; v, c i) is an increasing linear function. What s more, for all the cases, L(y; v, c i) achieves its minimum at y = (b i,(m) vi)+.

However, L(y; v, c i) is still not a good choice for optimization since L(y; v, c i) is neither convex nor concave, but quasi-convex in fact. And a sum of quasi-convex functions does not maintain the quasi-convex property and can have many local minima (Mohri and Medina 2014). We extend the technique in (Mohri and Medina 2014; Shen et al. 2020b) to tackle the special case:

1. We smooth Equation (6) to derive a surrogate loss function Lγ(y; v, c i), which is training-friendly and has a good approximation of Equation (6) theoretically.

2. We decompose Lγ as the difference of two convex functions, i.e., Lγ = g1 g2. Then we apply DC programming and coordination descent method to optimize the coupons.

Due to limited space, detailed formulas of Lγ and algorithms are presented in the supplementary materials.

Solution for the General Case In this section, we will discuss how to extend the aforementioned special case into the general case, i.e., the clickthrough-rates of different slots are also different. We decompose each VCG auction into m sub-VCG auctions which belong to the special case, and complete the coupon optimization based on the decomposition. Then we study how to combine coupons with reserve prices in our framework.

Constructing m sub-VCG Auctions

Algorithm 1 Constructing m sub-VCG auctions

1: Initialize Q = . 2: for j = 1 to m do 3: Let dj = αj αj+1, and construct a sub-VCG auction Aj as: there are n bidders, j slots, and each slot has the same click-through-rates dj. 4: Q = Q {Aj}. 5: end for

The decomposition process is demonstrated in Algorithm 1. There are m steps. At the j-th step, we construct the j-th sub-VCG auction, where there are j slots and n bidders, and all slots share the same click-through-rates dj. Thus, the j-th sub-VCG auction belongs to the special case. Furthermore, Theorem 1 denotes that given value proﬁle v and coupon proﬁle c, the results of these m sub-VCG auctions are equivalent to those results of the original VCG auction for both platform (in terms of revenue) and each bidder (in terms of allocation and payment).

Theorem 1. Given value proﬁle v and coupon proﬁle c, the original VCG auction and these sub-VCG auctions would receive the same bid proﬁle b. Besides, for bidder i, his total payment and allocation (the sum of obtained click-throughrates) within these sub-VCG auctions are equivalent to those in the original VCG auction.

As a result, we present Theorem 2 to denote that by computing the optimal coupon for bidder i in sub-VCG auctions, the optimal coupon for bidder i in the original VCG auction can also be obtained.

Theorem 2. Given v and c i, the optimal coupon c i for bidder i in the original VCG auction belongs to the following sets {0} {(b i,(j) vi)+}j [m],

where (b i,(j) vi)+ is the optimal coupon for bidder i in the j-th sub-VCG auction Aj.

Combine with the coordinate descent method, we propose Algorithm 2 to optimize coupon for the no-feature case. Here λ in line 7 denotes the learning rate, ϵ and Kout in line 10 are used to determine when the algorithm terminates.

Algorithm Design for the General Case The hypothesis set H consists of linear functions whose unbiased term is bounded, i.e., H = {h : xi 7 ω xi + c0| ω } and c0 is a positive constant. Besides,

Algorithm 2 Algorithm for the no-feature case

1: Run Algorithm 1 to construct m T sub-VCG auctions. 2: Initialize c 0 and kout = 0, and generate a random permutation of 1 to n as N. 3: repeat 4: Set cp c and kout kout + 1. 5: for i = N1 to Nn do 6: Fix c i, calculate the optimal coupon via evaluating Equation (5) at the following O(m T) points and returning the best y .

{0} {(bt i,(j) vt i)+}t [T ] j [m]

7: Use λy + (1 λ)ci to update ci. 8: end for 9: Generate a new random permutation N if LS(c) LS(cp). 10: until c cp ϵ or kout = Kout

is chosen to satisfy c0 max xi , which guarantees that coupons are non-negative because

ω xi + c0 c0 |ω xi| c0 ω xi c0 max xi 0.

It is worth noting that max xi can be bounded once we normalize the feature space. Note that Theorem 1 states that the results of the m sub VCG auctions are equivalent to those of the original VCG auction, which holds over the T VCG auctions, thus the empirical surrogate loss can be written as

j=1 Lγ(ωi xt i + c0; vt, ct i, At j), (7)

where At j denotes the j-th constructed sub-VCG auction of the t-th VCG auction by executing Algorithm 1, and the corresponding click-through-rate is dt j = αt j αt j+1. It is worth noting that At j belongs to the special case. Follow the work in (Mohri and Medina 2014; Shen et al. 2020b), we also use the technique DC programming for optimization. Therefore, we complete the algorithm design for the general case as Algorithm 3. Here DCA(ωk 1 i ) (line 8) means to solve the following optimization problem (Equation (8)),

min ||ωi|| Λ,s

j=1 st j δG2(ωk 1 i ) ωi s.t. j [m]

ct i = ωi xt i + c0, t [T] st j/dt j ct i jbt i,(j) + Pj 1 l=1 ct i,(l), t Cj 1 Cj 3 Cj 4 st j/dt j jct i jvt i + f t,j i,1 , t Cj 2 st j/dt j (1 + et,j i γdt,j i,1 )(ct i dt,j i,1) jbt i,(j) + f t,j i,1 , t Cj 2

st j/dt j ( et,j i γdt,j i,1 j)(ct i dt,j i,1) jbt i,(j) + f t,j i,2 , t Cj 3

st j/dt j φt,j i αt (ct i dt,j i,1) jbt i,(j) + f t,j i,2 , t Cj 4 (8)

Algorithm 3 Algorithm for the general case

1: Run Algorithm 1 to construct m T sub-VCG auctions. 2: Initialize ω 0 and kout = 0, and generate a random permutation of 1 to n as N. 3: repeat 4: Set ωp ω and kout kout + 1. 5: for i = N1 to Nn do 6: Use ω to initialize ω0 i , and calculate coupons for bidders except i via ct j = ω xt j + c0. 7: for k = 1 to K do 8: ωk i DCA(ωk 1 i ). 9: end for 10: Use λωK i + (1 λ)ω to update ω. 11: end for 12: Set Ψ = {0.1 (10 / ω )0.1j|j = 0, 1, . . . , 10}, compute η arg minη Ψ LS(η ω) and use η ω to update ω. 13: Generate a new random permutation N if LS(ω) LS(ωp). 14: until ω ωp ϵ or kout = Kout

where G2(ωk 1 i ) = P t,j g2(ωk 1 i xt i + c0; vt, ct i, At j) and δG2(ωk 1 i ) denotes an arbitrary element of the subgradient G2(ωk 1 i ). Besides, Cj k, dt,j i,1, dt,j i,2, et,j i , f t,j i,1 , f t,j i,2 and φt,j i are similar to the deﬁnitions in the special case with just a substitution from m to j as Equation (9).

dt,j i,1 = bt i,(j) vt i, dt,j i,2 = bt i,(j+1) vt i, et,j i = vt i,(j) vt i,

f t,j i,1 = Xj

l=1 ct i,(l), f t,j i,2 = Xj 1

l=1 ct i,(l) + dt,j i,1,

φt,j i = dt j/γdt,j i,1 (j(bt i,(j+1) bt i,(j)) + et,j i ),

Cj 1 = {t|vt i bt i,(j)}, Cj 2 = {t|vt i < bt i,(j), vt i vt i,(j)},

Cj 3 = {t|vt i < bt i,(j), vt i > vt i,(j), (1 γ)dt,j i,1 dt,j i,2},

Cj 4 = {t|vt i < bt i,(j), vt i > vt i,(j), (1 γ)dt,j i,1 < dt,j i,2}. (9)

Combination with Reserve Price We combine reserve prices with coupons to further improve the revenue by eliminating the negative payments caused by large coupons. Let ri + ci denote the eager reserve price for bidder i where ri is independent of ci, the eager reserve price works as below. 1. The auction ﬁrst eliminates the bidder who does not clear his reserve price, then the remaining bidders form the candidate set S = {i|bi ri + ci}. 2. Bidders in the candidate set S are allocated according to the allocation rule of VCG auction. 3. The payment rule can be modiﬁed as follows. If bidder i gets the j-th slot, then he need to pay

k=j (αk αk+1) max{b(k+1), ri + ci} αjci, (10)

where b(k+1) = 0 holds for k = |S|, . . . , m if |S| m.

It is worth noting that the payment (Equation (10)) must be non-negative. Furthermore, we use Proposition 5 to show the dominant strategy of bidders in VCG auction with coupons when we combine reserve prices. Thus we can still use vi + ci to denote the bid of bidder i when he is provided with coupon ci in experiments.

Proposition 5. In VCG auction with coupons {ci} and reserve prices {ri + ci}, the dominant strategy of bidder i is using coupon ci and bidding vi + ci.

Note that ri is independent of ci, we can naturally integrate the reserve prices into the framework of VCG auction with coupons once we optimize the coupon for each bidder. For example, if we simply select ri = 0 for bidder i, then the reserve price for bidder i is ci. Bidder i will always clear his reserve price, but his payment can never be negative.

In this section, we ﬁrst verify the validity of the design of surrogate loss function by comparing it with the real loss function. Then we examine the impact of hyper-parameters of our algorithms and verify the properties of coupons. Finally, we conduct some experiments to show the effectiveness of our algorithms against state-of-the-art algorithms.

Data Description

We use both synthetic data and industrial data to demonstrate the results of our experiments. As for synthetic data, we choose three different types of distribution to sample the value data, i.e., the uniform distribution, the Pareto distribution and the lognormal distribution. To be speciﬁc, we sample T numbers from a standard distribution with ﬁxed parameters for each bidder (i.e., X U(0, 1) or ln X N(0, 1)), and then each bidder is associated with a random scale size to multiply these T numbers as his values in T auctions. As for industrial data, it comes from one of the biggest short-form mobile video community in the world. We randomly extract 177 million auctions from the log. Each advertiser instance contains many features, including labels, industry category, pricing type (i.e., cost per click, cost per mille or cost per action), budget and so on, and the number of features for each bidder in each auction is 178. Besides, all the bids are transformed into the interval (0, 10), and features are normalized to satisfy xi 10. We choose c0 = 10 so that = 1.

Surrogate Loss vs. Real Loss

We use synthetic data to show the difference between Lγ and L. For a target bidder, we randomly select related T = 50 value proﬁles and generate others coupons. Without loss of generality, the click-through-rates are all 1. As Figure 2(a) show, Lγ S is a lower bound for LS, and the difference between two functions is relatively small. Besides, Figure 2(b) denotes that we can approach the real loss function as we select sufﬁciently small γ. Similar results are also shown on the industrial data (see in supplementary materials). Although small γ is necessary to guarantee the precision accu-

racy, too small γ could make the surrogate loss function tend to be discontinuous. γ is chosen to be 0.1 in the experiments.

Figure 2: Plot of the difference between LS and Lγ S on the synthetic data. (a) LS and Lγ S as the function of coupon y when γ = 0.09, where x-axis denotes the coupon y while y-axis denotes the value of loss. (b) average difference between LS and Lγ S as the function of γ, where x-axis denotes the choice of γ while y-axis denotes the difference.

Demonstration of Training Phase

We implement the algorithms for coupon optimization, where Algorithm 3 is implemented using Gurobi 9.0 (Gurobi Optimization 2021). We ﬁrst examine the impact of learning rate λ in terms of revenue. The results are shown as Figure 3(a), where Alg-2 and Alg-3 represent Algorithm 2 and 3 respectively and λ is selected from {0.01, 0.05, 0.1, 0.5}. We can see that Alg-3 always yields better performance than Alg-2 since it can utilize features. Algorithms may not converge within 20 iterations when λ is small, i.e., λ 0.1 in Alg-2 and λ = 0.01 in Alg-3. As for Alg-2, larger λ can achieve better performance, thus we choose λ = 0.5 in Alg-2 to guarantee convergence and achieve better performance. While for Alg-3, although larger λ can have higher revenue in some iterations, it is unstable during the training phase. Hence λ is set to 0.05 in Alg-3 to maintain robustness and obtain comparable performance. Besides, in the remaining experiments, we use ϵ = 0.001 and Kout = 20 in both algorithms. We further verify the property that the payment can be negative for some bidder when the coupon provided for him is too large. We calculate the ratio of negative payments after each iterations, i.e., #{(i,t)|pt i 0} m T . As shown in Figure 3(b),

Figure 3: Plot of training process. (a) revenue curve, where x-axis denotes the iteration while y-axis denotes the corresponding revenue gain. (b) ratio curve, where x-axis denotes the iteration while y-axis denotes the corresponding ratio of negative payments.

the payment of some bidder can be negative, but the ratio of negative payments is small (< 0.5%). Besides, the ratio increases to improve the revenue in the beginning, but then tends to decrease. What s more, the ﬁnal ratio of negative payments in Alg-3 is smaller than that in Alg-2.

Revenue Comparison We conduct some experiments to show the effectiveness of coupons and our algorithms. The performance metric is ρa = Reva Rev0

Rev0 100%, where Reva represents the revenue achieved through the corresponding algorithm a and Rev0 denotes the revenue obtained without these methods in VCG auction. The following methods are compared: (ARP) This method sets anonymous reserve price in VCG auction (Mohri and Medina 2014). (SRP) This method sets bidder-speciﬁc reserve price in VCG auction via maximizing vi(1 Fi(vi)) (Hartline and Roughgarden 2009). (BVCG) This method assigns a boost value for each bidder in VCG auction (Golrezaei et al. 2017). (Alg-2a/Alg-3a) This method combines Algorithm 2 or 3 with reserve prices ri + ci where ri = 0. (Alg-2b/Alg-3b) This method combines Algorithm 2 or 3 with reserve prices ri + ci where ri belongs to arg maxvi vi(1 Fi(vi)). Note that (Mohri and Medina 2014; Golrezaei et al. 2017) only study the second price setting, we extend their methods

to VCG auction as ARP and BVCG (details are provided in supplementary materials). As for synthetic data, given the type of distribution and the number of slots m, we randomly sample the value data and divide the whole dataset into training data and testing data, with training data makes up about 70%. Then we run different algorithms on the training data and calculate ρa on the testing data. This procedure is repeated for 20 times and the results when m = 4 are summarized as Table 1 shows.

Method Uniform Pareto Lognormal ARP 2.58(1.05) 8.88(2.38) 2.92(3.24) SRP 12.16(5.98) 9.80(3.36) 21.86(9.44) BVCG 7.51(3.32) 1.83(1.27) 6.94(2.80) Alg-2 13.91(5.77) 3.18(2.57) 10.36(4.77) Alg-2a 13.94(5.75) 3.28(2.57) 10.41(4.75) Alg-2b 15.75(6.07) 9.94(3.36) 22.54(9.15)

Table 1: Performance (i.e. ρa) on synthetic data when m = 4. Numbers in the brackets denote standard deviations.

We can draw the following conclusions from Table 1. Firstly, coupons work well on these synthetic datasets as Alg-2 can increase the revenue by a large margin. Secondly, Alg-2 always outperforms ARP, SRP and BVCG on the datasets sampled from uniform distribution. This is because coupons can approximate the optimal auction in (Myerson 1981) via producing similar allocation (see in supplementary materials). For other distributions, Alg-2 always has better performance than BVCG. Thirdly, results show the effectiveness of combining reserve prices with coupons. Alg-2(a) outperforms Alg-2 by eliminating the negative payments and Alg-2(b) performs the best among above methods in all datasets by setting bidder-speciﬁc reserve prices. Similar conclusions can also be seen in the results when m = 4, we demonstrate them in the supplementary materials. Considering the limited space, we omit the experiment results on industrial data here and refer readers to the full version of our paper.

In this paper, we study how to design coupons in VCG auction via a learning framework. Firstly, we derive the dominant strategy of each bidder and characterize the coupons. Then we start from a special case where slots are homogeneous and extend this special case to the general one via auction decomposition and complete the algorithm design. We also combine coupons with reserve prices in our framework. Finally, extensive experiments are conducted to demonstrate the effectiveness of the algorithms.

Acknowledgments

This work is is supported by Beijing Academy of Artiﬁcial Intelligence (BAAI), Science and Technology Innovation 2030 New Generation Artiﬁcial Intelligence Major Project No. 2018AAA0100904, 2018AAA0101103.

Bester, H.; and Petrakis, E. 1996. Coupons and oligopolistic price discrimination. International Journal of Industrial Organization 14(2): 227 242.

Board, S.; and Skrzypacz, A. 2016. Revenue management with forward-looking buyers. Journal of Political Economy 124(4): 1046 1087.

Cai, Q.; Filos-Ratsikas, A.; Tang, P.; and Zhang, Y. 2018a. Reinforcement Mechanism Design for e-commerce. In Champin, P.; Gandon, F. L.; Lalmas, M.; and Ipeirotis, P. G., eds., Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, 1339 1348. ACM. doi:10.1145/3178876.3186039. URL https://doi.org/10.1145/3178876.3186039.

Cai, Q.; Filos-Ratsikas, A.; Tang, P.; and Zhang, Y. 2018b. Reinforcement Mechanism Design for Fraudulent Behaviour in e-Commerce. In Mc Ilraith, S. A.; and Weinberger, K. Q., eds., Proceedings of the Thirty Second AAAI Conference on Artiﬁcial Intelligence, (AAAI18), the 30th innovative Applications of Artiﬁcial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artiﬁcial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, 957 964. AAAI Press. URL https://www.aaai.org/ocs/index.php/ AAAI/AAAI18/paper/view/16650.

Chawla, S.; Fu, H.; and Karlin, A. R. 2014. Approximate revenue maximization in interdependent value settings. In Babaioff, M.; Conitzer, V.; and Easley, D. A., eds., ACM Conference on Economics and Computation, EC 14, Stanford , CA, USA, June 8-12, 2014, 277 294. ACM. doi: 10.1145/2600057.2602858. URL https://doi.org/10.1145/ 2600057.2602858.

Clarke, E. H. 1971. Multipart pricing of public goods. Public choice 17 33.

Conitzer, V.; and Sandholm, T. 2002. Complexity of Mechanism Design. In Darwiche, A.; and Friedman, N., eds., UAI 02, Proceedings of the 18th Conference in Uncertainty in Artiﬁcial Intelligence, University of Alberta, Edmonton, Alberta, Canada, August 1-4, 2002, 103 110. Morgan Kaufmann. URL https://dslpitt.org/uai/display Article Details.jsp?mmnu=1\ &smnu=2\&article\ id=850\&proceeding\ id=18.

Duetting, P.; Feng, Z.; Narasimhan, H.; Parkes, D. C.; and Ravindranath, S. S. 2019. Optimal Auctions through Deep Learning. In Chaudhuri, K.; and Salakhutdinov, R., eds., Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, 1706 1715. PMLR. URL http: //proceedings.mlr.press/v97/duetting19a.html.

Edelman, B.; Ostrovsky, M.; and 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.

Golrezaei, N.; Lin, M.; Mirrokni, V.; and Nazerzadeh, H. 2017. Boosted Second Price Auctions: Revenue Optimization for Heterogeneous Bidders. SSRN 3016465 .

Groves, T.; et al. 1973. Incentives in teams. Econometrica 41(4): 617 631.

Gurobi Optimization, L. 2021. Gurobi Optimizer Reference Manual. URL http://www.gurobi.com. Accessed Mar. 1, 2021.

Hartline, J. D.; and Roughgarden, T. 2009. Simple versus optimal mechanisms. In Chuang, J.; Fortnow, L.; and Pu, P., eds., Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6 10, 2009, 225 234. ACM. doi:10.1145/1566374.1566407. URL https://doi.org/10.1145/1566374.1566407.

Hsu, J.; Morgenstern, J.; Rogers, R. M.; Roth, A.; and Vohra, R. 2016. Do prices coordinate markets? In Wichs, D.; and Mansour, Y., eds., Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 440 453. ACM. doi:10.1145/2897518.2897559. URL https://doi.org/ 10.1145/2897518.2897559.

Huang, Z.; Mansour, Y.; and Roughgarden, T. 2015. Making the Most of Your Samples. In Roughgarden, T.; Feldman, M.; and Schwarz, M., eds., Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 15, Portland, OR, USA, June 15-19, 2015, 45 60. ACM. doi: 10.1145/2764468.2764475. URL https://doi.org/10.1145/ 2764468.2764475.

Jin, Y.; Lu, P.; Qi, Q.; Tang, Z. G.; and Xiao, T. 2019. Tight approximation ratio of anonymous pricing. In Charikar, M.; and Cohen, E., eds., Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, 674 685. ACM. doi: 10.1145/3313276.3316331. URL https://doi.org/10.1145/ 3313276.3316331.

Kang, H.; Hahn, M.; Fortin, D. R.; Hyun, Y. J.; and Eom, Y. 2006. Effects of perceived behavioral control on the consumer usage intention of e-coupons. Psychology & Marketing 23(10): 841 864.

Lahaie, S.; and Pennock, D. M. 2007a. Revenue analysis of a family of ranking rules for keyword auctions. In Mac Kie-Mason, J. K.; Parkes, D. C.; and Resnick, P., eds., Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, 50 56. ACM. doi:10.1145/1250910.1250918. URL https: //doi.org/10.1145/1250910.1250918.

Lahaie, S.; and Pennock, D. M. 2007b. Revenue analysis of a family of ranking rules for keyword auctions. In Mac Kie-Mason, J. K.; Parkes, D. C.; and Resnick, P., eds., Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, 50 56. ACM. doi:10.1145/1250910.1250918. URL https: //doi.org/10.1145/1250910.1250918.

Mckenzie, R. D. 2008. Why Popcorn Costs So Much at the Movies: And Other Pricing Puzzles. Springer New York.

Mohri, M.; and Medina, A. M. 2014. Learning Theory and Algorithms for revenue optimization in second price auctions with reserve. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, 262 270. JMLR.org. URL http://proceedings.mlr.press/v32/mohri14.html.

Moraga-Gonz alez, J. L.; and Petrakis, E. 1999. Coupon advertising under imperfect price information. Journal of Economics & Management Strategy 8(4): 523 544.

Morgenstern, J.; and Roughgarden, T. 2015. On the Pseudo Dimension of Nearly Optimal Auctions. In Cortes, C.; Lawrence, N. D.; Lee, D. D.; Sugiyama, M.; and Garnett, R., eds., Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, 136 144. URL http://papers.nips.cc/paper/5766on-the-pseudo-dimension-of-nearly-optimal-auctions.

Morgenstern, J.; and Roughgarden, T. 2016. Learning Simple Auctions. In Feldman, V.; Rakhlin, A.; and Shamir, O., eds., Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, 1298 1318. JMLR.org. URL http://proceedings.mlr.press/ v49/morgenstern16.html.

Myerson, R. B. 1981. Optimal Auction Design. Math. Oper. Res. 6(1): 58 73. doi:10.1287/moor.6.1.58. URL https:// doi.org/10.1287/moor.6.1.58.

Ostrovsky, M.; and Schwarz, M. 2011. Reserve prices in internet advertising auctions: a ﬁeld experiment. In Shoham, Y.; Chen, Y.; and Roughgarden, T., eds., Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011, 59 60. ACM. doi:10.1145/ 1993574.1993585. URL https://doi.org/10.1145/1993574. 1993585.

Roughgarden, T.; and Schrijvers, O. 2016. Ironing in the Dark. In Conitzer, V.; Bergemann, D.; and Chen, Y., eds., Proceedings of the 2016 ACM Conference on Economics and Computation, EC 16, Maastricht, The Netherlands, July 24-28, 2016, 1 18. ACM. doi:10.1145/2940716. 2940723. URL https://doi.org/10.1145/2940716.2940723.

Shen, W.; Peng, B.; Liu, H.; Zhang, M.; Qian, R.; Hong, Y.; Guo, Z.; Ding, Z.; Lu, P.; and Tang, P. 2020a. Reinforcement Mechanism Design: With Applications to Dynamic Pricing in Sponsored Search Auctions. In The Thirty Fourth AAAI Conference on Artiﬁcial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artiﬁcial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artiﬁcial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 2236 2243. AAAI Press. URL https://aaai.org/ojs/ index.php/AAAI/article/view/5600.

Shen, W.; Tang, P.; Wang, X.; Xu, Y.; and Yang, X. 2020b. Learning to Design Coupons in Online Advertising Markets. In Seghrouchni, A. E. F.; Sukthankar, G.; An, B.;

and Yorke-Smith, N., eds., Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 20, Auckland, New Zealand, May 9-13, 2020, 1242 1250. International Foundation for Autonomous Agents and Multiagent Systems. URL https://dl.acm.org/ doi/abs/10.5555/3398761.3398905. Shen, W.; Tang, P.; and Zuo, S. 2019. Automated Mechanism Design via Neural Networks. In Elkind, E.; Veloso, M.; Agmon, N.; and Taylor, M. E., eds., Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, AAMAS 19, Montreal, QC, Canada, May 13-17, 2019, 215 223. International Foundation for Autonomous Agents and Multiagent Systems. URL http: //dl.acm.org/citation.cfm?id=3331696. Tang, P. 2017. Reinforcement mechanism design. In Sierra, C., ed., Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 5146 5150. ijcai.org. doi:10.24963/ijcai.2017/739. URL https: //doi.org/10.24963/ijcai.2017/739. Tang, P.; and Sandholm, T. 2011. Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization. In Walsh, T., ed., IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, 379 385. IJCAI/AAAI. doi:10.5591/978-1-57735516-8/IJCAI11-072. URL https://doi.org/10.5591/978-157735-516-8/IJCAI11-072. Tang, P.; and Wang, Z. 2016. Optimal Auctions for Negatively Correlated Items. In Conitzer, V.; Bergemann, D.; and Chen, Y., eds., Proceedings of the 2016 ACM Conference on Economics and Computation, EC 16, Maastricht, The Netherlands, July 24-28, 2016, 103 120. ACM. doi: 10.1145/2940716.2940766. URL https://doi.org/10.1145/ 2940716.2940766. Vickrey, W. 1961. Counterspeculation, auctions, and competitive sealed tenders. The Journal of ﬁnance 16(1): 8 37.