Optimal Auction Design with User Coupons in Advertising Systems

1 Introduction

Auction design has become one of the central topics at the intersection of economics and computer science. Various auctions are proposed in the literature over the years [Cramton et al., 2004; Aggarwal et al., 2006; Varian, 2007; Edelman et al., 2007], including the celebrated VickreyClarke-Groves (VCG) auction [Clarke, 1971; Vickrey, 1961; Groves, 1973] and Myerson's optimal auction [Myerson, 1981]. Both auctions are truthful, where bidders are incentivized to submit their true valuations as their bids. The appeal of the VCG auction is this mechanism maximizes social welfare, allocating the item to the bidder with the highest valuation, while Myerson's optimal auction maximizes the seller's revenue for a single-item scenario.

⇤To whom correspondence should be addressed.

One of the most successful applications of auction theory is online advertising, as online advertising is a major source of revenue for many Internet companies, e.g., Meta, Google and TikTok. According to the statistics by Statista 1 , 627 billion U.S. dollars were spent in 2023 on digital advertisements, and the industrial is still rapidly growing.

When applied to online advertising systems, besides the advertisers' bids, the standard auction design theory also needs to consider the relevance scores of the ads. Such relevance scores are usually captured by the click-through rates (CTRs) and the conversion rates (CVRs). Standard auction design theory implicitly assumes that the CTR and CVR are known when the user and the ad are given, and thus treat them as constants during the auction process.

However, in this paper, we consider a setting where the platform can offer coupons to the users when displaying the ads. The users can buy the corresponding advertiser's products or services at a lower price by using the coupons. Thus the coupons can increase both the CTR and the CVR of the ads. In such a setting, we can no longer view the CTRs and CVRs as constants, as offering different coupons can lead to different CTR and CVR improvements. Therefore, we study the problem of how to jointly design the coupon strategy, the allocation rule, and the payment rule to maximize the platform's revenue.

Coupons offer a financial discount off the regular price for users when purchasing a product. In economic studies, different prices may result in different demands, and such a relation is often described by a so-called "demand curve" [Mas-Colell et al., 1995]. The fundamental economic principle known as the law of demand intuitively states that as the price of a good falls, the demand rises [Nicholson and Snyder, 2012]. Therefore, offering coupons to the users increases the buyers' willingness to buy and therefore increases the CTRs and CVRs of the ads. From this point of view, coupons can be viewed as a way to balance the price and demand for advertisers. Most advertisers lack the ability to draw the entire demand curve for their products, while the platform can predict the CTR and CVR changes accurately with its massive amount of data. By leveraging such additional knowledge, the platform can design pricing strategies to better serve the interests of the advertisers.

1 https://www.statista.com/topics/990/global-advertisingmarket/#topicOverview

In our paper, we analyze the auction design problem with user coupons theoretically and conduct experiments to evaluate its performance. It is worth mentioning that, the first online ad auction mechanism that consider user coupons is proposed by Ni et al. [2023]. They empirically show that such mechanisms indeed improve the revenue of the platform. However, they consider the auto-bidding setting and their mechanism is not incentive compatible when the advertisers have quasi-linear utilities.

We summarize our contributions in this paper as follows:

• We model the auction design problem with user coupons mathematically and characterize the set of incentive compatible and individually rational mechanisms.
• Based on the above result, we formulate the revenuemaximization problem as a mathematical program, and provide an optimal mechanism.
• We conduct extensive experiments with both synthetic and industrial data sets to demonstrate the performance of our mechanism.

1.1 RelatedWork

Our paper is clearly related to the optimal mechanism design [Myerson, 1981; Maskin et al., 1981; Pavlov, 2011; Wang and Tang, 2014]. Another line of work aims to improve revenue for commonly used mechanisms in practice, such as the second-price auction, the generalized secondprice auction, and the VCG auction. These methods include optimizing reserve prices [Hartline and Roughgarden, 2009; Balseiro et al., 2021], boosts [Golrezaei et al., 2021; Deng et al., 2021], offering coupon to advertisers [Shen et al., 2020; Shen et al., 2021].

