# preferred_deals_in_general_environments__61cbd43e.pdf

Preferred Deals in General Environments

Yuan Deng1 , S ebastien Lahaie2 and Vahab Mirrokni2

1Duke University 2Google Research ericdy@cs.duke.edu, {slahaie, mirrokni}@google.com

A preferred deal is a special contract for selling impressions of display ad inventory. By accepting a deal, a buyer agrees to buy a minimum amount of impressions at a ﬁxed price per impression, and is granted priority access to the impressions before they are sent to an open auction on an ad exchange. We consider the problem of designing preferred deals (inventory, price, quantity) in the presence of general convex constraints, including budget constraints, and propose an approximation algorithm to maximize the revenue obtained from the deals. We then evaluate our algorithm using auction data from a major advertising exchange and our empirical results show that the algorithm achieves around 95% of the optimal revenue.

1 Introduction Display advertising is the practice of placing text, banner, or video ads on publisher websites for the purpose of raising brand awareness via ad views, known as impressions. The display advertising industry is a major source of revenue for online publishers and Internet companies. In 2017, the revenue of this market exceeded $27.5 billion for the U.S. alone [Pw C, 2018]. Traditionally, display advertising has been mainly sold via reservation contracts or real-time bidding. In a reservation contract, the publisher buys a ﬁxed amount of impressions on a segment of a publisher s inventory, over some amount of time (e.g., one month), and the publisher commits to sending the advertiser the impressions [Feige et al., 2008]. In real-time bidding, advertisers bid through an ad exchange to appear on the publisher s website as the impressions arrive. Recently, an intermediate form of contract known as a preferred deal has grown in popularity [Digiday, 2018]. Under a preferred deal, the advertiser and the publisher agree on a ﬁxed impression price and quantity (as in a reservation), but the advertiser is now given priority access to choose among impressions in real time. Impressions that the advertiser declines to buy can be sent on to other preferred deals with lower priority, or to an ad exchange. Mirrokni and Nazerzadeh [2017] recently initiated a formal study of preferred deals. They design an approximation algorithm, called the auction-adjusted greedy algorithm (AAG),

for the problem of designing preferred deals for advertisers based on their historical bids on an ad exchange, in order to optimize for revenue. The idea is that the advertisers bids on the exchange (normally in second-price auctions) provide information about their distributions of value for different impressions, and this information can be used to construct and optimize deals going forward. In practice, advertisers typically have strict budget limits on the amount they are able to spend on various parts of their marketing campaigns, and possibly other constraints such as volume constraints on the number of impressions from different subcategories of inventory (e.g., to ensure a diversity of impressions). In this paper, we design an approximation algorithm for optimizing revenue through preferred deals in the presence of budget and general convex constraints. To do so, we cast the AAG algorithm into a more general algorithmic framework which takes in an oracle that allocates impressions to optimize welfare, and results in a constant-factor approximation algorithm for the problem of optimal-revenue deal design. By using a constraint-aware social welfare oracle, we obtain constant-factor approximations in settings where buyer valuations are independent or additively correlated, where the constraint-aware social welfare is the social welfare respecting all constraints. For arbitrary correlation structures, we prove a negative result showing that no constant-factor approximation is possible. To efﬁciently implement the social welfare oracle in practice, we use a reduction by Cai et al. [2012] from ex-post to interim impression allocation rules, which leads to a largescale convex program. To our knowledge, this is the ﬁrst practical implementation of this reduction. We evaluate our algorithm using auction data from the Google Ad Exchange, and compare it against the original AAG algorithm as well as second-price auctions (with and without reserve prices) as benchmarks. We ﬁnd that the original AAG algorithm performs well at high budget levels, while second-price auctions perform well at low budget levels, but only our new algorithm achieves high revenue across the board, typically reaching at least 95% of the optimum.

Related Work. We brieﬂy discuss research closely related to ours in this section. For a review of the literature on display advertising, readers are encouraged to refer to Korula et al. [2016] and Choi et al. [2017] for recent surveys. As mentioned, Mirrokni and Nazerzadeh [2017] ﬁrst for-

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

