Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions
Authors: Gagan Aggarwal
Kshipra Bhawalkar
Aranyak Mehta
Divyarthi Mohan
Alexandros Psomas
Venue: NeurIPS 2022 Accept (2022)
Keywords: mechanism design
auctions
social welfare
price of anarchy
knapsack

Abstract: Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown.
The seller is now faced with a multi-parameter mechanism design problem.
Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. 

In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a ``Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e.g. the incremental bang-per-buck order, that give good approximations to ``knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than $2$ (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a $3$ approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.

Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions
Gagan Aggarwal Google Research gagana@google.. com
Kshipra Bhawalkar Google Research kshipra@google. com
Aranyak Mehta
Google Research
aranyak@google. com
Divyarthi Mohan Tel Aviv University divyarthinStau. ac.
Alexandros Psomas
Purdue University apsomasBcs pwrpomaaaesspuuuuuee.eeeee edu
Abstract
Internet auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown. The seller is now faced with multi parameter mechanism design problem. Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clan Clarke-Groool (VCG) auction, while truthful and welfare-optimal, is impractical.
In this paper, we tackle fundamental problem in the design of modern ad auctions. We adopt a "Myersonian" approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give truthful auction. Our main technical challenge designing monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't it hold for standard algorithms, e.g. the incremental bang- per-buck order, that give good approximations to "knapsack-like" problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within factor better than 2 (while there is non monooone FPTAS). Our main result is new, simple, greedy and monotone allocation rule that guarantees a 3 approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called Generalized Second Price (GSP) payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) bounded. Under standard no-overbidding assumptions, we prove bounds on the pure and Bayes-Nash PoA. Finally, we experimentally test algorithms real-world data.
Introduction
Internet Ad Auctions, in addition to being influential in advancing auction theory and mechanism design, half-a-trillion dollar industry [CF21]. A significant advertising channel is sponsored search advertising: ads that are shown along with search results when you type a query in search box. These ads traditionally were few lines of text and link, leading the standard abstraction for ad auctions: multiple items for sale to a set of unit-demand bidders, where each bidder has private value v, ais for the ad in position s, which has dlik-through rate Ci.. However, when using your favorite search engine, you might instead encounter sitelinks/extensionss leading to parts of the advertisers' website, seller ratings indicating how other users rate this advertiser or offers for
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

specific products. Advertisers can often explicitly opt in or out of showing different extensions with their ads. In fact, some extensions require the advertiser to provide additional assets, e.g. sitelinks, phone numbers, prices, promotion etc, and an ad cannot be shown unless this additional information available. All these extensions/decorations change the amount of space the ad occupies, as well as affect the probability of a user clicking on the ad. The new and unexplored abstraction for modern ad auctions is now to select a set of ads that fit within the given total space.
In this paper, we study the problem of designing a truthful auction to determine the best set of ads that can be shown, with the goal of maximizing the social welfare. More formally, we consider the Rich Ads problem. In our model, each advertiser specifies value per click o; and set of rich ads. Each ad has an associated probability of click ag and space Way that would occupy if shown. The space and click probabilities are publicly known. Crucially, advertisers' private information is not single-dimensional available: an advertiser can report only subset of the set of ads available if the allocation under this report improves her utility. The open problem we address in this paper whether there exist simple, approximately optimal and truthful mechanisms for Rich Ads.
addition to misreporting her value, there is another strategic dimension
Results and Techniques. The classic Vickrey- Caiccy---arkeeeee Clarke-Groves (VCG) mechanism is truthful and maximizes welfare for our setting, but it is computationally intractable: maximizing welfare is NP-complete (even without truthfulness) since our problem generalizes the KNAPSACK problem. It is also well known that coupling an approximation algorithm for welfare with VCG payments does not result in a truthful mechanism. And, maximal-in-ran range mechanisms [NRO1], that optimize social welfare over a restricted domain, even though are one way around such situations, have limited use, since the range of possible outcomes (allocations) has to be committed to before seeing the bidders preferences (i.c., needs to be independent of bidders reports). For single parameter problems, Myerson's 's lemma [Mye8]] I] can be used to obtain a truthful mechanism, as long as the allocation rule is monotone. The Rich Ads problem is not single parameter problem, so this approach does not immediately work. However, similar to the inter-dimensional (or "one-and-a- -n-aand-a-half" dimensional) regime [FGKK16, 16, DHP20, DGS+20], we can extend Myerson's 's lemma to domain. We show that an allocation rule that is monotone in the bid and the set of rich ads' can be paired with a payment rule obtain a truthful mechanism.
Incentive issues aside, the Rich Ads problem an extension of the KNAPSACK problem, called MULTI-CHOICE KNAPSACK: in addition to the knapsack constraint, we also have constraints that allow to allocate (at most) one rich ad per advertiser. As an algorithmic problem, this is well studied [SZ79, Law79]. The optimal fractional allocation can be derived using a simple greedy algorithm using the incremental bang-per-buck order. However, it turns out that the optimal (integral or otherwise) allocation, as well as other natural allocations, are not monotone. In fact, as we show, no deterministic (resp. randomized) monotone allocation rule can obtain more than half (resp. 11/12 fraction) of the social welfare. In contrast, without the monotonicity constraint, there is FPTAS for the MULTI-CHOICE KNAPSACK problem [Law79].
Our main result is providing an integral allocation rule that is monotone and obtains at least third of the optimal (fractional) social welfare. Pairing with an appropriate payment function we get the following (informal) theorem.
Informal Theorem. There exists a simple truthful mechanism, that can be computed in polynomial time, which obtains a 3-approximation to the optimal social welfare.
To obtain this result, we first find an allocation of space amongst the advertisers. In contrast to the optimal fractional algorithm described above which allocates greedily using the incremental bang- per-buck order, our algorithm allocates greedily using an absolute bang-per-buck order. Crucially, the space allocated to each advertiser in this way is monotone, even though the expected number of clicks (i.e. the utility) of the bang-pes per--ee-bbue ber--ueer-buuueeeee buck algorithm itself is not monotone. By post-processing to utilize this space optimally for each advertiser, we obtain an integral allocation that is monotone in the expected number of clicks. We prove that this allocation gives a two approximation to the optimal fractional welfare, minus the largest value ad. Finally, by randomizing between this integral allocation (with probability 2/3) and the largest value ad (with probability 1 1/3), we get a 3-approximation
Here, an allocation rule is defined to be monotone in the set of rich ads if the expected clicks allocated to an advertiser can only increase when the advertiser reports superset of rich ads.