Recently, Ni et al. [2023] proposed a new mechanism that offers coupons to users to increase the platform's revenue. However, they study the problem in an auto-bidding setting, and in their model, the cost of offering coupons is covered by the advertisers, making their mechanism nontruthful for advertisers with quasi-linear utilities.

Another relevant topic is the effect of offering coupons on consumer behaviors [Gopalakrishnan and Park, 2021; Ali and Muhammad, 2021; Li et al., 2020; Albert and Goldenberg, 2022]. They show that coupons in general have positive effects on consumers' purchasing behavior, and therefore increase sales volumes.

2 Preliminaries

In this section, we describe how we mathematically model the problem of designing auction mechanisms with user coupons and introduce some basic definitions into our setting.

2.1 Model

An online advertising platform (e.g., a search engine or a short-form video platform) sells an ad slot to n advertisers, denoted by [n] := ¶1↪ 2↪ · · · ↪ n♦. Each advertiser i 2 [n] has a valuation vi, which is drawn from a cumulative distribution function Fi(vi). We assume that Fi(vi) is differentiable with density function fi(vi) and that fi(vi) is bounded and supported on V = [0↪ v], i.e., 0 < fi(vi) < 1↪ 8vi 2 V. The valuation can be interpreted as the advertiser's willingness to pay for one click. When a user enters a query into a search engine or scrolls down on a short-form video app, an auction is triggered. In the standard auction setting, the advertisers first submit their bids to the platform. Denote the bid of advertiser i by bi 2 B, which may be different from the true valuation vi. The platform determines who wins the auctions and how much the winner should pay, and then shows the winner's ad to the user. During the auction process, the platform usually also takes into account the click-through rate (CTR) and the conversion rate (CVR) of each ad, where the CTR is the probability of the user clicking on an ad and the CVR is the probability of buying the advertiser's product conditioned on clicking the ad.

In this paper, we consider a setting where the platform also offers a coupon to the user when displaying the ad. Though offered by the platform, the coupon can be used when the user buys the advertiser's products. Such a coupon can clearly make the ad and the advertiser's product more attractive to the user and thus increase both the CTR and the CVR of the ad. Therefore, different from the standard auction setting, besides the winner and the payment, the platform also needs to determine a coupon ci 2 C = [0↪ c], for each advertiser i 2 [n]. We use the function hi := C 7! (0↪ 1] to represent the CTR of advertiser i's ad when coupon ci is offered to the user. In particular, hi(0) represents the CTR without a coupon. An ad is usually more attractive to a user if a larger coupon is offered. Thus we assume hi(ci) is a strictly increasing function. Similarly, we use ri := C 7! [0↪ 1] to represent the CVR of advertiser i's ad when coupon ci is offered, which is also assumed to be strictly increasing. For simplicity, throughout the paper, we also make the assumption that both hi(ci) and ri(ci) are differentiable. If the user buys the advertiser's product, the payment of the user is the price of the product less the coupon ci, and the platform also pays ci to the advertiser (directly or indirectly through the user) to ensure that the total payment is still the price of the product. Therefore, the expected cost of the coupon can be written as hi(ci)ri(ci)ci.

In our setting, apart from an allocation rule and a payment rule, a mechanism should also include a coupon function. In this paper, we allow the coupon ci to depend on the bid bi submitted by advertiser i. Formally, we have the following definition.

Definition 1 (Mechanism). A mechanism M is a tuple (φ↪ x↪ p), where:

• φ = (φ1↪ φ2 · · · ↪ φn) is the coupon function, where φi : B 7! C maps the bid bi of advertiser i to the coupon ci to be offered to the user;
• x = (x1↪ x2↪ · · · ↪ xn) is the allocation rule, where xi : Bn 7! [0↪ 1] takes the bid profile as input and outputs

the probability of advertiser i winning the auction;

• p = (p1↪ p2↪ · · · ↪ pn) is the payment function, where pi : Bn 7! R+ takes the bid profile as input and outputs the payment of advertiser i to the platform.