mally framed the preferred deals problem and considered the setting without constraints. The main reason behind the high revenue potential of preferred deals is bundling. Ghosh et al. [2007] show that it is computationally hard to ﬁnd the optimal bundling and propose approximation algorithms. Babaioff et al. [2014] demonstrate that the strategy of either selling each item separately or selling them all as a grand bundle can obtain a constant approximation of the optimal revenue for selling multiple items to a single buyer. Our results provide a constant-factor approximation for the multi-buyer case with general convex constraints under the assumption that the items are identically and independently drawn, which may be of independent interest. Another related line of work is auction design with budget constraints, which was initiated by Che and Gale [1998] (see also [Benoˆıt and Krishna, 2001; Che and Gale, 2000]). Pai and Vohra [2014] characterize revenue-maximizing auctions for a single unit. For multi-unit settings, Dobzinski et al. [2012] show that there is no Pareto optimal and incentive compatible mechanism if the budgets are private, and for public budgets, they give a unique mechanism that is Pareto optimal and incentive compatible, which was later extended to divisible units by Bhattacharya et al. [2010]. Our work is also related to the recent study of liquid welfare (see [Dobzinski and Paes Leme, 2014; Lu and Xiao, 2017; Azar et al., 2017]).

2 Preliminaries

In the preferred deals problem there is a publisher with a sequence of impressions, denoted as I, to sell to n buyers. Let v(k) = (v1(k), v2(k), . . . , vn(k)) be a valuation proﬁle of the buyers for the k-th impression. In this paper, we consider an environment where buyer i has a public budget constraint Bi. As usual, we use i to denote buyers other than i. We assume the buyer is risk-neutral with quasi-linear utility: the utility from purchasing such an impression with valuation v at price p is v p. However, if the buyer s total spend exceeds Bi, his utility becomes (in other words, the budget is a hard constraint on spend). Let xi : I [0, 1]n with P i xi(k) 1 be an allocation rule such that xi(k) speciﬁes the probability that buyer i gets the k-th impression. For convenience, let the norm of the allocation rule be |xi| = P k I xi(k). Denote buyer i s expected average valuation subject to xi by EI[vi|xi] = P

k vi(k) xi(k)

|xi| . In addition to the budget constraints, we consider an environment in which each buyer i has a personalized constraint Pi [0, 1]|I|.

Deﬁnition 1 (Personalized Constraint). An allocation rule x is feasible only if for each buyer i, xi Pi. We assume that Pi is convex and 0 Pi where 0 is a rule that does not allocate anything to a buyer, i.e., 0(k) = 0 for all k I.

Our personalized constraints are general enough to capture many practical requirements, such as overall volume constraints or weighted constraints on different subcategories of inventory (e.g., different user demographics). Let Ii be a ﬁnite set of different impressions from the perspective of buyer i. In other words, the set I of all impressions can be parti-

tioned into |Ii| subsets of impressions such that within each subset, the impressions are identical according to buyer i. Deﬁnition 2 (Identical Impressions). From the perspective of buyer i, impressions k and k are identical if their values are the same, i.e., vi(k) = vi(k ), and they are anonymous in Pi, i.e., for any xi Pi and all 0 δ xi(k) + xi(k ), xδ i Pi where xδ i (k) = δ, xδ i (k ) = xi(k) + xi(k ) δ, and xδ i (j) = xi(j) for all j {k, k }. Anonymity means that the two impressions can be treated as two copies of the same impression when checking whether the allocation rule satisﬁes the personalized constraint. We use fi : Ii [0, 1] to denote the (empirical) marginal distribution of buyer i s impressions: for κi Ii, fi(κi) = P k 1{k = κi}/|I|. We consider three types of correlation: no correlation, additive correlation, general correlation. In an environment with no correlation, we assume buyer i s distribution fi is independent of other buyers distributions f i. For additive correlation, we allow the valuations to be correlated by a common value. More precisely, vi(k) = η0 + νi(k) where νi is independent of νj(k) for any j = i and η0 0 is a random common component. An environment with general correlation means that there can be arbitrary correlation between valuations. Deﬁnition 3 (Preferred Deal). A preferred deal p, µ, I for a sequence of impressions I is speciﬁed by a price per impression p and a minimum purchase requirement µ. By accepting the deal, the buyer obtains priority access to the impressions in I and agrees to buy at least a µ fraction of the impressions, each at price p. By priority access, we mean that the buyer is given the opportunity to buy the impression before it is presented to any other buyer, in contrast to other selling mechanisms like auctions where buyers compete simultaneously. Given a deal p, µ, I for buyer i, since the price is ﬁxed, the buyer will always cherry-pick the impressions (i.e., buy impressions with highest valuations) to maximize her utility, subject to her personalized constraint and the minimum purchase requirement. Deﬁnition 4 (Cherry-picking). Let CPi be a cherry-picking function that returns the welfare-optimal allocation rule for buyer i, formally,

