Online Ad Allocation with Predictions
Authors: Fabian Christian Spaeh
Alina Ene
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Augmented Algorithms
Display Ads
Generalized Assignment Problem
TL;DR: We develop an algorithm for Display Ads and GAP that leverages machine-learned predictions.

Abstract: Display Ads and the generalized assignment problem are two well-studied online packing problems with important applications in ad allocation and other areas. In both problems, ad impressions arrive online and have to be allocated immediately to budget-constrained advertisers. Worst-case algorithms that achieve the ideal competitive ratio are known for both problems, but might act overly conservative given the predictable and usually tame nature of real-world input. Given this discrepancy, we develop an algorithm for both problems that incorporate machine-learned predictions and can thus improve the performance beyond the worst-case. Our algorithm is based on the work of Feldman et al. (2009) and similar in nature to Mahdian et al. (2007) who were the first to develop a learning-augmented algorithm for the related, but more structured Ad Words problem. We use a novel analysis to show that our algorithm is able to capitalize on a good prediction, while being robust against poor predictions. We experimentally evaluate our algorithm on synthetic and real-world data on a wide range of predictions. Our algorithm is consistently outperforming the worst-case algorithm without predictions.

Online Ad Allocation with Predictions
Fabian Spach Department of Computer Science
Alina Ene Department of Computer Science Boston University aene@bu. edu
Boston University fspaeh@bu.en
Abstract
Display Ads and the generalized assignment problem are two well-studied online packing problems with important applications in ad allocation and other areas. In both problems, ad impressions arrive online and have to be allocated immediately budget-constrained advertisers. Worst-case algorithms that achieve the ideal competitive ratio are known, but might act overly conservative given the predictable and usually tame nature of real-world input. Given this discrepancy, we develop an algorithm for both problems that incorporate predictions and can thus improve the performance beyond the worst-case. Our algorithm is based on the work of Feldman et al. (2009a) and similar in nature to Mahdian et al. (2007) who were the first to develop an algorithm with predictions for the related, but more structured Ad Words problem. We use novel analysis to show that our algorithm is able to capitalize on a good prediction, while being robust against poor predictions. We experimentally evaluate our algorithm synthetic and real-world data on a wide range of predictions. Our algorithm is consistently outperforming the worst-case algorithm without predictions.
Introduction
Advertising the internet is multi-billion dollar industry with ever growing revenue, especially online retail gains more and more popularity. Typically, a user arrives on a website which fills an empty advertising spot (called impression) by allocating it instantly Advertisers value users differently based on search queries or demographic data and reveal their valuations auctions through contracts with the website. Formulations of increasing complexity have been studied to capture this problem, creating a hierarchy of difficulty (Mehta, 2013). The most basic online bipartite matching, where each vertex on one side arrives online with all its adjacent edges and has to be matched immediately to one of the vertices on the other side, which were supplied offline. The problem and all generalizations admit a hard lower bound of 1 due to the uncertainty about future vertices. Motivated by online ad exchanges, where advertisers place bids on impressions, Mehta et al. (207)) introduced the Ad Words problem, which a generalization of online bipartite matching where we charge each advertiser for the amount they bid. Going beyond the Ad Words setting, (Feldman et al. (2009a) considered the more expressive problems Display Ads and the generalized assignment problem (GAP), and proposed algorithms for these settings with worst-case guarantees.
of many advertisers.
Classic algorithms that defend against the worst case of 1 are often overly conservative given that the real world does not behave like contrived worst-case instance. Recently, researchers have thus been trying to leverage prediction about some problem parameter to go beyond the worst-case (Mitzennacher and Vassilvitskil 2022). In the context of ad allocation, prediction can be the keyword distribution of users on certain day, or simply the advertiser allocation itself. Such prediction is readily obtainable in practice, for example through learning on historie data. Two opposing properties are important: The algorithm has to be consistent, meaning that its performance
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

should improve with the prediction quality. Simultameously, we want the algorithm to be robust against a poor prediction, i.c. not to decay completely but retain some form of worst-case guarantee. This is particularly important in the advertising business as much revenue is extracted from fat tails containing special events that are difficult or impossible to predict, but extremely valuable for the advertising business (e.g. advertising fan merchandise after team's 's victory). To this end. Mahddian ict al. (2007) developed an algorithm with predictions for the Ad Words problem and Medina and Vassilvitskii (2017) show how to use bid predictions to set reserve prices for ad auctions. Inspired by their work, we develop an algorithm with predictions for Display Ads and GAP.
We design the first algorithms that incorporate predictions for the well-studied problems Display Ads and GAP. The two problems are general online packing problems, that capture wide range of applications. Our algorithm follows a primal-dual approach, which yields a combinatorial algorithm that very efficient and easy to implement. It is able to leverage predictions from any source, such as predictions constructed from historical data. Using a novel analysis, we show that the algorithm is robust against bad predictions and able to improve its performance with good predictions. In particular, we are able to bypass the strong lower bound on the worst-case competitive ratio for these problems. We experimentally verify the practical applicability of our algorithm under various kinds of predictions that our algorithm is able to outperform the baseline worst-case algorithm due to Feldman et al. (2009a) that does not predictions, by leveraging predictions that are obtained from historic data, as well as predictions that are corrupted versions of the optimum allocation.
Our Contributions:
synthetic and real-world data sets. Here, we observe
1.1 Preliminaries
Problem Definition: In this work, we study the Display Ads problem and its generalization, the generalized assignment problem (GAP) (Feldman et al. 2009)). In Display Ads, there are advertisers E (1....,,)) }}} that are known ahead of time, each of which is willing to pay for at most B, ad impressions. A sequence of ad impressions arrive online, one at a time, possibly in adversarial order. When impression t arrives, the values War 0 for each advertiser a become known. These values might be a prediction of click-through probability or any valuation from the advertiser, but we treat them as abstractly given the algorithm. We have allocate immediately an advertiser, or decide not to allocate it at all. The goal is to maximize the total value Σa,: Tat Wat subject to Σ. Jat S. Be for all o, where Fat = if f is allocated to a and Fat = O, otherwise. GAP is a generalization of Display Ads where the size that each impression takes up in the budget constraint of an advertisers is non non-uniform. That is, each impression t has a size unt 2 0 for each advertisers a, and advertiser is only willing to pay for a set of impressions whose total size most Ba. More precisely, we require that Ea,
a Tot Uaa S B..
Free Disposal Model: general, it is not possible to achieve any competitive ratio for the online problems described above. Motivated by online advertising, |eelmman et al. (2009a) introduced the free disposal model which makes the problem tractable: when a new impression arrives, the algorithm allocates it to an advertiser o; if is out of budget, we can decide to dispose of an impression previously allocated to a. The motivation for this model is that advertisers are happy to receive more ads, long they only charged for the B, most valuable impressions. We refer the reader the paper of Feldman et al. (2009)) for additional motivation of this model. In this work, we consider both Display Ads and GAP in the free disposal model.
Related Problems: Display Ads and GAP are significant generalizations of well-studied problems such as online bipartite matching and Ad Words. In online bipartite matching, all values are 1. In Ad Words, values and sizes are identical. The latter setting allows for more specialized algorithms that exploit the special properties of this problem, as we discuss in more detail later.
The algorithms we study follow under the umbrella of algorithms that leverage predictions to obtain improved performance. These were studied in an extensive line of work, see e.g. the survey of Mitzenmacher and Vassilvitskii (2022). Following this established research, we use two important measures for the performance of the algorithm: The robustness ALG/OPT indicates how well the algorithm's 's objective value ALG performs against the optinum solution OPT; the consistency ALG /PRD measures how close the algorithm gets to the prediction's 's objective value PRD. Most algorithms with predictions, including the one presented in this work, allow to control the trade-off between robustness and consistency with parameter
Algorithms with Predictions:

---

