Refined Mechanism Design for Approximately Structured Priors via Active Regression
Authors: Christos Boutsikas
Petros Drineas
Marios Mertzanidis
Alexandros Psomas
Paritosh Verma
Venue: NeurIPS 2023 poster (2023)
Keywords: mechanism design
revenue maximization
randomized linear algebra
active regression

Abstract: We consider the problem of a revenue-maximizing seller with a large number of items $m$ for sale to $n$ strategic bidders, whose valuations are drawn independently from high-dimensional, unknown prior distributions. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute, and, even when they can be found, are often rife with various counter-intuitive properties. In this paper, following a model introduced recently by Cai and Daskalakis [CD22], we consider the case that bidders' prior distributions can be well-approximated by a topic model. We design an active learning component, responsible for interacting with the bidders and outputting low-dimensional approximations of their types, and a mechanism design component, responsible for robustifying mechanisms for the low-dimensional model to work for the approximate types of the former component. On the active learning front, we cast our problem in the framework of Randomized Linear Algebra (RLA) for regression problems, allowing us to import several breakthrough results from that line of research, and adapt them to our setting. On the mechanism design front, we remove many restrictive assumptions of prior work on the type of access needed to the underlying distributions and the associated mechanisms. To the best of our knowledge, our work is the first to formulate connections between mechanism design, and RLA for active learning of regression problems, opening the door for further applications of randomized linear algebra primitives to mechanism design.

Refined Mechanism Design for Approximately Structured Priors via Active Regression
Christos Boutsikas Purdue University cboutsik@purdue... edu
Petros Drineas Purdue University
Marios Mertzanidis
Purdue University
pdrineasqpurdue edu
mmertzanOpurduu... edu
edu
Alexandros Psomas
Paritosh Verma
Purdue University apsomasScs purdue. edu
Purdue University
verma1360purrue edu
Abstract
We consider the problem of revenue-maximizing seller with large number of items m for sale to n strategic bidders, whose valuations are drawn independently from nigh-dimensional, unknown prior distributions. It is well-known that optimal and even approximately-optima mechanisms for this setting are notoriously diffi- cult to characterize or compute, and, even when they can found, are often rife with various counter-intuitive properties. In this paper, following model intro- duced recently by Cai and Daskalakis [CD22], we consider the case that bidders' prior distributions can be well-approximated by topic model. We design active learning component, responsible for interacting with the bidders and outputting low-dimensional approximations of their types, and mechanism design compo- nent, responsible for robustifying mechanisms for the low-dimensional model work for the approximate types of the former component. On the active learning front, we cast our problem in the framework of Randomized Linear Algebra (RLA) for regression problems, allowing us import several breakthrough results from that line research, and adapt them to our setting. On the mechanism design front, remove many restrictive assumptions of prior work the type of access needed to the underlying distributions and the associated mechanisms. To the best of our knowledge, our work the first to formulate connections between mechanism design, and RLA for active learning of regression problems, opening the door for further applications of randomized linear algebra primitives mechanism design.
Introduction
The design of revenue- -ottiul-optimal auctions is central problem in Economics and Computer Science. In this problem, a revenue-me revemue-maximizing maximizing seller has m heterogeneous items for sale to n strategic bidders. Each bidder has type Rd which contains enough information encode the bidder's willingness to pay for every subset of items. Bidders' types are private information, and thus, in order provide meaningful guarantees the seller's revenue, the standard approach in Economics is to make a Bayesian assumption: types are drawn from a joint distribution 2.
Assuming single item for sale and bidders' types that drawn independently from known distributions, Myerson's seminal work [Mye81] provides closed-form solution for the revenue- optimal mechanism. Beyond this single-item case, however, multi-item mechanism design re- mains an active research agenda, even forty years later. Optimal mechanisms are no longer tractable, in any sense of the word, well as exhibit various counter- -unteerinttuiivv properties [MV07, DDT13, DDT15, BCKW15, HR15, HN19, PSCW22]; see [Das15] for survey. On the other
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

