# Refined Mechanism Design for Approximately Structured Priors via Active Regression

arXiv: https://arxiv.org/abs/2310.07874 · HTML: https://mlsanity.com/paper/2310.07874/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 11 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [Strong Duality for a Multiple-Good Monopolist](https://mlsanity.com/paper/1409.4150/) (2014)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Making the Most of Your Samples](https://mlsanity.com/paper/1407.2479/) (2014)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Understanding Incentives: Mechanism Design becomes Algorithm Design](https://mlsanity.com/paper/1305.4002/) (2013)
- [A Simple and Approximately Optimal Mechanism for an Additive Buyer](https://mlsanity.com/paper/1405.6146/) (2014)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [A Duality-Based Unified Approach to Bayesian Mechanism Design](https://mlsanity.com/paper/1812.01577/) (2018)
- [An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications](https://mlsanity.com/paper/1406.3278/) (2014)
- [Mechanism Design via Optimal Transport](https://mlsanity.com/paper/1503.01958/) (2015)
- [Simple Mechanisms for Subadditive Buyers via Duality](https://mlsanity.com/paper/1611.06910/) (2016)
- [Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")](https://mlsanity.com/paper/1304.6116/) (2013)
- [Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations](https://mlsanity.com/paper/1305.4000/) (2013)
- [Mechanism Design for Subadditive Agents via an Ex-Ante Relaxation](https://mlsanity.com/paper/1603.03806/) (2016)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [On Infinite Separations Between Simple and Optimal Mechanisms](https://mlsanity.com/paper/2205.13039/) (2022)

## Abstract (arXiv)

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~citecai2022recommender, 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.