CPi(I) = arg max xi Pi |xi| EI[vi|xi].

Moreover, let CPi(I, µ) be a cherry-picking function satisfying the purchase requirement µ exactly, formally,

CPi(I, µ) = arg max xi Pi |xi|=µ|I|

If Pi {xi | |xi| = µ|I|} = , then CPi(I, µ) = 0. Let CPWi(I) be the welfare obtained by cherry-picking, i.e. CPWi(I) = |CPi(I)| EI[vi|CPi(I)], and similarly, CPWi(I, µ) = µ|I| EI[vi|CPi(I, µ)]. Given a deal p, µ, I , the buyer will choose µ |I| impressions such that

µ = arg max µ µ Bi/(p|I|) µ (EI[vi|CPi(I, µ )] p)

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

and purchase the impressions according to CPi(I, µ ). The objective of the publisher is to design a series of preferred deals to maximize revenue. The publisher ﬁrst selects a priority list (π1, π2, . . . , πn) of ordered buyer indices, and a pair (pi, µi) of price and minimum purchase requirement for each buyer i. The publisher will offer deals to the buyers in sequence according to the priority list and a buyer will receive impressions that are left over from the buyers with higher priorities. More precisely, let Hi(p, µ, I) be the set of impressions purchased by buyer i when offered deal p, µ, I . Then, the publisher will offer deals ( pπ1, µπ1, Iπ1 , pπ2, µπ2, Iπ2 , . . . , pπn, µπn, Iπn ) where Iπ1 = I and Iπj+1 = Iπj \ Hπj(pπj, µπj, Iπj). For simplicity, we will omit the dependence on I or Iπj when clear from context.

3 Auction-Adjusted Greedy Framework

We ﬁrst introduce an algorithmic framework for computing preferred deals, which extends the algorithm proposed by Mirrokni and Nazerzadeh [2017] that works exclusively for an environment without any constraints. The framework reduces the problem of optimizing preferred deals to the problem of optimizing impression allocations. Let S be the set of buyers and ω(I, S) denote the maximum expected revenue that can be collected by offering a series of deals. Note that when S = {i} is a singleton, the optimal approach is to offer a deal with µi = |CPi| and pi = min{E[vi|CPi], Bi/|CPi|} .

Lemma 1. For any µ such that CPi(µ) = 0, given a deal p, µ with p = min{E[vi|CPi(µ)], Bi/(µ|I|)}, purchasing impressions according to CPi(µ) is buyer i s best response.

By Lemma 1, such a deal can extract the maximum social welfare subject to Pi or buyer i s budget. Therefore, ω(I, {i}) = min{CPWi, Bi}. For |S| 2, we can deﬁne ω(I, S) recursively as follows:

ω(I, S) = max i S,µ [0,1] {min(CPWi(µ), Bi)

+ ω(I \ CPi(µ), S \ {i})}.

In this formula, we abuse notation and let CPi(µ) be the set of impressions that buyer i would like to purchase, and therefore, I \ CPi(µ) is the set of remaining impressions after buyer i takes CPi(µ). By Lemma 1, to extract revenue min(CPWi(µ), Bi) from buyer i, the publisher can offer a deal with pi = min{E[vi|CPi(µ)], Bi/(µ|I|)} and µi = µ. However, computing ω(I, S) exactly takes exponential time. In particular, Mirrokni and Nazerzadeh [2017] show that it is NP-Hard to compute the optimal deals even without any constraints. To circumvent the hardness result, Mirrokni and Nazerzadeh [2017] propose an approximation algorithm, called auction-adjusted greedy algorithm (AAG), to generate a series of deals when there are no constraints. We cast their algorithm in a more general framework that can handle general convex constraints by taking in an impression-allocation oracle. To deﬁne an impression-allocation oracle, we ﬁrst deﬁne the notion of an impression-allocation rule.