Let v = (v1↪ · · · ↪ vn) be the valuation profile of all advertisers and v-i = (v1↪ · · · ↪ vi-1↪ vi+1↪ · · · ↪ vn) the valuation profile of all advertisers except advertiser i. We assume that the valuation of the n advertisers are independent random variables. Thus, the joint density function f := V n 7! R+ for the vector v = (v1↪ · · · ↪ vn) of individual valuations is

Also, we define f-i := V n-1 7! R+ as the join density function of vector v-i, f-i(v-i) = Qj2[n]∩i fj(vj)▷

Similarly, let b = (b1↪ · · · ↪ bn) and b-i = (b1↪ · · · ↪ bi-1↪ bi+1↪ · · · ↪ bn) denote all advertisers' bids profile and all advertisers' bids profile except advertiser i.

The auction procedure is as follows:

All advertisers simultaneously report their bid bi to the platform. After receiving the bids, the platform calculates the coupon ci for each advertiser i 2 [n] according to the coupon function φi(bi). The platform then computes the CTR hi and the CVR ri of each ad i based on the coupon ci. Next, the platform determines the winner and the payment according to the allocation rule x and the payment rule p. Finally, the platform displays the ad and offers the coupon to the user.

In this paper, we consider cost-per-click auctions, i.e., an advertiser only pays the platform when their ad is clicked by the user. Suppose all advertisers have quasi-linear utilities. Formally, if the bid profile is b, in mechanism M, the expected utility of advertiser i is

Since the platform needs to provide coupons to the users, the revenue of the platform can be represented as the payments from the advertisers minus the cost of providing the coupon:

Naturally, a mechanism should satisfy the following constraint as the platform only has a single slot for sale.

2.2 Direct Feasible AuctionMechanisms

A mechanism induces a Bayesian game among the advertisers. In such a game, an ad advertiser may have incentives to place a bid different from their true valuation if the bid gives them a better utility. There is a special class of mechanisms where the advertisers' utilities are maximized by submitting their true valuations. Such mechanisms are called truthful mechanisms. Before formally defining truthfulness, we first introduce some useful notations. Let Ui(M↪ vi) be the expected utility of advertiser i with valuation vi, i.e.,

For ease of presentation, we also define

to be the interim allocation rule and the interim payment rule, which are the expected winning probability and the expected payment of advertiser i when the valuation is vi.

Definition 2 (Incentive Compatibility (IC)). A mechanism is incentive compatible or truthful, if all advertisers reporting bi = vi form a Bayes-Nash equilibrium, i.e.,

According to the celebrated revelation principle [Myerson, 1979; Gibbard, 1973], we can, without loss of generality, restrict our attention to truthful mechanisms.

Another important property is individual rationality, which ensures the participation of the advertisers.

Definition 3 (Individual Rationality (IR)). A mechanism is individually rational if participating in the auction always leads to a non-negative expected utility for all advertisers, i.e., for advertiser i with valuation vi, we have

In this paper, we consider the set of feasible mechanisms.

Definition 4. A mechanism M = (φ↪ x↪ p) is feasible if it does not oversell, and satisfies both the IC and IR properties, i.e., M satisfies Equation (1), (2) and (3).

The following lemma characterizes feasible mechanisms.

Lemma 1. A mechanism (φ↪ x↪ p) is feasible, if and only if for any valuation profile v, the following conditions hold:

1. Function hi(φi(vi))Xi(vi) is monotone non-decreasing with respect to vi.
2. The expected payment of advertiser i satisfies

1. The allocation rule satisfies

According to Equation (4) in Lemma 1, to ensure incentive compatibility, the advertiser's payment should take into consideration the CTR's increase resulted from the coupons.

However, it may be difficult to jointly design the coupon function φi(vi) and the allocation rule Xi(vi) to ensure that the function hi(φi(vi))Xi(vi) is monotone non-decreasing, especially when the CTR function hi(·) is represented as a neural network model in most industrial applications. The following corollary gives a sufficient condition in which the coupon function and the allocation rule can be decoupled.

Corollary 1. The mechanismM= (φ↪ x↪ p) is feasible if the following conditions hold:

1. Function φi(vi) and Xi(vi) are both monotone nondecreasing with respect to vi;
2. Equation (4) and (5) are satisfied.