1.2 Related Work
Online Ad-Allocation with Predictions: To the best our knowledge, we are the first to study Display Ads and GAP with predictions. Related problems were considered in the work by Mahdian al. (2007) and Medina and Vassilvitskii (2017) for Ad Words, and by Lattanzi et al. (2020) for online capacitated bipartite matching. Medinna and Vassilvitskii (017)) use bid predictions to set reserve prices for auctions. [Lavsstdda et al. (2021) incorporate predictions of the dual variables into the proportional-weti -wightts algorithm (Agrawal et al. 2018 Karp et al. 1990 Lattanzi et al. 2020) for online capacitated bipartite matching. Chen and Indyk )021) analyze an algorithm that uses degree predictions by matching arriving vertices to vertices with minimum predicted degree. [Jin and Ma (2022) provide an algorithm for batched allocation in bipartite matching under predictions, based on the model of Fnng et al. (202T). As noted above, Ad Words and bipartite matching have additional structure, which is exploited in these prior works. In particular, the algorithms proposed in these works are not applicable to the more general problems Display Ads and GAP. Our algorithm builds on the approach of Mahdian et al. (2007) for the Ad Words problem, but substantial new ideas are needed in the algorithm design and analysis, discussed in more detail in Section 2
There has been further extensive work the design of worst-case algorithms and under random input models without predictions, which we now summarize,
The design of worst-case algorithms has been the focus of a long line of work which can, for instance, be found in the survey of Mehta (013). A large focus has been on Ad Words. Several combinatorial algorithms have been proposed. based on the work of Karp et al. (1990). The combinatorial approach is tailored to the structure of to these special cases. The primal dual approach is a more general approach that can handle more complex problems such as Display Ads and GAP (Buchbinder et al. [207]] Feldman et al., 2009a). In this work, we build on the primal- algorithm of Feldman et al. 2009a) and show how to incorporate predictions into their framework. The worst-case guarantee for online appartit-matching and therefore for all generalizations, is
Worst-Case Algorithms:
(Krrp et al. 1990).
Stochastic Algorithms:
The lower bound of 1 can be circumvented under distributional assumptions. This has been extensively studied for online bipartite matching (Karande al. 2011 Feldman et |l.]| 2009b] Jin and Williamson, 2022). Further work has been done for the Ad Words
problem (Devanur and Hayes] 2009] Devanur al. (0122) with generalizations due to Feldman et al.
(2010) for a more general stochastic packing problem.
2
Our Algorithm
In order to illustrate the algorithmic ideas and analysis, we consider the simpler setting of Display Ads in this section. Our algorithm for GAP is generalization of this algorithm and we include it in Appendix [B] For simplicity, we assume that our prediction is solution the problem, which is as in prior work (Mahdian et al., (007). However, due to our general analysis framework, we also consider our algorithm a starting point towards incorporating weaker predictors, such as partial solutions or predictions of the supply, which we leave for future work.
Prediction: We assume that we are given access prediction, which is fixed solution to the problem, given as an allocation of impressions to advertisers. With each impression f, we also receive the advertiser PRD(t) to which the prediction allocates t. In particular, this means that the prediction does not have to be created up front, but can be adjusted on the fly based on the observed impressions.
Given solution to the problem, we could also consider the following random-mixin mixture algorithm: For some parameter 9 E [0, 1], run the worst-case algorithm: with probability 1- q. follow the prediction exactly. This algorithm achieves a robustness of q. (1 () and consistency of q (1 2) 1 g. However, this is only in expectation and against a weak adversary that oblivious to the algorithm's 's random choices. In contrast, Algorithm[] T is designed to obtain its guarantees deterministically against the strongest possible adversary that can adapt to the algorithm's 's choices, which is identical to the setup in Mahdian et al. (2007). We observe that Algorithm clearlly outperforms this aantme algorithm in our experiments (ef. Section 4 which shows that our stronger setting is indeed valuable in practice. Furthermore, the random-mixture algorithm cannot be adapted to different predictors that are not solutions, such as the ones mentioned above.
Algorithm Overview: Our Algorithm, shown in Algorithm incorporates predictions in the
3

---

Display Ads Primal
Display Ads Dual
min Σ Baßa + Σ
max
Wat
a,t
Ya:
Σ Lat S
Bo
Va, t: 2 2 Wat - 3a
Va: Ba 2 0
vt: Σ Hat S
VI: 2t 2 0
Va, Zat
Figure 1: Primal and dual of the Display Ads LP
Algorithm
Exponential Averaging with Predictions
Input: Robustness-consistern trade-off parameter a E [1, 00), advertiser budgets Ba E N
2: Define the constants B == min, Ba, e (1 + } and og B ( a -1)
3: For each advertiser initialize 3a + 0 and allocate Bg zero-value impressions
4: for arriving impressions do
5: d(PRD) < PRD(tt)
6: ((EXP) - arg maxa { Wat - Ba}
7: if a (WaP)DD) - Bu(PRD)) WOCEXP) BatExP) then
8:
((PRD)
9: else
10:
((EXP)
11:
end if
12:
Allocate to a and remove the least valuable impression currently assigned to
13:
Let w1 I W2 < ... < WB, be the values of impressions currently assigned to in non-
decreasing order a/B.
B.
Update
Ba
B,
2
W.B.
6a
BBa
15: end for
primal-dual algorithm of Feldman et al. (2009)). The algorithm is based the primal and dual LP formulations in Figure The algorithm constructs both a primal integral solution which is an allocation of impressions to advertisers well as dual solution, given explicitly by the dual variables 3a. Analogously to other algorithms with predictions, the algorithm takes as parameter the value at larger value of means that we trust the prediction more. Similarly to the worst-case algorithm of Feldman et al. (2009)), the dual variables Ba play an important role in the allocation of impressions. When an impression arrives, we evaluate the discounted gain Wat 3g for each advertiser. The worst-case algorithm allocates the impression to the advertiser ((EXP) maximizing the discounted gain and only allocates the discounted gain positive, i.e. the value exceeds the threshold 3., Our algorithm modifies this base algorithm to incorporate predictions as shown in Line 7 and follows the prediction ((PRD) its discounted gain is sufficiently high fraction of the discounted gain of ((EXP). We refer the reader to the discussion below for more intuition on the choice of update. After selecting the advertiser to which to allocate the impression t, we remove the least valuable impression currently assigned to to make space for t, and then allocate to Another crucial part of the algorithm is the update rule for 3g in Line 14, which is updated in a novel way based on the parameter More preciscly, impressions currently allocated to a. Compared to the worst-case algorithm, we assign higher weight to impressions with less value which is essential for leveraging predictions.
set 8g
exponential averaging of the values of
To simplify the algorithm description and analysis, we initially allocate B,, impressions of zero value to each advertiser a. Furthermore, we assume that there exists "dummy" advertiser with large budget that only receives zero value impressions. Instead of not allocating an impression explicitly (either in the algorithm or the prediction), allocate the dummy advertiser, instead.

---

06-
0.5
0.3-
20
Conditency
Raluaines
0.4
Robustnes
0.8
02-
0.1
012
0.0
0.-
2.5
5.0
7.5
10.0
2.
3,3
7.5
10.0
0.5
0..8
1.0
Consisencyy
Figure 2: We illustrate the consistency-robustan trade-off of Algorithm for various values of and budgets B.
Intuition for our Algorithm: algorithm to incorporate predictions: The advertiser selection (Line 7 and the update of 3r (Line 14). We now provide intuition for both choices.
As noted above, we make two crucial modifications to the worst-case
First, let us illustrate the difficulties in incorporating predictions in the advertiser selection. Based on the worst-case algorithm, natural way incorporate predictions is allocate the prediction if the distorted gain ( approach does not work as shown by the following example: Consider a scenario where the prediction suggests constant advertiser ((PRD). Impressions are split into two phases: Phase contains for + ((PD))- The algorithm allocates all these impressions d(PRD) and the end of phase has BaRDRD) = In phase 2, a large amount impressions with Warpnnyt = and War 2a + ((PRD) arrive. Since the distorted gain Wa(PRD) 3. Pa(PRD) a-1 exceeds the discounted gain Wat B n=1 for a + d(PRD). the algorithm allocates d(PRD) which yields 0 gain. However, we forfeit an unbounded amount of potential value derived from allocating to advertisers & ((PRD)- An important takeaway of this example is the crucial observation that the algorithm should never allocate to the predicted advertiser if its discounted gain is O. The selection rule in our algorithm is designed to meet this important consideration.
BappRD; exceeds the maximum discounted gain. However, this
BaIPRD) impressions where only ((PRD) can derive a value of " 1 and wat
a-1 for
2a
Second, we need to change the update rule for Sq. We update 8a using a carefully selected exponential average of the values of impressions currently assigned to a, that incorporates confidence in the prediction parameterized by a. In contrast to the worst-case algorithm, we weigh less valuable impressions more. This lowers the threshold for the addition of new impressions, which allows to exploit more potential gain from the predicted advertiser.
Theorem 1.
Let B = ming Ba and eg == (1+ 1 Let OPT and PRD be the values of the optimal and predicted solutions, respectively. For any 2 1, Algorithm 7 Tobtains value of at least
ALG Z max (R(a) OPT, C(a) PPRD)
where the robustness is
e
R(a)
Beg
cg
B/B
-
a0e
and the consistency is
(e 1)
C(a)) = 1
max
B
In
67 -1
a
QB
-1
1 ca - max
e
a
(B 00).
Figure shows the above trade-off between consistency and robustness. We can observe that the guarantee rapidly improves as the minimum advertiser budget B increases, which is very beneficial both theory and in practice. The trade-off is comparable to the one obtained by Mahdian al.
(2007) for the more structured Ad Words problem.
5

---

Comparison to Prior Work: The work most closely related to ours is the work of Mahdian et al. (2007) which incorporates predictions into the algorithm of Mehta et al. (2007). These works are for the related but different Ad Words problem, and do not apply to Display Ads and GAP. In the Ad Words problem, the value of an impression is equal to the price that the advertiser pays for it, i.e., the size of the impression in the budget constraint. In contrast, in Display Ads and GAP, the values and the sizes are independent of each other (e.g., in Display Ads an impression takes up 1 unit of space in the advertiser's 's budget but it can accrue arbitrary value). Thus there is no longer any relationship between the total value/profit of the impressions and the amount of the advertiser's budget that has been exhausted. The Ad Words algorithms of Mehta et al. (2007); Mahdian et al. (2007) crucially rely on this relationship both in the algorithm and in the analysis. Due to the special structure of the problem, these algorithms do not dispose of impressions and consider only the fraction of the advertiser's budget that has been filled up in order to decide the allocation and to incorporate the prediction. Moreover, the algorithm and the analysis do not need to account for the loss incurred by disposing impressions. These crucial differences require a new algorithmic approach and analysis, which was given by Feldman et al. (2009a) using primal-dual approach. Since we build on their framework as opposed to the work of Mehta et al.) (2007), we also need a new approach for incorporating predictions, as described above in the intuition for our algorithm. Further, the primal-dual framework only helps in establishing the robustness but not the consistency of our algorithm, and we develop a novel combinatorial analysis for proving the consistency.
Analysis
In the following, we outline the analysis of Algorithm to prove Theorem I
Specifically, we show separately that ALG/OPT < R((a) (robustness) and AT.//PRD < C(a) (consistency).
Notation:
We denote with superscript (t) the value of variables after allocating impression t. E.g. a!!)
is the algorithm's 's choice of advertiser for impression 1. and (3(8) is the dual variable after allocating t.
Let
X. = (t: a = a} and P. {t ((PD) a)
(t)
be the impressions that were assigned to a and potentially disposed of, and the impressions that the prediction recommended for assignment to a, respectively. We set Ia- == X, and la == iPa n X as the size of the overlap. Let also T be the last impression and S, is the final allocation, i.c., the B, impressions allocated to a at the end of the algorithm. Finally, let ALG and PRD be the total value of the solution created by the algorithm and the prediction, respectively.
Robustness: Our proof for robustness closely follows the analysis in Feldman et al. 2009a by using the primal-dual formulation of the problem, with some additional care that is needed not to violate dual feasibility whenever we follow the prediction. We defer the full proof Appendix A.I
Consistency: We now show the consistency, i.e. that PRD is bounded by a multiple of ALG. The complete analysis can be found in Appendix A.2 while we only give high-level overview here.
common approach in the analysis of online primal-dual algorithms to employ a local analysis where, in each iteration, we relate the change in the value of the primal solution to the change in the dual solution (Buchbinder and Naor 2009). However, is not clear how to employ such a strategy in our setting due to the complications arising from our algorithm following a mixture of the worst-case and predicted solutions. We overcome this challenge using a novel global analysis that relates the final primal value to the prediction's 's value.
We now provide a high level overview of our global analysis. We start by noting that the objective value of our algorithm and the prediction is the sum of the impression values allocated to each advertiser, i.e.
ALG = Σ Σ Wat
and PRD = ΣΣ Wat
PES_
a TEP.
However, note that PRD contains values of impression that do not appear in ALG since ignore the prediction in some iterations, or already disposed of the impression. It is further unclear which advertiser to "charge" for impression that does not agree with the prediction.
Consider an impression for which we followed the worst-case choice ((EXP) that maximizes the discounted gain instead of the prediction. Due to our selection rule, the reason for this departure is

---

due to the discounted gains satisfying the following key inequality:
Wa(PRD)
I
(Wagxx))
- + BO(PRDY'
(1)
B
By using this important relationship, we upper bound the value PRD of the prediction using a linear combination of the values of impressions allocated by the algorithm (but possibly disposed of) and the thresholds. By grouping the impression values and dual variables by advertiser in the resulting upper bound, we are able to correctly charge each impression for which we deviated from the prediction to a suitable advertiser, thus overcoming one of the challenges mentioned above. To summarize, using ① we obtain bound PRD Σn PRD, where each PRD,, is linear combination of impression values and dual variables for advertiser a, and we want to compare this quantity to ALG,- EiEs, Wat-
Let us now consider a fixed advertiser a, and relate PRD, to ALG,- At this point, a key difficulty is that the amount PRD, that charged advertiser involves the threshold 3a. By definition, the threshold is a convex combination of the values of the impressions in the algorithm's 's allocation. This gives that PRD, is linear combination of only the weights, but this cannot be readily compared to aL due to the complicated structure of the coefficients in the former. To bridge this gap, we show a useful structural property (Lemma 4 that gives us the following upper bound on PRD,: If we define & as the i-th impression allocated to a, we have
la-La PRD Σ
Ia Σ 1ett-
Pewat +
b.Waa, + Watt,-n, Do
(2)
2 +1
for appropriate coefficients di thi and S2n. The RHS of this inequality accounts for the value as follows: the first sum is for the impressions that agree with the prediction; the second sum is for the impressions that disagree with the prediction; the final term accounts for the values of all impressions that were disposed. As this is (almost) a linear combination over impression values that all appear in
PRD./ALG, ALG (except Wats, -att,.B.))) ), we could bound the ratio PRD./ ALL., by the maximum coefficient in (2).
However, this does not lead to a constant competitive ratio. We therefore need a delicate analysis uniformly as possible among all values, where we use
(Lemma TO to balance the coefficients properties of the coefficients 6i vi, and Ω. and the structural property we derived in Lemma 4
In Appendix B we discuss how to generalize Algorithm I and its analysis to GAP, where impressions can take up arbitrary size tha in the budget constraints. This generalization uses a gain Wat uat. that considers the size of each impression. and the comparison of the worst-case and predicted choices are updated correspondingly. We also change the update of Ba to consider the impression density Wat/ Mat- We also note that our technique can be used to achieve a slight improvement in the guarantees, but we omit this in the interest of simplicity and conciseness.
4 Experimental Evaluation
We now evaluate the practical applicability of Algorithm T We use multiple baseline algorithms on different kinds of predictions, which we describe below. We showcase results on real-world and synthetic data, with further experimental results in Appendix C
We compare Algorithm I to the uundom-mixtun algorithm described in Section (Random Mixture) and the worst-case algorithm without predictions due to Feldman et al. (2009a) (Worst-Case Baseline). Additionally, we consider two modifications of the worst-case algorithm: One allocates to the impression of maximum value (Greedy Baseline) and the other to the impression with maximum gain after disposal (Discounted Greedy Baseline).
Algorithms:
Predictors: We consider variations of the following predictors. Recall that each predictor is fixed allocation of impressions to advertisers that is revealed online.
(1) Optimum Solution (OPT): The optimum solution obtained by solving the problem optimally offline using an LP solver. To evaluate our algorithm's 's robustness, we also consider version of the optimum solution where a random p-rrcction of the allocations has been corrupted. Under a random corruption, we corrupt by reallocating to randomly chosen advertisers. For biased corruption, we sample a random permutation offline and corrupt by reallocating according to this permutation, generating more adversarial corruption.
7

---

compot oe p [63L]
PrevieeDay
Geedy
Dusifowe (0:11)
OPT Rase comprr oe 65 (0.17)
Roston Matuee
Dacourted Gredd Busine
20
L0-
1.00
0.6-
0.4-
DFF 3.0
QP1 randon comption (816)
Prewouullyy (1.54)
Gredy Eood
Werbs Casa Soadrr
(2.0))
Randon
Discurted Gready Baselise
1.30
Consienn
1:55
Ralenteaa
0.75-
1.01
0.50
0.75
Figure 3: Experimental results on You (top) and Yahoo datasets (bottom) using different predictions for varying a. The solid lines show our algorithm and the dashed lines the random- mixture algorithm. We run the algorithms 5 times and report average for both algorithms and the standard deviation only for our algorithm, to avoid clutter. For the robustness, the black line shows the performance of the worst-case algorithm without predictions due to Feldman et al.) (2009)). For each predictor, we also include in parentheses the average competitive ratio over runs (c.g. PreviousDay (0.66) indicates that the average competitive ratio for the solution of the Previous Day prediction was 0.66). We run the random-mixture algorithm for each prediction and == 1/a.
DualBaze OPT random corruption
OPT bizsed corruption
1.00
2.5
Comistency
Robustress
0.98
2.0
0.96
1.5
0.94
101
0.4
0.6
1.0
0.4
0.6
0.8
1.0
Prediction Compatitionnes
Prediction Competitiveness
DusiRave
OPT compuption
OPT bissed commpttion
1.00
Consinency
Robuztnes ess
0:95
0.00
0.2
0.2
Prediction Competiivennss
Prediction
Compalitiennes
Figure 4: Performance of algorithm on the iPin You (top) and Yahoo (bottom) datasets for with predictions of varying quality obtained as follows: We vary the sample fraction E [0, 1] for the dual base algorithm and p E [0, 1] for random and biased corruptions. The prediction competitiveness is defined as PRD/OPT.
(2) Dual Base: We generate a solution using the algorithm Devanur and Hayes (2009). Here, we sample the initial e-fraction of all impressions and optimally solve scaled version of the dual LP to obtain the dual variables {Ba) g We get primal allocation for all future impressions by allocating to the advertiser that maximizes the discounted gain Wat Ba. but do not update 8...
(3) Previous Day: We look at all impressions from the previous day and optimally solve the dual LP offline to obtain dual variables [.3]... To get a prediction for today's 's impressions, we use the same algorithm as above and allocate to the advertiser maximizing the discounted gain.
Real- World Instances: We generate two instances for Display Ads based on the real-word datasets iPin You (Zhang et al. 2014) and Yahoo Yahhoo! 2011).
8

---

(1.00 Duffboo
uasoon pomplton p (077)
Mittet Graad Baadin
Dicounta Grendy Bouckee Cans-Case Basiin
bosel own gu (622)))
1/1
Cookoerry
1.-
Figure 5: Experimental results for varying values of on synthetic data with 12 advertisers and 2000 impressions of 10 types, where we report the same quantities as in Figureßi We use different predictors with 1.5. We conducted experiments with significantly more or less impressions, where we obtain similar results, and we therefore omit these.
(1) YPinYou: The iPin dataset contains real-time bidding data from the iPin You online adver- tisement exchange. This dataset contains 40372 impressions over days and 301 advertisers. Each advertiser places multiple bids for an impression. We use this bid data to construct the dataset. Specifically, we set the maximum of those bids as the advertiser's valuation. We assume a constant budget for each advertiser of 10 impressions as it makes for an interesting instance.
(2) Yahoo: We replicate the experimental setup of Lavastida et al. (2021) who generated an instance of online capacitated bipartite matching based on Yahoo dataset Yahoo 2011). Capacitated online bipartite matching special case of Display Ads where all impression values are Based on this dataset, we create an instance of capacitated online bipartite matching with around 2 million impressions and 16268 advertisers for 123 days. We defer the details to Section C.T
Synthetic Instances: We obtain random synthetic data for a fixed set of T impressions and advertisers as follows. We first generate a of impression types, whereas each type is meant to model a group of homogeneous users (e.g. similar demographic or using similar keywords) and advertisers value users from the same group identically. We sample an advertiser's 's valuation for each impression type from an exponential distribution. To represent a full day of impressions, we assume that display times of impressions from a certain type are distributed according to a Gaussian with some uniformly random mean in [0, 1] and a fixed standard deviation a. We then sample the same number of impressions from each type along with display times, and order them increasing display time. Finally, we equip each advertiser with some fixed budget that makes for a difficult instance.
Figure and Figure 5 show results for real-world and synthetic instances, respectively. For each predictor, we show the consistency (left) and robustness (right) for varying a. Figure Asoows with predictions of different quality, described in the figure caption.
Results:
results for
Discussion: We make several observations. On real-world instances, there is only a single prediction for which the performance of our algorithm drops below the worst-case algorithm, even for heavily corrupted predictions. E.g., on the YPin dataset, our algorithm is still able to leverage a prediction with corruption rate high p 50%. and improve upon the worst-case algorithm (see the green and black lines in the top right plot of Figure 3.. Moreover, for higher performing predictors, the improvement over the worst-case algorithm is significantly higher in both datasets. See for example, the Previous Day predictions on the iPin You dataset (the purple and black lines in the top right plot of Figure 3) or Dual Base predictions on the Yahoo dataset (the orange and black lines in the bottom right plot of Figure 3). The increase in robustness is surprising as it does not follow the behavior of theoretical bounds (ef. Figure 2 which hold against an adversarial prediction. This suggests that on real-world data, our algorithm is able to exploit "good suggestions" from the prediction while ignoring "bad suggestions". Second, as we can see in Figure 3 the consistency of our algorithm for predictors except the optimum is always above 1, and is sigmificantly high for artificially corrupted predictions. The robustness of our algorithm remains high in almost all cases, even for the most heavily corrupted predictions (cf. the right side of Figure 4.. On synthetic instances, we observe that our algorithm is robust against both random and biased corruption, as the robustness does not drop to the prediction's 's low competitiveness of z 0.7. Furthermore, our algorithm performs well in combination with the dual base prediction for = 0.1 (the orange line in Figure even though the first 200 impressions are not representative of all impressions. On all instances, we clearly outperform the mandom-mixtu algorithm which merely interpolates between the objective values of the casst-case algorithm and the prediction.

---

Conclusion
We introduce a novel algorithm with predictions for Display Ads and GAP with free disposal. Our algorithm is based on the primal-dual approach and can be efficiently implemented in practice. We show its robustness using the primal-dual method similar to Feldman et al. (2009a) and use a novel combinatorial proof to show its consistency. Finally, our algorithm, which able to improve beyond the worst-case performance using readily available predictions. An interesting direction left open by work is understand the optimal trade-off between robustness and consistency for Display Ads and GAP. This challenging direction has been explored recently in the works (Jin and Ma [022] Wei and Zhang 2020) for related problem. Limitations: Our algorithm requires a strong prediction that is a solution to the problem. We leave weaker predictions, such as partial solutions or predictions of the supply, for future work.
experiments show the applicabilityy of
Acknowledgments
FS and AE were supported in part by NSF CAREER grant CCF-1750333, NSF grant III-1908510, and an Alfred P. Sloan Research Fellowship.
References
Shipra Agrawal, Morteza Zadimoghaddam, and Vahab Mirrokni. Proportional allocation: Sim- plc, distributed, and diverse matching with high entropy. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 99-108. PMLR, 10-15 Jul 2018. URL httpps:/prroceedings mlr wwwpppressvvee www.waal8a.abbrrreoaaa
Niv Buchbinder and (Seffi) Joseph Naor. The design of competitive online algorithms via a primal: Dual approach. Found. Trends Theor. Comput. Sci., 3(2-3):93-263, feb 2009, ISSN 1551-305X.
doi: 10.1561/04000000224 URL https:ts:://dot org/ 10. 10tt//0000111100000000022
Niv Buchbinder, Kamal Jain, and Joseph (Seffi) Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms ESA 2007, pages 253-264, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540- 75520-3.
Justin Y. Chen and Piotr Indyk. Online bipartite matching with predicted degrees. abs/2110. 1439, 2021. URL httpstts::////// http://arxiw..or//a////11//0
CoRR,
Nikhil Devanur and Thomas P. Hayes. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In ACM Conference on Electronic Commerce. Association for Computing Machinery, Inc., January 2009.
Nikhil R. Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, page 388-48 404, New York, NY, USA, 2012. Association for Computing Machinery. ISBN htttps////// org/ 10. 1145/222012
9781450314152. doi: 00.1145/229912.2229960 2229043
Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin Pâl. Online ad assignment with free disposal. In Workshop of Internet Economics (WINE), pages 374-385 2009a.
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-e/e. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117-126, 2009b.
doi: 10. 109/FOCS.2009 2009.72.
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In Mark de Berg and Ulrich Meyer, editors, Algorithms ESA 2010, pages 182-194, Berlin, Heidelherg, 2010. Springer Berlin Heidelberg. ISBN 978-3-
642-15775-2.
10

---

Yiding Feng, Rad Niazadeh, and Amin Saberi. Two-stage stochastic matching with application to ride hailing. In SODA. pages 2862-2877. SIAM, 2021.
Billy Jin and Will Ma. Online bipartite matching with advice: Tight robustness-conniisennyy tradeoff's for the two-stage model. In NeurIPS, 2022.
Billy Jin and David P. Williamson. Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model. In Michal Feldman, Hu Fu, and Inbal Talgam-Cohen, Cohen, editors, Web and Internet Economics, pages 207-225, Cham, 2022. Springer International Publishing. ISBN 978-3-030-94666-0.
Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the Forty-Thine Annual ACM Symposium Theory of Computing, STOC 11, page 587-596, 596, New York, NY. USA, 2011 1. Association for Computing Machinery. ISBN 978 9781450306911. doi: 10. 10.1145/1993636.J 1993715. URL https: org 10///10.11 1145/ 1993636. 1998715
R. M. Karp. U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite match- ing. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC '90, page 352-358, New York. NY, USA, 1990. Association for Computing Machinery. ISBN 0897913612. doi: 10.1145/1002116100066. URL htttps:://oo.oorg/110. 1145/100216 100262
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online Scheduling via Learned Weights, pages 1859-1877. 2020. doi: 10. 10.113377.9971111199999941 URL
https://epubs. siam.
Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Using Predicted Weights for Ad Delivery, pages 21 21-31. 2021. doi:
0Tt.///9981111197688 URL http::ttss:ppppe s siam
org/doi/ 10. 1137/1 9T11//1..977111176683000
Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Proceedings of the 8th ACM Conference on Electronic Commerce, EC '07, page 288-294, New York, NY, USA, 2007, Association for Computing Machinery. ISBN 9781595936530. doi: 10. 10.1145/1209910 1250952
//doi. org/10. 01145/1209111
Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid pre- dictions. In Proceedings of the 31t International Conference Neural Information Processing Systems, NIPS' 17, page 1856-1864, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8 (4):265 368, 2013. URL //dx:p://dxxox/ org 1tt1:/10.11100000000000000 1561/0400000057
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. ACM, 54(5), oct 2007. ISSN 0004-5411, doi: 10.1 (0.1145/1284320 1283321. URL.
https://doi.org: /tt////0ooo..///0...//// 11000..14444
1284321
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7):
33-35. jun 2022. ISSN 0001-0782. doi: 10. 10.1145/3528087. URI. httth::////// org/10.11155 3528087
Alexander Wei and Fred Zhang. Optimal robustness-consiisennyy trade-off's for leamiig-augmented online algorithms. In NeurIPS, 2020.
Yahoo. Yahoo! webscope, 2011. URL https::/ sandbox. yahoo. ywm.o.coo.. September 2022.
Accessed
Weinan Zhang, Shuai Yuan, Jun Wang, and Xuchua Shen. Real-time bidding benchmarking with ipinyou dataset, 2014. URL https: / //axxv/vvvv////////////aa//aaaa/ wwwrii..rg////eee abs/ 144007077

---

A Omitted Proofs
We will need the following helper Lemma in the proofs of consistency and robustness.
Lemma 2. Recall that eg (1 )²² and ag B a/BB
( -11) 1).
We have
1. EB S EB. and
2. QB aB.
Proof. It is well known that en converges to from below for B - co. Furthermore, we can show that 0g is decreasing in for all a 2 by taking the derivative
0 0B
a
1
a-1
a-1
(1 11-0) 01)
B
+
B
B
B
1 a-1
1-0
1
-1=0
B
where the bound follows from Bernoulli's inequality, which states that 1+ & (1 + x)" for r 2 and (0, 1).
A.1 Proof of Theorem 1 (Robustness)
We write and D to denote the objective value of the primal and dual solutions, i.e. P Ea Eies, Wat and D = E. Baga + E, 24 where 2, is specified in the following proof sure feasibility. We can show that after the allocation of each impression t,
CB
AP2
AD
Beg
o C
where AP and AD are the increase in the primal and dual solution values, respectively. Since we create feasible primal and dual solutions, this is sufficient bound the robustness due to weak duality, There is one main difference to Feldman et al. 2009a):: In their algorithm, setting the dual variable to W B. ensures dual feasibility ((EXP) is the advertiser with maximum discounted gain. However, in order not to violate dual feasibility when following the prediction, we need to increase the dual variables by a factor of ag. Note that for 1, this recovers the competitiveness obtained by Feldman et al. 2009a).
Proof. Consider iteration where assign an impression to advertiser and let w1 W12 I Wn, be the values of impressions currently allocated to a in non-decreasing order. Let up be the least valuable of the impressions allocated
the end of iteration 1, i.e. the impression that is removed to make space for f. Assume that after allocating impression to a, it becomes the k-th least valuable impression allocated with value wat wk. Thus, using that wy 2 wi-1,
can bound
a Ba B.
B.
g(t-1) 1)
alB, 11/BB WFCB. B.
Σ
B. aBBa-i)/B,
-1
1
WFCB.
B.
i=k+1
a/ Ba
B BB-B-i-))BB
B
B,
a(B.-()) -i) BB.
Wif B.
(w: Wi 1)
B,
1=0
k=
B/B.
BB--1
B
aBB (Ba-i-1))
8(
W.C
B
eg_
which is tight when impression! / becomes the most valuable impression assigned to a. We can now write g(()) as function of the bound 3 (t-1))
a/B.
B
B(L)
e
B.
a(B. -0/B. Ba
w.e W B,
B
12

---

Bn
B --1
B.
BB, B. +WB. WbEB. Ba
W Ba
B,
-1
1=0
a/Ba
Ba
of Ba
Ba
a/Bu
Ba
Ba
W/:-1 WB-1BB. Ba
a(Bu-i Ba
Ba
(WB. WDF
Bn
-1
i=1
BBa
Ba
a/ Be ((1-1)
1)
C
B.
(WB, woe
Ba
P0
BB.
Pa 1 which is feasible as the discounted value wat - 1(1 of the
We set 21 = aB UBB."
chosen advertiser may only be ag-times less the maximum discounted value Wacexey& pl due to the advantage of the predicted advertiser. This yields dual increase of
Ba (3!0 ((t-1))
AD
+ 2
Ba
8(0) a
8(t-1)
+ aB
WB. - 3(t-1)
s Ba
((0 P
(t-1)) 1)
+ 0B
WB. - 3((-11)
a
a/ Bo -
Ba
BBa
a/
g(t-1) +
B,
(WB, -Wo
+ tBB (BB, - -1
BB
BB (t-1) +
a
(WB.
wp + 0
WB. Pa
3(1-1))
ca
BB
(
aB
B((-1)
+aB WB. -3(1-1)
BB a
w
WB.
a BB
Rg
20
20
< 0
a
B
(3(0-1) - wo
a
+
QB
WB.
-//1-11 + aB
WB. - -((-11)
-1
C
BB
(3(0-1)
a
WB. - B8(-1)
0B
(
w0
+ 0:
CB
1
B
a o/B
a
0B (WB. - wo) = B
BB (WBB - wp)
BB 1
where the second inequality is due ag aB, and eB S BB.,, shown in Lemma 2
A.2 Proof of Theorem
|
(Consistenncy)
In the following, we upper bound PRD using the comparison Line of Algorithm Lemma 3. We have
PRD < Σ (a)
Σ
Wat - B(1-1))
Σ
Wat
O
IEX.AP.
tEPaNX.
Proof. We first split impressions into two categories: Either the algorithm followed the prediction and assigned t to (! = (PRD)'' or the algorithm ignored the prediction and assigned t to a
(2) (t) (EEP)) # (PRDD)- In the latter case, due the selection rule in Line of Algorithm
3 (1-11)
3(t-1)
an w. "ORRD)
(6) (PRD)
< w
(EXP) 8
66
(RXP)
In symbols,
PRD
Σ
Σ
Wat +
Wat
a
rEP XX
LEPaNX.
13

---

((1-1)
1
g((=))) Spexp:
w
(0)
War
aB
rEP
1X,
tEPanx,
3((-1)
E
Wat 1
E
Wat
Q IEX,)P.
XX,
tEP..X.
(t)
where the last equality holds because (Pa), Ja and {Xa}, are both partitioning the set all impressions due to the introduction of the dummy advertise For (t), we use that Ba can only increase in each round and bound
3 g S ( La) (8
tEP X
For the remainder of this section, we consider a fixed advertiser a. Let us denote with i; the i-th impression allocated to a. Let
Wat - 3/4 301-11)
Wat
0B IP..)P.
tEP
as part of the the bound on PRD Lemma
In order to understand this bound, we make some useful observations in the following lemma to simplify the analysis. The key idea is that may assume that impressions in X, ordered to be non-decreasing. In particular, we need to argue that the sum ΣxEx, (P. gft-1) can only decrease (as this term is negated in (+)) when impressions in X, are ordered to be non-decreasing: Intuitively, each 3(*-1) depends only on the B, most valuable impressions assigned before impression t, no matter the order in which (t-1) arrived. We can thus minimize each 3 gt- if the impressions allocated prior to t are the impressions of smallest value. To simultancously minimize each 8( in the sum, we order the impressions in X₂ to have non-decreasing value. We prove this simplification formally in the following lemma.
Lemma 4. Without loss of generality, may assume that PanXa are the most valuable impressions in X., and that impressions in X., arrive such that their values are non-decreasing.
Proof. We may assume that the impressions in Pa n X, are the most valuable impressions in X,: this can only increase the value of P. but leaves S,, unaffected, as So are by design the B, most valuable impressions in X,, All impressions in (x) are from X,, so reordering impressions only affects (+). Specifically, values in X, ordered to be non-decreasing. Assume the contrary that the i-th impression added to a the last that is order. That is Was, I Wat, S ... S Wat, and there exists a I such that Watz-1 S Wetc+1 < Waty. Moving 4i+1 ahead to its ranked position within the first impressions allocated to a changes the ordering as follows (the first and second row show the impression values before and after changing the position of 44+1, respectively):
show that the sum Σiex, XP. a6(-1) in (+) is minimized if the
Watr < ... < Wat, S Wat,
S WWaty+ S S... < Wats
Wat, < ... Wat; 1 < Water1 Wat, 5... < Wat;
Note that each position decreases in value, even strictly the j-th position. As such, the exponential
average (((-1) decreases as well for < 1++1; it remains constant for 2 4++1 as it only depends on the R, most valuable impressions assigned up / which remain the same. We can thus simultaneously
minimize git) for each by putting X, in non-decreasing order. This reordering does not affect (T()) or the other terms in (x), may indeed assume that values are non-decreasing.
In light of Lemma we write (+) follows.
14

---

Lemma 5. We have
La-2a (+) = a Σ
La
Wat: 3(t1-1))
+
Wat
la fa+1
Proof. Impression values are non-decreasing due to Lemma impression in X.- The impressions (Ta la 1 ,.... Ia] X O Pa are thus the most valuable. We can now write (+) as
so War, is the i-th least valuable
Σ
Wat 1
5/ B((-11)
Σ
Σ
B((-1))
Σ
Wat
Wat,
Wat,
aB PEX.AP.
aB
IEP
i=
where (l11-1 impression in {ti-1 + 14 } was allocated to a.
o(ln-1) there was no change the dual variable of advertiser a since no
Combining Lemmas and 5 obtain: Lemma 6. PRD < En PRD, where
1 la
Ia Wat, + (Ia La) ((T).
PRD, = QB
Was. Bl(-1))
In the following, we use the non non-decreasing ordering of impressions in X, to compute ((t+-)) and bound PRD, with linear combination of values Wat, Consider the j-th impression t, allocated to a. Since we assume that impression values are non-decreasing, we know that becomes the most valuable impression right after it is allocated. After the allocation of the (j + 1)-th impres- sion to it becomes the second most valuable impression, and so forth, until it is disposed after the allocation of the (j B2)-th impression. The value Wat, therefore appears alongside each
coefficient in the convex combination that defines (((--1) for {j + j + B.). Expanding each (1t g(4+-1) in the sum E/- fo g(tr-1) in PRD we thus observe that the coefficients of values Wat, for j S La Le Ba sum up to We use this fact cancel out most of the values in DLa Wat. What remains are only the values Wat, for E {Le la Ba + 1...., la La For i T (I. la B2 + +,...., - Ba), we bound Wat, by Watz, Ba which really the best we can hope for. Formally, we show:
Lemma 7, We have
Ta-La
PRD S
Σ
DtWat, +
Σ
waw Wats, Ba Da
-l,-B.+1
i=l 10
with coefficients
a/B, B,
a(l, EGs -i)/Ba
6, = (Ba La)
Ba
B
alTa
-i/B B,
1 EB
B.
80
QB
a
Ba
1i = 1 + (Ba
(a)
B
B
allo
Bi)BB
BB
a(B,- -ka)/B. Ba B.
1 Ωg B C
a B
6 B.
Proof. We start by rewriting the terms in PRD, individually. Since assume that the values are non-dccreasing, we can express g(t--1) as the exponential average of values Wat, Bu ... Wat,., of the last B, impressions (for simplicity, set Wat, = 0 for j < 0). Summing over multiple iterations, we thus obtain for the sum over the dual variables that
Ta-fa
a/Ba B
(t:-1)
a(t-j-1)/B.
Pa
Wat, C..
0 f=1 j=i-b
-1
15

---

o//B
Bu
min
Bu.lo-Pa
B,
Σ
a(i-j-1)/B.
Watz
Bn
BB
A=j+1
o/Ba
BB
la
min Ba.d--las1
B
a
Wal,
B.
1
B
o/Ba
BB
B -la
L
B.
a(i-1)/R, B)
Wat;
Ba
B,
1=1
a/B Ba
la-la
I 1--4-1
a(i-1)/Ba
We
Ba
Ba
j=
B, fa+
Ia Ba-La
La-ka
(a(l)-lo- -1)
Wat; +
Wat;
CBa,
BB
t= B +4+1
where for the last equality, we use that the two inner sums are geometric. We can use this expression to cancel out most of the terms of the first sum in PRD,,
ta
(8(-11)
Wart
I. - B -ta
1
alle Callo-ka-i BiiiB/Ba -1
Wat:
Wat:
Wat;
CB
0B (CB. 1)
i=1
1=1
i=l, B, +4+1
1 Ta
alIn -la la-iB/B.
Ba
Wat:
1
BB,
a
i= BB, +1
alla -la Ba
BB
BB,
Wat:
BB
i=l--Ba-
14-
alla -la -i)BB
B
a(l -l
BB
C Ba
B.
B.
Wat:
Wat;
en -1
i= B.+
BB
We use that War. S Watz, Ba for all i < La - Ba to upper bound the second sum, divided by a,,, in
to
1 B
8 alla -b, fo- -i)BBa
Wat.
0. i=l, B. +l
B. -1
I Ba
a(,, -la L1-1//B.
< Watis Ba aB i=ln - B. -a+1
Σ
BB
B,
(4)
B -1
BS
ai/ Ba EB
aa Watis Ba an B,
i=
al B. -fa)BB. Ba
Watis Ba ag eg.
1
1
laca
a
B,
e Ba
(5)
-1
o Ba 1
B.
=
Furthermore, by definition of ((T) g(tia)
(Ba (a) (()
BB, la)
B
Wat. CB.
(lI--)/BB.
(6)
i=
16

---

We combine 3.
5 and (6) and group terms to obtain the desired bound
fa
la
la
aff fa (a-i)/
PRD, S
Wat: +
Wat
B.
Ba
+ Watt-- Da
0B
Bg
-1
im la t1
i=
Ba-1
R Ba
(Ba - la)
Ba
Σ
C
CB.
a(la-i)/B,
ea
Ba
i=l Ba+1
la-Ba
a Ba -1
alla - Bb
Wat:
(Be la)
Ba
CB
a(l.
-1/BB,
1 EB.
BB
B. 1
ag
im la - Ba+1
=0:
La
a/Ba
Wat:
1 (Bo - (a)
B,
ea
alla - 1)/Ba
Bn
+WI,, - B, Zo
i= +++1
V1
can express ALG analogously:
Lemma 8. We have ALG En ALG, where
ALG. =
Wal.
Proof. We have ALG E. Wat- As we always dispose of the least valuable impression in Algorithm [ S, are the B., most valuable impressions in X.. Due to Lemma these are Ele,-
S. = [1a B. ,a and hence Eies, Wat Li=l.
Wat, ALG..
We upper bound the ratio PRD/ALG by max, PRD. PALL/ALG.. To this end, we fix advertiser and upper bound the ratio PRD,/ALC AALG. Recall from Lemmas 7 and g that we can express PRD, and ALG,, linear combination comparing impression value coefficients. However, in the following lemma, we show how to use the non-decreasing ordering due Lemma to obtain tighter bound.
impression values. We could obtain natural upper bound by
We define
1
and
1//
i=,, B,+1
+1
the total factor mass values Wat, for de and the respectively. Let Ta ($. + V. + Qaa) /B. be the average factor. Recall that
Tw-
PRD,
Σ
D:Wat +
thw + Watz, B. Ps
-lh-BB+1
i= 21
ALG.
Σ
Wat.
-1+
In the following lemma, we use that Wat, S Wat, for S j due to Lemma to further upper bound the RHS by linear combination of the values, where move mass from coefficients on Was, to coefficients on Wat, Additionally, we move mass from Q2 to coefficients Φ; for (Ia - B, + 1,..., la {n) and from Φ; to tb for j E (La la + I...., Ia]. In the best case, we are able to redistribute mass equally across all values, in which case the consistency is given as the average factor Ta- Otherwise, the factors on the largest values dominate, giving us a consistency of V Valla
17

---

Lemma 9. We have
PRDa
max
Va Taz to
ifla > 0 otherwise
ALGa
Ta
where
1+
BB.
B
-1
aB
BB
and
ala/
BB
V/ a aa
BB
CB
1
1+
Ea
Ba
Proof. We calculate Ta and Ma/La separately in Lemma 10 below. Our main goal is to distribute mass from the factors dis t4, and from 22 equally to the values taking a closer look at the factors 6; and vú First, note that d/ is always decreasing in i as
WI,- We begin by
Ba
4 1 (Be
La)
B
BBa
alla-i/B.
20
We can therefore bound the linear combination over values value Wy = 1 E/a tu -1 Wat, as
4Lo la + 1, ,,...,........................
,....,,,a! Lo} using the average
In
In
Σ
Wat v
Σ
Wyth
= Wy Va-
(8)
T +1
im fa+1
However, di is not always decreasing which can be seen by rearranging
a/Ba
alI. -i1
Φi (Ba - La)
BB.
caa
(ToTo-))/ -i)BB
1
B.
B.
BB
-1
OB
B
B. (Bu la) La) (a))(e))
cooBo- (Bo (1)
aa
alle
B 0B CB. -
e BB.
CB.
+
aB
We observe that di is decreasing if (Bu - la)
CB.
aaB.
- 1) is least att//B B. and we analyze
ag CB.
two cases based on the relationship of both terms.
Let first assume that (B, la) ( aa/BB 1) as e B.
aLl/BB. such that di is decreasing in 7 over {La Ba + I,..., la and
which helps us bound the linear combinations in Lemma
(Ia - la + 1...., T} by the average values We == B. Li=h. B. Wat, and the respectively.
We further use that Wati--P. S Th charge mass from P2 to Q and obtain due to ( that
Σ
Wat, 6. +
Wat; 24 + Wats, So
i= B.
s= +1
Ws 4. + Ty v Worl. Zg
(9)
Ws ( Qa) Ww Va
ws BBa - la) Ta + To ( + Ω2 - (Ba - -aa
Ta) + t V
la to
Σ
Wa + wh (Φ. + Sp - (Ba (a)
Ta) + T V.
(10)
-=lt-Ba+1
On the other hand, if (B, - ta)
a/BBa ca/Ba
ala/Ba -la/ we can no longer bound the values an n.
B.
over (4a Bg + I,..., La) by the average value Vg. However, each factor o; is less than Ta which can be seen by rearranging
18

---

Φ BB
(Bo - La)
CBa
a/Ba
e Ba
ata/BB /Bo
BB.
all--1 -il-ii/B. B
Bg
a
a Ba
1
B.
S 1
BB
=
B
1 aB
to the equivalent expression
lo) (Ba - La)
(Baa
B/Ba
-
1)
BB
ola/Ba
Ba
alla-1)
Ba
20
20
1
B
I 0
( 1)
0.B
QB.
aB.
20
which is true since the LHS is <. 0 and the RHS > O. We can thus charge To Oi of mass from Ωg the coefficients oi for each E {La Ba + ....... La fa} which yields
Jn
Wat. +
Σ
Wot: vo + Walss Po
B1
lat1
la
Wat, ds + Th Vo + Watss Ba La
t= Ba+1
La
La
Ta Wat;
Σ
Wat; (Ta (h)) +w Va + Watse Ba Da
(=1, B1+1
i=la-Ba
20
la-ta
La-la
Ta Wat
Wati no (Ta (Ta-))) 0i) + W.y Va + Watia-n Da
im Ba+1
la Bl+1
La-la
Ta Wat, + Wats,
(Da + Pa - -Baa - [a) + Uy Va
(11)
im
In both cases
(10 and
we have shown that
ln-ba
In Σ
Σ
Wat 0i
War, the
Wasto Ba Zr
I-lo-B.-
-la-
Ia
Σ
TaWat, + ( + Q2 (B, - Ta) + thg Vo
i=1a-B.+1
for a 1 < We. If la O,
we charge the remaining mass N, if the factors over (Ia C, + 1.... T} leave enough space. In symbols, this means
La la
Wataa, + ($. +2 - (B. (a) + Tv V
i= T= T-T-BB-1 B.-1
1a la
Σ i=T-B.+l
Ta Wat, + Wy max (T + S2 -Ba Ea) Ta. 0} + th V
Ln-la
Σ
Ta Wat, Wy max {T_ Va Q2 (B, la) Ta. Va
i= Bu++
Σ
Ta Wat, Wy max flata, Va
T-T-B. BT++B.+1
19

---

1a ta
Ia
Val Fas
S To
Wat, + max
Waf
la
1= Ba +1
i= ta+t
V
max
Tar
Wat-
Lu
tES.
If la O, have V. 0 and immediately obtain by definition of Ta that
La-ba
Wa + 2 ( + 2a -B,, -aa) + Uv V.
Σ
WaWats-
A Ba+1
i=
Ba+1
Lemma 10. We have
ala/Ba
V.
Ba
B.
1 +
la
la
e
Ba
and
1
B.
Ta 1 +
B.
Ba
aB
a a.a
Proof. We compute
T-la
Pa
Σ
Φi
B.
T-h
(Ba -Ba La) (a)
a/B.
-1)
aLa/BB
a(T-i)/B.
1
a
Bg
Ea
-
CB.
aB
Bu
B
Q
E
T- Ba+1
ola/ Ba
(Ba -aa
aBBa -
-ata BBa
BB
BB.
+ (Ba - Ea)
1
BB.
BB, -1
Bn
Ba
BB
Ba
OB BB.
a- Bu
BB -1
(Ba - -aa
CB.
BBa
ala/
Ba
Q
C..
B
1
aB
1
BB.
CB.
0 Ba 1
and
Va
ti
i=
a/B.
1 (Ba La)
BB
(T 11)
a
B
(=T-1a+1
a/B,
1 at./B, Ba 1
CB
la + (B,
Eg)
B.
e Ba
B.
ata! Ba B
= la + (Ba ta)
BB
1
Summing up.
Q + V + Ss
ct... BB
αa (Ba - Ea)
1
Cn CB.
ata/Ba Ba
+
CB.
1
1
e B
ag
1 aB
a/ Ba 1
B
ala/Ba -
al Ba
-la)/
+ lg + (Ba la)
e B
1
Eee
B,
B.
Ba
-1
aa
e
B,
20

---

1
1
1
Bg 1
B
(Be
(a)
CBa
-1
aB
BB.
Ba
aB
E
Ba
+ +
Ba
e0
1
aB
Ba
B,
1
aB
1
(Bg
La)
BB
BA
QB
Ba
Ba
B
Bg
1
-
0
la
E Ba
= Ba
BaBB Ba
1
B
Bn
1
aB
CB.
-
QB BB
B
1
1
1
B.
B
Boe
B.
-aB
a Ba
Ba
which does no longer depend on la Dividing Va by la and 2, + u. ta by Ba yields the result.
Putting everything together, have PRD/ALC I max, max Ta max,, El..... B.] W /a/La as To does not depend on &.. The reader can refer back to Figure for an illustration of this upper bound. In the following lemma, we further analyze analytically max,, B.). V Va/C, and compare it with to obtain the upper bound:
(B.........
Lemma 11. The consistency of Algorithm is given by
PRD/ALG (1+
cB - In (e ((9))
max
c
cB -1
aB
a
Proof. Due to Lemma 9 is sufficient to show
1 1 max
CB
B
In
(c
max (Ta vo/Lo)
if lo > otherwise.
a
aB
Ta
By Lemma T0 know for the first term in the maximum that
1
Ba
1+
BB
BB
an
OB.
This term is maximized for B, B since
1
e
1+
BB.
-1
BB
1aB
Ba
B
a/ Ba
BB
1
1
1
< 1
+
B
B
0B
GB
0B
0
aB
=ip(a)
due to Lemma 2 The lemma statement therefore follows immediately if f, 0. We may thus
assume that lg and use Lemma 10 determine the second term the maximum
$
1
(2-1)
=
(e -1)
la
where x la/ la/Ba. The second term behaves similarly to the first
Q
-1-1) (ear -1) < 14
1 (--1) (c -
= 1
0 B.
since (e - 1) / (ch.
-1) 1) < (ear - 11) (c 1).
We define g(a,2) = ( - (e -
such that we can write
V + S4 Va
1
max
< +
cg - max (((a).g(a,))).
tg
21

---

We want to remove the dependency on z in g by maximizing over a E [0, for a fixed a. As g(a, x) is continuous, suffices evaluate g in both endpoints and find the stationary points. We have
g(a,0) - lim - -1) (eg - -1) lim a00
x) (EB
lim x-0
(cn
(1-)))lnnee))e = In(e
by L'Hoptial. Further, ( 1) = 0. Next, we find the stationary points x E [0, as solutions to the equation
(1) x
-1)
caa
ix ga ((,,x") x²) = -In(c))
B
= 0
(x+)2
which is equivalent to
(1
B 0z -1 In
oxx
B
x
There is no closed form solution for x", but we can replace en This yields a new function
g with the RHS of the above.
y ( (1-1))n(e31) In(eg))?
(--1)
h(a,
eS In(e)) (1 y)² eg
with h(a, x²) = g(a,," We can thus maximize over y E [0, 1] to obtain an upper bound on g(x*). Note that (oa, 0) = In(e@) = g(xx 0) and h(a, 1) = 0 = g 1). To this end, let y be such that
0
Ma. y ) (1- eg -ln(())) (1 y²)
oy
which is equivalent to (n(eg) (1 y²) - 0 y = Iu(eg))
We evaluate h in y and obtain
2 matnn
h(a, y²) = (neB)
a (n(()))
cB
In(eg)e CB.
Note that y" 0 = a 2 2/ In(e)). Furthermore, h² (a) always exceeds the endpoint g(a, 0): We calculate
h" (aa)) M(a,8)) In(eg) e² c
In In 2/2
Z In(eg e²
= In(e@)
where the inequality is due to e² 2 ez In
> 0. Therefore, for all æ E [0, 1]. (e
a/22
[n(e]]
if S In(eg)
g(a,)) <
(a)) otherwise.
We consider both intervals separately. Let first consider the the case when Jo, in(eg) If
B < there could be multiple intersection points between p(a:) and a In(e)). However, the situation easier if B >> 2o as the intersection points given by
p(a) = e
ar - 11=1- 3
and a² 1.79, whereas ar In(e)) dominates p(a:) between and a"
remains to consider the case 2 Iuten,)) Again, there can be many intersection points of p(a)
with a In(RR,)) and (a)). However, if B - oo, then p(a) already dominates h² (ax) for > 2 which we can see as follows. First,
1
e - = p(a)
h² (a(a)= a-2
a a
22

---

e
4e-
a
We can see that 1-e is decreasing in a as
i 11 -
(a
c² +1)
0
da
a²
which holds as 1+ S e". Finally, we check that (2) = 2.10 = p(2).
B Generalized Assignment Problem
The generalized assignment problem (GAP) is generalization of Display Ads where impressions t can take up any size that in the budget constraint advertiser a. This formulation encompasses both Display Ads and Ad Words, and empirically compare predictions due to Mahdian et al. (2007) in Section C.3 For simplicity of presentation, we assume that budgets are all and instead, Wat + O. However, before it possible adapt the algorithm to work with large sizes Wat. We state the LP below.
the Ad Words algorithm with
GAP Primal
GAP Dual
min Σ Be + Σ
max
Tat
ast
ya:
Σ Mattiat
S
Va,t: t: 2t Wat Uat
vt:
Σ Pat
Algorithm@2is generalization of Algorithm to GAP. An immediate difference is that the discounted gain Wat Ua respects the impression size Ver in accordance with the changed dual constraint. We still follow the predicted advertiser if its discounted gain still is a sufficiently high fraction of the maximum discounted gain. However, we might now have remove multiple impressions with least value-size ratio to accommodate the new impression. The update for 8g also differs and is based on value-size ratios of impressions allocated a: For fixed advertiser let Ug Σeex, Mat be the total size of all impressions ever allocated to a. For any x E (0, Ua] define wz as the minimal ratio such that
Σ
Uat x.
(12)
Then, we can naturally define Ba as the exponential average over ratios ex As before, we also assume that there exists a dummy advertiser that only receives impressions of zero value-size ratio and that all advertisers are initially filled up with impressions of zero value.
B.1 Robustness
Theorem 12. Algorithm 7 Jaas a robustness of
ALG
c 6-11
OPT
ave
Proof. Assume we assign impression advertiser while disposing of some impressions make space. We will bound the dual increase multiple of the primal increase. We now assume that after allocating a. it becomes the impression with highest value-size ratio (a general proof follows analogously to the proof of robustness for Display Ads in Section A.I) D). The primal increase is simply
Un
U--1
U.-1
Wz dr
WT.
Wz dx.
AP
dx Wat
U.-
Va-ual uat
Ux
Ua 1ut Bat Ux
U. - uut U2
23

---

Algorithm 2 Exponential Averaging with Predictions for GAP
Input: Robustness-consistene trade-off parameter a E [1, 00)
2: For each advertiser initialize Pa f 0 and fill up with zero-value impressions
3: for all arriving impressions do
4: ((PRD) < PRD(t)
5: ((EXP) f- arg maxa maxa Wat Uat
6: a a (WappD) ( 2 Wf(Exp) Marexp), ( (xxP))) then
7: a < ((PRD)
8: else
9:
a f- ((EXP)
10:
end if
11:
Dispose of impressions with least value-size ratio currently allocated to a until there uat of
free space and allocate t to
Un
Let az
in (2) and update 3n ca
W
a(U, -6) dx
U.
Up
13: end for
At the same time,
3(0
a
Wr alUa -x) dæ
ea
Un -1
Up
Un Mut
We e alU' xx) dr + for.
Us
Nu-1
a
We ealu -2) dx
We We cal -x) dx
a
U U-- -i-l-muge
Ux
U.- Ux
Ux
Un Hat
Un-1
a
Wz c (Un - x- uo- dee + Wat
W2 a(U x)) dor
6
U. -1 uut
U -1 use
Ux
UV-1
g(t
+
a
Wat 10-1-us. Ug
Wr ca(Us- -x) x)
6a -1
W1at Mate (6(1)) and obtain, since gauus
We set 2t =
Oclaat due to that -
AD g(t)
3(1-1) 1)
+ zt
U.-1
= am
-1) g( g(1-1) +
a
Wz all do + a (Wtt use 1(t
Wat
ea -
J.. 1-
Ux
Uu
atllat
1l--1)
4 2a -1
Wat
We e a(Ua-x2) dx
+ Wat uor
U.. aaa
Ux
Qg
a
U1-1
Wx dx
Waa
ea
1
U.
10 11
Uxz
ae
AP.
ea
B.2 Consistency
Theorem 13. Algorithm 7 Thss consistency of
ALG PRD
1 e E- ------1
-1
max
ca
As before, we split the impressions i. based on whether the algorithm followed the prediction or not. If the algorithm ignores the prediction, can that (Waraany Morra, <

---

W (x(p))) PaCEx)) due to Line 6 in Algorithm 2
With a similar calculation, we obtain
PRD Σ
2RD4
Σ
Σ
Wor +
Σ
Wht a BEX,iP.
Σ
1(t-1)
Σ
UarPa
((t
t.PaNX,
1EX.
DEP.
Once again, fix an advertiser a. Let Pa EiEPanx, Vot that can bound
Σ X.
BarBa ((t-1) a < - Pa) ((2)
We still have to argue that the worst-case is when all impressions are ordered such that their value-size ratios non-decreasing and the impressions in P. X are the ones with maximum value-size ratio among X.. The latter is obvious as can only increase the value of PRD, so remains to show that the non-decreasing value-size ordering minimizes the third sum in PRD, (the first two sums are invariant under reordering). To this end, note that the value of 8. for GAP is the limit of 3a for Display Ads in the following sense: For positive
0, can split each GAP-impression t E X, into di identical Display Ads-impressions with value " while assuming a budget of 1/c. u: Then, the GAP 3, and Display Ads 3, are identical. As we know from Display Ads, the worst case is achieved when the Display ads-impressions with value Be are in non-decreasing order. In this ordering, consecutive Display-Ads impressions with identical value = still correspond to the same GAP-impression t, also know that this ordering is the worst-case for GAP. We may therefore assume that the impressions are ordered such that their value-size ratios are non-decreasing. As such, obtain
us
(1)
3
Wr ca( - x) =
We (ly-a) ( de = (((0)
6
J
Ux
y-1 Up
where y U
Combined with the fact that P. X, are last impressions in Xa. we can now write
Σ
1
Mat ((1-1)
+
Wat
DX.
tEX,
P.
(EX, P.
U.
1 UU We
1 Us
Wx dx
dx
3(2) dx
Ju. p Ux
OK J
Ur
a
Jo
This helps us to compute g(x) PRD, and rewrite the whole term as a linear combination of value-size ratios.
Lemma 14. We have
Ue Pa ws
Uo Wz vode +
WU. -1 Ωa
PRD <
S +
U--1
U
Ux
WV,-1
where
1 L - -
62 (1 Pa)
80 a(U
a
2/ = + (1 - (po) -((
ςa -1
Ωg = 0 -
1
Pat" - (00l-ppppa)
Proof. We rewrite the third sum in PRD,,
Va-Pa PP
((x) dx
25

---

Q
Pa
Wy c (= dydx
ea
0
2-1 Uy
Pa
Wy
m, -
nD dxdy
e
Un 1- Pa Why
Un Un-Pu uy Up-Pa Po-
cat drdy +
a
drdy
0
uy
en
U. By 50
Un 1-11-ppp Pa Wy dy +
Ua Pa Wy (calUe-Ra- - dy
tly
e 1. By
where for the last equality, simply evaluated the integral. Using this in place of the second sum in PRD, cancels out most the terms the second sum:
Pa
Wz
Pa.
dr
31 dæ
0
Ux
00
Un
UUs - 1- Wy dy
Ua Ua-Pa
Wy (cllU=-p--V) -1) dy
dr
Ux
Uy
6 1
Un 1- By
Un
Pa
Wy
ca(Uu- - -v) -
dy
U.
Pa.
pa
U0 Po
By e²
(V@ pe -1)
dy
J.. 1-111-p
Pa
Uy
60 1
U. Po
Wy e"
caa -Pa-
1--1
Wy ea aaUuu- Pa) V)
dy +
dy.
(13)
JU
My eat
U. U.-11p4 1-p
Uy
ạ - 1
We upper bound the third sum
1 Ua-1
Wy 60
ca(Uu-Po-)
WV, 1
ạ (Pau--pa-))
dy
dy
0
U1-1-pa
uy
6a
uū Q U. e² 11
PaEa
eo
u0 ea -1
1-po
WU.
Pae
(0 ca(t-pa))
(14)
Uy.
=fa
Furthermore,
Un
(1 - Pa) 8(Ua) (1 Pa)
a
Wr (u dx
(15)
_ J.-1 Us
Combining 13
14
and
15) and grouping terms yields
Un Wx dx
Un-Pa
wy ea
ea(Uu--aa
dy + WT, -1 Ωa UV
1. Pa
+
Ux
a Ua-1
Uy
-1
Uu
Wr c(U cr.
+ (1
Pa) ạa
ca-1
Un-1
Ur
Un-Di Da We
ca ca(Ua-pe -pu xx)
(1 - Pa)
a
c
aa -x) +
dx
U--1 Ur
Ea
ea -1
=0z
Un
We
1 (1
Pa)
a xxU)-x)
dx WU. -1 Sr.. WV,
U.-Pa
Ur
Vi
26

---

Analogously to Display Ads, we define
Ul-Pa Pa
Ue
Pa
0zdx
and
Va
dx
Un-1
Up-p
and the total coefficient Ta == Pa + Va + Sgg which by a calculation similar to Lemma 10 can be shown to be
1
ea
1
Ta
e
a
Lemma 15. We have
V
PRD S max
Tas
ALG
Pa.
Pa and otherwise,
PRD S ALG.
Proof. Again, let
Ua 1P- Pa We dx
W6
Pa Un-1
Ux
1 Uv We dæ
By
Pa.
Un Ur
be the average coefficients the intervals (Ue 1, U, Pal and (Uo - Pas U.), respectively. The
latter coefficients are still decreasing as
2 = 11 Pa)
ea
20
so we can bound the linear combination
Ua
Un
Uadx S Uw
vadx Va.
Ua-pa Pa
Ux
U.-p
However, ow is not always decreasing which can be seen by rearranging
Φx = (1 - Pa)
6a - (a(Ui -x)
a
1 lea
(oa -Poa-Po-a ~a= 6 1
a
1
(1- Pa) a
-apa
1
calUa-o)
a
a
We observe that ou is decreasing if (1 - [o) a is at least ape and we analyze two cases based on the relationship of both terms:
a
(1-Pa) 1 ape; We have JU.-1 us
Un-Pa we
dn S we 4 a and thus
Up-Pa Pa Wx
Uo wx wadx + WU. WU.-1 Sa
dr +
11 Ux
Un-p Us
uVA-1
< We D1 + th V + Wa.1. B, Pa
we {$, Paa) + ww V,
wy (1 Pa) Ta + wg (i, + Ω2 - (1- (a) Ta) + Wig V
U, wx dx ws ( Sh (1 Pa) Ta) th V.
(16)
U--1
' pa) a < 1e ape; We can still show that 6o S Ta as
27

---

1 lea ea(ua-pa- Paalu-Pa-a PP-
Ox -1 (1=1pppl Pa)
a
alVa 1--0) 2)
60 -
6a
1
< 11
c
1a
1
1 c
(1 Pa) a -
aape
ca(Uu-x)
I e
c
a
Q
a
20
20
20
Therefore,
Pa wr
Nia We ddr +
WV, Ωa
2rdx +
U1 -1
U.-p
WV,-1
U1 Pa We drdr + th V
WU,-1 Gh
up
uU.-1
Ua
Pa
Un Pa
(Ta 6u) dx + Wy Va Wt, 11 Qa
Jadx
U0a
Us
Un-1
Up
uV.-1
Un
Pa
Wy
Un -Po WV.-1 (Ta 2xx) do + Ww V + MV,-1
Wib-11 Pa
Un-
U.-1
MU,-1
Un- Pa Wa
Wū.-1
Tadl +
(4a + Sha - (1 Paa) + tw Vo
(17)
Ug
UV.-1
In both cases (16) and 17 we have shown that
Us-Pa we drdx + f
UU we dhdrr
WU--1 Qr
JU.-1 ux J.-p us
4U.-1
Ua- Ua-Pa
Jadx (T, + Qaa (1 Pa) Ta) tv V
Ua-1
Up
for a v I WT.
U. Pa Wx
Tadr + 1 ( + Us (1 (1-pa)
Pa) Ta) + Wv Va
U--1
Ux
Pa
W/ dx + Tw max (2, + Sa -(1 - Pa)) Ta. 0} + tw V
<
U. -1
Ux
U.
Wz
radx + we max { + Va + S2 (1 Pa)) Tas Va
Jn 11
Ux
V.
Wz
Tadx Wy max (PaTas Val
U
Ux
-Po
Wz dx + max
Va U.
Wz dx
< Ta
Ta:
J.-1
Na Uu-pu U
Tar Va Un
wx dx
< max
Po U Ukz
No dr if Pa 00 0
S Ta Ju--1 us
Note that for the bound of Lemma we did not require that 4, is integral. We can thus apply
Lemma to bound max { Ta: and obtain the same result, which proves Theorem 13
28

---

0.2,
0.02 (0.56)
1.0,
0.02 (0.79)
Random Mixture
0.2,
0.2 (0.67)
1.0,
0.2 (0.83)
Worst- Case Baseline
1.8-
0.9
1.6
Consistency
Rolussteess
1.4
0.7
1.2-
1.0
Figure 6: Experimental results for varying values of synthetic data with 12 advertisers and 2000 impressions of 10 types, where we report the same quantities as in Figure We use Dual Base predictions for different a and Note that there are two black lines indicating the performance the worst-case algorithm without predictions, corresponding to the datasets with differing o.
DualBase
OPT random comruption
OPT biased corruption
0.950
Consistency
Robustresss
0.925
0.900
0.4
1.0
0.1
0.6
1.0
Prediction
Competitiveness
Prediction Competitiveness
DualBase
OPT
corruption
corruption
Consistency
Robustress
0.9
0.8
0.7
0.2
0.4
0.6
0.8
0.2
0.4
0.6
1.0
Competitiveness
Prediction
Competitiveness
Figure 7: Performance for varying prediction quality with the data from Figure (top) for = 2 (top) and a 5 (bottom).
C Further Experimental Results
C.1 Real-Worke Data
Description of the Yahoo Dataset:
The original dataset contains impression allocations to 16268 advertisers throughout 123 days, each tagged with the advertiser that bought the impression and set of keyphrases that categorize the user for whom the impression is displayed, Lavastida et al. (20TT) then consider the 20 most common keyphrases and create an impression type for each non empty subset thereof. Whenever an advertiser buys an impression with a certain set of keyphrases, we assume that all impression types that correspond to a superset of these keyphrases are relevant for this advertiser, and that derives some constant value (say, 1) from this allocation. At the same time, the number of impressions we create from each impression type (i.e. the supply) is the number of impression allocations in the original dataset that show that the impression type relevant an advertiser. As such, we obtain around 2 million impressions. Lavastida et al. 2021 try multiple
29

---

OPT
OPT bissed comppttinn p= (0.73)
Wore-Case Baseline
DualBase (0.63)
OPT biased corruption p (0.81)
1.2
1.0
Consexency
1.0
Rolssttres
0.9
0.8
0.6
Figure 8: Performance on worst-case instance with different predictors.
impression orders and budgets the advertisers, but due to space constraints we restrict ourselves to display all impressions of type at once, in supply-ascending order. We determine advertisers' budgets by allocating each impression to one of the advertisers with non-zero valuation uniformly at random and taking the number of allocated impressions at the end to be the advertiser's budget.
C.2 Synthetic Data
Results: Figure 5 shows consistency and robustness of our algorithm on synthetic data on T = 2000 impressions TO types and k 12 advertisers, for variation of predictions. The plot shows the performance for predictions from the optimum solutions (with varying corruption) and the dual base prediction. Our algorithm converges to almost perfect consistency and robustness for a 10, given the optimum solution. At the same time, we observe that the algorithm is robust against both random and biased corruption, as robustness does not drop to the prediction's low competitiveness of around 0.7. Furthermore, the algorithm performs well in combination with the dual base prediction for e = 0.1 even though the first 200 impressions are clearly not representative all synthetically generated impressions.
To investigate the our algorithm in conjunction with an easily available prediction, we also analyze the behavior of the dual base algorithm for different values of a and c in Figure 6 The performance of our algorithm under dual base predictions clearly improves for increasing values of a as impressions become more evenly distributed across the day. Generally, sampling more impressions helps but dual base predictions may also lead to drop in robustness, and more samples can even lead to a more adversarial prediction, as we explore further below. Yet, the robustness does still stays above the prediction's is competitiveness in these cases.
Figure 7 shows consistency and robustness for different predictions with varying competitiveness on (2, We achieve this by varying the fraction E [0, 1] of samples for the dual base algorithm and the corruption rate E [0, 1] for random and biased corruptions. For a 2, the consistency exceeds 1 the prediction not very good (competitiveness below 0.9). The algorithm influenced by a bad prediction since = is low, so the total obtained value remains relatively constant. For 5, the algorithm might however follow the bad choices of the prediction, so the competitiveness varies more. As expected, the average robustness decreases for increasing a, but dual base prediction starts out with much lower robustness than the corrupted predictions. The reason for that is that both the dual base algorithm and exponential averaging make their decisions based on the discounted gain. Our algorithm might therefore easily disregard a corrupted prediction as its discounted gain is low (or negative), but the dual base prediction looks like sensible choice. The dual base algorithm therefore manages to fool the algorithm for low a, while biased corruption leads to the worst corruption for larger values of a.
heavily
Hard Instances: We consider the worst-case instance for the Display Ads problem described in Mehta et al. (2007). h. For advertisers, we create impressions of types i of type has zero value for the first = We.t 1. We first show all impressions of type 1, then all impressions of type 2, and so forth. The instance difficult as the algorithm-ng knowing about future impressions- has to allocate impressions of type equally among advertisers that can
An impression Wy-1.1 = and value for
advertisers W1,1
the following advertisers Wr,t
30

---

GAP ExpAug (0.79)
Mahdian (0.70)
Worst-Case Baseline
1.30
0.950
Contischhy
Rolustres
0.925
1.15
0.000
1.10-
Figure 9: Performance on synthetic Ad Words instances, compared to the algorithm of Mehta et al. (2007). The black lines show the robustness two worst-case algorithms without predictions: The algorithm due to Feldman et al. (2009a) which is the basis for our algorithm, and the algorithm of Mchta al. (207)), which serves basis for the algorithm of Mahdian al. (2007).
derive value from this impression type. As shown by Mehta et al. (2007). the competitiveness of the exponential averaging algorithm reaches 1 1 for oo on this instance.
evaluate the performance our algorithm on this worst-case instance Figure Providing the optimum solution as prediction allows the algorithm to quickly ascend to perfect robustness of 1. We also consider two (biased) corrupted versions of this prediction with p E {50%, 75%}. In both cases, the algorithm still achieves robustness above the competitiveness of the prediction. The dual base algorithm cannot deliver meaningful predictions as it only sees impressions of the first type, which are clearly not representative of the following impressions by construction.
C.3 Evaluation of GAP on an Ad Words Instance
With an algorithm for GAP, we can also solve AdWords instances. This allows us to compare our generalized algorithm to the algorithm of Mahdian et al. (2007) under the same predictions. In Figure 9, we run both algorithms on synthetic instances from Section C.2 with an optimum prediction and random corrptiion (p 0.5). Both algorithms seem to have similar consistency, but our algorithm achieves a better robustness, due to a different choice of constants in the underlying algorithms.
31


Reviews:
[{"review_id": "EWZoNVsHiO", "reviewer": "Reviewer_3Ccp", "summary": "This paper considers the online display ads and generalized assignment problems under free disposal in the \"algorithms with predictions setting\".  In the display ads problem there are offline advertisers $a$ with budgets $B_a$.  A sequence of impressions arrive online with differing values to each advertiser (impression $t$ has value $w_{at}$ to advertiser $a$).  The algorithm must either allocate each impression to an advertiser, earning its value and consuming one unit of the advertiser's capacity, or reject the impression entirely.  Decisions are made irrevocably, but in the free disposal model the algorithm may assign more impressions to an advertiser than their capacity allows but the algorithm only gains the value of the most valuable impressions that fit within the capacity.  The generalized assignment problem generalizes the display ads problem by allowing impression $t$ to instead consume $u_{at}$ units of advertiser $a$'s capacity.\n\nIn the \"algorithms with predictions\" setting the online algorithm also has access to potentially noisy predictions about the optimal solution.  In particular, this paper assumes that the algorithm may access a prediction $PRD(t)$ when impression $t$ arrives which gives a hint about which advertiser to allocate impression $t$ to in an optimal solution in hindsight.  The prediction may be incorrect, so two quantities are analyzed: consistency and robustness.  Consistency is given by the worst-case ratio of $ALG/PRD$, where $ALG$ is the algorithms solution quality and $PRD$ is the predictions solution quality.  Robustness is given by the worst -case ratio of $ALG/OPT$, where $OPT$ is the optimal solution in hindsight.\n\nTheoretically, this paper gives algorithms with non-trivial tradeoffs between robustness and consistency.  The algorithm is based off of the primal-dual algorithm used by Feldman et al. 2009, but modified to account for the predictions.  Proving their consistency bound needed new techniques since a local analysis as is typically used in the primal-dual method is insufficient here.\n\nThe authors complement the theoretical results with an experimental analysis on both real and synthetic data of their proposed algorithm using various predictions as input.  The experiments compare to the worst-case baseline of Feldman et al. 2009 and the simple random-mixture algorithm they discuss in the introduction.\n\n\n\n", "questions": "## Questions\n\n - Can you\n\n - Please clarify what is meant by \"prediction competitiveness\" in the plots in Figure 4.\n\n - What was observed experimentally for the competitive ratio of the worst case baseline?\n\n - In Figures 3 and 5 the average competitive ratio across 5 trials is reported in parentheses for different predictors.  Since there is a hypereparameter $\\alpha$ that is varied can you clarify which value of $\\alpha$ was used to produce these numbers?\n\n## Comments\n\n - For the plots in figure 2, it might be helpful to visually compare with the consistency/robustness guarantees that would be guaranteed by the random-mixture algorithm as well as the algorithm due to Mahdian et al. 2007.\n", "limitations": "I believe the authors have adequately addressed potential limitations and there is not a high potential for negative societal impacts from this work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper considers online allocation problems motivated by advertising applications in the algorithms with predictions setting.  Prior work has considered related problems in this setting.  This paper considers more general versions of these problems and also considers the free-disposal setting, which has not yet been considered in the algorithms with predictions literature.  The paper gives strong theoretical guarantees for their algorithm and complements this with a thorough experimental analysis.", "weaknesses": " - Some of the presentation of the results in the experiment section could be clarified/improved.  See comments/questions below.\n - The improvement over the worst-case baseline using \"more realistic\" predictions is somewhat narrow (although in practice this smaller improvement could matter in some cases).\n - Theoretically, it is not clear if the trade-off between robustness and consistency is tight.  Giving tight guarantees has become of interest recently, see the two references below:\n    - Wei, A., Zhang, F., \"Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms.\"  NeurIPS 2020.\n    - Jin, B., Ma, W., \"Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model.\"  NeurIPS 2022.  (this paper may also be good to discuss in the related work).\n\n\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and address the weaknesses in the following.\n\n1. We thank the reviewer for the suggestions for improvements. We will incorporate them in the paper.\n\n2. Indeed, the improvement over the worst-case algorithm when using the Dual Base prediction is small. We discuss the performance of our algorithm with the Dual Base prediction in Section C.2 under “Results”. We observed in all of our datasets, both in real-world and synthetic instances, that the Dual Base prediction is a poorly performing algorithm despite its strong theoretical guarantees (e.g. on the iPinyYou dataset, Dual Base achieves a competitive ratio of 64% while the worst-case algorithm of Feldman et al (2009a) achieves 95%). We speculate that the reason is that it constructs a fixed allocation rule based only on an initial sample. Moreover, we observe that the errors of the Dual Base algorithm may mislead our algorithm. We observe that the better performing predictors which we obtain by corruptions of the optimum lead to much better results. \n\n3. We thank the reviewer for the suggestion and the references. We will cover the references and include a discussion on tightness in the revision. Our analysis technique can be brought further to achieve a slight improvement in the guarantees. However, doing so is quite technical and we omitted it in the interest of simplicity and conciseness. We think it is a interesting direction for future work to see whether a different analysis can yield more significant improvements. \n\nWe also address the reviewer's questions.\n\n1. The prediction competitiveness is the ratio of the objective value of the predicted solution and the optimum, i.e. $\\mathrm{PRD}/\\mathrm{OPT}$. We will add this to the description.\n\n2. The competitive ratio of the worst-case baseline is 95.8\\% on the iPinYou instance, 87.6\\% on the Yahoo instance in Figure 3, and 90.6\\% for the synthetic instance in Figure 5. The black line in the plots shows the robustness of the worst-case baseline, which coincides with the competitive ratio.\n\n3. The competitive ratio of the predictors are independent of $\\alpha$. The value of $\\alpha$ is used only by our algorithm, alongside a predicted solution.\n\nWe thank the reviewer for the comment on Figure 2 and we will add the other guarantees to a revised version of our paper."}, {"review_id": "hX8KvYyljS", "reviewer": "Reviewer_2o36", "summary": "The paper discusses the problem of ad allocation and its generalization, the generalized assignment problem (GAP), which are two well-studied online packing problems with important applications in ad allocation and other areas. The paper presents an algorithm for both problems that incorporate machine-learned predictions and can thus improve the performance beyond the worst-case. The algorithm is based on the work of Feldman et al. (2009a) and similar in nature to Mahdian et al. (2007) who were the first to develop a learning-augmented algorithm for the related, but more structured Ad Words problem. The paper’s contributions are that it designs the first algorithms that incorporate machine-learned predictions for Display Ads and GAP. The two problems are general online packing problems that capture a wide range of applications. The algorithm follows a primal-dual approach, which yields a combinatorial algorithm that is very efficient and easy to implement. It is able to leverage predictions which can be learned from historical data. Using a novel analysis, the paper shows that the algorithm is robust against bad predictions and able to improve its performance with good predictions. In particular, it is able to bypass the strong lower bound on the worst-case competitive ratio for these problems. The paper experimentally verifies the practical applicability of its algorithm under various kinds of predictions on synthetic and real-world data sets. Here, it observes that its algorithm is able to outperform the baseline worst-case algorithm and the random-mixture algorithm.", "questions": "See the Weakness section, especially Weakness 2.", "limitations": "See the Weakness section, especially Weakness 1.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* Originality: lies in its use of machine-learned predictions to improve the performance of online packing algorithms for ad allocation, i.e., Display Ads and GAP.\n* Quality: presents a rigorous analysis of its algorithm and provides experimental results that demonstrate its effectiveness.\n* Significance: addresses an important problem in online advertising and provides a novel solution that can improve the performance of existing algorithms.", "weaknesses": "1. The paper does not provide a detailed analysis of the limitations of its algorithm. For example, it is not clear how the algorithm would perform in situations where the predictions are inaccurate or where there are other sources of uncertainty. \n2. The paper does not provide a comparison of its algorithm with other state-of-the-art algorithms for online ad allocation. This makes it difficult to assess the relative performance of the proposed algorithm and to determine whether it is truly novel and effective. \n3. The paper does not provide a detailed discussion of the practical implications of its algorithm for real-world ad allocation systems. This could be addressed in future work by providing a more detailed analysis of the computational requirements and scalability of the proposed algorithm, as well as by conducting experiments on real-world data sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address the mentioned weaknesses in the following.\n\n1. Our algorithm is specifically designed to perform well even if the predictions are inaccurate (from any source of uncertainty). In the field of learning-augmented algorithms, the measure of robustness is used to indicate how well the algorithm performs under an arbitrarily bad prediction. We show a theoretical bound on the robustness in Theorem 1 and experimentally validate our algorithm on inaccurate predictions in Section 4.\n\n2. To the best of our knowledge, we compare our algorithm against the state-of-the art algorithms with theoretical guarantees for the problems we consider, both with and without predictions. We are the first to develop learning-augmented algorithms for the problems Display Ads and GAP. For these problems, we compare against the state-of-the-art worst-case algorithm, which is due to Feldman et al. (2009a). This work achieves a competitive ratio of $1-\\frac{1}{e}$ which is best possible in the worst-case. For the more structured Ad Words problem, to the best of our knowledge, the best known competitive ratio with predictions is achieved by the algorithm of Mehta et al. (2007). We evaluate our algorithm on Ad Words instances and compare with this work in Section C.3 of the appendix in the supplementary materials. We will reference this in the main body. We would appreciate any suggestions from the reviewer on other algorithms and we will try to add them to a revised version of our paper. \n\n3. We do provide experiments on the real-world datasets Yahoo and iPinYou in Section 4 (Line 293) of our paper. These are the two main datasets that are publicly available. If the reviewer has suggestions for other datasets that are suitable, we are happy to try to evaluate our algorithms on these datasets. Our algorithm is very efficient and scalable, and we ran all our experiments on a laptop with an i7-1165G7 CPU and 16Gb of memory. We are happy to add a discussion on the scalability of the algorithm in the next revision. We agree with the reviewer that exploring the implications of our work on real-world ad allocation systems is an interesting direction for future work. "}, {"review_id": "rFOCjwTKb9", "reviewer": "Reviewer_9H3m", "summary": "This paper studied Display Ads and the generalised assignment problem (GAP) where ad impressions arrive online and are allocated immediately to advertisers on the offline side. The difference between the two problems is that in Display Ads each impression takes uniform size of advertisers’ budgets, while in GAP the size is non-uniform. The paper considered the setting that incorporates predictions for allocation, which can be accessed by the algorithm upon arrival of each impression. The paper proposed a primal-dual algorithm based on Feldman et al. (2009a), with new ingredients to deal with predictions. Firstly, the new algorithm decides whether to allocate an impression to the predicted advertiser or to one with max discounted gain based on comparison involving a robustness-consistency trade-off parameter. Secondly, the algorithm updates the dual variable with an exponential mechanism involving the trade-off parameter. The paper provided theoretical analysis for the robustness and consistency factors, as well as experimental results on synthetic and real world datasets.", "questions": "1. In Theorem 1 the robustness R is a decreasing function with respect to \\alpha, but in experiments the robustness has a trend of (slightly) increasing w.r.t. \\alpha. What is the cause of this phenomenon?\n\n2. The limit of R(\\alpha) in Theorem 1 tends to be 1 when \\alpha tends to be 0. How does R(\\alpha) compare with the worst-case ratio 1-1/e?", "limitations": "The paper briefly discussed limitations of the proposed algorithm.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Online matching and related problems have been extensively studied in the literature and found their applications in online business. This paper studied Display Ads and GAP, which are generalized version of online bipartite matching and Ad Words, that could capture more complicated scenarios in practice. Worst-case guarantees can be restrictive, while external or historical information may be available for making online decisions. This paper proposed an efficient and effective algorithm in this setting.\n\n2. The paper proposed a solid primal-dual approach with theoretical performance guarantee that incorporates predictions that is accessible in general forms. The performance of the algorithm improves over worst-case and random mixture baselines in experiments.\n\n3. The paper is clearly written. The main text provides necessary intuition and discussion about the algorithm and analysis, as well as comparison with related work.", "weaknesses": "1. The paper only presented the proposed approach for Display Ads in the main text, but put the whole GAP part to Appendix. It would be helpful to briefly discuss in the main text how to extend the approach to GAP and take care of general impression sizes.\n\n2. It is not clear if consistency is a good metric for evaluating the performance of algorithms with predictions. Unlike robustness, the consistency factor relies on a varying value of solution PRD to be compared against. For instance, in the upper left of Figure 3, the consistency value is high when PRD itself has low competitive ratio, while it is below 1 when PRD=OPT. It is hard to relate the absolute value of consistency to the quality of ALG.\n\n3. The paper mentioned that the algorithm incorporates machine-learning predictions in abstract and introduction, which seems misleading. The actual algorithm receives a prediction PRD(t) for each impression t, which is presented in an abstract form and is not necessarily related to machine learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments and address the weaknesses in the following.\n\n1. We thank the reviewer for this suggestion and we will add such a discussion to the main body. Our reason for discussing only Display Ads in the main body is that it contains some of the most important algorithmic ideas of our approach.\n\n2. Our work follows the standard practice in the literature on learning-augmented algorithms to measure the performance of an algorithm via consistency and robustness. We agree with the reviewer that when the prediction is good, the consistency allows us to gauge how closely the algorithm follows it. For worse predictions, it is most informative to look at both consistency and robustness, as this tells us how well the algorithm is able to overcome errors in the prediction.\n\n3. It is true that predictions can come from any source and we will clarify this in a revised version of our paper.\n\nWe now address the reviewer's questions.\n\n1. This is an interesting point an we will add an explanation for this behavior to a revised version of our paper. In our theoretical analysis, we have to assume an adversarial input from our prediction, which means that the robustness necessarily declines the more we trust the prediction. In practice, a prediction is not chosen to be adversarial, even though its objective value can be much less than the optimum. In our experiments, we observe that for increasing $\\alpha$, our algorithm is able to exploit “good suggestions” more while it still ignores “bad suggestions”. This explains why there is no immediate trade-off as in the guarantees of Theorem 1 and showcases the practical merit of combining worst-case algorithms with learned predictions, which may still err on some parts of the input.\n\n2. In our paper, we only consider parameters $\\alpha\\ge1$. For $\\alpha=1$ (which means that we do not trust the prediction at all), our algorithm is identical to the worst-case baseline due to Feldman et al. (2009a). In this case, we also recover the worst-case competitive ratio of $1-\\frac{1}{e}$ in the large-budget case."}, {"review_id": "WkYmExrYWg", "reviewer": "Reviewer_eG65", "summary": "This paper is for the online matching problem in the display advertising domain. Essentially there are shopper/supply side requesting coming in in a sequential order, and static advertiser side demand with budget constraint. The goal is to do some sort of global optimization (as opposed to greedy strategy to maximize value for each request t). The paper proposed a learning-augmented algorithm and demonstrated its effectiveness via a theorem as well as simulations. \n\nScore changed from 6 to 7 after seeing the rebuttal from the authors.", "questions": "see pros/cons", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The robustness against low-quality prediction. This is a very nice property to have for an algorithm to be practical. It seems the benefit doesn't vanish thought it decays. Given that the prediction quality is always something with uncertainty and affects the cumulative value for any algorithm, what is shown in this paper is already good.\n\n2. Convincing simulation/experiment results using real-world dataset.\n\n3. I particularly like line 170 - 191 which has done a nice job explaining the intuition of algorithm 1.", "weaknesses": "1. Don't know if the #impression over #advertiser ratio will significantly affect the simulation results, but I think this ratio are similar in those tested datasets. It's worth a little more discussion. I think for real-world scenario, the actual ratio won't be in the scale of 100.\n\n2. I think the gain beyond the greedy algorithm that maximizes the single-impression utility is usually more important than the regret compared to OPT. Worth having related info in the paper.\n\n3. How to handle the targeting constraint? This is very common in display advertising that an advertiser is only interested in a subset of impressions relevant to their own business. It effectively means one additional constraint in the primal problem.\n\n4. The level of contribution beyond what is done in existing work. I didn't get the idea that Bama 2020 work forms this as an open problem though indeed they are relevant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and now address the mentioned weaknesses.\n\n1. This is an interesting point and we have now conducted further experiments with synthetic data using #impression to #advertiser ratios from 20 to 2000. We did obtain similar results for these ratios when scaling budgets for the advertisers proportionally (if the budget is too low or too high, the instance becomes very easy and the baseline exponential averaging algorithm manages to extract close to 100% of the optimum value). We will add such experiments and a discussion to a revised version of the paper. The plots can be found in the PDF that was attached to the global comment above in Figure 2.\n\n2. We thank the reviewer for this suggestion. Following the reviewer's suggestion, we added greedy algorithms as baselines to our experiments. We ran experiments with two greedy schemes: One which considers only the impression values (Greedy), the other the gain after disposal (Discounted Greedy). The evaluation shows that the two greedy schemes do worse than the algorithm of Feldman et al. (2009a) in all instances, except for the Discounted Greedy algorithm on synthetic data. We provide the experimental results in the PDF that was attached to the global comment above in Figures 1 and 2. From a theoretical perspective, the competitive ratio with respect to the optimal solution provides the strongest guarantee and this coincides with the robustness in our setting.\n\n3. Targeting constraints can be directly modeled by setting the value $w_{at}$ of impression $t$ and an advertiser $a$ without the need for additional constraints. For instance, if an impression $t$ is not relevant for advertiser $a$, we can set $w_{at}$ to any negative value, which will ensure that the impression $t$ is never allocated to advertiser $a$.\n\n4. Our algorithm and analysis are a significant departure from prior works. More specifically:\n\n    - Compared to Metha et al. (2007), which is the most closely related algorithm with predictions, we tackle problems that have less structure, thus require the use of free disposal and foremost new algorithmic ideas to incorporate predictions. A detailed comparison can be found in Lines 200 through 218.\n\n    - Compared to Feldman et al. (2009a), which is the most closely related algorithm without predictions, we develop a novel analysis to prove consistency. Feldman et al. (2009a) analyzes their algorithm in a local manner by relating the changes in the primal and dual objective values after each individual update to the solutions, as it is common for algorithms following the primal-dual framework (see e.g. the survey of Buchbinder and Naor (2009)). This local approach is not sufficient to obtain our guarantee. Instead, we analyze our algorithm via a novel global argument that expresses the objective values of the prediction and the final solution constructed by the algorithm as suitable linear combinations of the impression values. A direct comparison of the coefficients in the resulting linear combinations will not give our guarantee. Instead, we make several important observations that allow us to redistribute mass across coefficients (see Lemmas 4 and 9 in the appendix). The resulting analysis is delicate, as we can see for example in the proof of Lemma 9 in the appendix. We believe our novel approach could potentially be used to obtain improved learning-augmented algorithms for other problems in the primal-dual framework, such as the ones detailed in the work of Buchbinder and Naor (2009).\n\n    - Bamas et al. (2020) develop learning-augmented algorithms for covering problems using the primal-dual method but leave packing problems for future work in their discussion on future directions. One of the main problems considered by Bamas et al. (2020) is set cover, which is a fundamentally different problem to ad allocation, both with and without predictions. Our works and theirs do not overlap beyond the general use of the primal-dual framework."}]

Author rebuttal:
Following reviewer eG65's suggestions, we ran additional experiments with two additional baselines and varied the number of impressions in our synthetic instances. The two additional baselines are two greedy schemes: One considers only the impression values (Greedy) and the other the gain after disposal (Discounted Greedy). The results can be found in the attached PDF.

Meta-review: This paper gives strong theoretical guarantees for using predictions in online allocation problems. The reviewers felt this work went beyond prior work leveraging new algorithmic predictions and extending prior models. Overall, this was viewed as a novel contribution.
Decision: Accept (poster)