Deﬁnition 5 (Impression-allocation Rule). An impression allocation rule is (a1, , an) [0, 1]n with P ai 1 such that ai speciﬁes the fraction of impressions allocated to i. Deﬁnition 6 (Impression-allocation Oracle). Given a set of buyers S and a sequence of impressions I, an impressionallocation oracle O returns an impression-allocation rule.

Algorithm 1: AAG Framework

Input: Impression I, a set of buyers S, impression-allocation oracle O Output: Sequence of deals D.

If (|S| = 0) Return

Compute a = O(S, I) Let S0 = {j S|aj = 0} and S1 = S \ S0. D0 {(pj = 0, µj = 0)}j S0

For each buyer j S1 µj = aj pj = min{E[vj|CPj(µj)], Bj/(µj|I|)}

Choose a buyer i arg maxj S1 pj

D (pi, µi) + AAG(I \ CPi(µi), S1 \ {i}) + D0 Return D

Given an impression-allocation oracle O, the AAG framework (Algorithm 1) takes a set of buyers S and a sequence of impressions I as input and outputs a series of deals. Intuitively, in each recursion, the AAG algorithm obtains the minimum purchase requirement µj from the impressionallocation oracle O and computes the associated price respecting µj as well as the constraints, such that buyer j will buy exactly all the impressions from CPj(µj) according to Lemma 1. Finally, the algorithm selects a deal with maximum price to offer.

3.1 Constraint-aware Welfare and Oracle To apply the AAG framework in an environment with constraints, the key is to choose an impression-allocation oracle that respects all these constraints. In an environment without any constraints, the maximum social welfare is a natural upper bound on the revenue of any deals. However, in the presence of budget constraints and other constraints, the maximum social welfare could be much larger than the revenue of the optimal deal: consider a simple case where there is only one buyer and a single impression, and the buyer with budget 1 has valuation m on the impression. In this example, the maximum social welfare is m but the maximum revenue, bounded by the budget, is 1. Therefore, instead of social welfare, we use the constraintaware social welfare as the benchmark, which generalizes the concept of liquid welfare deﬁned exclusively for budget constraints [Dobzinski and Paes Leme, 2014]. Intuitively, constraint-aware social welfare is social welfare subject to the budget constraints and the personalized constraints.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Deﬁnition 7 (Constraint-aware Social Welfare). Given a set of buyers S and a set of impressions I, the constraint-aware social welfare CAW(S, I) is computed according to the following convex program:

max P i P k vi(k) xi(k) s.t. xi Pi i P k vi(k) xi(k) Bi i P i xi(k) 1, xi(k) 0 i, k

(expost-CAW)

In the program, the ﬁrst set of constraints ensure that the allocation rule satisﬁes all personalized constraints, while the second set of constraints ensure that the welfare contribution from each buyer does not exceed her budget constraint. The remaining constraints ensure that the allocation rule is valid. Let x CAW(S,I) be the allocation rule that maximizes CAW(S, I). Deﬁnition 8 (Constraint-aware Impression-allocation Oracle CAO). Given a set of buyers S and a sequence of impressions I, the constraint-aware impression-allocation oracle CAO returns an impression-allocation rule a = (a1, , an), where ai = P k x CAW(S,I) i (k)/|I|.

4 Approximation Guarantee In this section, we present the formal proof for the approximation guarantee by applying the AAG framework with constraint-aware social welfare oracle for additive correlations. We also provide a lower bound for general correlations.

4.1 Additive Correlation Recall that under the additive correlation model, values take the form vi = η0 + νi where the νi are independent and η0 is a random common component. We ﬁrst consider the special case of no correlation (η0 0) and show that the AAG algorithm with CAO gives a 1/2-approximation. Theorem 1. The expected revenue of the sequence of deals found by the AAG algorithm with CAO is at least 1 2CAW(S, I) when there is no correlation.

Proof. Let SOL(S, I) be the revenue generated by AAG algorithm with CAO with input S and I. We prove by an induction on the size of S from |S| = 1 to |S| = n. When S = {i}, if pi = E[vi|CPi(µi)], then SOL(S, I) is exactly CAW(S, I); otherwise, SOL(S, I) is Bi, but CAW(S, I) must be equal to Bi in this case. Therefore, the base case is true. Assume the induction hypothesis is true for all |S1| s. Then for |S1| = s + 1, for convenience, let

α(S, I|S , I ) = P k I P i S vi(k) x CAW(S,I) i (k)