In the standard auction design setting with no coupons, it is well-known that the monotonicity of Xi(vi) together already implies the incentive compatibility property. The above corollary shows that any such mechanism is also incentivecompatible in our setting, as long as the coupon function is monotone. Therefore, applying any monotone coupon function to an existing truthful mechanism does not violate the IC property, making such coupon designs easier to implement.

2.3 Revenue MaximizationMechanism

In this section, we characterize revenue maximization mechanisms in our setting. Before stating our results, we define a different version of the virtual value function here.

Definition 5. For each advertiser i, define

The standard definition of the virtual value function is:

Our definition is different in that we also include the coupon function. The standard definition of the virtual value function is irrelevant to the mechanism, while here we need to take into consideration the coupon function, which is part of the the mechanism. Using the standard definition, our virtual value function can be written as:

The following Lemma 2 is similar to Myerson lemma [Myerson, 1981] and is helpful for designing optimal auctions.

Lemma 2. The revenue of any feasible mechanism M = (φ↪ x↪ p) can be written as:

3 The Optimal Mechanism

According to Lemma 2, to maximize revenue, the platform should design the coupon function φi(vi) and the allocation rule xi(v) to maximize Equation (6). We choose to design the two functions separately in order to make the task of optimizing Equation (6) easier, and then show that although separately designed, the two functions together form a feasible mechanism.

We first design the coupon function φi(vi) to maximize each Ji(vi). For ease of presentation, we define the function

Clearly, by plugging in any coupon function ci = φi(vi), we get 'i(φi(vi)↪ vi) = Ji(vi).

View vi as a parameter and let correspondence Φi(vi) be the set of maximizers of function 'i(ci↪ vi).

For any vi, function 'i(ci↪ vi) is a clearly continuous and bounded function of ci, thus Φi(vi) is always a non-empty set according to the extreme value theorem. Now we define a special coupon function 2 as

It is clear that such a coupon function maximizes 'i(ci↪ vi) in a point-wise way, i.e., for any vi, φi(vi) optimizes 'i(ci↪ vi). Thus the virtual value function Ji(vi) is also maximized with such a choice:

Before we discuss our optimal mechanism, we first introduce the increasing difference property of a function and present some related results that will be useful later.

Definition 6 (Increasing Difference). A function g : A⇥B 7! R has increasing differences in (a↪ b), if for all a0 ≥ a and b0 ≥ b,

If we view b as a parameter of function g, then the difference of the function values at a0 and a is a function of b. Increasing difference means the difference function is an increasing function of the parameter b. The increasing difference also implies the difference function is an increasing function of the parameter a.

Note that the property of increasing difference is ubiquitous in game theory. It is applied to cutoff strategies in Bayesian games [Akerlof, 1970] and more recently in supermodular games [Levin, 2003]. The following lemma gives a sufficient condition for the virtual value function Ji(vi) to be non-decreasing.

Lemma 3. If function 'i(ci↪ vi) has increasing differences in (ci↪ vi), then Ji(vi) is monotone non-decreasing with respect to vi.

Now we introduce a technical condition called regularity [Myerson, 1981], and discuss two cases based on whether a problem instance is regular or not.

2 A more careful definition would be φi(vi) = supci2Φi(vi) ci. However, according to Berge's maximum theorem [Berge, 1963; Ok, 2007], The set Φi(vi) is non-empty and compact. Therefore, supci2Φi(vi) ci is attainable in C and sup can be replaced by max.

Definition 7 (Regularity). A problem instance is regular, if for all advertisers, function i(vi) is monotone nondecreasing.

The above regularity condition is a standard definition in the literature. Here, we identify an equivalent condition.

Lemma 4. A problem instance is regular, if and only if function 'i(ci↪ vi) has increasing differences for all i.

3.1 The Regular Case

Now we design the allocation rule xi(v) in the regular case. It is clear that to maximize Equation (6), the platform should allocate the slot to the advertiser with the highest Ji(vi) among those with Ji(vi) ≥ 0. We show that this design, together with the choice of φi(vi), forms a feasible mechanism. Let M(v) = ¶k ♣ Jk(vk) ≥ Jk0(vk0)↪ 8k0 2 [n]♦ be the set of advertisers with the highest virtual values. We present our optimal mechanism for the regular case in theorem 1.