---

to the optimal social welfare. Since the overall allocation rule is monotone, we can pair it with an appropriate pricing to get a truthful mechanism.
We proceed to further explore the merits of our monotone allocation rule by pairing it with the Generalized Second Price (GSP) payment rule, which charges each advertiser the minimum threshold (on their bid) below which their allocation changes. The overall auction is not truthful. However, we can analyze its performance by bounding its social welfare in a worst-case equilibrium. In particular, we consider the full information pure Nash equilibrium, where bidders best-respond to a profile of competitors bids, as well as the incomplete information Bayes-Nash equilibrium, where the bidders best-respond to a distribution of valuation draws and bids for the competitors. The corresponding pure Price of Anarchy (PoA) and Bayes-Nash Nash Price of Anarchy are the ratios of the optimal social welfare to the welfare of the worst equilibrium. In either setting, we make the standard no-overbidding assumption, where bidders do not bid more than their value. This assumption required as without the PoA of even the single-item second price auction (which is truthful) can be unbounded? 2
Informal Theorem. There exists a simple mechanism with a monotone allocation rule, paired with the GSP payment rule, which under the no-overbidding assumption guarantees a pure Price of Anarchy (resp. Bayes- PoA) of at most 6 (resp. 1-1/e)
We prove our PoA bounds by identifying a suitable deviation for each advertiser, and bounding the advertiser's 's utility in this deviation relative to the social welfare of the optimal integral allocation, our integral bang-per-buck allocation (in the equilibrium), and the largest value ad (in the equilibrium); as opposed to single-dimeng dineesinmns PoÅ bounds, the knapsack constraint in our setting introduces a number of technical obstacles we need to bypass. To prove a bound for the Bayes- -ash PoA, we combine techniques from our pure PoA bound with the standard smoothness framework [Rou15al In particular, the smoothness part of our argument is very similar that of [CKK* 15] for the Bayes-Nast PoA of the standard GSP position auction. Due to the specific form of the smoothness framework that we use, our bound also applies to mixed, correlated, corrse-correlated and Bayes-Nash with correlated valuations. Our PoA results can be found in Appendix E.
Finally, we provide an empirical evaluation of our mechanism on real world data from a large search engine. We compare performance of our mechanism with VCG and the fractional-optimal allocation that doesn't account for incentives. Our empirical results show that our allocation rule obtains at least 0.4 fraction of the optimal in the worst-case. However, there are many instances where our allocation rule is almost as good as VCG. In fact, the average approximation factor of our allocation rule 0.97. Furthermore, our mechanisms are significantly faster than VCG, even with the Myersonian payment computation. We also empirically evaluate heuristic extensions of our algorithms when there is a bound on the total number of distinct rich ads shown.
Related work. Traditional sponsored search auctions have been studied extensively [AGM06, Var07, EOS07]. A number of recent works relax the traditional model of sponsored search auc- tions [CMSWCI W20, Huml6 and introduce different versions of the "rich ads" problem [DSYZ10, CKSW17, GHLY 19, HIK 18]; the specific model we study in this paper is new. [DSYZ10] are the first to formulate a rich ad problem where ads can occupy multiple slots. They analyze VCG and GSP variants for a special version of the rich ad problem where ads can be of only one of two possible sizes. They leave the problem addressed in this paper as an open problem for future work.
Much of the literature focuses on GSP-like rules (e.g.. because the cost of switching from existing GSP to VCG can be high [VH14]). [CKSWI7] consider the more general rich ad problem where there are constraints on number of ads shown and position effects in the click through rate. But their setting is still single-parameter the set of rich ads. They provide a local search algorithm that runs within polynomial time and a generalized GSP like pricing go with it. However, as opposed to our interest here, their auction is not truthful, nor do they give any approximation guarantees. [GHLY19] consider the optimization problem when the probability of click is submodular or subadditive in the size of the rich ad. They give log m an LP rounding based algorithm that provides approximation for submodular and a 2 log log m approximation for subadditive, with respect to the social welfare assuming truthful bidding. They however do not provide a truthful payment rule, or any PoA guarantees. These works also focus on single-dimensional setting (where the advertiser is strategic about its bid but the set of ads is publicly
advertisers report a bid per click and cannot mis-report
CConsider, for example, the equilibrium where all bidders bid O. except the lowest bidder, who bids infinity.
3

---

known). In contrast, we consider a cuuti-dimensional setting. Our simple and truthful mechanism also has a monotone allocation function, so we pair it with GSP as well.
The PoA of the GSP auction for text ads was studied in [CKKK11, LB10, LPL11]. Our PoA bounds use the smoothness framework introduced in [Rou15a], and later extended by [CKK+15] 15] show PoA bounds for GSP (as well as in [Rou15b] and [ST13] for more general use).
2 Preliminaries
Rich Ad Model. We introduce the following model for the rich ads auction problem. There is set N of n advertisers and universe of rich ads S. Each advertiser E N has private value per click is and a private set of rich ads A, C S.² We use v = (v1, U2,.... (n)) to denote the vector of values per click and A (A1, A2,.... A,) to denote the vector of sets of rich ads. For every advertiser i E N, each rich ad j E S has publicly known space Wij and a publicly known probability of click azj. We use Vij for the value of rich ad j for advertiser i. If j & A,, then the value of advertiser i Vig = O: otherwise, Vij = 0ty2/.- An advertiser can be allocated only one of the ads from the set S. Finally, there is a total limit W on the total space occupied by the ads. We assume without loss of generality that for each and each j. Waj S W. as any ad that is larger than W cannot be allocated integrally in space W. A (randomized or fractional) allocation x E [0, 1]x[|s| indicates the probability Iıj that ad j is allocated to advertiser i. An allocation is feasible if each advertiser gets at most one ad, i.. Ejes Biy- S 1 for all i E NN, and the total space used is at most W, i.c.
DieNJes Wijyi I W. An allocation is integral if z4j E 1J, for all E N and j E S.
Our goal is to maximize social welfare. For an allocation x = Alg(v, A), (Wlgal(v A)) = Σng Uij We can write an integer program for the optimal allocation follows, by introducing binary variable 2i E {0.1) for the allocation of advertiser i N and rich ad j E S. The objective is to maximize welfare Eg Tay subject to Knapsack constraint Σ, E WajJaay S W, and Tij < 1 for all i E (expressing that each advertiser can get only one ad).
feasibility, i.e. mij
Mechanism Design Considerations. By standard revelation principle arguments, it suffices to focus on direct revelation mechanisms. Each advertiser i E N reports bid 6; and a set of rich ads S: S S. Similarly to many works in the inter dime--immnsional regime, e.g. [MV09, DW17], we assume that S, S A,, that is, an advertiser cannot report that they want an ad they don't have. Let b = (b,, .e....bb. b,) to denote the vector of bids and S = (S1, , S,) to denote the vector of sets of rich ads. We use byj by . Osy j E S, and b,j = otherwise, and refer to the rich ad using (reported value, space) tuple (bej. Way)- ). A mechanism selects set of ads to show, of total space at most W, and charges a payment to each advertiser. Let (b,(b,, S) be the probability that ad is allocated to advertiser i, and (b, S) denote the expected payment of advertiser i. Let x, (b, S) be the allocation vector of advertiser We assume that for any valid allocation rule for j & S; T.y (b, S) = O. We slightly overload notation, and use (b, S) to denote the expected number of clicks the advertiser will get; that is, z;(b,)) per-elick opca(b, (b.S) S) = pz (b. (b)
Ejes, Taj (b, S)ay. If required we refer to the cost
Advertisers have quasi-linear utilities. An advertiser with value v. and set A, has utility (b,,(b.)) p. (b, S). when reports are according to b and S. Let us (1,,,, Ai + b, S;; b_,, S_:) be the utility of advertiser when her true value and set of ads are vi A,, but reports b;, S, and everyone else reports according to b_,, S_,. For ease of notation we often drop b p. S_, when it's clear from the context. When the profile of true types is fixed, we drop (v, A:) and use the notation (b,b,, Sy. S-.).
mechanism truthful if no advertiser has an incentive to lie, i.e. for any all b_,. S_s. u,(u,, A, - w; A; b_... S_;) 2 us uu A; + b; S;; b i. S Smi). for all us A,, b,, S,, A mechanism is individually rational if in all of its outcomes, all agents have non-negative utility.
We are interested in auctions that are computationally tractable, truthful, individually rational, with the goal of maximizing the social welfare SW (W(xx(, S)) = E; (br,(b,)). S). Even ignoring truthfulness
2 We expect the rich ads to be tailored to an advertiser, so we assume that A; n Ar- = 0. for i, e AC "Note that this safe to assume. The space consumed by rich ad is evident when the rich ad is provided. The probability of click can be predicted by the platform (e.g. using machine learning models).
4

---

and individual rationality, the computational constraints rule out achieving the optimal social welfare; therefore, we seek approximately optimal mechanisms.
Definition 1. A truthful mechanism M obtains an a factor approximation to the social welfare if SW(XM (v.A)) A)) 2 SW SWxxPPT (xoPr(v, A))/a.
Formal definitions of the Generalized Second Price and the Price of Anarchy are deferred to Ap- pendix A (since all the instances where they are used are also in the appendix).
Optimal fractional allocations. The algorithmic problem a special case of a well-known varia- tion of the KNAPSACK problem, called MULTI-CHOICE KNAPSACK [SZ79]. The integer program for MULTI- CHOLCE KNAPSACK is the same as the integer program above, except that the inequality constraint Ej Vig S 1 is replaced with an equality. Our problem is easily reduced to the MULTI- CHOICE KNAPSACK problem by introducing a null ad with (aso, Waa) = (0, ().[S279] provide characterization of the optimal fractional solution of BULTI-CHHICE KNAPSACK and provide fast algorithm to compute the fractional optimal solution. As is colloquial in the KNAPSACK literature,
we refer to the ratio bik
as Bang-pes per-Buck and the ratio byy hig with Wij > Wik as Incremental Wi
witk
Loong-per-iicg Duc-Buck. [SZ79] show that allocating ads in the incremental lang-per-buck order gives the optimal fractional solution. We state this standard algorithm in Appendix A. We refer the solution constructed by this algorithm as OPT and use it as benchmark in our approximation guarantees. We note few more properties of OPT.
Fact 1 ([SZ79]). In the optimal fractional allocation constructed by the algorithum, all advertisers except one have rich-ad allocated integrally. Also for any advertiser i allocated space W,, in OPT, the allocation maximizes the value that advertiser can obtain in that space.
This fact also implies 2-approximate integral allocation follows. Construct optimal fractional solution using the incremental bang-per-buck order. Let denote the advertiser that is allocated last: select the larger of the optimal fractional solution without i' and the highest value ad of
3 Monotonicity and Lower Bounds
Monotonicity implies truthfulness. In single-parameter domains, Myerson's 's lemma provides handy tool for constructing truthful mechanisms. One has to only construct a monotone allocation rule, and then the lemma provides complementary payment rule such that the overall mechanism is truthful. We extend this approach to our particular multi paalliep domain. If the set of ads is fixed for each advertiser, then monotonicity in bid and Myerson-like payments imply truthfulness. We give constraints between the allocation rules for different sets of ads and show that they imply truthfulness everywhere using
seal-to-global argument. We begin by defining monotonicity in our setting. An allocation rule is said to be monotone if it is monotone in each dimension the buyer's preferences.
Definition 2. An allocation rule x(b, S) is monotone in b,, S. for each i, if (1) For all b., S...S..,33 Sg by > bi we have (b, S, b...S..) 2 z,(b,, S; S-i. and (2) For all bu, S_,, b,, S 2 S;; we have r,;b,, S b S_.) 2 x; 1;,b,, S. b_,,S_i)
As the following example shows, the optimal allocation rule is not monotone. The example also shows that monotonicity is not necessary for truthfulness (since VCG is truthful and optimal).
Example 1. Consider two advertisers with two rich ads each. Both have value and the rich ads have (value, size) = (1, 2, The space available is In this case, the optimal integer solution chooses the smaller ad from one advertiser and the larger ad from other. However, if one of them removes their smaller option, they get the larger option deterministically:
The next lemma (proof in Appendix B) shows that monotonicity is sufficient for truthfulness. Lemma 1. If valid allocation rule x(b, S) is monotone in b. S for each i E N, then charging payment p: (bb S) (,,; S) -Jo r, (b, b S)db results in truthful auction.
Lower bounds. Next, we illustrate the challenge in coming up with allocation rules which are monotone in the set of rich ads. We also prove that monotonicity rules out approximation ratios strictly better than 2 for deterministic mechanisms (and 12/ 11 for randomized mechanisms).
5

---

As we' ve seen in Example 1, the algorithm that finds the optimal integer allocation is not monotone. The following example shows that simple algorithms such as selecting ads in the incremental bang- per-buck order, or the 2 approximation algorithm presented in Section 2 are not monotone either. Recall that baun-per-buck- biy/wij and incremental mang-per-buck
with Wij > Wik-
way wii--ik
Example 2.
We have two advertisers A and B. A has two rich ads with (value, size) as (3.5).3.5,3). B has one ad with (value, (3,3)
(i) Suppose W- = 4. The incremental bang-per-buch algorithu picks A : (2, followed by B (3. 3). The rich ad A 13.5,,3 3) does not get picked over =3,3), despite having higher bang-per-buck, since it has smaller incremental bang-per-buck (of 0.75). On the other hand if A removes the rich ad (2, 1), the algorithm picks A (3.5,3, 3) at the very beginning, and A obtains higher value.
(ii) Suppose W = 3.5, the optimal fraction solution is A (2. 1) with a weight of 1.0 and B : (3.3)
with weight 2.3/3. The 2-approximation algorithm of Section 2 compares allocating just A (2, or just (3.3), and chooses B. But if A removed (2, then the optimal fraction solution is A: (3,5,3 3) with weight 7. 1.0 and B (3,3) with weight 0.5/3. 3. The 2-approximation algorithm compares A : (3.5,3) 3) and B (3.3), 3). and chooses because it has higher value. Thus A gets a higher value by removing (2, 1).
The next theorem gives lower bounds on the approximation factor monotone algorithm can achieve.
Theorem 1. No monotone and deterministic (resp. randomized) algorithm has an approximation ratio better than 2 - E (resp. 12/11 - for any > O.
Proof. There are two advertisers. Each advertiser has two rich ads: e,, The total space is 3. The optimal solution has value (2 + <). To obtain an approximation better than 2 - e, we must choose small ad for at least one of the advertisers. Since the algorithm is monotone, when that advertiser does not provide the small ad, the algorithm cannot give them the larger ad. Thus when the advertiser does not provide the small ad, the algorithm must give this advertiser nothing, resulting in welfare at most (1 - E). See Appendix B for the proof for randomized algorithms.
4 A Simple Monotone 3-Approximation
In this section we give our main result: monotone algorithm that obtains 3 approximation to the optimal social welfare. First, we give a fractional algorithm for allocating space to each advertiser i. Second, we show that optimally (and integrally) using the space given each advertiser i gives monotone allocation. Finally, we show that randomizing between the former algorithm and simply allocating the max value ad is monotone rule that obtains 3 approximation to OPT. Omitted proofs (and definitions) can be found in Appendix C. We show that the truthful payment function matching our allocation rule can be computed in polynomial time in Appendix C.3.
Monotone space allocation algorithm We start by giving monotone algorithm for allocating space to each advertiser. This total space allocated is monotone in b; and S, for all i E N. Our algorithm also provides allocation of rich-ads to that space, but this allocation by itself may not be monotone, and may not provide good approximation. Our algorithm, which we call ALG g, works as follows (see Appendix C for a formal description). First, we order the ads in the bang-per-buck order. We iteratively choose the next ad in this order; let i be the corresponding advertiser, and j be the rich ad. We replace the previous ad of with j. if this choice results in more space allocated to i. If there is not enough space we fractionally allocate j and terminate.
The following observation shows that any ads removed for not fractional-optimal solution as well. See Appendix A for the precise definition of dominated.
will not be used by the
Observation 1. Let j' E E; be some ad removed from E, in "step 2" of ALG for having space at most Wij. Then either j' = j or j' is a "dominated" ad.
Next, we prove that ALGG allocates space that is monotone in b, and S;, for all i E N.
'Even though we only seek integer monotone algorithms. this example shows that even the fractional allocation not monotone: when A provides all ads its value is 2, but when A removes (2, 1), its value is 3.5.

---

Theorem 2. Let x(ALGB) denote the allocation of ALGg. Then. for all i E N. b, I b1: E, Wiy (ALG (b, (b, S)) S Ej (eLj:,(AAGGn b b- S)) Also, for all and S S S the space W; is monotone in Si E; WisTi (A,G (
- Ej w.zzijAAG S-.)..
B is inefficient since the bang-per-bus ber-buck allocation can change the relative order which the advertisers are assigned space, generating sub-optimal outcomes.
Example 3. Let M be a large integer. Let W = M - and consider two advertiser A and B. A has two rich ads with (value, size) as (1, 1), (1 + E, M - -1). has one rich ad with (value, size) [M-1 M 1). Fractional OPT selects A (1, filll and B ( . - 1) fractionally with ( M
weight (M - (M - 1) and obtains a social welfare 1 MM The bang-per-buck allocation in e, ALG selects A: (1 (1+6 e, M) fully and obtains social welfare (1 +).
While the space allocated is monotone in the bid and rich ads, the allocation itself may not be monotone, since ALGB may allocate an advertiser larger ad with lower value than another option; we provide an example in Appendix D.
Integral Monotone Allocation. The allocation generated by ALGB can be fractional for one advertiser, and can be sub-optimal (but integer) for some of the other advertisers. In the following algorithm, post-process to find the best single ad that fits in W.
Algorithm (ALG1). First, run ALGB. Let W; be the space allotted to advertiser i. Second, post-process to allocate the ad with maximum value that fits in W., i.e. j E argmax mi sw; big. Any remaining space left unallocated.
Observe that ALG, is monotone, since (1) the space allocated by ALGB is monotone, and (2) if the space allocated by ALG n is larger, then the poot-processing that allocates the highest value ad that fits in this space will also result in same or larger value. However, ALG, alone might be an arbitrarily bad approximation: we provide an example in Appendix D.
Main result. Our main result is the following theorem.
Theorem 3. The randomized algorithm that runs ALG, with probabillty 2/3, and otherwise allocates the maximum valued ad, is monotone in b; and S,, obtains a 3'-approximation to the social welfare, and this approximation factor is tight.
Proof. Let bmaz denote the value of the maximum valued ad. We will first show that 2SW (X(((GG))) 2 SW (X(Xx))).. Let Val(x, A, = E'ie bey EEes myy be the fraction of the social welfare of allocation x, SW(x), contributed by a subset of ad- vertisers A for space 5. Let x* XOPT(b.S) denote an optimal fractional allocation. Let W; B.LG 8)) and W W.(OPT(b, S)) denote the total space allocated adver- tiser in ALGB and the optimal allocation x", respectively. The space allocated in ALG, is exactly the same as W.. Recall Fact that there an optimal fractional allocation where at most one advertiser is allocated fractionally. Let i' be the advertiser whose allocation in x" is fractional. There also at most one advertiser in ALG whose allocation fractional: the advertiser corresponding to the very last ad that is included; let z" be this advertiser. We start by giving a series of technical claims, First, we bound the part of SW SW(x(OPT) contributed by advertisers who are allocated more space in A ALGB n than in OPT. Let I denote the set of advertisers i with W. 2 WT.
Claim 1. Val(x*, I (F), W Val(x(ALG,). (t),
Let - be the set of advertisers with We Wt. IF then W, W. for all i. We note that b, -r;(((A (ALG,) b, x for all i + i' by Claim 1. Also bwar 2 b, x². Thus we get SW (x((xxTT) (ALGr)) + bmax 2 SW(OPT). So for the rest of the proof we assume K. o 0. We bound the portions of SW(Xorr) contributed by k E IC using the following claim.
Claim 2. For all le E KC (i' and i E N,, we have
by W.
(ALG()
W:
That is, advertisers that are allocated less space in ALG, than in x", must have lower as otherwise their rich ad would be considered by ALG, and they will be allocated more space.
7

---

Finally we bound the contribution of i', that is the ad allocated fractionally in OPT as follows:
Claim 3. Let (bs. s), (be, E) with s < l be the ads used in x the optimal fractional allocation for i'. It holds that: (i) he-
8-s < W. i E N. and (iii if 8 S Wi then by S (AL..))
(.ILG) for all E N, (ii) if > We, then ha (ALG() for all W
The proof of this claim is more involved. Intuitively we can bound the smaller of i's allocated ads (if it is small enough) with the value i' obtains in ALG, and the larger ad since it is allocated last has the lowest incremental bang-per-buck than any other advertiser's ad and hence the incremental lang-per-bucks is also lower than the other ad's actual bang-pere nang-per-buck.
We put all the claims together to bound Val(x", [t),,, W.) Ifs We, then by Claims and we see that the bang-pe per--eerreeee ber-buck of & E JKU { is less b, (ALG for all i. Then the value for K. U } in OPT is less than the contribution of advertisers using the same total space in ALG
(I) If s I Wy, then by Claims 2 and we get that b, < by X (ALG)) and the bang Bang-per- perg--ee--uckk--e buck of the ads in ALGB is higher than that of K \ { and be-b,, Thus we have.
Val(x", KU (F), ())= S Val(x", ('', by x S Val(x(ALGB).
8-3
Val(x", KKU KU ('), W S Val(x", ( (1), W + b, + (W; - be-ba b
(-s
I Val(x(ALGGB) W) + by xx (ALG1)
(2)
Hence by putting both I and IC together we get,
SW(Xorr)= Val(x*, ,I) (t', WT) + Val(x* KCU (f), W*)
I Val(x(ALGr), (t') W) + V,, W) + by Xx (ALGI)
Val(x(4EG;),,,, + Val(x(ALG
< 2Val(x(ALG)).. W) + bmaz
where the first equality is the definition of (WxXor)), and the second inequality puts together Claim I and Equations (1), and (2). The third inequality holds because I (f' S N. The final inequality holds because b. x; (ALGT) 2 b, (ALGG B) for all + i", and by X x (ALGa) S bmaz.
Thus we have that (W(XorT) S (A W) + bmax Therefore, running ALG, with probability 2/3 and allocating bmax with probability 1/3 is 3-approximation to SW (XOPT)) Since our algorithm is randomizing between two monotone rules, it is monotone as well. We give an instance which shows that the approximation of the algorithm is at least 3 in Appendix C.
5 Experiments
In this section we present some empirical results for our truthful mechanisms. The allocation rules we use for our theoretical results can be extended to obtain higher value. First extend ALG, to skip past a high bang-per per-buck buck ad that does not fit in the remaining space. More precisely, recall that ALG, calls ALGB to get the space allocation. ALG n stops when the ad being considered cannot be fit fully in the remaining space. The advertiser corresponding to this ad still gets allocated the remaining space, which is filled with the highest-value ad that fits in prot-procsssing In our modified version, we update AL.G g to skip past this large ad. This is equivalent to dropping step (3) of ALG B (i.e., we keep going until we run out of ads), and running the rest of ALG, as is. We call this modified algorithm GreedyBy BrredyByBangPere BangPerBuck. For our theoretical result we also select the maximum value ad with probability 1/3. In practice this can be very inefficient. For our empirical evaluation, we extend this to continues to allocate as long as space is remaining. Similar to the Greedy By BBygnngerBBuck the algorithm skips past a high value but large ad that cannot fit, and continues allocating until the space or the set of rich ads runs out. We call this algorithm GreedyBy Value. is worth noting that these extensions do not improve the worst-case approximation ratio of Theorem 3: we include a brief proof in Appendix F. We implement our proposed randomized algorithm by flipping a coin with probability 2/3 for each query and selecting the result of Greedyyyle Bag algorithm if it is heads and GreedyBy Value otherwise. We call this RandomizedGreedy, As bascline,
8

---

Algorithm
ApproxECPM
time-msec
GreedyByBangPerDBee
0,9493
0.7363
GreedyByVer Value
0.9196
0.3242
RandemizedGreedy
0.9393 = 0.0001
0.5983 = 0.0007
IntOPT
1.0
6.9988
Table I: Average performance of the algorithms compared to IntOPT. We report average approxi- mation of eCPM relative to IntOPT and average running time in miliseconds. We report confidence intervals for the randomized algorithm by noting the average performance over all queries over 100 runs.
45 MCFT
Hy Cwwphhit
Tandentredrreeey
Figure I: Histogram of approximation factor for IntOPT, Greedy GreedyyyyaagPeerBuce and RandomizedGreedyy compared to Fractional Optimal.
have implemented InOPP, that uses seute-horce-search to evaluate all possible allocations and compute the optimal integer allocation. This allocation paired with the VCG payment rule (which is computed by computing the integer OPT with advertiser é removed, and subtracting from that the allocation of all advertisers other than in the optimal allocation) gives the VCG mechanism. Finally, we implement the incremental bang-per-buu order algorithm as IncrementalBPB to compute the fractionally optimal allocation.
We evaluated our algorithms from real world data obtained from a large search advertising company. The data consists of sample of approximately 11000 queries, selected to have least 6 advertisers each. All the space values for the rich-ads are integer. We use 500 as the space limit as that is larger than the space of any individual rich ad. Table compares the average performance of these algorithms. Our algorithms are comparable to InOPP, on average, but require a lot less time to run.
We first compare the approximation obtained by various algorithms to the fractional-optimal. In and IntOPT obtain at least 0.55 fraction of the fractional opt, while the approximation factor for BrredyByyallu can be as low as 0.4. There is also a substantial amount of mass the 1.0 bucket where integer-opt and fractional-opt coincide and the greedy al algorithms also sometimes achieve that. Next we compare the approximation obtained by various algorithms to IntOPT
Figure we see that
In Figure 2 we see the approximation obtained by various algorithms compared to the IntOPT allocation. There are more queries where we obtain the optimal approximation, but the worst- case is still 0.6 for we plot a heatmap to correlate the approximation factor obtained by GreedyyyBanggerrte Greedy By Value with IntOPT as the baseline. In Figure 2, we compare the approximation factor of
and 0.4 for GreedyBy Value. For additional insight,
and
57
03
00
04
05
0.5
0.4
045 10
Figure 2: Histogram of approximation factor for Greedy Vallue Value, BeeedyyyBangPerBaaee and ran- domized Greedy compared to IntOPT. Height of each bucket represents the fraction of queries in the bucket. Last figure shows correlation of approximation factor relative to IntOPT for GreedyBy Color-scale in the heat-man map by log(number of queries) bucket.

---

and AI Dww.elllooeeeaesst
14
04-
Figure 3: CDF running time in milliseconds for for GreedyBy Value, IntOPT algorithms.
GreedyBy Valuue and BrreddyyyannPerBBBuce Blank spaces in this plot correspond not having any queries with a particular combination of approximation factors. We note that a lot of the queries have the same approximation factor for Greedy Value and GreedyByBangPecee more often has better
indicating
that RandomizedGreeddy won't t make mistakes. But approximation factor than GreedyByVale Value, sticking GreedyBy BangPerBuck as the only heuristic might perform better. Finally, in Figure 3 we compare the clock-time of our allocation rules with that of the IntOPT allocation rule.
These allocation rules are monotone, so they can be paired with Myerson's 's payment rule as implied by Lemma 1. We evaluate the time required to compute the payments and relative revenue compared to VCG in Appendix G (Table 3). Since the focus of our paper is welfare maximization we do not consider reserve prices. A possible direction for future work is study the trade-offs between welfare and revenue of our mechanism under different reserve prices. Additionally, in Appendix G we evaluate our algorithms with added cardinality constraints and show that obtain reasonable approximations to the optimal allocation.
Acknowledgements
The work Divyarthi Mohan was partially supported by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement no. 866132) and by the Israel Science Foundation (grant no. 317/17). Alexandros Psomas is supported in part by NSF CAREER award CCF-2144208, Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Any opinions, findings, and conclusions recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of Algorand Foundation. Part of this work was done when Mohan and Psomas were employed at Google Research.
10

---

References
[AGM06] Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In Joan Feigenbaum. John C.-I. Chuang, and David M. Pennock, editors, Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), Ann Arbor, Michigun, USA, June 11-15, 2006, pages 1-7. ACM, 2006.
[CF21] Ethan Cramer-Flood. Worldwide digital ad spending year-end update. e-Marketer,
2021.
[CKK* + 15] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Ky- ropoulou, Brendan Lucier, Renato Paes Leme, and Eva Tardos. Bounding the inefficiency of outcomes in generalized second price auctions. J. Econ. Theory, 156:343-388, 2015.
[CKKKI1] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Ky- ropoulou. On the efficiency of equilibria in generalized second price auctions. In Proceedings of the 12th ACM conference on Electronic commerce, pages 81-90, 2011.
[CKSW17] Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko, and Christopher A. Wilkens. Sponsored search auctions with rich ads. In Rick Barrett, Rick Cummings, Eugene Agichtein, and Evgeniy Gabrilovich, editors, Proceedings of the 26th Interna- tional Conference on World Wide Web, WWW 2017, Perth, Australia, April 3-7, 2017, pages 13-51. ACM, 2017.
[CMSW20]
Riccardo Colini Baldi-B,ldeschi, Julián Mestre, Okke Schrijvers, and Christopher Wilkens. The ad types problem. In Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta, editors, Web and Internet Economics 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings, volume 12495 of Lecture Notes in Computer Science, pages 45-58. Springer, 2020.
[DGS+20] Nikhil R Devanur, Kira Goldner, Raghuvansh Saxena, Ariel Schvartzman, and S Matthew Weinberg. Optimal mechanism design for single-minded agents. In Pro- ceedings of the 21 ACM Conference on Economics and Computation, pages 193-256. 2020.
[DP220] Nikhil R Devanur, Nima Haghpanah, and Alexandros Psomas. Optimal multi-unit mechanisms with private demands. Games and Economic Behavior, 121:482-505, 2020.
[DSYZ10] Xiaotie Deng, Yang Sun, Ming Yin, and Yunhong Zhou. Mechanism design for multi- slot ads auction in sponsored search markets. In Der-Tsai Lee, Danny Chen, and Shi Ying, editors, Frontiers in Algorithmics, pages 11 11-22, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
[DW17] Nikhil R Devanur and Matthew Weinberg. The optimal mechanism for selling budget constrained buyer: The general case. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 39-40, 2017.
[EOS07] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-prics auction: Selling billions of dollars worth of keywords. American Economic Review, (7(1):242-25 March 2007.
[FGKK16] Amos Fiat, Kira Goldner, Anna Karlin, and Elias Koutsoupias. The fedex problem. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC 16, page 2 21-22, New York, NY, USA, 2016. Association for Computing Machinery.
[GHLY19]
MohammadAmin Ghiasi, MohammadTaghi Hajiaghayi, Sébastien Lahaie, and Hadi Yami. On the efficiency and equilibria of rich ads. In Sarit Kraus, editor, Proceedings of the Swenty-Fight International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 301-307. ijeai.org, 2019.
11

---

[HIK' + 18] Jason D. Hartline, Nicole Immorlica, Mohammad Reza Khani, Brendan Lucier, and Rad Niazadeh. Fast core pricing for rich advertising auctions. In Eva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 111-112. ACM, 2018.
[Hum16] Patrick Hummel. Position auctions with dynamic resizing. International Journal of Industrial Organization, 45:38 46, 2016.
[KP99] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual symposium on theoretical aspects of computer science, pages 404-413, Springer, 1999.
[Law79] Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4(4):339-33 -366, 1979.
[LB10] Brendan Lucier and Allan Borodin. Price of anarchy for greedy auctions. In Proceedings of the twenty-first annual ACM-SIAM symposium Discrete Algorithms, pages 537- 553. SIAM, 2010.
[LPL11] Brendan Lucier and Renato Paes Leme. Gsp auctions with correlated types. In Proceed- ings of the 12th ACM conference on Electronic commerce, pages 71 71-80, 2011.
[MV09] Alexey Malakhov and Rakesh V Vohra. An optimal auction for capacity constrained bidders: network perspective. Economic Theory, 39(1):113-128; 2009.
[Mye81] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
[NR01] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games Econ. Behav. 35(1-2):166-99) 2001.
[NR10] Uri Nadav and Tim Roughgarden. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In Amin Saberi, editor, Internet and Network Economics 6th International Workshop, WINE 2010. Stanford, CA, USA, December 13-17, 2010. Proceedings, volume 6484 of Lecture Notes in Computer Science, pages 319-326. Springer, 2010.
[Rou15a] Tim Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5):32:1- 32:42, 2015.
[Rou15b] Tim Roughgarden. The price of anarchy in games of incomplete information. ACM Trans. Economics and Comput., ((1))::::6662))) 2015.
[ST13] Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceed- ings of the forty-fifth annual ACM symposium on Theory of computing, pages 211-220, 2013.
[SZ79] Prabhakant Sinha and Andris A. Zoltners. The multiple-choice knapsack problem. Operations Research, 2733)-003-515, 1979.
[Var07] Hal Varian. Position auctions. International Journal of Industrial Organization, 1666)1163 2007.
[VH14] Hal R. Varian and Christopher Harris. The veg auction in theory and practice. American Economic Review, 104(5):442-45, May 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See "Results and Techniques" and Section 5
12

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See technical sections (all but Section 5)
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs missing from the first pages can found in the appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [No] The data is proprietary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We report error bars due randomization of the algorithm and report distribution over sample of queries.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We ran our algorithms on a single machine.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or URL? [No]
The assets are proprietary
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] The data does not contain any personally identifiable information or offensive content
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "xSptrXWA4Ld", "reviewer": "Reviewer_j41M", "summary": "The paper study the internet as auctions problem with the advertiser has a rich set of ads with different value and space requirement. They adopt the `Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads.  The shows that the proposed a new, simple, greedy and monotone allocation rule that guarantees a  three approximation as compare the optimal.", "questions": "see weakness above.", "limitations": "No", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. the study problem is interesting.\n2. Theoretical results is provided.\n3. Experimental results is conducted.\n\n# Weakness\n1. I am not familiar with this area. I am confused with the claim in the abstract that \"We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded.\".  This seems create a contradiction.  Since they provide a monotone allocation rule in this paper  and also shows in  Lemma 1 that a monotone allocation with the corresponding payment rule will lead to truthful auction.  Will this lead to a truthful auction ?\n\n2. The uploaded pdf version is obscure when zoom in.\n\nSince I am not familiar with this area, I am willing to align my score with other reviewers if they are experts in this area.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hdpGfIO31zz", "reviewer": "Reviewer_6VM1", "summary": "In this paper, the authors consider the “Rich Advertising Auctions”, where advertisers can opt in or\nout of showing different extensions with the ads, which also makes the setting not single-dimensional. The objective is to design truthful mechanisms to maximize social welfare. \n\nAlthough the VCG mechanism is truthful and maximizes social welfare, it involves solving an NP-complete problem which is thus not efficient. \n\nThe first result set in this work is that the authors show no deterministic monotone rule can approximate the optimal welfare within a factor better than 2, and they design a simple greedy and monotone allocation rule that guarantees a 3 approximation. This algorithm combines a greedy procedure using the bang-per-buck order, and a randomizing between this procedure and the largest value ad. \n\nThe second result is to consider the Generalized Second Price (GSP) payment rule, which charges each advertiser the marginal threshold below which their allocation changes. The authors show that this mechanism is not truthful, but the resulting price of anarchy is bounded, under the standard assumption of no-overbidding. \n\nThe authors also provide an empirical evaluation of the designed mechanism on real-world data.\n", "questions": "Can you say a few more words about how to apply “Myersonion payment function” to the experiments?", "limitations": "None", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAs far as I check, the results are correct. The paper is well written, and I can follow most parts easily. By the way, I actually think that most of the footnotes include quite important information for readers to understand the problem, which is not necessary to put in footnotes.\n\nAnother issue is about the presentation. I think some proofs in the main body can be sacrificed in exchange for a section of PoA, including the definitions there, like GSP and PoA. I think they are quite important for the authors to understand and appreciate the results. \n\n\nWeaknesses:\n\nI am not an expert on this work, and thus sought help from a colleague who works on Bayesian mechanism design. The comments are as follows. The new model is novel, which can be interesting to be studied. The results are not surprising, and most techniques are standard, including the Myerson Lemma, knapsack algorithm, and the way to analyze the price of anarchy. The results are good to be published, but may not be NeurIPS. \n\nI kind of agree with the colleague, but with low confidence. Although I do not have enough knowledge of recent progress in this area, some key ideas used in this paper are indeed straightforward. For example, the randomization and the bang-per-buck order procedure are widely used in knapsack-related problems. The analysis of PoA is also not surprising if I did not miss the technical obstacles here; It bounds each advertiser’s utility gain from deviation but we need to carefully take knapsack constraint into consideration. \n\nOverall, I think this paper is not exciting but can be accepted if space is allowed.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HxvBaw6MWf5", "reviewer": "Reviewer_rnSK", "summary": "The basic model of search advertising auctions is by now well understood, but industry has long faced a practical challenge when adapting this model to rich formats that can show multiple versions of each add of different sizes and with different combinations of decorations.  The resulting combinatorial problem has been challenging from both computational and incentive perspectives.  This paper proposes a simple greedy approach which is a variant of the optimal fractional algorithm.  This forms the heart of a truthful mechanism which is shown to have both provable guarantees and strong empirical performance. ", "questions": "Part of the reason these approaches are needed is the intractability of VCG, but in the experiments VCG seems faster than I would have expected (0.03 msec).  Is the data used for the experiment nicer in some way than average? If not why is this performance of VCG inadequate?", "limitations": "See weaknesses", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nWhile the rich ad problem has received some prior attention in the literature, this is the first paper I have seen which presents what I would consider a largely “complete” solution.  The main theoretical result (Theorem 3) is compelling and supported by a number of other results which add to the richness of the paper.  I also appreciate that the analysis goes beyond simply achieving the theoretical bounds but discusses several heuristic improvements that do not affect the theory but improve performance in practice.  The empirical results provide a convincing demonstration of the benefits of the approach by showing strong performance relative to the theoretically intractable and practically 10x slower VCG.\n\nWeaknesses:\n- Results in the main paper feel somewhat cramped.  The paper does a reasonable job trying to fit things in within the page limits, but it does mean that quite a bit of the richness only really shows up in the appendix.\n- As is sadly often the case in this space the reproducibility of the work is limited due to the commercial sensitivity of advertising datasets.  Nevertheless, some work has done a better job of at least defining models for generating synthetic data and running experiments on it as well to provide somewhat greater reproducibility.\n- The one missing piece that led me to describe the solution as only “largely” complete is the omission of reserve pricing, which is crucial in practice.  This is acknowledged in Appendix G, and as mentioned the paper is already quite full, but I would have hoped for at least some discussion of how reserve prices can be reasonably applied since this doesn’t seem immediately obvious and I could imagine multiple ways to apply score-based reserves (raw score vs score-per-buck and per-advertiser vs per-variant).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8qQcmtpSwt", "reviewer": "Reviewer_f2B3", "summary": "The authors introduce a rich ads auction problem which can be considered as a special case of the well-known MULTI-CHOICE KNAPSACK problem. If the designer allocates ads using the bang-per-buck idea directly, there is an example that shows the allocation is not monotone. They show that no deterministic monotone rule can approximate the optimal welfare within factor 2. Their main result is a greedy allocation mechanism that approximates at least one-third of the optimal welfare. ", "questions": "I have no questions. ", "limitations": "There is no potential negative societal impact. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "There are some different versions of rich ad problems. The authors answer an open problem in [DSYZ10]. Both positive and negative results look strong to me. The mechanism is easy to implement in reality and the performance in the experiment is quite good. Overall, the paper is well-written. \n\nNo obvious weakness is found.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept