On Infinite Separations Between Simple and Optimal Mechanisms
Authors: Alexandros Psomas
Ariel Schvartzman
S. Matthew Weinberg
Venue: NeurIPS 2022 Accept (2022)
Keywords: mechanism design
revenue maximization
correlated distributions

Abstract: We consider a revenue-maximizing seller with $k$ heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior $\mathcal{D}$. It is known that there exist priors $\mathcal{D}$ such that simple mechanisms --- those with bounded menu complexity --- extract an arbitrarily small fraction of the optimal revenue~(Briest et al. 2015, Hart and Nisan 2019). This paper considers the opposite direction: given a correlated distribution $\mathcal{D}$ witnessing an infinite separation between simple and optimal mechanisms, what can be said about $\mathcal{D}$?

\citet{hart2019selling} provides a framework for constructing such $\mathcal{D}$: it takes as input a sequence of $k$-dimensional vectors satisfying some geometric property, and produces a $\mathcal{D}$ witnessing an infinite gap. Our first main result establishes that this framework is without loss: every $\mathcal{D}$ witnessing an infinite separation could have resulted from this framework. An earlier version of their work provided a more streamlined framework (Hart and Nisan 2013). Our second main result establishes that this restrictive framework is not tight. That is, we provide an instance $\mathcal{D}$ witnessing an infinite gap, but which provably could not have resulted from the restrictive framework. 

As a corollary, we discover a new kind of mechanism which can witness these infinite separations on instances where the previous ``aligned'' mechanisms do not.

On Infinite Separations Between Simple and Optimal Mechanisms
Alexandros Psomas
Ariel Schvartzman
S. Matthew Weinberg
Abstract
We consider geeeue-maximizing seller with k heterogeneous items for sale a single additive buyer, whose values are drawn from a known, possibly correlated prior D. is known that there exist priors such that simple mechanisms those with bounded menu complexity optimal revenue (IBCKWIS 15, HN19]). This paper considers the opposite direction: given correlated distribution DD witnessing an infinite separation between simple and optimal mechanisms, what can said about DD?
extract an arbitrarily small fraction of the
[HN19] provides a framework for constructing such D: it takes as input a sequence of k-dimensional vectors satisfying some geometric property, and produces D witnessing an infinite gap. Our first main result establishes that this framework is without loss: every D witnessing infinite separation could have resulted from this framework. An earlier version of their work provided a more streamlined framework [HN13]. Our second main result establishes that this restrictive frame- work is not tight. That is, we provide an instance D witnessing an infinite gap, but which provably could not have resulted from the restrictive framework.
As a corollary, we discover a new kind of mechanism which can witness these infinite separations instances where the previous "aligned" mechanisms do not.
1 Introduction
Consider revenue-maximin maximizin seller with items for sale to single additive buyer, whose values for the k items are drawn from known distribution D. When & 1, Myerson's seminal work provides a closed-form solution to the revenue-optimal mechanism, and it has particularly simple form: simply post price == arg maxp {p Pree-p(u 2 p]}. and let the buyer purchase the item they please ([Mye&1]). I].. For > 1, however, this multi-dimensional mechanism design problem remains an active research agenda forty years later.
While simple, constant- factor approximations are known in quite general settings when D is a product distribution ([CHK07, CHMS10, CMS15, KW12, LY13, BILW14, Yao15, RW15. CDW16 16, CM16, CZ17D, there may be an infinite gap between the revenue-optimal auction and any simple counterpart when values are correlated (BCKW115, 15, HN19]). More specifically: one simple way to sell k items is to treat the grand bundle of all items as if were a single item, and sell using Myerson's 's optimal
'Department of Computer Science, Purdue University, apsomas @amomas@cs.ppp @c.. purdupurdeeeeee edu. Supported part by an NSF CAREER award CCF-2144208, a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of Algorand Foundation.
'Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), schvart- man.ariel@ meriel@gmail.com Research conducted while at DIMACS, Rutgers University and supported by the National Science Foundation under grant number CCF-1445755.
Department of Computer Science, Princcton University, smweinberg@ princeton.edu. Supported by NSF CCF- 1717899
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

auction (which sets price arg maxp(p- Pra-- DIE 2 pl)). Letting BRev(D) denote the revenue achieved by this simple scheme, [HN19] further show a connection between (Rev(D) and any simple mechanism through the lens of menu complexity; any mechanism with menu complexity at most C generates expected revenue at most C- BRev(D).
These works establish a strong separation between simple and optimal auctions: even when k = there exist distributions D such that Rev(D) oo (the optimal revenue) while BRev(DD 1. The fact that Rev(D) = oc does not on its own suggest that D must be "weird" (the one- dimensional distribution with CDF Rev(D) (D))/B)v(D) = oc, which can never occur for a onnediinn distribution.
1/vz has this property). The "weird" property is that
[BCKW15] and [HN19] establish sufficient conditions for distribution D to satisfy Rev(D) (D)/BRev (D)= = oo. Simply put, the goal of this paper is to study necessary conditions for a main results. The first establishes that the sufficient condition presented in [HN19] is in fact necessary for Rev(D) ((D))BRe(()) = oo (Theorem 6). The second establishes that the sufficient condition used in an earlier version of that work [HN13] and [BCKWI5 15] is not necessary (Theorem 9). In establishing Theorem 9, we also construct a distribution D such that Rev(D)/BRev(2) = oc yet the mechanism witnessing this provably falls outside the scope of any previous constructions (Corollary 11).
distribution satisfy Rev (D) (D))
oc. We provide
A recent line of work has borrowed tools from machine learning (more specifically, recommender systems) to approximate buyers with complex, high-dimensional valuations via cow-dimensional topic models [CD22]. Their work recognizes some settings where finding approximately optimal mechanisms for these buyers reduces to finding approximately optimal mechanisms for buyers whose valuations are approximated by the topic models. In this context, work helps clarify the limits where this modeling approach is effective: a model is tractable if and only if it steers clear of the [HN19] framework. Beyond this specific direction, we note that there is a significant community at the intersection of machine learning and multi-item auction design, and understanding the limits of tractability is important for this community.
Proper context and formal statements of our results require precise definitions, which we provide in Section 2 immediately below. Section 3 provides formal statements of our results, along with context alongside related work. Subsequent sections provide proofs.
2
Preliminaries
We consider an auction design setting with single buyer, single seller, and k heterogeneous items. Note that our positive results hold for arbitrary k, while our constructions use only k = 2 (and k = 1 not possible). We use D to denote a distribution over TR the (possibly correlated) distribution over the buyer's values for the k items. The buyer is additive, meaning that their value for set of items S is equal to Eies 02- We use Rev(D) to denote the optimal expected revenue achievable by any mncentive-compation mechanism (formally, the supremum of expected revenues, or do if the supremum is undefined), and let BRev(D) denote the revenue achieved by selling the grand bundle as single item using Myerson's 's auction. Finally. a mechanism M is a set {(7, h. where each T E [0, 1kk denotes vector of probabilities, and p; E IR denotes a price. When the buyer's valuation is J, they pay the auctioneer P:(T). where i( := arg max, T q p... Rev (ev(D, .M) denotes the expected revenue achieved by particular mechanism M on distribution D. We will also use the shorthand gt (T7) to denote the allocation vector purchased by a vector ह, and DM (īJ) to denote the price paid (we may drop the superscript of M if the mechanism is clear from context).
Brief Overview of [HN19]. Below, we formally define two geometric properties of sequences of points, which are the focus of this paper. Many of the ideas below appear in both [BCKWIS) 15] and [HN19], but we will use the formal definitions from [HN19] (and an earlier published ver-
'We briefly remind the reader that BRev(D) serves as proxy for the achievable revenue by any simple mechanism, especially when focusing on the gap hetween infinite and finite. For example, the revenue achieved hy selling the items separately is at most &BRev(D) the revenue achieved by any deterministic mechanism is at most 2* BRev(D) (D). and, more generally, the revenue achieved by any mechanism which offers most m distinct options is at most mBRev(() [HN19]]
'How ties are broken is irrelevant to our results all results hold for arbitrary biebbrea Also, all mechanisms include an all-zero pair g (O..... 0). po 0 to insure individual rationality.

---

sion [HN13]), Below, morally the vectors T. correspond to possible (scaled) valuation vectors, and the vectors &. correspond to possible vectors of allocation probabilities.
Definition 1. Let +00), with each H; E 20 Let Q = ( be another ordered sequence of N points, with each T E [0, 1)2, and starting with qo = (0, 0). Define the following:
(T=) be an ordered sequence of N points (N may be finite, or equal to
N
X,Q
gap;
X.Q
min ( USJC
7 Z.
MenuGap(X,9)
Σ
gap;
|
We will also slightly abuse notation and define MenuGap(X) supo (MenuGap(X,
MenuGap( X) some measure of how distinct the angles of points in X are. To get intuition for this, might try to write short proof that when & 1, MemuGap(X) MenuGap( X) = whenever all H. E X are parallel). We provide such proof in Appendix A. MenuGap(A Q) is just some geometric measure with no obvious intuition for why this quantity should be of interest to auction designers. However, one key result of [HN19] shows that this quantity has connections to simplicity
1 for all X (or that
optimality gaps. Specifically, they show:
Theorem 2 ([HN19), Proposition 7.1). For every pair of sequences X (E.) (g:) starting with To = (O,..., 0), and all & > O, there exists distribution 'D and mechanism M s.t.:
Rev(D, M) (1- -Mee-Meaa (X, Q).
BRe
Moreover, for all i E [N], the support D contains single point of the form CgTs, for some Ci E R.+ (and other points). Additionally, 9a (c.T.) T/
The "Moreover...." portion of Theorem 2 gives some insight to their construction. Further insight can be deduced by observing that the constraint "gap," - E. (Ø: -"-)"""" "fy"" looks similar (but far from identical) to an incentive compatibility constraint involving a valuation vector ž; and two allocation vectors T., 7j. We refer the reader to [HN19] for further details and intuition for this connection. Theorem 2 gives a framework for proving simplicity vs. optimality gaps, but leaves open the question of actually finding pair of sequences X, Q. They approach this through the following observation:
Definition 3. Given a sequence of points X (2)) 13 starting with To = (0, ..., 0). define SupGap(X) (read "support gap of ") as SupGap(X) == MenuGap(X, X).
Observation 4. For all X, MenuGap(X) 2 SupGap(X).
Finally, [HN13] propose an explicit construction of a sequence X with infinite SupGap. Theorem 5 ([HN13]). There exists an infinite sequence X of points in [0, 1]2 s.t. SupGap(X) co.
Theorems 2 and together yield a two-dimensional distribution with Rev (D)) oc. It is also worth noting that all prior constructions follow this approach as well. For example, [BCKW15] provides an infinite sequence X of points in [0, 1]s such that SupGap(X) = 00. oo.
3 Our Results
Independent of Observation 4 and Theorem 5, Theorem alone provides a framework for constructing distributions 'D so that Rev(D) (D)//RBvv() (D) is large: find sequences X so that McnuGap( (X) is large. Our goal is to understand to what extent this framework is complete for constructing such instances. Our first main result establishes that any distribution with Rev (D)/BRev(D) = oc could have resulted from the frumework induced by Theorem 2. Specifically:
'Oserrve that gap; X.Q and MenuGap(X, Q) might be negative. Any claims made throughout this paper regarding MemuGap(XX X Q) are vacuously true when MenuGap(X* Q) < O. We allow gap, x.Q to be negative to match the definition of [HN19] verbatim (although our work will also show that this peculiarity of their detinition is not significant).
3

---

Theorem 6. For any distribution D over k items, there exists sequence of N points (N can be finite, or equal to +-0) X (Z:) with each H; E supp(D), such that
Rev(D)
MenuGap(X) (BR
In particular, (/ReeDD)/BBBvll = oc, then MemuGap(X)-
well.
complete proof of Theorem appears in Section 4. Observe also that because MenuGap(> (X) is monotone (in the sense that adding points to X, anywhere, cannot possibly decrease MenuGap(X the fact that X is a subset of the support of D (rather than the entire support) is immaterial." Put another way, the important aspect in constructing X is how elements in the support of D are ordered, rather than which points are included.
Observation 4 further provides a framework to construct sequences so that MenuGap(X X) is large: construct sequences X so that SupGap(X) is large. One may then wonder if SupGap(X) and MenuGap(X X)) are approximately related, for all X. For this specific question, the answer is triv- ially no, due to incompatibility with scaling (multiplying every point in X by 1/2 will decrease SupGap(XX X) by factor of 2, but not MenuGap(X)), Therefore, not much insight is gained by studying this precise question.
Instead, we observe that the interesting aspect of constructions resulting through SupGap(X) is that H and & are aligned (that is, क. G --66 4i for some G; Rza). Specifically, even if q = F. this equality is not maintained by the construction of Theorem 2. However, if q and o; are aligned, this alignment property is maintained by the construction. We therefore propose the following definition, which captures the maximum value achievable by MenuGap(X, Q) when X, Q are aligned.
Definition 7. Let X = (1:) be ordered sequence of N points in 1] (N may be finite, or equal to +oo), Let also C = (ci)/= be an ordered sequence of numbers, with each E [0, 101x starting with co Define:
and AlignGap(X,C) C) max sgap, X.C 1
sgap, X,C = min 2. (c, cjāz), J43
We will also slightly abuse notation and denote by AlignGap(XX == supo (Aligo(AllgGaa(.. C)).
Recall that we have chosen to let c; range in [0, 1/|| (rather than be fixed at 1, or 1/||ž, to give potential constructions flexibility in scaling q- Additionally, by ensuring that the contribution of each sgap, X.C X.C is non-negative, we give potential constructions flexibility to ignore points in the
sequence. That is, any construction using MenuGap directly can always set q == arg maj J. which effectively just drops ã from the sequence. Counting max(0. sgap, sgap;..) towards the objective (rather than just sgap, X.C) gives constructions that arise through AlignGap the same flexibility. Lemma 8. For all X, AlignGap(X) < MenuGap(X).
The proof of Lemma 8 is in Appendix B. Lemma 8 induces framework to design sequences with large MenuGap: design sequences with large AlignGap. Our second main result establishes that this framework is not without loss of generality, even for k = 2. Specifically:
Theorem 9. There exist sequences X
= E [0, 1]2 such that:
AlignGap(X) < but
MenuGap(X) dc.
A complete proof of Theorem 9 appears in Section 5. By the discussion following Definition 7, the source of this gap is entirely due to the requirement that the sequence Q be aligned with X (and is not due to inability to scale, or inability to ignore difficult points in X). We make this crisp with the following definition and corollary, which construct novel distribution witnessing (D)/BRev((D
Rev(D) BRev (D) = oo that is provably distinct from all previous approaches.
Definition 10. For distribution D and mechanism M, define the Aligned Revenue of M on D:
ARev(D, == Ee (U)-I(I is parallel to gM (7)).,
ARev(D) == (up(ARev(D, M)).
M
"Of course, if the support of D is uncountable, then clearly the entire support of D cannot be included in X.

---

ffr all Corollary 11. There exist distributions DD over two items such that Rev(D)/ARev()) = cc.
A proof of Corollary 11 appears in Appendix C. It is worth noting that all previous constructions estab- = oo proceeded by producing
lishing (ev(D)/BRev(()) the [BCKW15] construction provides such an X when A = 3, the [HN13] construction provides an X when & = 2, and the [PSW19] [1] construction adapts parameters in that of [HN13]. By Theorem 2, this implies not only that Rev(D), (D/BBD)))R)))
X such that SupGap co. Indeed,
20, but also that ARev (D) lary 11 establishes the existence of a fundamentally different construction," our D has a finite ratio between ARev(D) (D)/DD)))DD)))) (D), yet still maintains an infinite ratio between (D) (D))BRev(D)
oo, Corol-
Additional Related Work. We've already discussed the most related work to ours, which is that of [HN19, BCKW15]. There is also large body of work studying product distributions specifically, and establishes that simple mechanisms can achieve constant factor approximations in quite general settings [CHK07, CHMSI0, CMS15, KW12, LY13, BILWI4 14, Yao15, RW15, CDW 16, CM16, CZ17D. Recent works have made progress in obtaining arbitrary approximations ([BGN17, CMS+19J] which again rely on the assumption that D is product distribution.
Three recent lines of work address the [BCKW15, HN19] constructions in a different manner. First, [CTT19, CTT20] consider the related buy-many model (where the auctioneer cannot prevent the buyer from interacting multiple times with the auction). [CTT19] establishes that selling separately achieves an (log k- -aappooxiatiion to the optimal buy-many mechanism in quite general settings (including the settings considered in this paper). In a different direction, [PSW19] uses the lens of smoothed analysis ([STO4]) to reason about the robustness of the [HN19] constructions. Finally, [Carl7] considers a correlation robust framework in which the valuation profile is drawn from a correlated distribution that is not completely known the seller; the goal is to design a mechanism that maximizes the worst-case (over correlations) seller revenue, when only the items' marginal distributions are known. [Carl7] shows that selling each item separately is optimal; see [BGLT19, GL18] for further work in this model.
4 A Converse to Theorem 2: The [HN19] Framework is WLOG
In this section, we prove Theorem 6. Our proof has two main parts. First, we will take the optimal auction for 'D (or one that is arbitrarily close to optimal) and repeatedly simplify it through sequence of lemmas, at the cost of small constant-factors of revenue. The second part takes this simple menu and draws a connection to MenuGap. Missing proofs can be found in Appendix B.
Simplifying the Optimal Mechanism. We show that for every D, there exists an approximately- optimal mechanism which satisfies some useful properties. First, argue that may ignore menu options with low prices.
Definition 12.
We say that a mechanism M is c-expensive every option has price at least c. Claim 13. For all e E R>,, all distributions D, and all mechanisms M, there exists a c-expensive mechanism M' satisfying Rev(D, M') Rev(D, M) cc
Our next step will show that we can assume further structure on the prices charged, at the cost of a factor of two.
Definition 14. c-expensive mechanism M is there exists odd (respectively, even) integer i such that ad (T) E [c- 2 21+1).
(respectively,
Claim 15. For all c-expensive mechanisms M, and all D, there exists either an oddly-priced or evenly-priced c-expensive mechanism M' satisfying Rev M') Z Rev(D,
This concludes our simplification of the mechanism. In the subsequent section, we draw connection between MenuGap and the revenue of oddly- or evenly-prict c-expensive mechanisms.
Connecting Structured Mechanisms to MenuGap. We begin with the following definition, which describes our proposed X, K based on structured mechanism for D.
OOn technical level, our construction certainly borrows several ideas from previous ones, however.
5

---

Definition 16 (Representative Sequences), Let M be c-expensive mechanism which is oddly-priced or vvency-priced, and let DD be any distribution. An e-representative sequence for M, is the following:
Define (D, M) = (O,....
Define offset a to if is oddly-priced, and if M is evenly-priced.
For all j E N4, define B, == {ī E supp(D) pM MM (0) E [c- 1)+-1)+a c. 22 2205-1)at)))
For all j E M4. let F, B3 be such that ||رر|| S || (1 for all ē Bj.
For all j E N4, let q3 = qM (2z))
Proposition 17. Let M be c-expensive, and oddly- or evenly-priced. Let (X,Q) be an Rev(D.M)
representative sequence for M, D. Then: MemuGap(X, Q) 2 4(e+e)
Proof. The proof will follow from two technical claims. The first claim relates | and (R)v(D). The second claim relates Rev(D, .M) and MenuGap(X, Q). Crucially, this claim uses the fact that the mechanism is either oddly-priced -iiicy-ppeee or evenly-priced (and therefore pM (Æ.). (ø,) differ by at least factor of 2, for any i j).
Claim 18. (1 + +) (D) 2 ||:|| Pra-D(u E B:).
X,Q Claim 19. X, an s-representative sequence for M, then gap; gapx.0 2 Pd (2:)/2.
With these two claims, we can complete the proof of Proposition 17:
20
X.Q
gap
MemuGap(X, Q) =
|
M (T+)
(Claim 19)
||
Mdd (Zz) Pre E B,]
(Claim 18)
2 (1 + BRev(DD
1=1
E E DiFEE IE Mx)) PReNDIÜ E B,]
2
4. 4.(1 + ++)+)Re((V)
(Dv
2 4 (1+ B)Rev((D)
Above, the first line is the definition of MenuGap. The fourth line uses the fact that for all i E B, (M(T < 22( (((i-))+a11 Rev(D, M), and using the fact that every E supp(D) with (ū)) > 0 is in some B;-
22(1 1)+a < 2p (zt). The final line is just rewriting the definition of
Wrapping Up. Proposition 17, together with the fact that an oddly- or wenly-priced mechanism is guaranteed to get a good approximation to the optimum, now suffices to prove Theorem
Proof of Theorem 6. Set c Rev(D)/100, and 1/100. Note that e-representative sequences are guaranteed to exist for any M, D, as >> 0. Let M' denote the c-expensive mechanism promised by Claim 13. Let then M" denote the oddly- or evenly-prices mechanism promised by Claim 15. Finally, let X, Q denote the e-representative sequence for M" D. We get:
MemuGap(X, ( > (Proposition 17) Rev (D,M') M")
4(1 + BRevv
Note that for all E > 0, such an E, exists, even if B, is not closed (as long as B, is non-empty). In particular, because M is c-expensive, we know that 711 > > 0 for all who pay 2 c. If B, is empty, instead omit Zy, T from both lists (i.e. decrease all future indices by one).

---

8-4
X 36 (1,0)
X 400 (1.0)
Figure An illustration of two layers our construction. The number of points each layer increases with f, but they are always evenly spaced between (1, 0) and (0, 1). The direction in which the points are placed alternates between clockwise and counterelockwise.
Rev(D, M")
(Climm 15)
8(1 + E) B)R
Rev(D)
(Claim 13)
8(1 ()Rev(D)
Rev(D)
9BR)v(D)
5 No Converse to Lemma 8: Separating MenuGap and AlignGap
In this section we prove our second main result: Lemma 8 does not admit a converse, even approxi- mately. We briefly remind the reader that all previous constructions witnessing Rev(D) Rev(D)/BRev()) (D) oo arose by establishing sequences X with AlignGap(X) Theorem establishes that constructions exist outside of this more restrictive framework. Missing proofs can be found in Appendix B.
so (in fact, even SupGap(X) oo).
Description of our construction. Our infinite sequence X consists of consecutive layers of points. For = 2 to oc, layer & has n. == (4)] + points. These points/vectors have e, norm equal to one, and are evenly spaced (in terms their angle) between (1, 0) and (0, 1). If is even, they go counterclockwise from (1,0) to (0, 1). If é odd, they clockwise from (0, 1) to (1,0):
Define nı (() + 1. Define 02 2(n -1
Point Te, is the jth point in the gth layer, and is sins())))sin((f(t) when is even, or (sin(j0)),cos(j)))) when L is odd.
The infinite sequence X is ((Ec)) )2
Figure/ demonstrates two layers of our construction. In the remainder of this section, we may refer the sequence of points žz.j by a single indexed sequence F, The latter is the same the former where points are ordered lexicographically with respect to the original indexing.
Upper Bounding AlignGap(X) via Lagrangian duality. We first upper bound AlignGap(X) and establish that it's finite. To this end, observe that for any sequence X, AlignGap(X (X) is the solution to the following (infinite, if X is infinite) mathematical program, where the variables are sgap;, Cg (the sequence F. fixed, as we're aiming to compute A AlignGap(X)).
max E, max (0, sgap,)/||
AlignGap(X):
subject to:
Vi.j < i: sgap, S 7. (G0 - c5
Vi: 0 < a < 1/1
7

---

We next proceed with series of relaxations of this program. Some steps are specific to our choice of X from Section 5, while others hold for arbitrary X. Our first step is specific to this construction, and simply bounds || 1. Consider the following mathematical program:
max E, max sgap;)
AlignGap'(X)
subject to:
Vi.j < sgap, S 54 (c,33 - -czT5)
vi: c S v2.
Observation 20, For the sequence X defined Section 5, AlignGap'(XX) 2 AlignGap(X).
Proof. Every 3; construction has || 1| 2 | 1|2 1. Therefore, the new objective function only larger. Moreover, every & in the construction has || 2 1/v2 (because the lz norm 1), so this is relaxing the upper bound on C;.
We proceed to upper bound AlignGap' (X) via Lagrangian relaxation of the formulation above. Consider the following Lagrangian relaxation. We put Lagrangian multiplier 1 on every constraint of the form sgap; I F.. (c.,, c- 111 for all >> 1, and Lagrangian multiplier of 0 all other constraints involving sgap. We will not put Lagrangian multiplier on constraints binding c, to [0, /2], and keep those in the program. This yields the following Lagrangian relaxation (for simplicity notation below, define Co == 0, and define To = =0):
max E, max(p.sgap]] Z (c,7 c--1 sgap,,
LagRel,(X) (subject to:
vi: 0 S q < /
Observation 21. For all X, AlignGap'( (X) < LagRel,(X),
We now proceed to further simplify LagRtl, (X). The next step is defined below:
max E, -. (q.ī c-17.-1)
LagRela(X) subject to: Vi: c S v2
Observation 22, For all X, LagRel, (X) = LagRel,(X).
Finally, we can rewrite the objective function group all coefficients of c, For ease of notation below, define ēN+1 (if N is finite. N oc, there are no notational issues).
max Σ, GT (z: -i+1))
LagRel(X): (uubject to: : e S /2
Observation 23, For all X, AlignGap'(>) (X)= < LagRel (X) = LagRel, (X) = LagRel(X).
Now, we move analyze LagRel(X) for our particular sequence X.
Claim 24, For the sequence X defined in Section 5, LagRel(X) = /2. Σ, E. Z
Proof. For all i, Ft (Z; - F(+1) 2 O. as each H; has lz norm exactly one. Thus, the optimal solution for LagRel(X) X) sets each G; == 2. Recalling that J, Z, = for all i concludes the claim.
Proposition 25. For the sequence X defined in Section 5, LagRel(X) < 6.
Proof. Let us first observe that if F. is the last point in layer, then in fact ē Z. and therefore 1 Z. Z1+1 Therefore, these terms do not contribute to the sum. We can then rewrite the term to sum over all layers as follows:
LagRel(X) V2.
Σ
Σ
1 Fij Fei++1
1=
-2.
Σ
(ne 1). Cos
8

---

I 22 Σ (ne 1). 1//2
π²
V2. Σ 8(ni 1)
v2.
Σ 88 In (6)
n²²
6
Above, the first line follows by the reasoning in the first paragraph. The second line follows by observing that the angle between any two points in layer is exactly 02 (and the two points question of f2 norm equal to one). The third line follows as cos(O2) 2 0g /2 for any 0₂ E [0, ' r/2) (and all 0g are indeed in 00, π /2). The fourth line follows by substituting the definition of 0g as a function of ng. The fifth line follows by definition of The final line is just calculation for this particular infinite series (this follows as Ei=2 (E) S 3).
Observation 20, Observation 23, and Proposition 25 yield the main result of this section: Proposition 26. For the sequence X defined in Section 5, AlignGap(XX S 6.
Step Picking a Q to Lower Bound MenuGap(X). Finally, we propose sequence Q and show that MenuGap(X, Q) oc. We describe the sequence again in layers, to match our description of X (that is, the vector Tr.j corresponds to the vector æzy)). In particular, for each even layer É, the vectors Te, will have fixed u-coordinate, and the y-coordinate will increase with j. For each odd
layer, will introduce new vectors (i.e. will just let gap, X,Q 0 for all i in odd layer). Specifically, the construction as follows:
Define a = Ei=e (I) (and note that a < o0).
Define žι = 1 Σラ= jln"())
Define 6; = ze - atl="(F)*
For j < n2 define Zt.j 1 8, cot((j + 1)8z). For ne 1. define 24,j := 1.
For all even f, and all j. set बे, == (ze, 2t.)).
For all odd E, and all j. set T..j arg maxe ca [Tt. g
Proposition 27. MenuGap(X,QQ
cc.
In our proof (Appendix B) we first analyze which point sets the gap for Tt.,, and observe that must either be Øe,-- or 9-2.012-11 (that is, it must be the previous point in the same layer, or the final point in the previous even layer). We can then bound the gap of each layer exactly, and then take a sum over layers: for any even layers we have that the sum of gaps is at least Ejo gap;j
X.Q 2 8, In(ne)/2, where gapr.j X.Q = gap; X.Q where Z == Fe.s (7, is the jth point on
layer f). Recall that de one (e we conclude that:
XQQ gapi.
Σ oz 1n-en(2))/2- = Σ 2atln(1)
E even 1=0
even
This completes the proof of Theorem 9: Proposition 26 establishes that AlignGap(X) S 6, while Proposition 27 establishes that MenuGap(X) 20.
1o see that ze,j 2 0 observe that cot(z)) 5 1/2 for all ar E [0, x/2]. Therefore get 8 cot((j + 1)0g)) < 2(m=1)) < 2 5eme 2[[log g
"+110 < 6e +0+1) #
for all E (a 1.9). To see that ze,, < simply note that
loga
the term subtract can't 't be negative.

---

6
Conclusion
We study the nature of distributions D with Rev(D)/BRev(2) framework to construct such distributions, and therefore established sufficient conditions [BCKW15, HN19]. Our first main result establishes that the most general of these frameworks is in fact complete (Theorem 6). Our second main result establishes that the more restrictive framework, through which all previous constructions arose, is not complete (Theorem 9). Finally, we build upon our main construction to develop novel distribution D witnessing (Dv(D) (D)/BRr)(D) oc, but for which none of the "aligned" mechanisms of prior work can possibly witness this (Corollary 11).
co. Prior work established a
In terms of future work, it remains open as to whether there is an alternative definition for "sequences with MenuGap(X) oo" which is easier to parse. Our work establishes that understanding such sequences is necessary and sufficient to understand distributions with (ev(D) (D))/Bevv(D) = oc, and establishes that "sequences with MemuGap(X) = oo" is not equivalent to "sequences with AlignGap(X) co." But it would be exciting for future work better understand sequences with MenuGap(X) (X)= = 00.
Interestingly, ongoing work by [AS22] uses the framework developed in this paper in order to prove approximation results for so-called fine-grained buy-many mechanisms, class of mechanisms which interpolates between buy-one and the recently introduced buy-many mechanisms [CTT19, CTT20J. In general, our techniques make possible for future work explore the gap between various simple versus optimal benchmarks without having to reason directly about the underlying mechanisms.
References
[AS22] Sepehr Assadi and Ariel Schvartzman. Fine- siee-graied buy-many mechanisms are not much better than bundling. Manuscript from author's 's website., 2022.
[BCKW15] Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. Pricing lotteries. Journal of Economic Theory, 156: 144-144, 2015.
[BGLT19] Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang. Correlation-robust analysis of single item auction. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193-208. SIAM, 2019.
[BGN17] Moshe Babaioff, Yannai A. Gonezarowski, and Noam Nisan. The menu-size complexity of revenue approximation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 869-877, 669-877,2017.
[BILW14] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg, A simple and approximately optimal mechanism for an additive buyer. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 21-30. IEEE, 2014.
[Carl7] Gabriel Carroll. Robustness and separation in multidimensional sereening. Economet- rica, 85(2):453-488, 2017.
[CD22] Yang Cai and Constantinos Daskalakis. Recommender systems meet mechanism design. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC '22, page 897-914, New York, NY, USA, 2022. Association for Computing Machinery.
[CDW16] Yang Cai, Nikhil R Devanur, and S Matthew Weinberg. A duality-based unified approach to bayesian mechanism design. ACM SIGecom Exchanges, 15(1):71-77, 2016.
[CHK07] Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference on Electronic Commerce, EC '07, pages 243-251, New York, NY, USA, 2007. ACM.
[CHMS10] Shuchi Chawla, Jason D Hartline, David L. Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 31 3-200. ACM, 2010.
10

---

[CMI6]
Shuchi Chawla and J Benjamin Miller. Mechanism design for subadditive agents via an ex ante relaxation. In Proceedings of the ACM Conference on Economics and Computation, pages 579-596. ACM, 2016.
[CMSI5] Shuchi Chawla, David Malec, and Balasubramanian Sivan. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior, 91:297-317, 2015.
[CTTI9] Shuchi Chawla, Yifeng Teng, and Christos Tzamos. Buy-many mechanisms are not much better than item pricing. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 237-238. ACM, 2019.
[CTT20] Shuchi Chawla, Yifeng Teng, and Christos Tzamos. Menu-size complexity and revenue continuity of buy-many mechanisms. CoRR, 0etp2003.10666 2020.
[CZ17] Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pages 170-183. ACM, 2017.
[GL18] Nick Gravin and Pinyan Lu. Separation in correlation-robur monopolist problem with budget. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pages 2069-2080. STAM, 2018
[HN13] Sergiu Hart and Noam Nisan. The menu-size complexity of auctions. In Michael J. Kearns, R. Preston McAfee, and Evva Tardos, editors, Proceedings of the fourleenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, pages 565-566 ACM, 2013.
[HN19] Sergiu Hart and Noam Nisan. Selling multiple correlated goods: Revenue maximization and menu-size complexity. Journal of Economic Theory, 183:991-1029, 2019.
[MSS + 19] Pravesh Kothari, Divyarthi Mohan, Sahil Singla, Ariel Schvartzman, and S. Matthew Weinberg. Approximation schemes for a unit-demand buyer with independent items via symmetries. In David Zuckerman, editor, 60th IEEE Annual Symposium Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 220-232. IEEE Computer Society, 2019.
[KW12] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium Theory of computing, pages 123-136. ACM, 2012.
[LY13] Xinye Li and Andrew Chi-Chih Yao. On revenue maximization for selling multiple independently distributed items. Proceedings of the National Academy of Sciences, 110(28): 1232-11237, 2013.
[Mye81] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981
[PSW19] Alexandros Psomas, Ariel Schvartzman, and Matthew Weinberg, Smoothed analysis of multi-item auctions with correlated values. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 417-418. ACM, 2019.
[RW15] Aviad Rubinstein and S Matthew Weinberg. Simple mechanisms for subadditive buyer and applications to revenue monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 377-394. ACM, 2015.
[ST04] Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirly-sixth annual ACM symposium on Theory of computing, pages 81-90. ACM, 2004.
[Yao15] Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 109. Society for Industrial and Applied Mathematics. 2015.

---

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 Section 6
(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 set of assumptions of all theoretical results? [Yes] See Prelimi- naries and subsequent technical sections.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs for all state- ments made can be found either the first 9 pages, or in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(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 the random seed after running experi- ments multiple times)? [N/A]
(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)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite 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 as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
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]
12


Reviews:
[{"review_id": "YpxO3zjKcqz", "reviewer": "Reviewer_92Mc", "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.\n\nIndeed, 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)$.\n\nSpecifically, [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)$.\n\nThis result raises 2 natural questions:\n\n1) Is MenuGap$(X,Q)$ the \"right\" quantity to get multiplicative gaps $Rev(\\mathcal D)/BRev(\\mathcal D)$?\n2) 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?\n\nThe 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.\n\nFor 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.", "questions": "I did not see any typo, the paper is in general clearly written. But here are a few remarks:\n\n- 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.\n\n- if space permits, I would have put the proof of Claims 18-19 in the main body of the paper.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths are (in my opinion) the following:\n\n- The paper is well-written and clear given the quite complicated definitions.\n- The results seem non-trivial and correct.\n- 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.\n\nI see no obvious weaknesses.", "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": "RHvyzhc9jF", "reviewer": "Reviewer_aofd", "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.\nThe 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.\nA reduction from previous work provides a recipe for constructing such \"infinitely-separated\" instances, by constructing instances with infinite MenuGap.\n\nThe authors' first main result is that infinite MenuGap is also a _necessary_ condition for an instance to be infinitely-separated.\nA subclass of such infinite-separated instances can be characterized by those also with an infinite SupGap, which is always less than MenuGap.\nPrevious constructions of infinite MenuGap always involved infinite SupGap, suggesting that infinite SupGap may also be necessary for an instance to be infinitely-separated.\nHowever, 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.", "questions": "I have zero clarification questions because the manuscript was crystal clear.\n\nIf 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", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+: This paper has exceptional writing: concise, yet precise and an easy to follow train of thought.\n\n+: The results are quite complete and provide a comprehensive understanding of when Rev/BRev = infty.\n\n+: 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.\n\n-: 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.", "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": "JU1NF4Gkg4W", "reviewer": "Reviewer_nmG2", "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.", "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", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n- 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. \nThe 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.\nIn 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. \n- 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).\n- 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. \n- 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.\n\n\nWeakness:\n- 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.\n\nDespite 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. \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": "0oN6wzP_v1h", "reviewer": "Reviewer_qmDH", "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.", "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.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\n+ 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.\n\nQuality\n\n+ 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.\n\nClarity\n\n+ 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.\n\nSignificance\n\nThis 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.", "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