Theorem1. If a problem instance is regular, then the following mechanism M = (φ↪ x↪ p) is an optimal mechanism:

φi(vi) =max¶Φi(vi)♦↪

where Φi(vi) is defined in Equation (8).

Proof. By setting φi(vi) = max¶Φi(vi)♦, the function 'i(ci↪ vi) is maximized pointwisely. Thus, the function Ji(vi) is maximized. And by setting xi(v) = 1 for the advertiser i with the highest and non-negative Ji(vi), the platform's expected revenue (Equation (6)) is maximized. Therefore, the mechanism defined in Theorem 1 is revenue-optimal.

Nowwe show that it is also feasible. In particular, we show that it satisfies the conditions in Corollary 1. According to Topkis's Theorem [Topkis, 1978], φi(vi) is a monotone nondecreasing function. Since the problem instance is regular, we have that Ji(vi) is monotone non-decreasing. It follow that, given any v-i, the allocation rule xi(vi↪ v-i) is a monotone non-decreasing function of vi. Taking expectation over v-i, we have that Xi(vi) is also monotone non-decreasing. Therefore, the first condition of Corollary 1.

As for the second condition, notice that Equation (5) clearly holds, and Equation (4) follows from taking the expectation over v-i on both sides of Equation (12).

3.2 The Irregular Case

Without the regularity condition, the function Ji(vi) is not a monotone non-decreasing function. This means the allocation rule defined in Equation (11) is also not monotone nondecreasing. As a result, the expected allocation Xi(vi) may also not be monotone, leading to possible violations of the first condition in Lemma 1. To address this issue, we apply the so-called ironing trick to the function i(vi) to ensure that the ironed function i(vi) is monotone. Therefore, the corresponding function 'i(ci↪ vi) has increasing differences. We show that replacing 'i(ci↪ vi) by 'i(ci↪ vi) yields a feasible and optimal mechanism. The following definition of ironing is a standard technique in the literature.

Definition 8 (Ironing [Myerson, 1981]). Let qi = Fi(vi) 2 [0↪ 1] and define ki(qi) = i (F -1 i (qi)). The ironing procedure is as follows.

1. Let Ki(qi) be the integral of ki(qi):
2. Define Li : [0↪ 1] 7!R be the "convex hull" of the graph of function Ki(qi):

where q1 ↪ q2 ↪ γ 2 [0↪ 1] and γq1 + (1 - γ)q2 = qi;

