Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper considers the problem of 1 buyer, 1 seller selling k items. In the context of this problem, they look at a mechanism from prior work that relates the ratio of optimal revenue to the myerson's optimal revenue for the total bundle and the menuGap. In particular, prior work showed that there exists a sequence generated using a framework such that ratio of optimal revenue to the myerson's optimal revenue via showing menu gap is infinity. The first result in this paper is that this framework is without loss of generality. The second result in this paper is that there exists a sequence where align gap is small but the menu gap is infinity.
strengths_and_weaknesses: Originality

+ This paper is a primarily theoretical/conceptual paper where the goal is to understand prior work on revenue maximizing schemes for selling multiple items. This paper is original in that it pushes the state of understanding on this problem and some of the constructed schemes.

Quality

+ The obtained results, the corresponding proofs are of high-quality. The results are non-trivial to obtain and definitely improves the understanding of this specific problem.

Clarity

+ Overall the paper is well-written however, the target audience is a small set of people who understand the theory of prior work. The paper does not make much efforts to make this broadly accesible and/or mention why the results are significant.

Significance

This is the primary qualm I have with this submission. The paper is extremely niche and narrow to be of interest to a large machine learning community (e.g., Neurips). The paper seems to be making some incremental understanding over prior theorems. It is very hard for me to see why the results presented in this paper are important or significant. I believe this paper may be suitable for a niche conference for the appropriate community and don't believe this is appropriate for a conference like neurips.
questions: Could you please elaborate why the results obtained in this paper are significant/relevant for the larger machine learning community? In my opinion, I think the paper needs to be written more broadly and accessible
limitations: This is a primarily theory paper. So there aren't much potential negative societal impact.
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 authors focus on multi-item mechanism design with valuations distributions that are correlated across items. They study conditions under which there is an infinite gap in revenue between the optimal mechanism and grand bundling/simple mechanisms.
strengths_and_weaknesses: I really enjoyed reading this paper. I think it provides a useful understanding of when optimal mechanisms can have finite vs infinite size for multi-item auctions. 
- The topic is important and interesting, as it sheds light on when simple and practical mechanisms perform well, in non-trivial settings in which the valuation distribution can be correlated across items. -  - Theorem 6 shows that the framework of Hart and Nisan is essentially "tight". Hart and Nisan showed the following result: let M be a mechanism (of infinite menu size). If for some distribution D, M gets infinitely more revenue than any mechanism with a finite menu) then MenuGap(X) is infinite where X is related to the support of D. 
The current paper shows the converse, showing that this characterization is essentially tight: for any distribution D with an infinite gap, there is a set X of points in the support of D such that MenuGap(X) is infinite.
In turn, the paper shows that the quantity MenuGap is essentially the right metric to characterize whether the gap between any finite and the optimal mechanism is infinite in terms of revenue. 
- Despite Theorem 6 stating the existence of an X as described above, the proof of Theorem 6 actually shows how to construct this X if we know the distribution D. This provides a way to verify systematically/algorithmically when the revenue gap is finite (it suffices to construct this X and compute its MenuGap. If it’s finite, then the revenue gap is finite).
- The authors extend their results to show that AlignGap, a natural but more restrictive version of MenuGap motivated from previous work does not enjoy the same property: there can be an infinite gap between AlignGap and MenuGap. This means that there exists situations where AlignGap(X) is finite, but there exists a distribution D on (a rescaling of) support X with an infinite revenue gap. 
- I believe the techniques are non-trivial and interesting (for example the proof of Theorem 6 requires throwing away menu options that have low prices, and dividing the support of the valuation distribution according to price intervals of growing size), yet the paper is written in such a way that they are very easy to follow.


Weakness:
- I believe the main weakness of the paper is that even though the paper shows that MenuGap seems to be the right/tight measure of complexity of the problem, there is a slight mismatch between theorem 2 and 6. In particular, Theorem 2 does not allow you to argue directly whether the ratio of revenues is infinite for a given distribution D, as it does not tell you how to find a X’ such that MenuGap(X’) lower bounds the ratio of revenues between optimal and simple mechanisms. Rather, it constructs D from X’. It would be useful to provide such a construction for the characterization to be fully tight algorithmically.

Despite this weakness, I think this is a good paper that provides additional understanding on what optimal mechanisms look like in multi-dimensional mechanism design with correlated valuations, and I would like to see the paper accepted. 

questions: - Do the authors of the paper have a sense of whether it is possible to construct/how, for any distribution D with infinite gap, some set X such that MenuGap(X) is also infinite? I think saying a word about this would tighten the results of the paper
limitations: N/A
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 authors study Bayesian mechanism design where the goal is to maximize expected revenue of selling k (heterogeneous) items to a single buyer with additive valuations.
The authors investigate when the optimal revenue is infinite while the best-possible revenue from selling all items in a grand bundle is finite; this question has significance for understanding the power of any mechanism (such as deterministic bundle pricing) that has a finite menu size.
A reduction from previous work provides a recipe for constructing such "infinitely-separated" instances, by constructing instances with infinite MenuGap.

The authors' first main result is that infinite MenuGap is also a _necessary_ condition for an instance to be infinitely-separated.
A subclass of such infinite-separated instances can be characterized by those also with an infinite SupGap, which is always less than MenuGap.
Previous constructions of infinite MenuGap always involved infinite SupGap, suggesting that infinite SupGap may also be necessary for an instance to be infinitely-separated.
However, the authors' second main result is to show that this is false---in fact, they construct an infinitely-separated instance that has not only finite SupGap, but even finite AlignGap, a concept introduced by the authors.
strengths_and_weaknesses: +: This paper has exceptional writing: concise, yet precise and an easy to follow train of thought.

