Preferred Deals in General Environments

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 [PwC, 2018]. Traditionally, display advertising has been mainly sold via reservation contracts or real-time bidding. In a reservation contract, the publisher buys a fixed 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 fixed 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 efficiently 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 first 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 find 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 briefly 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] first formally 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 find 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 profile 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 ∑i xi(k) ≤ 1 be an allocation rule such that xi(k) specifies the probability that buyer i gets the k-th impression. For convenience, let the norm of the allocation rule be |xi| = ∑k∈I xi(k). Denote buyer i's expected average valuation subject to xi by EI[vi|xi] = ∑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| .

Definition 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 finite set of different impressions from the perspective of buyer i. In other words, the set I of all impressions can be partitioned into |Ii| subsets of impressions such that within each subset, the impressions are identical according to buyer i.

Definition 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 satisfies 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) = ∑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.

Definition 3 (Preferred Deal). A preferred deal 〈p, µ, I〉 for a sequence of impressions I is specified 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 fixed, 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.

Definition 4 (Cherry-picking). Let CPi be a cherry-picking function that returns the welfare-optimal allocation rule for buyer i, formally,

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

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

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 first 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 first 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 define ω(I, S) recursively as follows:

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 define an impression-allocation oracle, we first define the notion of an impression-allocation rule.

Definition 5 (Impression-allocation Rule). An impression allocation rule is (a1, · · · , an) ∈ [0, 1]n with ∑ ai ≤ 1 such that ai specifies the fraction of impressions allocated to i.

Definition 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.

Choose a buyer i ∈ argmaxj∈S1 pj

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-awareWelfare 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 defined 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.

Definition 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:

In the program, the first set of constraints ensure that the allocation rule satisfies 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 xCAW(S,I) be the allocation rule that maximizes CAW(S, I).

Definition 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 = ∑k xCAW(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 first 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 2 CAW(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

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:

Notice that

where the first inequality is due to the fact that xCAW(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 = ∑k xCAW(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,

where the equality uses the fact that there is no correlation, the first inequality is due to the fact that xCAW(S,I) j constrained in j ∈ S \{i} is a valid solution for program (expostCAW) 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,

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

Theorem 2. The expected revenue of the sequence of deals found by the AAG algorithm with CAO is at least 13 CAW(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∗ = argmaxi 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 the other buyers have valuation z 1 2ℓ+1 + 1. The maximum social welfare is E[maxi vi] = ∑n-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 first 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 first 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 ∑ℓ Aℓ = 2n. Thus, as z goes to ∞, the ratio between the revenue generated by preferred deals and the maximum social welfare is

4.3 Efficient 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 efficient algorithm to implement CAO. The complexity of our algorithm is polynomial in ∑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| = ∑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:

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 ∑i xi(k) ≤ 1 for all k ∈ I and xi(k) ≥ 0 for all i and k ∈ I. The oracle then returns ai = ∑κi∈Ii χi(κi) · fi(κi). We can now apply the techniques developed by Cai et al. [2012] to obtain an efficient separation oracle to verify whether χ is feasible. In theory, a program with an efficient separation oracle can be solved efficiently 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 (AdX) over a period of one day in summer 2018. The data consists of bids from real-time second price auctions for specific 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 first 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 first 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 fixed 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 first 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 finding the revenue-maximizing reserve for each buyer. We also consider the original auction-adjusted greedy algorithm (AAGNoBudget) proposed in [Mirrokni and Nazerzadeh, 2017], which ignores the budget.

1

0.75

0.5

0.25

0

Revenue against social welfare

Liquid Welfare Naive SPA

AAGBudget

AAGNoBudget Optimal SPA

0.25

0.5

0.75

1

1.25

1.5

5.2 Empirical Results

We implemented our algorithm and experiments in Python 2.7, using the Glop linear programming solver 1 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 (AAGNoBudget) performs poorly especially when the budgets are small, and improves as the budgets increase. This is because, when the budget is small, the AAGNoBudget algorithmmight 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 AAGNoBudget, 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 efficiency. To understand why welfare can be higher than liquid welfare for the second-price auctions, recall that liquid 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.

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

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 AAGNoBudget 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 12 -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.