The design of revenue-maximizing combinatorial auctions, i.e. multi-item
auctions over bundles of goods, is one of the most fundamental problems in
computational economics, unsolved even for two bidders and two items for sale.
In the traditional economic models, it is assumed that the bidders' valuations
are drawn from an underlying distribution and that the auction designer has
perfect knowledge of this distribution. Despite this strong and oftentimes
unrealistic assumption, it is remarkable that the revenue-maximizing
combinatorial auction remains unknown. In recent years, automated mechanism
design has emerged as one of the most practical and promising approaches to
designing high-revenue combinatorial auctions. The most scalable automated
mechanism design algorithms take as input samples from the bidders' valuation
distribution and then search for a high-revenue auction in a rich auction
class. In this work, we provide the first sample complexity analysis for the
standard hierarchy of deterministic combinatorial auction classes used in
automated mechanism design. In particular, we provide tight sample complexity
bounds on the number of samples needed to guarantee that the empirical revenue
of the designed mechanism on the samples is close to its expected revenue on
the underlying, unknown distribution over bidder valuations, for each of the
auction classes in the hierarchy. In addition to helping set automated
mechanism design on firm foundations, our results also push the boundaries of
learning theory. In particular, the hypothesis functions used in our contexts
are defined through multi-stage combinatorial optimization procedures, rather
than simple decision boundaries, as are common in machine learning.

本研究探讨自动机制设计算法在组合拍卖中的应用，提供了关于组合拍卖类的样本复杂度分析，为自动机制设计奠定了坚实基础并推进了学习理论的边界。

自动机制设计的样本复杂度

Sample Complexity of Automated Mechanism Design

In the design and analysis of revenue-maximizing auctions, auction
performance is typically measured with respect to a prior distribution over
inputs. The most obvious source for such a distribution is past data. The goal
is to understand how much data is necessary and sufficient to guarantee
near-optimal expected revenue.
Our basic model is a single-item auction in which bidders' valuations are
drawn independently from unknown and non-identical distributions. The seller is
given $m$ samples from each of these distributions "for free" and chooses an
auction to run on a fresh sample. How large does m need to be, as a function of
the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the
optimal revenue is achievable?
We prove that, under standard tail conditions on the underlying
distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our
lower bound stands in contrast to many recent results on simple and
prior-independent auctions and fundamentally involves the interplay between
bidder competition, non-identical distributions, and a very close (but still
constant) approximation of the optimal revenue. It effectively shows that the
only way to achieve a sufficiently good constant approximation of the optimal
revenue is through a detailed understanding of bidders' valuation
distributions. Our upper bound is constructive and applies in particular to a
variant of the empirical Myerson auction, the natural auction that runs the
revenue-maximizing auction with respect to the empirical distributions of the
samples.
Our sample complexity lower bound depends on the set of allowable
distributions, and to capture this we introduce alpha-strongly regular
distributions, which interpolate between the well-studied classes of regular
(alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this
definition is of independent interest.

本文通过研究直接基于分布进行收益最大化拍卖的样本复杂度，探讨了数据量在何种程度下可以保证期望收益最大化接近最优，并且构建了一个解释了拍卖、非常接近最优的收益、参与竞标者出价的估值分布之间相互作用的下界。