+: The results are quite complete and provide a comprehensive understanding of when Rev/BRev = infty.

+: I agree with the authors that AlignGap is the right concept to use to make their second main result stronger, and find this to be generally useful.

-: Although I like the theory, I'm not sure why I should care about characterizing the pathological instances with Rev/BRev=infty, especially in a broader Neurips context.  The paper also does not make much effort to address this, until the end of the Conclusion, and even those connections are used to answer further mostly-theory questions.  Anyways, this discussion could be outside the scope of this particular paper, and I am overall quite positive about it.
questions: I have zero clarification questions because the manuscript was crystal clear.

If the authors have space, perhaps they could entertain the one weakness I pointed out.  I find the questions being studied centered about pathological worst-case constructions, and would love to know whether these instances are believed to arise in practice, or whether answering these questions is useful for informing auction design in practice.
limitations: N/A
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: This paper studies separation between the simple and optimal mechanisms in terms of revenue when selling $k$ heterogeneous items to a single buyer. An arguably simple scheme is to offer to sell either all the items together at a fixed price or nothing (hence treating all the items together as a grand bundle). Let us call the revenue achieved by this strategy the "bundle revenue", we denote its value by $BRev(\mathcal D)$, where $\mathcal D$ is the distribution of the valuations of the buyer for each item (valuations for different items can be correlated). However, there is no reason to believe that this would give the best possible revenue. I.e. there is no reason to believe that $Rev(\mathcal D)$ (the optimal revenue for distribution $\mathcal D$) and $BRev(\mathcal D)$ are equal, or even close.

Indeed, a recent work [HN19] exhibits instances where the multiplicative gap between $BRev(\mathcal D)$ and $Rev(\mathcal D)$ is infinite. To achieve this result, they identify a geometric quantity that is based on defining two sequences of $k$-dimensional vectors where $X=(\overrightarrow{x_i})$ with $\overrightarrow{x_i}\in \mathbb R_{\geq 0}^k$ and $Q=(\overrightarrow{q_i})$ with $\overrightarrow{q_i}\in [0,1]^k$. From these two families, one can define a quantity called MenuGap$(X,Q)$ that is intimately linked to the multiplicative gap $Rev(\mathcal D)/BRev(\mathcal D)$.

Specifically, [HN19] shows that for any $X,Q$ and any $\epsilon>0$, there exists a distribution $\mathcal D$ such that $Rev(\mathcal D)/BRev(\mathcal D)>(1-\epsilon) \cdot$MenuGap$(X,Q)$.

This result raises 2 natural questions:

1) Is MenuGap$(X,Q)$ the "right" quantity to get multiplicative gaps $Rev(\mathcal D)/BRev(\mathcal D)$?
2) Looking at the result of [HN19], one can observe that the vectors $\overrightarrow{x_i}\in X$ and $\overrightarrow{q_i}\in Q$ are colinear for all $i$. In fact, *all* constructions of some MenuGap$(X,Q)$ quantity in the past literature satisfy this property. Does there exist constructions such that MenuGap$(X,Q)$ is big but only of $Q$ and $X$ are *not* colinear?

The authors answer both these questions. For the first one, they show that for any distribution $\mathcal D$ there exists two families of vectors $X,Q$ (with $X$ that is included in the support of $\mathcal D$) such that MenuGap$(X,Q)>Rev(\mathcal D)/(9\cdot BRev(\mathcal D))$. That is, if we do not care about constant factors, the theorem of [HN19] is "complete" in the sense that every distribution that witnesses a specific gap can be obtained through this theorem.

For the second question, the authors answer positively. There exists a set $X$ where MenuGap$(X,Q)$ can be unbounded for a suitable $Q$ but MenuGap$(X,Q)<6$ for any $Q$ that is colinear to $X$. This result reveals that there are constructions that are fundamentally different from previous works.
strengths_and_weaknesses: The strengths are (in my opinion) the following:

- The paper is well-written and clear given the quite complicated definitions.
- The results seem non-trivial and correct.
- The results seem interesting. I am not an expert in mechanism design but the gap between simple and complicated mechanisms seems important to understand (and in particular its relation with this geometric quantity). This paper gives results in that direction.

I see no obvious weaknesses.
questions: I did not see any typo, the paper is in general clearly written. But here are a few remarks:

- Is there an intuition as to how you constructed the non-aligned example? It would be nice to explain a bit more if there is any intuition.

- if space permits, I would have put the proof of Claims 18-19 in the main body of the paper.
limitations: NA
review_title: null

Meta-review: metareview: This very well-written studies Bayesian mechanism design where we aim to maximize the expected revenue of selling k items to a single buyer with additive valuations. The authors investigate when the optimal revenue is infinite while the best-possible revenue from selling all items in a grand bundle is finite; this question has significance for understanding the power of any mechanism---such as deterministic bundle pricing---that has a finite menu size. A reduction from previous work provides a recipe for constructing such "infinitely-separated" instances, by constructing instances with infinite "MenuGap". The first main result is that infinite MenuGap is also a necessary condition for an instance to be infinitely-separated. A subclass of such infinite-separated instances can be characterized by those also with an infinite "SupGap"---a gap that is upper-bounded by the MenuGap. Previous constructions of infinite MenuGap always involved infinite SupGap, suggesting that infinite SupGap may also be necessary for an instance to be infinitely-separated; the second main result falsifies this by an infinitely-separated instance that has finite SupGap. 

Despite some concerns about fit with NeurIPS, I find the overall fit quite good. 

confidence: Certain
Decision: Accept