Therefore, CAW(S, I) = α(S, I|S, I). Let i be the buyer that the algorithm offers a deal to with input (S, I). First:

CAW(S, I) = α(S, I|S, I) = α(S, I|{i}, I) + α(S, I|S \ {i}, CPi(µi)) + α(S, I|S \ {i}, I \ CPi(µi)).

Notice that

α(S, I|S \ {i}, I \ CPi(µi)) CAW(S \ {i}, I \ CPi(µi)) 2 SOL(S \ {i}, I \ CPi(µi))

where the ﬁrst inequality is due to the fact that x CAW(S,I) j (k) constrained in j S\{i} and k I \CPi(µi) is a valid solution for program (expost-CAW) with S \ {i} and I \ CPi(µi) as input, and the second inequality is by the induction hypothesis. Next, for any buyer j, notice that if pj = Bj/(µj|I|), then we have pj µj |I| = Bj α(S, I|{j}, I). Otherwise, notice that µj = aj = P k x CAW(S,I) i (k)/|I| and pj = EI[vj|CPj(µj)] is the average valuation of aj fraction of impressions due to cherry-picking. Therefore, we have α(S, I|{j}, I) pj µj |I| for all j. As for α(S, I|S \ {i}, CPi(µi)), since there is no correlation,

α(S, I|S \ {i}, CPi(µi)) = µi α(S, I|S \ {i}, I) µi α(S \ {i}, I|S \ {i}, I) µi α(S, I|S, I)

where the equality uses the fact that there is no correlation, the ﬁrst inequality is due to the fact that x CAW(S,I) j constrained in j S\{i} is a valid solution for program (expost CAW) with S \ {i} and I as input, and the last inequality is because of the fact that the welfare does not decrease by introducing an additional buyer since 0 Pi. In addition,

α(S, I|S, I) = P j α(S, I|{j}, I)

P j pj µj |I| maxj pj |I| pi |I|

where the second-to-last inequality is due to the fact that P j µj = P j aj 1. Therefore, we have α(S, I|S \ {i}, CPi(µi)) pi µi |I|. To sum up, we have

CAW(S, I) = α(S, I|{i}, I) + α(S, I|S \ {i}, CPi(µi)) + α(S, I|S \ {i}, I \ CPi(µi)) 2(pi µi |I| + SOL(S \ {i}, I \ CPi(µi))) = 2SOL(S, I)

Theorem 2. The expected revenue of the sequence of deals found by the AAG algorithm with CAO is at least 1 3CAW(S, I) with additive correlation.

4.2 General Correlation However, when the correlation can be arbitrary, we show that even in an environment without any constraints, the performance of preferred deals can be arbitrarily bad. Theorem 3. There exists an instance in which preferred deals can generate revenue at most O(1/n) of the maximum social welfare even without any constraints. Note that it is trivial to achieve a 1/n-approximation by offering the buyer i = arg maxi E[vi| 1] a deal with price E[vi| 1] and minimum purchase requirement 1, where 1 always allocates the impressions: 1(k) = 1 for all k.

Proof of Theorem 3. We create an example as follows. Let z to be some positive real number. For each 0 ℓ< n, we create n z1 1

2ℓimpressions and denote by Qℓthe set of these impressions. Among Qℓ, for each 1 i n, there are z1 1

2ℓimpressions such that buyer i has valuation z 1 2ℓwhile

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

the other buyers have valuation z 1 2ℓ+1 + 1. The maximum social welfare is E[maxi vi] = Pn 1 ℓ=0 n z1 1

2ℓ z 1 2ℓ= n2 z. However, notice that for any buyer, they will cherry-pick the impression in the order of Q0, Q1, , Qn 1. Given any deal, assume the ﬁrst impression buyer i picks (the impression with highest vi) is lefti and the last impression (the impression with lowest vi) is righti. Let Aℓ= |{lefti | lefti Qℓ}| + |{righti | righti Qℓ}| be the number of ﬁrst or last impressions in Qℓ. Note that if Aℓ= 0, all impressions in Ql is chosen by only one buyer, which contributes revenue at most z1 1

2ℓ z 1 2ℓ+ (n 1) z1 1

2ℓ (z 1 2ℓ+1 + 1) z + 2(n 1) z1 1 2ℓ+1 . If Aℓ> 0, then in the best scenario, these Aℓbuyers pick all z1 1

