For revenue and welfare maximization in single-dimensional Bayesian settings,
Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms
(SPMs), though simple in form, can perform surprisingly well compared to the
optimal mechanisms. In this paper, we give a theoretical explanation of this
fact, based on a connection to the notion of correlation gap.
Loosely speaking, for auction environments with matroid constraints, we can
relate the performance of a mechanism to the expectation of a monotone
submodular function over a random set. This random set corresponds to the
winner set for the optimal mechanism, which is highly correlated, and
corresponds to certain demand set for SPMs, which is independent. The notion of
correlation gap of Agrawal et al.\ (SODA10) quantifies how much we {}"lose" in
the expectation of the function by ignoring correlation in the random set, and
hence bounds our loss in using certain SPM instead of the optimal mechanism.
Furthermore, the correlation gap of a monotone and submodular function is known
to be small, and it follows that certain SPM can approximate the optimal
mechanism by a good constant factor.
Exploiting this connection, we give tight analysis of a greedy-based SPM of
Chawla et al.\ for several environments. In particular, we show that it gives
an $e/(e-1)$-approximation for matroid environments, gives asymptotically a
$1/(1-1/\sqrt{2\pi k})$-approximation for the important sub-case of $k$-unit
auctions, and gives a $(p+1)$-approximation for environments with
$p$-independent set system constraints.

本文介绍了如何通过单序列挂牌策略（SPMs）来进行拍卖，尤其是在由某些环境约束下，可以与最优机制相媲美。通过与相关差的概念建立联系，本文相对于随机集合的单调子模函数期望来解释了拍卖机制表现的性能，并表明某些 SPM 可以通过很好的固定因子来近似于最优机制。