1. Let `i(qi) be the derivative of Li(qi):

1. Obtain i(vi) by variable substitution:

Based on the ironed i(vi), we can define:

After the ironing procedure, the function i(vi) becomes a monotone non-decreasing function. The monotonicity of both hi(ci) and i(vi) implies the ironed function 'i(ci↪ vi) has increasing difference. Before we present our main result, we prove a lemma that is helpful when deriving the optimal mechanism in the irregular case.

Lemma 5. For any feasible mechanism (φ↪ x↪ p), the platform's revenue can be written as

Directly optimizing Equation (6) may result in an infeasible mechanism. Lemme 5 states that we can optimize Equation (13) instead.

Theorem 2. In an irregular problem instance, define

Then the following mechanism M = (φ↪ x↪ p) is an optimal mechanism:

Note that for the regular case, Theorem 2 is the same as Theorem 1. Theorem 2 can be applied to any general case.

4 Properties of the Optimal Mechanism

In this section, we derive properties of the optimal mechanism, and try to understand the benefits brought by including user coupons in our setting. We first identify a simple case where the platform should not offer a coupon.

Lemma 6. The optimal mechanism does not offer coupons for advertiser i if i(vi)  0.

Proof. Recall that in the optimal mechanism, the coupon function ¯ φi(vi) maximizes ¯ 'i(ci↪ vi) = hi(ci)[i(vi) - ri(ci)ci] = hi(ci)i(vi) - hi(ci)ri(ci)ci for any given vi. Clearly, the second term hi(ci)ri(ci)ci is a non-decreasing function. If i(vi)  0, the first term become non-increasing, making ¯ 'i(ci↪ vi) a non-increasing function of ci. This means setting ci = 0 maximizes ¯ 'i(ci↪ vi). Thus, we have ¯ φi(vi) = 0, i.e., the optimal mechanism offers no coupon in this case.

The following result shows that if the optimal mechanism offers a coupon, then the marginal cost of the coupon should equal to the marginal gain in revenue.

Lemma 7. If vi satisfies ¯ φi(vi) > 0, then we have:

Proof. The coupon function ¯ φi(vi) should maximize ¯ 'i(ci↪ vi) in the optimal mechanism. If ¯ φi(vi) > 0, according to first-order condition, we have:

If advertiser i's ad is displayed, the probability that the user buys the advertiser's product is hi(ci)ri(ci). So hi(ci)ri(ci)ci is the expected cost of the platform due to providing the coupon. In the standard auction setting, when bidding vi, i(vi) can be regarded as the contribution of advertiser i to the platform's revenue for one click, and the perimpression contribution is then i(vi)hi(0). However, in our setting, the platform's revenue also comes from the CTR increase for offering coupons to the users, i.e., i(vi)hi(ci). Lemma 7 shows that the optimal coupon should be such that the marginal coupon cost is exactly covered by the marginal revenue gain.

5 Experiments

We tested our proposed mechanism by conducting a series of experiments, using both synthetic and industrial data. We compared it with three baseline methods: Myerson Auction, Auction with Constant Coupon Value (CCV), and Auction with Randomized Coupon Value (RCV). The Myerson Auction doesn't offer coupons, while CCV and RCV offer coupons to users. The coupon values in CCV are constant, while in RCV they're randomized. The key difference between CCV, RCV, and our method is the coupon function. In our method, coupon values depend on the advertisers' bids, unlike in CCV and RCV. However, all three methods meet the conditions of Lemma 1, so the optimal bidding strategy is to bid truthfully.

5.1 Synthetic Data

We generate a data set using a method similar to the one in [Ni et al., 2023]. We consider a pre-defined coupon set that contains only several possible coupon values, and we generate the corresponding CTRs and CVRs. We suppose there are n = 8 advertisers and that they participate in m = 100↪ 000 auctions. In each auction, each advertiser's values are drawn from the same log-normal distribution (lnvi ⇠ N(3↪ 1)). For each advertiser i, the CTR without coupon hi(0) is drawn from the uniform distribution U(0▷005↪ 0▷5), and the CVR without coupon ri(0) is also drawn from the same uniform distribution. The coupon set contains only 4 different coupons: C = ¶0↪ 2↪ 4↪ 8♦. For each advertiser i, we let hi(2) = 1▷1 · hi(0)↪ hi(4) = 1▷2 · hi(0)↪ hi(8) = 1▷3 · hi(0), and ri(2) = 1▷1 · ri(0)↪ ri(4) = 1▷2 · ri(0)↪ ri(8) = 1▷3 · ri(0). We use 80↪ 000 auctions to select the best coupon strategies for the second and third baseline algorithms. We use the other 20↪ 000 auctions to verify the experimental results between our method and the baseline methods.

Method

We simulate each auction via the following procedures in our methods.

1. For each advertiser i, we enumerate all coupons and compute each advertiser's best coupon using our mechanism.
2. We rank advertisers according to the virtual values defined in Definition 5.
3. The advertiser with the highest virtual value wins the auction and his payment is computed via payment rule (Equation (12)) in Theorem 1.

Results

We compare the performance of our mechanism with the other three baseline auctions mentioned above. 3

We first verify that in this experiment environment, both φi(vi) and Ji(vi) are monotone non-decreasing with respect to vi for each i. Since all advertisers' values, CTRs, and CVRs are drawn from i.i.d. distributions, we only need to verify the monotonicity of a single advertiser. We sample one CTR and one CVR for one advertiser and use different valuations to compute the corresponding coupon and virtual value according to the coupon function in Theorem 1 and virtual value function defined in Definiton 5 for each valuation. The results are shown in Figure 1(a) and 1(b). The monotonicity of both φi(vi) and Ji(vi) indicates that we do not need to apply the ironing technique to guarantee the IC condition.

3 We choose not to compare our mechanism against [Ni et al., 2023] since their mechanism is not truthful in our setting, and it is not clear how the advertisers would bid under their mechanism.

Then we simulate the 20,000 auctions and compute the average revenue, social welfare, and the advertisers' total utilities. The results are shown in Table 1. Compared to the Myerson auction without offering coupons, the auction with constant coupon values, and the auction with randomized coupon values, our mechanism increases revenue by about 19.76%, 1.9%, and 6.4% respectively. Also, our mechanism increases the advertisers' total utility by 32.58%, 10.47% and 15.52% respectively, and the social welfare by 26%, 6.2%, and 10.96% respectively. According to the synthetic datagenerating method, the advertisers and the users are all symmetric. Thus, the constant coupon value strategy is better than the randomized coupon value strategy. These results show that our mechanism leads to a win-win situation by increasing social welfare and revenue simultaneously. Our mechanism is also clearly beneficial to the users as they can buy the products or services provided by the advertisers with a lower price.

5.2 Industrial Data

We also conduct experiments using an industrial data set. The industrial data we used comes from Kuaishou, a major short-form video and live-streaming platform. It is worth mentioning that the platform charges the advertisers in a perimpression fashion. Thus the CTR value is unimportant. In this case, we re-define the CVR ri(·) to be the probability of the user buying a product or service from the advertiser, conditioned on seeing the ad. We also need to re-define the virtual value function as follows:

Our mechanism can also be easily modified accordingly, thus we omit the detailed definition here.

We select 1,000 ads to conduct the experiment. In this experiment, we trained the CVR prediction model instead of randomly sampling them from certain distributions. To collect enough data for the training, we offer different coupons for these ads in 14 days and sampled 300,000 data records. Our data contains numerous features for users, products, and advertisements, respectively.

We sample 100 advertisers and 100,000 users to conduct the auction process. Then, we randomly choose 80,000 users to select the best coupon strategies for the second and third baseline algorithms. We use the rest to verify the experimental results between our method and the baseline methods.

Method

We conduct the experiment using the following procedure:

1. We train a CVR model using the collected data. The input of the model consists of all the features mentioned above, as well as the coupon value in order to predict the CVR for different coupons.
2. For each auction, we sample a user from the set of users and predict each advertiser's CVR using our CVR model. Then we discrete the coupon space for each advertiser, compute the φi(ci↪ vi) for each possible coupon ci, and choose the maximum one as the optimal coupon.
3. We rank advertisers according to the modified virtual value function (Equation (16)) and allocate the slot to the advertiser with the highest virtual value and compute his payment via the payment rule (Equation (12)).

Results

The results are shown in Table 2, where we normalize the results using the advertiser's utility in Myerson Auction. Compared with the other three baseline methods, our mechanism increases revenue by 28%, 27%, and 16% respectively. Our mechanism increases the advertisers' total utility by 313%, 91%, and 43% respectively. Our mechanism increases social welfare by 67%, 43%, and 24% respectively.

6 Conclusion

In this paper, we consider the auction design problem of online ad auction with user coupons. Our mechanism space contains that of the standard auction setting as a special subset. Thus, the optimal mechanism in our setting can achieve a higher revenue than the celebrated Myerson auction. We characterize the set of IR and IC mechanisms and also provide the optimal mechanism in closed form. Such a mechanism can be viewed as optimizing the product price for the advertisers to balance price and demand by using additional knowledge possessed by the platform. Our experiments show that our mechanism leads to a win-win situation for the platform, the advertisers, and the users.

Acknowledgements

We thank all the anonymous reviewers for their helpful comments. This work was supported in part by the National Natural Science Foundation of China (No. 62106273 & No. 72192805), the Fundamental Research Funds for the Central Universities, the Research Funds of Renmin University of China (22XNKJ16), and Kuaishou Technology Co., Ltd.