2ℓimpressions that they have valuation z 1 2ℓfrom Qℓ. Therefore, it can contribute at most Aℓ z1 1

2ℓ z 1 2ℓ+ (n Aℓ) z1 1

2ℓ (z 1 2ℓ+1 + 1) Aℓ z + 2(n 1) z1 1 2ℓ+1 . Note that P ℓAℓ= 2n. Thus, as z goes to , the ratio between the revenue generated by preferred deals and the maximum social welfare is

limz 2n z+(n 1) Pn 1 ℓ=0 z 1 1

4.3 Efﬁcient Implementation of the Oracle Although AAG algorithm with CAO provides good approximation, the computational complexity of CAO depends on the number of impressions, which could be huge in practice. To overcome this hurdle, we describe an efﬁcient algorithm to implement CAO. The complexity of our algorithm is polynomial in P i |Ii|, the number of different impressions. In fact, writing down the ex-post allocation rule xi : I [0, 1] takes O(|I|) time, which is already unacceptable. To alleviate this problem, we consider an interim allocation rule χi : Ii [0, 1] for 1 i n such that χi(κi) represents the probability that buyer i receives impression κi Ii. Given an ex-post allocation rule x, we can compute the interim allocation rule χ by χi(κi) fi(κi) |I| = P k:k=κi xi(k). We can now use the following program to compute the interim allocation rule that maximizes the constraint-aware social welfare: max P i P κi Ii vi(κi) fi(κi) χi(κi) s.t. χi Pi i P κi Ii vi(κi) fi(κi) χi(κi) |I| Bi i χ is a feasible interim allocation rule where χ is feasible if and only if there exists a feasible expost allocation rule x that can induce χ, where an ex-post allocation rule x is feasible if P i xi(k) 1 for all k I and xi(k) 0 for all i and k I. The oracle then returns ai = P κi Ii χi(κi) fi(κi). We can now apply the techniques developed by Cai et al. [2012] to obtain an efﬁcient separation oracle to verify whether χ is feasible. In theory, a program with an efﬁcient separation oracle can be solved efﬁciently by the ellipsoid method, while in practice, constraint generation can perform well, as evidenced by our implementation in the next section.

5 Empirical Evaluation We evaluate the performance of our framework by focusing on an environment with budget constraints only, and therefore, our constraint-aware social welfare is known as liquid

welfare in the literature [Dobzinski and Paes Leme, 2014]. We use data collected from the Google Ad Exchange (Ad X) over a period of one day in summer 2018. The data consists of bids from real-time second price auctions for speciﬁc ad spaces online, known as inventory units. Because secondprice auctions are truthful, we can construe the bids as the advertisers values for each impression and use the data for the purpose of preferred deal optimization. An advertiser s bid for an inventory unit can vary throughout the day due to variations in context (e.g., the user viewing the ad).

5.1 Data Set and Experiment Setup

We run our experiment on 5 high-volume inventory units for the day in question. Recall that the complexity of our algorithm mainly depends on the number of buyer-bid pairs. Therefore, we discretize the bids to cents and only consider the top 50 most frequent buyer-bid pairs. In particular, for each inventory unit, we ﬁrst compute the frequencies for distinct buyer-bid pairs. Then, we sort the pairs in decreasing order of frequency and retain the top 50 pairs. Finally, in our experiment, we take the ﬁrst 100K auctions in which at least two of the top 50 buyer-bid pairs appear in the auction to form our instances. These are the impressions to be allocated via preferred deals. Our algorithm can scale well beyond 100K impressions and we choose 100K because it represents a sizable instance where it is still possible to exactly compute the maximum liquid welfare using LP (expost-CAW), so that we are able to report exact approximation numbers.

For each inventory unit, we conduct experiments parametrized by a budget ratio r [0.1, 1.5]. This parameter controls the ratio between the expected total budgets and the social welfare, which is the summation of highest bids over all auctions. For a ﬁxed setting of r, we repeat the experiment 50 times and generate the budget as follows: for each run, (1) compute the contribution si to the social welfare for each buyer i, by summing buyer i s bids over all auctions that it wins; (2) set buyer i s budget to a value uniformly drawn from [0, 2 si r], so that the mean of the generated budget is si r, proportional to the buyer s social welfare contribution. By our construction, as r increases, the budget constraint becomes looser and one should expect the liquid welfare benchmark to increase as r increases. Finally, for each budget ratio r and each method, we report the ratio between the average of the revenue (welfare) for the 50 runs and the social welfare.