hand, significant research effort has culminated in numerous compelling positive results, such as simple and approximately optimal auctions [CHK07, CHMS10, CMS15, Yao15, RWI5, CM16, CDW16, CZ177 KW19, BILW20J, as well as efficient algorithms for computing near-optimal auc- tions [AFH+12, 12, CDW12a, 2a, CDW12b, CDW13a 13a, 11b), even with just sampling access to the type distribution [CR14, HMR15, DHP16, MR16, CD17, GHZ19, BCD20, GW21J.
Despite all this progress, however, there are key challenges in applying these results in practice. First, the computational complexity, sample complexity, approximation guarantees, and communication complexity (i.e., the amount of information the bidder should communicate to the seller) of these results often depend on the number of items m, which could be prohibitively large (e.g., think of m as the number of items on Amazon. com). Second, bidders' type distributions are typically high-dimensions or otherwise complex objects, that are not known nor can they be sampled. Instead, the designer might have an estimated distribution DD e.g., through market research, that is close to the real distribution D. Motivated by these issues, Cai and Daskalakis [CD22] introduce a model where the true type distribution Dj of bidder i is close to a structured distribution D.. Specifically, they assume that there is an underlying design matrix A E R=*k of k "archetypes," with io < m. Intuitively, bidder i can be approximated by a linear combination of k archetypal bidders. This same assumption has been central in the study of recommender systems. In this model, [CD22] give framework for transforming a mechanism M for the low-dimensional distribution D. into mechanism for the true type distribution with good revenue guarantees, and whose computational and communication complexity does not depend on the number of items m.
The impact of their work notwithstanddnn, the above results require strong structural assumptions on: the design matrix A; the bidders' valuation functions; and very specific access to (or exact knowledge of) the structured distribution D_ and the mechanism M. Our work connects the recommender system approaches for mechanism design with recent progress on Randomized Linear Algebra for active learning for regression problems. We relax, and even remove these restrictive assumptions, and open the door to future exploration of more elaborate recommender system models in the context of mechanism design, using randomized linear algebra primitives.
The framework and results [CD22]. To place our results in context, we start with a brief overview of [CD22]. which considers a setting where the type distribution D; of bidder i is close to a distribution D. in the Prokhorov distance, under the loo norm (Definition 1). Here, D. first samples a vector z E [o, 11th from a low- -iwddimeniooall distribution Dz... and then outputs Az, where A E Rm=* is a known matrix. The proposed framework has a learning and a mechanism design component.
Their learning component consists of a communication--fficcenn query protocol Q for interacting with each bidder such that, if the type t. of bidder i satisfies ||t:- Az e, the query protocol outputs a vector Q(t,) such that [[Q(t,) - z|130 S Soo." [CD22] give such query protocols under strong (distinct) conditions on A, and specifically when A: (i) satisties an assumption similar the separability condition of [DS03], (ii) is generated from a distribution where each archetype is an independent copy of an m-dimensional Gaussian, or (iii is generated from a distribution where each archetype is an independent copy of an m-dimensionall, bounded distribution with weak dependence. We discuss these restrictions in more detail in Appendix 1.4.1. The query complexity, as well as the error Coo, depend on them, but, importantly, are independent of the number of items m.
Their mechanism design component is a refinement of robustification result of [BCD20). For this transformation to work, one needs to interact with the mechanism and the underlying distributions us- ing highly non-trivial operations, which are computationally demanding, and require exact knowledge of bidders' valuation functions. In our work we overcome this issues by developing new reductions and plugging them in the framework established by [BCD20] and [CD22]. The overall interplay between the different mechanism design and active regression components can be seen in Fig. 1.
Combining the two components, [CD22] obtain mechanisms for D, for constrained-addiite bidders. In these mechanisms, each bidder is required to answer a small number of simple Yes/No queries
By efficient we mean a query protocol that asks each bidder a small amount of queries. Se also Definition 3. 2 Recall that for any (integer) < p- < oo and vector x E Rd, ||x| Ed |x,PP; ; for p oc.
|x|| so = m.. |x:]. See [CD22] for an exact expression for Çoc.
A function is constrained-adddee if S), Teings Ejer ty. where I is a downward-closed set system.
2

---

of the form "are you willing to pay for item j?" such that the loss in revenue and the violation in incentive compatibility do not depend on the number of items m.
1.1 Our contributions
Randomized Linear Algebra (RLA) for active learning, RLA for active learning has focused on solving regression problems of the form
z = arg min ||t Ax|lp-
for lp norms with 1 p < oc, by querying only subset of elements of the vector t. In prior work on RLA for active learning, the focus has been on recovering an approximate solution that achieves a relative error constant factor approximation to the optimum loss. We adapt these bounds to our setting, which could include noisy instead of exact queries, and prove bounds for the lp norm error of the exact minus the approximate solution. Specifically, we bound [|Q(t.) - zllp S Sp. We provide bounds on Sp for all integers 1 I p < oc. Our bounds depend on the modelling error ||t Ax Ip and some measure of the query noise (see Definitions 4 and 5); both dependencies are expected. Importantly, our bounds hold for arbitrary archetype matrices, very much unlike the work of [CD22], which focused on very restricted classes of matrices. single property of the archetype matrix, the smallest singular value with respect to the lp induced matrix norm, Omin.p (A), can characterize the quality of the error. As minn, (A) decreases, the error S, grows. Intuitively, miin, (A) is a measure of independence of the archetypes, with small values corresponding to linearly dependent archetypes. The query complexity needed to achieve error 4o is almost linear (up to logarithmic factors) on for p = 1 and p- = 2. and grows with h///2 for p 2 3. Our query complexity bounds have no dependency on m (number of items) d (dimensionality of type) enabling to produce results way beyond constrained- valuation functions.
valuations, as d = 2n dimensions suffice to encode arbitrary
critical to highlight that our ability to provide bounds on the approximation error for arbitrary archetype matrices is, at least partly, due to leveraging information from the archetype matrix A. Specifically, we use this information to select which bidder types to query, instead of just querying types uniformly at random. This information involves the computation or approximation of the well-studied leverage scores of A for p = 2 and of the so-called Lewis weights for all other values of P (see Section 3.1). We do note that in our framework, the errors due to the modeling of the bidder type t as the product Az and the query noise are always bounded by the respective lp norm. Thus, our models are more restrictive compared to the &oo norm models of [CD22]. However, to the best of our knowledge, even assuming such restrictive models, the results and tools of prior work do not extend to arbitrary archetype matrices. This precisely the gap that is bridged by our work, using RLA for active learning of Ep norm regression for 1 S p < xo.
Mechanism Design. On the mechanism design front, our main contribution is relaxing the assump- tions of [CD22. BCD20J on the type of access needed to the low-dimensional distribution and the mechanism for it. Specifically, we further refine the robustification result of Brustle et al. [BCD20] and remove the need for the aforementioned strong oracle.
The main difficulty of transforming mechanisms for one distribution into mechanisms for another distribution is that the two distributions might not share the same support. The crux of the issue is that the incentive constraints are very delicate; a small change in the underlying distribution may drastically change the agents' valuation distribution over the mechanisms" outcomes. One way to tame the distribution of outcomes is to map bids that are not in the support of the initial distribution, to bids that are. Brustle et al. [BCD220] do this by "'ottmmalyy misreporting" on behalf of the bidder, (u, Mit,, b-:))]. where De,s is a rounded-down by calculating argmax, s/sppttt Eb
version of Dr.t- As we' ve discussed, for this operation to be viable, many things need to be assumed about what the designer knows and can compute about M, Dr.., and the bidder's valuation function. Our approach, instead, leverages the fact that when two distributions are close in Prokhorov distance, under any Ep norm, any point on the support of one distribution is close to a point on the support of the other, with high probability. Our construction simply maps a report w; to the "valid" report (approximately) closest to w; in fp distance. This operation is linear on the support size. Furthermore, our overall robustification result holds for all norms, not just lo and our construction completely agnostic to bidders' valuation functions.
3

---

Combining the components. Combining the two components we can, without any assumptions on A, given mechanism for the low-dimensional prior, design mechanisms with comparable revenue guarantees, where each bidder is required to answer a small number of queries. Our queries ask a bidder her value for subset of items, and our mechanism can accommodate any valuation function, significantly extending the scope of our results.
Related Work. Aside from the work of [CD22), on the mechanism design front, the most relevant works are [CD17], that consider learning multi-item auctions given "approximate" distributions, and [BCD20], that consider learning multi-item auctions when type distributions are correlated, yet admit special structure. On the RLA front, we leverage and adapt multiple recent results on approximating Ep regression problems in an active learning setting. We discuss prior work on RLA for active learning and its connections our setting in Section 3.1 and Appendix D.
Preliminaries
n denote the first natural numbers. A rexenue-maximizing seller has set [m]] of m heterogeneous items for sale to n strategic bidders indexed by [ni]. Bidder i has a private type vector t; E Rdd and the types of all bidders are represented by a valuation profile t= ( tn). Bidder i has a valuation function 0, : IRd 2/ml + R,, that takes as input the bidder's type and (possibly randomized") set of items S S [m] and outputs the bidder's value for S. Note that d < 2nh since expressing a valuation function requires at most one real number per subset of items. Types are drawn independently. Let D xee(m) D, be the distribution over bidders' types, D_, /ejnn//s)) Dj be the distribution of all bidders excluding i, and supp(D) be the support of distribution D.
Let [n]
Mechanisms. A mechanism M = (x.p) is tuple where R4 + 2|mml is the allocation rule, and p RRd - RT is the payment rule, which map reported types to allocations of the items and payments, respectively. Specifically, (b) == (I(b)) denotes the probability that bidder i receives item j for input valuation profile b. and (bb = (p(b)); denotes the amount bidder i has to pay. Let u; (b)) be the utility of bidder i with type t, for participating in mechanism M, under reports b. Bidders are risk-free and quasi-linear i.e., u, ut,t.. where the expectation is taken over the randomness of the allocation rule. Since we only consider truthful mechanisms, unless stated otherwise, reported types will be the same as the true types.
E [o, x(b)) p. (b)),
bidder's objective is to maximize her utility. The seller strives to design mechanisms that incentivize bidders to report truthfully. We use the following notions of truthfulness. A mechanism M is Bayesian Incentive Compatible (E-BIC), for each bidder E [n]] any type t, and misreport t² we have that: Et_;-D [M: (t,, Mt,,, t-:))] 2 E- (u,(t, (c, 8)CBIC if for each bidder i [n], and any misreport t! we have that:
t-:))] - e. A mechanism M is
P
E (INND=
(t, ()) 2
E bIND_ (t, M(t ()) - 1)1 2 6.
E
A (c, -)C mechanism is BBCIC mechanism; O-BIC mechanism is simply BIC. Finally, mechanism Ms is ex-post Individually Rational (IR) if for all valuation profiles and all bidders E n, u, t-:)) Z O. The seller's objective is maximize her expected revenue. For mechanism M and distribution D we denote the expected revenue Rev(M, D) = EELD Evetn pc(t)) Note that, we are calculating revenue assuming truthful reports, even for, e.g., (c, 8)-BIC mechanisms.
Statistical Distance. In this work we design mechanisms that work well, as long as they are evaluated on distributions that are "close" to D. Here, we define the notion of distance between two probability measures that we use throughout the paper.
Definition 1 (Prokhorov Distance). Let (U, d) be a metric space and B be a o-algebra on U. For A E B, let A = {x: By E A s.l. TT. < }} where π is some distance metric. Two probability measures P,
B have Prokhorov distance: inf(E 0 P(A) Q(A9) + E and ((A) S P(AF) + e, A E B). We choose n to be the En-distance, and we denote the Prokhorov distance between measures P. Q as (p(.QQ).
'Each subset might be selected according a probability distribution.

---

The following is an equivalent characterization of Prokhorov distance due to Strassen [Str65]. Lemma 1 ([Str65]). Let 'D and D'' be two distributions supported on IR". TT D') S e iff there exists coupling of D and D', such that P(x.))~>(lIx yllp > a] S.
Recommendation system-inspired model. We assume that, for each bidder, there exists a known design matrix A E Rdxk 5 where the columns of A represent k "archettpps", for a constant k. Our results hold if these matrices are different for each bidder, however, for ease of notation we will assume all bidders have the same design matrix. For each bidder there exists distribution Zz, supported on the latent space [0, 1l Let D. A De, be the distribution induced by multiplying sample from D2,, with the design matrix A, i... Dj is the distribution of Ay where y ~ Dz,--
The valuation function over the latent types is defined as (z,, S) (AZ,, S) for any bundle S S [m]. We will use the following notion of Lipschitz continuity for valuation functions.
Definition 2 (Lipschitz Valuation), A valuation function v(.; :) R x [0, 1 - RR is L-Lipschitz, for any two types t, t' E d and any bundle S S [m]]. (o(t, S) - v(t', S) S Lllt t'lloc.
We include table, Table 1, with all the notation used throughout the paper in the appendix.
3 Active Learning for Regression and Mechanism Design
In this section, we state our main results, deferring all technical proofs to the appendix. We present mechanisms that completely agnostic with respect to D, the distribution from which bidders' types are drawn from. However, we have limited access (described later in this section) to (i) a design matrix A; (it) distributions D2,, over R² where for all E [n]] (D;; A o D2..) S 6al for some Endi.p >> 0; and (iii) a mechanism M for D. xi(n) Dz.s. This limited access to the design matrix motivates the use of active learning, which deals precisely with settings where the algorithm is allowed to (interactively) query subset of the available data points for their respective labels (see [MD21, MMWY22] for precise definitions of the active learning setting in regression problems). Our approach is modular and starts by building an active learning component for regression problems (Section 3.1) followed by the mechanism design component (Section 3.2). We combine the two components to get overall mechanism for D in Section 3.3.
3.1 Active learning for regression via Randomized Linear Algebra
active learning query protocol for the seller that interacts with each bidder i, and infers their type t. E TRd by accessing only small subset of elements of the type vector (as d is very large). We use Q to denote the query protocol, whose latent space g A bidder interacts with the query protocol
Our objective to design a communication-effiiiaaa
output is a vector in the truthfully if it is in her best interest to evaluate functions requested by the protocol on her true private type t;. We use @(t.) E E to denote the output of Q when interacting with truthful bidder with type t.. We now define the notion of an (Emdl.ps Sps p) -query protocol and the notion of query noise. Definition 3 ((eal.pp Sp. queery protocol). is called an (Emat.pp Sp: pu-uurryyyyuuu protocol, if. for all E R and z E R satisfying ||t Azliz S Eadt,p. we have ||z- 2(t) Sp.
Definition& 4 (Query noise). Let t; be the true type of a bidder. Our query protocol can access entries oft, + Cng.v where Eng.p is an (unknown) vector. The query noise Eng.p satisfies ||<ng.pllp I Eng.p
The query noise depends on the specifics of the interactions between the seller and the bidder. For example, if the seller is only allowed ask queries of the form "'what is your value for the subset S?",, the query noise Sag.p is equal to zero. Our bounds will also depend on the model error.
Definition 5 (Model error). Given valuation profile E RRd, the model error is Eaat,p if. for all i E [n), there exists E &R such that ||t, Azilpp pp < Endl.p-
Note that, we don't 'tn have bounds of the form "|[t, Az, S E" for individual types, but for the distributions D. and A Dz,,- The characterization Prokhorov distance (Lemma 1) allows us to relate the two quantities in the proofs that follow.
Notice that we consider the more general case of having d number of rows (instead of m).
5

---

We now rephrase the above discussion in order to cast it in the framework of Randomized Linear Algebra (RLA) and active learning. Dropping the index i for notational simplicity, we assume that Az R t. and we seek to recover an approximate solution vector Q(t) such that the lp norm error between the approximate and the optimal solution is bounded. Importantly, the query protocol Q is not allowed full access to the vector t in order to construct the approximate solution vector. This is well-studied problem in the context of RLA: the learner is given a large collection of k-dimensional data points (the d > k rows of the design matrix A E 124x)), but can only query small subset of the real-vale valled labels associated with each data point (elements of the vector t E Rd).. Prior work in RLA and active learning has studied this problem in order to identify the optimal number of queries that allow efficient, typically relative error, approximations of the loss function. In our parlance, prior work has explored the existence of query protocols that construct vector Q(t) such that
||t AQ(t)) S 7plit Azllp:
where 7p > is an error parameter that controls the approximation accuracy. Of particular interest in the RLA literature are relative error approximations, with 7, = 1 + e, for some small > 0; see [MMWY21, MMWY22] for a detailed discussion. However, relative error approximations are less important in setting, since protocols in Section 3.2 necessitate Sp 2 Endi,p. For p = 2. the underlying problem is active learning for least-squares regression: [DMMSII] analyzed its complexity (namely, the number of queries) of query protocols in this setting, eventually providing matching upper and lower bounds. Similarly, for p = 1, the underlying problem is active learning for least absolute deviation regression, robust version of least-squares regression: [MD21] analyzed the complexity of query protocols in this setting. The query protocols of [DMMS11, 1, MD21] are straightforward: they sample a small set of labels (i.e., bidder types) and elicit the bidder's preferences for this set. Then, the respective lp norm regression problem is solved on the smaller set and the resulting solution is returned as an approximation to the original solution." 6 The types to be sampled (see Appendix D.1 for details) selected using distributions that can be constructed by accessing only the design matrix A. Specifically, for the p = 2 case, one needs to compute or approximate the leverage scores of the rows of the matrix A. For the p 1 case, one needs to compute or approximate the Lewis weights of the design matrix A. (The Lewis weights are an extension of the leverage scores to Ep norms for p A 2.) The work of [DW17, DWH18, DM21, DW18, CP19] for the p = 2 case involves more elaborate query protocols, using primitives such as volume sampling and the Saa---ppiima---iaaaaaaaea for active learning for regression problems was recently resolved in [MMWY22, MMWY21]; we discuss their approach in our context in Appendix D.2.
sparsifier improve the query complexity. Finally, the p > 2 case
To the best of our knowledge, our work is the first one to formulate connections between mechanism design and Randomized Linear Algebra for active learning. Two technical points of departure that are needed in order to adapt the RLA work for active learning to the mechanism design framework are: (i) we need to derive bounds of the form of eqn. (1) for the f, norm distance between the exact and approximate solutions, whereas prior work typically bounds the error of the loss function when an approximate solution is used; and (ii) the entries of the bidder's type vector might not be known exactly, but only up to a small error. The latter assumption corresponds to the use of noisy queries in the model of [CD22] and is known to be equivalent, up to logarithmic factors, to threshold queries via binary search. Our work addresses both technicalities and seamlessly combines the RLA work for active learning with mechanism design.
Prior to stating our main result, we need to define a fundamental property of the design matrix A E [Bd that will affect the approximation error. Let
minggp (A)
min XERF ||x 1==1
||Ax|pp
For p = 2, this is simply the smallest singular value of the matrix A. For other values of p. the above definition is the standard generalization of the smallest singular value of A for the induced matrix Ep norm. Notice that o min. (A) is property of the matrix A and can be computed a priori via, say, the QR factorization or the Singular Value Decomposition (SVD) for p = 2 and via linear programming for 1. As we will see in Theorem below, smaller values of minn, (A) result in increased sample complexity for our query protocols.
'To be precise, multiple smaller problems have to be solved and a "good enough" solution has to be chosen in order boost the success probability. See Appendix D for details.

---

Theorem 1. Let A E Baxk be the design matrix, and recall the definitions of the model error Edr.p (Definition 5) and the query noise (Definition 4). For all integers 1 S < oc. there exist query protocols Q using Sp queries for each bidder i E [m], such that, with probubility at least 1 - ô,
12-- 2 S SplEnat. + Eng.p) Cp
)min.((A)
holds for all n bidders i E [m]. Here cp is a small constant that depends on p.? The respective query complexities for p = and p = are (asymptotically) identical:
81 = 22 = O (I: In In mn/))..
For p 2 3, the query complexity is
1//2 Inn k- In 11%/))
Several comments are in order. (i) The error Sp is a small constant times the modelling error plus the error due to noisy queries. In the limit case where the modelling error is equal to zero and the queries are noiseless, the bidders' types can be recovered exactly in our framework. However, as the modelling error and the query noise increase, approximating user types becomes harder and less accurate. (ii) Importantly, the approximation accuracy of Theorem grows linearly with the inverse of the smallest l, norm singular value of the design matrix A. Our results indicate that the approximation accuracy of the query model Q depends on this simple property of the design matrix A. For example, focusing on the p = 2 case, our theorem shows that as the archetypes (columns of the matrix A) become more linearly dependent and the smallest singular value approaches zero, the error of our approximation worsens. This is quite reasonable: archetypes are linearly dependent, then it is increasingly difficult to approximate the respective entries of the vector z. (iii) The query complexities $ and $2 are asymptotically identical, growing linearly with & In k. where k is the number of archetypes. They both depend on the log of the number of bidders (due to a union bound) and on the log of 1/5, where 8 is the failure probability. The query complexity for p 2 3 is larger and is dominated by the 1.2aa term. Importantly, the query complexity remains independent of d, the number of bidder types, which, in worst case, could be exponential to the number of underlying items. (iv) Improving the sampling complexities 81 and 82 has been a topic of intense interest the RLA community and we defer the reader to [MMWY21 MMWY22], which has essentially provided matching upper and lower bounds for various values of p. We just note that for the well-studied p = case, volume sampling approaches [DW17, DWH18, DM21, DW18] achieve essentially matching bounds, while the work of [CP19] removes (at least in expectation) the In & factor from $2, at the expense of significant additional protocol complexity. From technical perspective, we note that Sp 2 Endl,p. as necessitated in Theorem 2 and that our query protocols are all one-round protocols.
Finally, notice that our theorem works for all p 2 1, but not for p xo, which was the setting of [CD22]. In Appendix D.4, we present a (modest) improvement of the result of [CD22] and explain why it seems improbable that the p design matrices. This a strong motivating factor to explore properties of mechanism design for the recommender system setting for other lp norms, we do in this work.
case can be generalized to much broader class of
3.2 The Mechanism Design component
The goal of the mechanism design component is to transform a mechanism M for D into a mechanism M for Dr. We first define exactly the type of access to D, and M our construction requires.
Definition 6 (Access to M). By "query access to M" we mean access to an oracle which, given valuation profile t, outputs the allocation and payments of M on input t.
Definition 7 (Access to D.). By "oracle access to D" we mean access to (1) sampling algorithm St for each i E [n], where Si(x, 8) draws sample from the conditional distribution of Dz.i on the k-dimensional cube x x (21, + 55), and (2) an oracle which, given as input a type t, for bidder i, outputs the type in the support of Dz.a that is closest to t; in Ep distance, i.e, outputs argmin compp(D |1, t']lp-
We make no attempt to optimize constants and focus on simplicity of presentation. In our proofs, ei = 2.5; C2 7.5; and for p 2 3. cp 18 (200) / 3. Notice that the last constant converges to 21 p increases.
7

---

If the allocation is randomized, our approach works even if the query to the oracle returns a (correct) deterministic instantiation of the randomized allocation." 8
In Definition 7, the first part of our oracle access (sampling from the conditional) is also necessary in [CD22]. The second part is new to our work, and replaces a strong requirement in [CD22]. In more detail, given a type t;, Cai and Daskalakis [CD22] (as well as Brustle et al. [BCD20]) need to know if t, E pupp(Dz,s) and, if not, need access to x.suppt DD [u, b-)))
where Dz.; is a rounded-down version of D...- However, for arbitrary distributions and mechanisms, this task might be computationally inefficient, or simply infeasible. In our work, we need access to argmin a (eapp((D..) ||t, E'Ilp in the "no" case.
Given these definitions, our main theorem for this component is stated as follows.
Theorem 2. Let D = x be the bidders' type distribution and v2 : Rdd x 20m + R2 be a L-Lipschitz valuation function for each bidder E [n]. Also, let A E RRdx be a design matrix and D. x D22, where D., is distribution over B for each i E [m]]
Suppose that we are given (1) query access to a mechanism M that is IR and BIC w.r.t. Dr and valuations { hE(n) (2) oracle access to D., and (3) any (Emal.ps Sp: p--uery protocol Q with Sp 2 Emdi.y- Then, we can construct a mechanism M that is oblivious to D and v(:-)), such that for all D that satisfy Tpl Tp A o D2.)) S Endi,p for all i E [n], the following hold: (I) M only interacts with every bidder using Q once, (2) M is IR and (1 B)CBI w.r.t DD where μ 0( and and (3) the expected revenue of M is at least Rev(M, D.) O(mn).
= (
Note that MM is an indirect mechanism, so it is slightly imprecise to call it (1) MBCBIC Formally, interacting with Q truthfully is an approximate Bayes-Nash equilibrium.
In order to prove Theorem 2, we use a key lemma, Lemma 2, which establishes the robustness guarantees of Theorem 2. but in the space of latent types. Intuitively, let t; be the type of bidder
i, and z; be a random variable distributed according to De.s. We know that (P,,, A o D.) S Endl.p S Sp. Due to Lemma I, there exists a coupling such that with probability greater than 1 - Sp. It: Az: lp S Sp- Since the seller uses a (fmal.p: Sp. p)-query protocol, with probability at least Sp. (Q((t) l1ppp> I Sp- Note that, this implies that z; and ((t.) are distributed such that their Prokhorov distance is at most Sp- At this step, Lemma 2 provides us a mechanism M, constructed from M. that we can execute on types ((t,)..... ... Q(t,), ), obtained by interacting with the bidders via the query protocol. With probability least Sp. we have that ||t, Az; so I |t AAz S Eddl.p and thus, using the fact that the query protocol ensures [|Q(t.) - III,, I Gp as well, we have ||t, - (t,))) S Eall,p + k| A Go. The guarantees of M for the distribution over Q(t,))s are therefore translated into guarantees (with a small error) of the overall mechanism for the DD
The proof of Lemma 2 is quite involved and is the main focus of our analysis. Here, we sketch the key ideas behind the proof, and defer all formal arguments to Appendix C. The proof uses the following notion of a rounded distribution.
Definition (Rounded Distribution). Let F. be a distribution supported on R For any 8 > 0 and L E [0. 87", we define function p(t.6) IR + R. such that r ((.,5) (x) = maz { [[=]]]] - e, 0} for all i E [K). Let x be a random vector sampled from F. We define [F as the distribution for the random variable 7l p(t,8) (x)). and we call [F,, the rounded distribution of F.
We follow an approach similar to Brustle al. [BCD20]. The main idea that arguing directly about mechanisms for distributions that are close in Prokhorov distance is difficult. On the flip side, arguing about mechanisms for distributions that are close in total variation distance much easier, since the total variation is a more stringent (and hence more tamable) notion of distance. The key observation is that, if two distributions are close in Prokhorov distance then, in expectation over the random parameter É, their rounded-down versions are close in total variation distance.
'That is. if, for example, M allocates item j to bidder i with probability 1/2 and with the remaining probability item j is not allocated, our construction does not need to know this distribution/fractiin allocation and works even if nature samples and returns an integral allocation for item j.
8

---

Our overall construction is via three reductions. First. in Lemma 3, given a mechanism for F: we design a mechanism for the rounded-down version. Second, Lemma 4, given a mechanism for the rounded-down F₂ we design mechanism for [FrJe,s which maintains its guarantees (T) is small. Third, in Lemma 5, given a mechanism for [FaJe.s s we design mechanism for F. Fig. presents a detailed overview of the overall design architecture, and how the RLA and different mechanism design components interact.
Latent typea
Interaction
(t,
Sampling Access to DD
Rounding Down (+)
Adtive Learning-bossed Query Protocal
type t
M BIC wr D
2 tt.
locatioon poyments
rounded bids
type l
insokes
allocation
Mechanism
Mechanism
M
M
wae [Paies [Lanna 5)
psyments
[Dies
findl alccation payments
(Jamiaa))
type
Mechanism Mr Apx. BIC (Lemma
Mochanism M: Apx. BIC wrt D. (Lemma 2)
Mechanism M: (1), PJC wrt (Theorem 2)
Overall Design of the Active Learning-based Mechanism Design Framework
Figure Agents interact with the query protocol Q, which Iearns their latent types Q(t,)s. The mechanism design component (which is oblivious to the distributions of the true agents' types D) then uses these to produce the final allocation and payments, utilizing only query access to M and sampling access to D- such that the overall framework is approximately (n, 11)-BIC wrt D.
Our proofs for Lemmas 3 and are adaptations of the corresponding lemmas of [BCD20), where main task is to flesh out the exact dependence the dimensionality of the latent space and the fy-norm (versus the é -orm in [BCD20J). The novelty of our approach comes in the construction and analysis of Lemma
The difficulty of transforming mechanisms for [FaJe, into mechanisms for [FaJe, s is that the two distributions might not share the same sup- port. Thus, we need way to map bids that are not in the support of [FzJe,s to bids that are. Brustle et al. [BCD20] do this by "optimally misreporting" on behalf of the bidder, by calculat- ing argmar (A..),,)) E, (>((FF) +Jr. [u, M(z, b-:))], and then picking matching pay-
ments that make the overall mechanism IR. Our approach leverages the fact that Fr, and Fz,; are close in Prokhorov distance, and thus any point on the support of one distribution is close point on the support of the other, with high probability. An ideal construction would map report to the "valid" report (i.e., a report the support of {Fe.ile,)) that minimizes the l, distance to w;. This operation is linear on the support of [F and does not need any information on the valuation functions, nor on the actual probabilities that elements of the distribution are sampled with. Unfortunately, our assumption (finding the closest point w.r.t. tp) on [Fssle,ss but only Fz.ti prove that, by occurring small loss. our assumption suffices.
what "oracle access" means does not allow to do this operation

---

3.3 Putting everything together
Combining Theorems 1 and 2, we can give mechanisms for concrete settings. Formally, we have the following theorem.
Theorem 3. Under the same setting as in Theorem 2, for bidders with arbitrary valuation functions, we can construct mechanism M using only query access to the mechanism M (Definition 6) and oracle access to distribution D (Definition 7), and oblivious to the true type distribution 'D. We consider queries (to each bidder i) of the form "What your value for the subset of items S?"
Mechanism M is IR and (ms p.) -BC w.r.t. D, where μr - O(vSp) and lj - [l and the expected revenue of M is at least Rev(M,, Dz) - (nn). Additionally, with probability at least 1 8,
Sp cp (Fmin.p (A)) Emdi.p
for small constant Cp that depends on the parameter (see footnote 7). The number of queries is O (k- In k In(*/6)) and O (k* In k In(n/6)) for 1, and 3. respectively.
The proof of Theorem follows from Theorem 2 and Theorem 1, and is deferred to Appendix B.
As we've already discussed, the main mechanism of Cai and Daskalakis [CD22] requires bidders to have iettrained-addiitio valuations', as well A satisfy a number of restrictions. Here, we completely remove both conditions. On the flip-side, [CD22] ask bidders weaker queries, of the form "are you willing to pay price r for item j?" Using such queries, one can binary search over т, and drive down the query noise (see Definition 4). For Lx. the extra cost of such operation would be In (Il [[>)), where e is the desired accuracy. However, for other p-norms, for the same target accuracy, this operation requires an extra factor (llo(dd/P)) queries, giving dependence on d.
Conclusions and Future Work
In this paper, we study mechanism design for prior distributions close topic model, inspired from the recommender systems literature. We formulate connections between mechanism design and Randomized Linear Algebra for active learning for regression problems, importing ofte-off-the-rr results from Randomized Linear Algebra to mechanism design, and alleviate or relax restrictive assumptions of prior work. Developing deeper understanding of such connections is important direction for future research. For example, one could study this and other topic models in the context of mechanism design for correlated bidders, two-sided markets, information structure design, etc. Additionally, another interesting open problem would be to develop framework for proving lower bounds for mechanism design (e.g., lower bounds on the query complexity for single-round or multi-round protocols used to communicate with the bidders) using known limitations of algorithms in active learning, and vice-versa.
Acknowledgements
Christos Boutsikas, Petros Drineas and Marios Mertzanidis are supported in part by DOE award SC0022085, and NSF awards CCF-1814041, CCF-2209509, and DMSS-1126677. Alexandros Psomas and Paritosh Verma are supported in part by an NSF CAREER award CCF-2144208, a Google Research Scholar Award, and a Google AI for Social Good award.
"A valuation function constrained-addiive vtt, mazreinas Ejer tys where is a downward- closed set system.
10


Reviews:
[{"review_id": "KAvjewdca8", "reviewer": "Reviewer_NuQU", "summary": "This paper studies mechanism design for auctions.  A model of the bidders preferences with a low dimensional latent state is proposed. By interacting with the bidders, the latent state can be estimated with active learning. From here a mechanism design is derived.\n\nDisclaimer: I am not an expert in mechanism design, however I have a background in mathematics, computer science and ML. Unfortunately, I found this paper extremely hard to understand despite significant effort.\n", "questions": "General questions:\n* On a high level, what is the goal and what is optimized? i.e. what are the actions of the seller and the bidders, and what's the interaction/information exchange protocol?\n* What is the significance of having n bidders? It seems to me that there is no structure shared between the bidders, so the procedure is applied to each bidder i independently.\n\nline 25: what is \"willingness to pay\"? is this simply the maximal price the bidder is willing to pay for a subset of items?\n\nline 48/64: Here A \\in R^(m times k) but later we have that A \\in R^(d times k). This is very confusing. What is the interpretation of the vector Az_i? Are those prices the bidder i is willing to pay?\n\nline 66: \"communication-efficient query protocol Q for interacting with each bidder\". Most terms here have not been introduced nor can be reasonably inferred from the context.\n\nline 75-79: This paragraph is impossible to understand just from this paper. E.g. u_i, v_i have not been introduced. It is not explained what a transformation of a mechanism is (nor is it clear what the mechanism itself is).\n\nline 101: What is d? Before there was only m, n and k?\n\nline 150: What's a randomized subset? What and how is randomized?\n\nline 154: Some more intuitive explanation of \"mechanism\" is needed. What are \"reported types\" what are \"allocations of the items and payments?\" What's a valuation profile?\n\nline 162-171: What's the relevance of truthful mechanism, and how do we ensure to get a truthful mechanism? Can you explain the equation 166 more intuitively?\n\nline 189: What's a bundle? Previous we had \"randomized subsets\"? At least make the terminology consistent.\n\nline 223: What was the reason to introduce the index i in the first place?\n\nline 271: What's the protocol \"Q\"? It seems like the more interesting contributions are left out of the main part of the paper. I would suggest to add some examples to illustrate active learning protocol.\n\nline 332: What's an indirect mechanism?\n\n\nMinors:\n\nline 24: add range, i.g. \"i \\in [n]\"\ndisplay above line 87: What's the range of x?\n", "limitations": "see above", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "* The paper brings together results from active learning and mechanism designs.\n* The paper refines and strengthens results from prior work.\n\n", "weaknesses": "I found this paper really challenging to read. The introduction is long, too formal to provide a mtahematical introduction but not formal enough to make sense to give a complete formal picture. After the introduction the setting is formally introduced, creating redundancy and leaving the reader with 6 pages of setup that is extremely hard to understand without additional background knowledge. I am also missing concrete and simple examples to illustrate the setting, or possible a picture/diagram of the seller/bidder interaction.\n\nI cannot evaluate the significance of this work; in my view the work is also not directly related to machine learning (except for invoking some fairly standard results on active learning). Perhaps this paper is better off at a different venue.\n\nTo make this paper more accessible, I suggest have a less formal, but more complete introduction (in terms of the background); then the formal setting (possibly simplified), explaining the key ideas of the procedure (not just the results). See my questions below.\n\nI did not comprehend section 3.2 despite a reasonable effort. Despite myself lacking the relevant background, I think the accessibility of this paper needs to be improved before acceptance. The relevance to the ML community is also not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions. We recognize that it is a difficult paper to comprehend without a background in mechanism design. We respectfully disagree with the reviewer regarding whether this work belongs to NeurIPS: numerous mechanism design papers appear in NeurIPS every year, over the past several years, and one of the topics in the CFP is algorithmic game theory. We also disagree that our work employs fairly standard results in active learning: we do use prior work on active learning for $\\ell_p$ regression problems via randomized linear algebra, but the combination with mechanism design is (in our opinion) quite non-trivial. \n\nBelow we answer your specific questions.\n\n- ``On a high level, ... exchange protocol?''\n\nThe overall problem is, given (query access to) a mechanism for a low-dimensional/structured prior distribution, design a mechanism for the real prior distribution, in a way that is agnostic to the real distribution (but given query/oracle access as described in Theorem 3). The seller's actions are the set of all solutions to this problem; however, the \"right\" way to think about this is that we take the view of the seller. The bidders simply interact with whatever protocol we provide in a way that their (expected) utility is (approximately) maximized. In terms of the information structure (who knows what), there is an asymmetry: we assume that the bidders know the true prior, while the seller/we do not.\n\n\n- ``What is the significance ... independently.''\n\nMechanism design for n bidders is very different and much harder than mechanism design for a single bidder, even if the bidders' valuations are mutually independent. See \"Multi-Item Auctions Defying Intuition?\" by Daskalakis for a collection of interesting observations and results on the very similar phenomenon of selling independent items to a single additive bidder (where, e.g., selling each item optimally is a terrible meechanism)\n\n- \"line 25: ...''\n\nYes.\n\n\n- \"line 48/64: ... \"\n\nRegarding the difference between line 48 and the main part of the paper, $A \\in R^{m \\cdot k}$ is the assumption in the Cai-Daskalakis paper. In our work, we can allow matrices where the number of rows is much larger than the number of items. We will further clarify this.\n\nFor additive valuations, indeed a type $t_i$ can be thought of as a vector whose $j$-th entry, $t_{i,j}$, is exactly the willingness to pay/valuation of agent $i$ for item $j$. However, a vector/type $t_i$ can have different meanings for different valuation functions. So, we do not make any assumptions about types and only ask that the type of a bidder encodes, in some way, their valuation for the different subsets of items.\n\n- \"line 66: ...\" and \"line 75-79: ...\"\n\nWe will clarify and elaborate more on those concerns. \n\n- \"line 101: ...\"\n\n$d$ is the dimension of a type. So, for an additive function, it would be natural to have something like $d=m$, and it's always the case that $d \\leq 2^m$ (as we explain in 150-151), but we keep $d$ as a different variable (as opposed to Cai and Daskalakis that have $d=m$) to highlight what affects and what doesn't affect our error bounds.\n\n- \"line 150: ...\"\n\nA distribution over subsets of items. The valuation function of a bidder is evaluated, typically, on the outcomes of the mechanism. So, if the mechanism allocates to an agent item $1$ with probability $0.5$ and items $2$ and $3$ otherwise, the valuation function takes as input this distribution over bundles and outputs a number (the value of the agent for this distribution over bundles). We will clarify this.\n\n- \"line 154: ...\"\n\nA mechanism consists of two functions. The allocation function takes as input types and outputs an allocation (a distribution over bundles). The payment function takes as input types and outputs a number for each agent, the amount they owe (or should be paid; payments can be negative). Agents optimize for their own utility, so the types reported to the mechanism might differ from the real types, hence the term \"reported types.\" A valuation profile is the vector of $t = (t_1, \\dots, t_n)$ with all the bidders' types. We will further clarify some of these points (e.g., switch \"type profile\" to \"valuations profile\" across the paper).\n\n- \"line 162-171: ...\"\n\nThe design of truthful mechanisms is, essentially, the whole point of the field of mechanism design. Here, the mechanism $\\hat{M}$ is truthful for the low-dimensional distribution; the goal/point of Thm 2 is to construct an approximately truthful mechanism for the real distribution.\nEquation 166 is saying that, by lying, the probability that an agent gains more than epsilon is smaller than delta.\n\n- \"line 223: ... \"\n\nFor the active learning component, indeed the index $i$ is redundant. However, we thought it would be somehow more confusing to simply drop the index just for 3.1, since $t_i$ is the vector that this component is called on in the overall construction/protocol.\n\n- \"line 271: ...\"\n\nWe describe the details of our protocol in Appendix D. Given the page limit, it was indeed the case that we had to move all main technical contributions to the supplementary material. We will attempt to add such examples, as the reviewer suggests.\n\n- \"line 332: ...\"\n\nWe will further clarify this. The point here is that we defined mechanisms to be \"direct,\" aka take as input types. However, here (Thm 2) the bidders don't directly interact with a mechanism but with the query protocol (that calls a mechanism). Hence the combined process is a game (where truthfulness is a Bayes-Nash equilibrium), not a direct mechanism."}, {"review_id": "DkYWSyp67j", "reviewer": "Reviewer_pEGj", "summary": "Based on a model by Cai and Daskalakis [CD22], the authors propose a modular approach to design Bayesian Incentive Compatible mechanisms. In step 1, the algorithm learns the agent's type vector which is a very high dimensional vector. In step 2, given a mechanism based on the low-dimensional type learned in step 1, the author propose a way to robustify the mechanism. ", "questions": "1. What would be the potential challenges if we want to extend the result to other two-sided market models? \n1. A key assumption is that the type distribution admits some form of low-dimensional representation. How could one verify this assumption in realistic settings such as ad auctions for e-commerce?", "limitations": "The paper is theoretical and brings out the connection between randomized linear algebra and mechanism design. As a non-expert, I did not have the time to check the proof, but in my opinion, the paper adds valuable insights to the field of mechanism design.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The interaction between linearized linear algebra and mechanism design is explored, which is very exciting.\n", "weaknesses": "see limitations. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions. We also thank the reviewer for appreciating the connection between RLA and mechanism, which we believe is an exciting direction for future research. \n\nBelow we answer your questions.\n\n- ``What would be the potential challenges if we want to extend the result to other two-sided market models?''\n\nThis is a very interesting question for future work. Unfortunately, we lack the expertise in two-sided markets to offer more than an educated guess about concrete technical challenges. Our educated guess is that the main obstacle would be proving a robustification result for two-sided markets. Some very recent papers (e.g. ``On the Optimal Fixed-Price Mechanism in Bilateral Trade'' by Cai and Wu) consider limited information in two-sided markets, but for the machinery in our paper (and the Cai-Daskalakis paper) to extend, much stronger results seem crucial.\n\n- ``A key assumption is that the type distribution admits some form of low-dimensional representation. How could one verify this assumption in realistic settings such as ad auctions for e-commerce?''\n\nWe are not aware of any empirical evaluations of this assumption for auctions and e-commerce, and we feel that this would be an interesting topic for future empirical work in this context. Our work was initially motivated by the model of Cai and Daskalakis (whose work also did not consider whether this assumption holds in practice). However, the core idea of using a \"low-rank plus noise\" model stems from well-established fields like recommender systems and latent semantic indexing. In both of these areas, for over 25 years, user preferences (in the case of recommender systems) or documents (in the case of latent semantic indexing) have been modeled as a linear combination of a small underlying set of prototypes (vectors) plus noise. In the context of latent semantic indexing and recommender systems, such models have served as starting points for many theoretical and experimental approaches, before being replaced and expanded by more complicated and non-linear models. The mechanism design community is still at the stage of understanding the behavior of linear models and our work contributes significantly by employing active learning and randomized linear algebra to fully generalize prior work.\n"}, {"review_id": "tWUACAuxur", "reviewer": "Reviewer_Nu2U", "summary": "In this paper, the authors extend the model proposed by [CD22] to a more general setting and incorporate the techniques from Randomized Linear Algebra (RLA) for active learning literature with revenue-maximizing multi-item mechanism design. Compared with [CD22], this paper extends the infinity norm to any l_p norm when measuring the approximation of query protocol so that the RLA for active learning techniques can be applied to improve the accuracy of the query protocol. In terms of the mechanism design front, the authors relax many restrictive assumptions in [CD22]. This paper seems the first paper utilizing RLA for active learning of regression problems to mechanism design.", "questions": "The authors mention they can also improve the results in [CD22] for the infinity norm setting. Can you provide more discussions in the main context? What is the improvement? How significant compared with [CD22]. \n\nHow important is the $l_p$ norm metric  in your proof, is all the RLA literature focusing on $l_p$ norm? Is there a way to utilize the techniques there for $l_\\infty$ norm. IIUC, the reason you can relax the assumptions (e.g. the relaxed oracle access to the distribution) from [CD22] in the mechanism design front highly depends on $l_p$ norm? Can you provide more discussions regarding this?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper lies in the intersection between game theory and learning algorithms and it should be of interest to many researchers in this field.\n\nThe paper is well-structured and the authors convey the main contributions of the paper in a very clear way, which is easy to understand as a researcher in the EconCS field.\n\nThe paper is technically solid and the theoretical results are non-trivial. Even though this paper is regarded as an “incremental” paper built upon [CD22], the technical contribution of this paper is still significant.\nOverall I like this paper and recommend the acceptance of this work.\n", "weaknesses": "The novelty of this paper is limited, given it follows the exact same setting in [CD22], but I am not too bothered by this.\n\nIt will be better to state Lemma 2 more explicitly, as it is one of the main technical novelties of this paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions.\n\n- ``The authors mention they can also improve the results in [CD22] for the infinity norm setting. Can you provide more discussions in the main context? What is the improvement? How significant compared with [CD22].''\n\n\nFor the $\\ell_\\infty$ norm we provide small improvements to the results of Cai and Daskalakis when bounding $\\lVert \\tilde{z} - z \\rVert_{\\infty}$. We avoid a quadratic dependence on $\\sigma_{min}$ (of a certain matrix) and an extra factor of $\\sqrt{k}$. These improvements are discussed in detail in our Appendix, Section D.4. They stem from a better characterization of the $\\ell_2$ regression solution that is used as a proxy for the $\\ell_\\infty$ regression solution and results in better dependencies on the condition number of the archetype matrix and other quantities.\n\n- ``How important is the norm metric in your proof, is all the RLA literature focusing on $\\ell_p$ norm? Is there a way to utilize the techniques there for $\\ell_\\infty$  norm. IIUC, the reason you can relax the assumptions (e.g. the relaxed oracle access to the distribution) from [CD22] in the mechanism design front highly depends on $\\ell_p$  norm? Can you provide more discussions regarding this?''\n\nThe $\\ell_\\infty$ norm is an $\\ell_p$ norm as well with $p\\rightarrow\\infty$. There are standard lower-bounds that prove that $\\ell_\\infty$ regression is impossible, in full generality, in an active learning setting: simply put, one needs to essentially observe all measurements in order to solve $\\ell_\\infty$ regression, because modifying even a single entry could significantly change the output of the regression problem. This is the fundamental reason underlying the strong assumptions in Cai and Daskalakis: without assuming tremendous structure in the archetype matrix, there is no hope of solving $\\ell_\\infty$ regression in an active learning setting. And indeed, this is the point of departure for our work: we present mechanisms that work with other, more robust, norms (in the context of active learning at least). Eventually, we present a fully general result for all $\\ell_p$ norms, which also shows that as $p\\rightarrow \\infty$, the active learning setting gets weaker, since the sampling complexity increases. This is precisely the issue with the choice of the $\\ell_\\infty$ norm in prior work."}, {"review_id": "hTjH5QK3jd", "reviewer": "Reviewer_wo8x", "summary": "This paper presents an intriguing correlation between mechanism design and randomized linear algebra within regression problems. I find the parallel drawn between the approximation error in active learning for regression issues and $(\\epsilon, \\delta)$-Bayesian incentive compatibility in mechanism design particularly insightful. The authors further demonstrate, through the delegation of results from the active learning for regression problem, the possibility of creating a higher-dimensional mechanism from a lower-dimensional one.", "questions": "I must commend the authors for these novel observations. However, I feel that the paper heavily leans on results already established in the literature, with less emphasis on clarifying the newly introduced correlation. I must confess that I found sections of the paper challenging to grasp. While the contributions of the paper could indeed be noteworthy, they would certainly benefit from improved elucidation. Please consider enhancing the presentation to ensure a more comprehensive understanding for readers.", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper appears to bridge the gap between two previously disconnected problems. This represents a highly intriguing venture in terms of enhancing our understanding of diverse issues and facilitating cross-domain learning. The potential for knowledge transfer and interdisciplinary insights is certainly commendable in this work.", "weaknesses": "While this paper tackles potentially insightful ideas, I found it somewhat challenging to follow the authors' explanations. It seems that the essence of their contributions could be further highlighted and articulated. I encourage the authors to strive for greater clarity and more effective communication of their key points to enhance the overall readability and impact of their work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We appreciate the reviewer's effort to read through our paper and their positive comments regarding knowledge transfer from RLA to mechanism design. We will do our best to improve the presentation of our results, but we would like to highlight that our paper used prior work in innovative ways. We recognize that this is a subjective statement. However, to substantiate it, we would like to mention that we do use prior work on active learning for $\\ell_p$ regression problems via randomized linear algebra, but the combination with mechanism design is (again, in our opinion) quite non-trivial: we had to modify the mechanism and analysis of Cai and Daskalakis to operate using $\\ell_p$ norms and we had to connect the active learning results with the mechanism design framework, as discussed in the Appendix of our work. We will make every effort to better highlight this novel combination of results in the main paper (instead of the Appendix) in the final version of our paper and include figures (see ``global response'')."}, {"review_id": "A1LiuxqexI", "reviewer": "Reviewer_RniX", "summary": "The paper studies Bayesian approximate mechanism design in a structured world, where each bidder's preferences can be roughly captured by a \"topic model\", i.e., the true valuation function is close to a linear combination of a few representative valutions.  Inspired by prior work, the paper follows a two-stage design: the seller first \"queries\" each bidder and tries to recover the bidder's latent valuation (i.e., coefficients corresponding to the representative valuations)  Then, with the recovered approximate latent valuations, the seller constructs a mechanism by placing blackbox queries to a good mechanism in the latent space.  (Importantly, it is assumed that we already know a good mechanism in the latent space.)  The main result is a design that requires much milder regularity conditions on the representative valuations, which also requires less communication with bidders.  The new design works for metrics induced by $\\ell_p$ norms for $p \\in [1, \\infty)$ whereas prior work focuses on the $\\ell_\\infty$ norm.", "questions": "(Also including detailed comments here)\n\nLine 42, \"... often depende on the number of items m, which could be prohibitively large ...\": while this claim is largely true, I wonder to what extent this is because of the intrinsic richness of information induced by heterogeneous items.  E.g., if all items are the same then at least the amount of communication needed shouldn't depend on m.  Can you comment on this?\n\nLine 69, conditions on A: do you mean \"(i), (ii), *or* (iii)\"?\n\nLine 149, $v_i: \\mathbb{R}^d \\times [0, 1])^m \\to \\mathbb{R}_+$: so the allocation of a mechanism is one number between [0, 1] for each item?  Is this general enough when bidders have non-additive valuations (e.g., a randomized mechanism may need to specify how items correlate in addition to the marginal probabilities)?  Or do you really mean $\\{0, 1\\}^m$?\n\nLine 154, \"$x: \\mathbb{R}_+^{nd} \\to [0, 1]^{nm}$\": again, why output only the marginal probabilities here?\n\nLine 219, \"we don't have bounds of the form ...\": this is a bit confusing at this point because Definitions 3 and 5 both talk about bounds precisely of this form.  Can you clarify?\n\nLine 323, Theorem 2: here you do write \"$v_i: \\mathbb{R}^d \\times 2^{[n]}$\".  Would be nice to be consistent (also see earlier comments).", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is fairly well organized.  In particular, the authors clearly explain their technical contributions in the main paper without giving too much detail, which I appreciate very much.  The paper studies a sensible and well recognized problem and makes solid progress.  Conceptually, I like the \"observation\" that designing the query scheme is really closely related to central problems in numerical linear algebra, which indeed enables the authors to borrow ideas from that extremely rich body of research.  Technically, the authors give a good overview of their approach, and I'm convinced that there are nontrivial ideas involved.", "weaknesses": "The paper is (unavoidably) a bit dense with heavy notation, etc.  I think it would help to use a simple running example to illustrate how things work.  The mechanism is also a bit complex, which is not ideal but perhaps hard to avoid too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions.\n\n- \"Line 42, ... Can you comment on this?\"\n\nIndeed, assuming richness of the valuation function is what drives the dependence on $m$ for the results cited. One way to view the current work (and the work of Cai-Daskalakis) is that we take the first steps to move away from such assumptions by borrowing technical tools from the rich field of RLA.\n\n- \"Line 69, conditions on A: do you mean \"(i), (ii), or (iii)\"?\"\n\nYes; we will fix this.\n\n- \"Line 149... \", \"Line 154: ...\", \"Line 323: ...\"\n\nThank you for catching this. Indeed, a valuation takes as input a distribution over subsets, not just the marginals. Similarly, the allocation rule outputs a distribution over subsets. We will correct these typos.\n\n- \"Line 219, \"we don't have bounds of the form ...\": this is a bit confusing at this point because Definitions 3 and 5 both talk about bounds precisely of this form. Can you clarify?\"\n\nOur assumption is not on the individual types, as Definitions 3 and 5 need, but on the overall distributions. The way this is reconciled in the proofs is by a coupling argument, and specifically Lemma 1 (see lines 336-339). We will clarify this."}, {"review_id": "7HwCxfxpxF", "reviewer": "Reviewer_mHuT", "summary": "This paper demonstrates that results qualitatively similar to [CD'22] can hold under considerably weaker considers on the latent-factor matrix A, by using randomized linear algebra and a modified mechanism design to circumvent prior restrictions.\n\nEDIT: The rebuttal convinced me of the significance of the work and its contribution, and I have raised my score accordingly.", "questions": "Are there other Mechanism Design arguments based on Prokhorov's Distance in the literature? Could the results of CD22 be improved or simplified using your proof techniques?\n\nIn Defn 4, the authors assume access to \"elements of t_i + epsilon_...\". Do they mean \"entries of\"?", "limitations": "The setting is somewhat niche. In particular, the RLA model assumes queries of the elements of valuation vectors up to noise. This requires that the principal can elicit somewhat truthful valuations of items from the agent. This assumption is treated non-economically; i.e, the agent is assumed to be at most \"epsilon_nq\"-strategic. I think the authors should comment on why it is realistic to assume not only query access, but access to (approximately truthful) queries!", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper substantially weakens the requirements on the design matrix A required by CD22\n2. The mechanism design argument based on translating Prokhorov distance into TV distance via rounding seems novel and more broadly useful. \n3. This paper makes an interesting connection between randomized linear algebra and mechanism design that is relatively new to the statistical learning community. \n4. The comparison to past work is thoroughly explained. \n5. The notation table was much appreciated.", "weaknesses": "1. It seems that there is quite a lot of notational overheard, and quite a few assumptions. There are many notions of error and approximation floating around and it would be beneficial to try and streamline some of them. For example, having a recapitulation of assumptions in the appendix would be helpful.\n\n2. At times, it feels like the paper is making an incremental contribution to a rather niche setting. Correct me if I'm wrong but it seems that the techniques for RLA are fundamentally standard, even if the notion of approximation is specific to this setting.\n3. The authors should try to explain what if any contributions they make to mechanism design / Econ+ML more broadly. One can always imagine defining newer settings with more minutiae. Why is this the \"right one\"?\n\n\nIn summary, my main concern is whether or not this particular set of assumptions is more \"fundamental\" than CD'22, and whether the techniques here (esp. in rounding for Mechanism Design), are more broadly useful.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions. \n\nRegarding your comment about the setting being niche, we respectfully disagree. In the last 20 years, internet ad auctions have been extremely influential in advancing auction theory/mechanism design (at least from the CS side), in addition to being a half-a-trillion-dollar industry. From the theoretical side, we understand that designing optimal auctions is difficult (and there are many ways that the literature has quantified what \"difficult\" means), and also that the complexity/error when designing near-optimal auctions must depend on the (huge) number of items, limiting the applicability of numerous recent results in this domain. This dependence is unavoidable when one assumes richness in the valuation structure of the agents, i.e. when items' values are very different from each other. Removing dependence on the number of items is not a niche issue, but, in our view, a first-order consideration when taking theoretical results to practice. Unfortunately, mechanism design does not yet have a language for quantifying \"similarity\" between items. One can view our work, and the work of Cai-Daskalakis, as taking the first steps to develop such a language by borrowing technical tools from RLA. \n\nRegarding the truthfulness of queries, our mechanism is approximately truthful. That is, an all-knowing, infinitely powerful agent that lies in the optimal way (lying here means answering queries dishonestly), can only make a little bit more than an agent that doesn't lie. Our (economic) assumption is that if lying optimally can only provide a small benefit, agents will opt for behaving honestly. We find this to be a realistic assumption: if an agent with unbounded power and knowledge can only profit a bit from deviating, a real-world agent won't attempt to spend resources to find a profitable deviation.\n\nWe can comment on both of these issues.\n\nBelow we answer your questions.\n\n- ``Are there other Mechanism Design arguments based on Prokhorov's Distance in the literature? Could the results of CD22 be improved or simplified using your proof techniques?''\n\nPapers that study the robustness of mechanisms under inaccurate priors often also study the Prokhorov metric, e.g. \"Multi-item mechanisms without item-independence: Learnability via robustness\" by Brustle et al., or \"Posted Pricing and Prophet Inequalities with Inaccurate Priors\" by Dutting and Kesselheim. Indeed, we do improve upon CD22 in various ways: we extend the learning component to other norms, we remove assumptions in the mechanism design component, and in the combined component, our analysis distills the parameters that affect the errors, allowing us to push beyond the case of restricted additive valuations.\n\n- ``In Defn 4, the authors assume access to \"elements of $t_i$ + ...\". Do they mean \"entries of\"?''\n\nYes; we will correct this."}]

Author rebuttal:
We would like to thank all six reviewers for their reviews and constructive feedback. We recognize that, since our work spans two areas, Randomized Linear Algebra and Mechanism Design, some technical parts of our paper are harder to follow if one does not have a background in both domains. We do believe that our work does open the door to future interactions between these two fundamental areas, that had absolutely no intersection in prior literature. The majority of the reviewers agreed with this assessment. We would also like to mention that NeurIPS has historically accepted numerous papers in both Mechanism Design and Randomized Linear Algebra, therefore we believe that a paper that intersects the two areas very much belongs to this conference.

We commit to making every effort to follow reviewer comments and improve the presentation of our work in order to make it accessible to the broadest possible audience. We will incorporate the valuable suggestions from all reviewers in the final version of this paper. We will also include the attached figure (adjusted to incorporate reviewers' feedback, of course) in the final version of the paper. (Please let us know if the figure is not visible.)

Meta-review: Reviewers generally felt positive about this paper, especially after discussion with the authors. They generally agreed that using ideas from randomized linear algebra to improve upon recent work in mechanism design is a nice contribution. Bridging these two areas is valuable and hopefully will lead to interesting follow up work at their intersection. 

Many reviewers felt that the paper was difficult to read, and some recommended rejecting based on this concern. I strongly encourage the authors to incorporate reviewer comments and generally work on improving the presentation for the camera ready version. While a paper spanning two areas can be difficult to write cleanly, it is important to put emphasis on trying to do so as much as possible, if the paper is to have impact and be readable by members of both the RLA and mechanism design communities.
Decision: Accept (poster)