# Multi-Item Mechanisms without Item-Independence: Learnability via Robustness

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2019.

## Built on by (most cited first, 23 of 23)

- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [Estimation of Standard Auction Models](https://mlsanity.com/paper/2205.02060/) (2022)
- [User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization](https://mlsanity.com/paper/2302.08108/) (2023)
- [Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce](https://mlsanity.com/paper/2405.07038/) (2024)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Learnability of Parameter-Bounded Bayes Nets](https://mlsanity.com/paper/2407.00927/) (2024)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Sample Complexity of Forecast Aggregation](https://mlsanity.com/paper/2207.13126/) (2022)
- [A Robust Multi-Item Auction Design with Statistical Learning](https://mlsanity.com/paper/2302.00941/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)
- [Price of Anarchy of First-Price Auctions in Agentic Markets](https://mlsanity.com/paper/2610.20587/) (2026)

## Abstract (arXiv)

We study the sample complexity of learning revenue-optimal multi-item auctions. We obtain the first set of positive results that go beyond the standard but unrealistic setting of item-independence. In particular, we consider settings where bidders' valuations are drawn from correlated distributions that can be captured by Markov Random Fields or Bayesian Networks -- two of the most prominent graphical models. We establish parametrized sample complexity bounds for learning an up-to-varepsilon optimal mechanism in both models, which scale polynomially in the size of the model, i.e.~the number of items and bidders, and only exponential in the natural complexity measure of the model, namely either the largest in-degree (for Bayesian Networks) or the size of the largest hyper-edge (for Markov Random Fields). We obtain our learnability results through a novel and modular framework that involves first proving a robustness theorem. We show that, given only ``approximate distributions'' for bidder valuations, we can learn a mechanism whose revenue is nearly optimal simultaneously for all ``true distributions'' that are close to the ones we were given in Prokhorov distance. Thus, to learn a good mechanism, it suffices to learn approximate distributions. When item values are independent, learning in Prokhorov distance is immediate, hence our framework directly implies the main result of Gonczarowski and Weinberg. When item values are sampled from more general graphical models, we combine our robustness theorem with novel sample complexity results for learning Markov Random Fields or Bayesian Networks in Prokhorov distance, which may be of independent interest. Finally, in the single-item case, our robustness result can be strengthened to hold under an even weaker distribution distance, the L'evy distance.