We compare the auction-adjusted greedy algorithm with budget (AAGBudget) against three other methods. The ﬁrst is the basic second-price auction. In a second-price auction with budget constraints, the buyer s submitted bid is adjusted by taking the minimum between his bid and his remaining budget. We call a second-price auction naive if it is without reserve (Naive SPA). In a second-price auction with optimal personalized reserves (Optimal SPA), we optimize reserve prices by ﬁnding the revenue-maximizing reserve for each buyer. We also consider the original auction-adjusted greedy algorithm (AAGNo Budget) proposed in [Mirrokni and Nazerzadeh, 2017], which ignores the budget.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Inventory ID 1 2 3 4 5 Liquid Welfare 72.1% 74.8% 74.1% 78.6% 83.7% AAGBudget 71.8% 70.9% 73.8% 75.9% 78.8% AAGNo Budget 44.4% 41.2% 40.2% 45.2% 54.5% Naive SPA 5.5%, 99.7% 34.8%, 92.4% 22.2%, 93.8% 34.3%, 95.3% 33.8%, 94.8% Optimal SPA 61.2%, 66.2% 44.9%, 86.7% 66.5%, 71.6% 50.9%, 87.1% 62.1%, 82.1%

Table 1: Revenue and welfare (respectively) as the fraction of the social welfare for r = 1. For the Liquid Welfare, AAGBudget, and AAGNo Budget, revenue is equal to welfare.

0.25 0.5 0.75 1 1.25 1.5

Liquid Welfare Naive SPA AAGBudget AAGNo Budget Optimal SPA

Revenue against social welfare

0.25 0.5 0.75 1 1.25 1.5

Liquid Welfare Naive SPA AAGBudget AAGNo Budget Optimal SPA

Welfare against social welfare

Figure 1: Revenue and Welfare Plot: the x-axis is for the budget ratio r and the y-axis is the ratio between the revenue (welfare) of different methods and the social welfare

5.2 Empirical Results We implemented our algorithm and experiments in Python 2.7, using the Glop linear programming solver1 to compute the liquid welfare within our algorithm. Each run of the experiment takes roughly 30 seconds on a single CPU. Figure 1 demonstrates the revenue and welfare trends for a single inventory unit as the budget ratio r is varied (trends were very similar across all inventory units), and Table 1 summarizes the results for r = 1. From Figure 1 we see that our algorithm s (AAGBudget) revenue performance closely tracks the optimal revenue achievable as captured by the liquid welfare for all values of r. The original AAG algorithm that does not take budget into account (AAGNo Budget) performs poorly especially when the budgets are small, and improves as the budgets increase. This is because, when the budget is small, the AAGNo Budget algorithm might offer a deal that violates buyer s budget. Given such a deal, the buyer may reject the deal, resulting in 0 revenue. This is why AAGBudget shows 0 revenue up to r = 0.5. Recall that for AAGBudget and AAGNo Budget, revenue is equivalent to welfare. An opposite revenue trend holds for the second-price auction benchmarks: their revenue performance decreases as r increases. This is because when the budget is small, the second price auction may be able to exhaust all the budgets within 100K auctions and therefore approach the liquid welfare optimum. For second-price auctions, especially the one with optimal reserves, there is a trade-off between revenue and efﬁciency. To understand why welfare can be higher than liquid welfare for the second-price auctions, recall that liquid

1See https://developers.google.com/optimization/lp/glop.

welfare only provides an upper bound on the revenue but not the welfare. If auction prices are consistently low but values are high, it is possible to achieve a high total welfare beyond the available budget, while respecting budget constraints. Table 1 provides results, indexed against the optimal social welfare (unconstrained by budget) to interpret both the revenue and social welfare levels together. When comparing revenue directly against liquid welfare (the revenue optimum), AAGBudget s performance ranges from 94 99% of the optimum across inventory units, whereas AAGNo Budget ranges from 54 65% and Optimal SPA from 60 90%. Our algorithm s revenue performance is consistently close to the liquid welfare benchmark across all values of r and outperforms all other algorithms, which demonstrates that our algorithm has a stable and much better performance in practice than the theoretical 1

