Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: In this paper, the authors consider the “Rich Advertising Auctions”, where advertisers can opt in or
out 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. 

Although the VCG mechanism is truthful and maximizes social welfare, it involves solving an NP-complete problem which is thus not efficient. 

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

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

The authors also provide an empirical evaluation of the designed mechanism on real-world data.

strengths_and_weaknesses: Strengths:

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

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


Weaknesses:

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

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

Overall, I think this paper is not exciting but can be accepted if space is allowed.

questions: Can you say a few more words about how to apply “Myersonion payment function” to the experiments?
limitations: None
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
While 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.

Weaknesses:
- 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.
- 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.
- 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).

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
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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. 

No obvious weakness is found.
questions: I have no questions. 
limitations: There is no potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: # Strengths
1. the study problem is interesting.
2. Theoretical results is provided.
3. Experimental results is conducted.

# Weakness
1. 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 ?

2. The uploaded pdf version is obscure when zoom in.

Since I am not familiar with this area, I am willing to align my score with other reviewers if they are experts in this area.
questions: see weakness above.
limitations: No
review_title: null

Meta-review: metareview: Reviewers agreed that rich ad auction is significant and are excited about theoretical bounds on the positive result (achieved by a simple mechanism) and the negative result. Overall, this is a solid theoretical paper on an important and classical problem in industry.
confidence: Certain
Decision: Accept