Multi-Item Mechanisms without Item-Independence: Learnability via Robustness
Multi-Item Mechanisms without Item-Independence: Learnability via Robustness
复制标题
没有项目独立性的多项目机制：通过鲁棒性实现可学习性
DOI：
10.1145/3391403.3399541
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Daskalakis, Constantinos
中科院分区：
文献类型：
--
作者：
Brustle, Johannes;Cai, Yang;Daskalakis, Constantinos
我们研究了学习收益最优多物品拍卖的样本复杂性。我们获得了第一组积极的结果，超出了标准，但不切实际的设置项目的独立性。特别是，我们考虑的设置中，投标人的估值是从相关的分布，可以捕获马尔可夫随机场或贝叶斯网络-两个最突出的图形模型。我们建立了参数化的样本复杂性界限，用于在两个模型中学习最大ε最优机制，其在模型的大小上呈多项式扩展，即项目和投标人的数量，并且在模型的自然复杂性度量中仅呈指数，也就是说，（对于贝叶斯网络）或最大超边的大小（马尔可夫随机场）。我们通过一个新颖的模块化框架获得了我们的可学习性结果，该框架首先涉及证明鲁棒性定理。我们表明，只给出投标人估值的“近似分布”，我们可以学习一种机制，其收入几乎是最优的同时，所有的“真实分布”，接近我们在Prokhorov距离。因此，要学习一个好的机制，只需学习近似分布。当项目值是独立的时，Prokhorov距离中的学习是即时的，因此我们的框架直接暗示了Gonczarowski和温伯格[36]的主要结果。当项目值从更一般的图形模型中采样时，我们将联合收割机的鲁棒性定理与新的样本复杂性结果相结合，用于学习Prokhorov距离中的马尔可夫随机场或贝叶斯网络，这可能是独立的兴趣。最后，在单项目的情况下，我们的鲁棒性结果可以得到加强，以保持在一个更弱的分布距离，利维距离。
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-ε 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[36]. 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 Levy distance.
登录
查看更多内容
DOI：
10.1137/1.9781611973075.49
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Patrick Briest;Shuchi Chawla;Robert D. Kleinberg;S. Weinberg;A. P. Sloan;Foundation Fellowship
通讯作者：
Foundation Fellowship
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Yang Cai;C. Daskalakis
通讯作者：
C. Daskalakis
主导策略与贝叶斯多项目拍卖：最大收入确定和比较
DOI：
10.1145/3033274.3085120
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
A. Yao
通讯作者：
A. Yao
DOI：
10.1016/b978-0-12-386908-1.00037-9
发表时间：
2018-11
期刊：
Wiley Series in Probability and Statistics
影响因子：
--
作者：
Bruce E. Blaine
通讯作者：
Bruce E. Blaine
收入最大化和事后预算约束
DOI：
10.1145/2764468.2764521
发表时间：
2015
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
C. Daskalakis;Nikhil R. Devanur;S. M. Weinberg
通讯作者：
S. M. Weinberg