2-approximation guarantee.

6 Conclusions We studied the problem of preferred deals with general constraints and provided an approximation algorithm to maximize the revenue obtained from the deals. We also validated our algorithm with experiments on real data, which showed that its empirical performance far surpasses the theoretical guarantees. One interesting future direction is to improve the approximation ratio or prove a matching lower bound for preferred deals, even in an environment without any constraints. Another interesting question is to understand how to combine and optimize the various ways used to sell display ad impressions together, including reservation contracts, preferred deals, and open auction.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Azar et al., 2017] Yossi Azar, Michal Feldman, Nick Gravin, and Alan Roytman. Liquid price of anarchy. In International Symposium on Algorithmic Game Theory, pages 3 15. Springer, 2017. [Babaioff et al., 2014] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. In 55th Annual Symposium on Foundations of Computer Science, pages 21 30. IEEE, 2014. [Benoˆıt and Krishna, 2001] Jean-Pierre Benoˆıt and Vijay Krishna. Multiple-object auctions with budget constrained bidders. The Review of Economic Studies, 68(1):155 179, 2001. [Bhattacharya et al., 2010] Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia. Incentive compatible budget elicitation in multi-unit auctions. In Proceedings of the 21st annual Symposium on Discrete Algorithms, pages 554 572. SIAM, 2010. [Cai et al., 2012] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. In Proceedings of the 44th annual ACM Symposium on Theory of Computing, pages 459 478. ACM, 2012. [Che and Gale, 1998] Yeon-Koo Che and Ian Gale. Standard auctions with ﬁnancially constrained bidders. The Review of Economic Studies, 65(1):1 21, 1998. [Che and Gale, 2000] Yeon-Koo Che and Ian Gale. The optimal mechanism for selling to a budget-constrained buyer. Journal of Economic Theory, 92(2):198 233, 2000. [Choi et al., 2017] Hana Choi, Carl F. Mela, Santiago Balseiro, and Adam Leary. Online display advertising markets: A literature review and future directions. Columbia Business School Research Paper, (18-1), 2017. [Digiday, 2018] Digiday. GDPR is giving new life to programmatic guaranteed deals. https://digiday.com/media/gdpr-giving-new-lifeprogrammatic-guaranteed-deals/, 2018. [Dobzinski and Paes Leme, 2014] Shahar Dobzinski and Renato Paes Leme. Efﬁciency guarantees in auctions with budgets. In International Colloquium on Automata, Languages, and Programming, pages 392 404. Springer, 2014. [Dobzinski et al., 2012] Shahar Dobzinski, Ron Lavi, and Noam Nisan. Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2):486 503, 2012. [Feige et al., 2008] Uriel Feige, Nicole Immorlica, Vahab Mirrokni, and Hamid Nazerzadeh. A combinatorial allocation mechanism with penalties for banner advertising. In Proceedings of the 17th International Conference on World Wide Web, pages 169 178. ACM, 2008. [Ghosh et al., 2007] Arpita Ghosh, Hamid Nazerzadeh, and Mukund Sundararajan. Computing optimal bundles for sponsored search. In International Workshop on Web and Internet Economics, pages 576 583. Springer, 2007.

[Korula et al., 2016] Nitish Korula, Vahab Mirrokni, and Hamid Nazerzadeh. Optimizing display advertising markets: Challenges and directions. IEEE Internet Computing, 20(1):28 35, 2016. [Lu and Xiao, 2017] Pinyan Lu and Tao Xiao. Liquid welfare maximization in auctions with multiple items. In International Symposium on Algorithmic Game Theory, pages 41 52. Springer, 2017. [Mirrokni and Nazerzadeh, 2017] Vahab Mirrokni and Hamid Nazerzadeh. Deals or no deals: Contract design for online advertising. In Proceedings of the 26th International Conference on World Wide Web, pages 7 14, 2017. [Pai and Vohra, 2014] Mallesh Pai and Rakesh Vohra. Optimal auctions with ﬁnancially constrained buyers. Journal of Economic Theory, 150:383 425, 2014. [Pw C, 2018] Pw C. IAB internet advertising revenue report. https://www.iab.com/wp-content/uploads/2018/05/IAB2017-Full-Year-Internet-Advertising-Revenue-Webinar Presentation.pdf, 2018. Accessed: 2019-06-26.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)