Robust Revenue Maximization Under Minimal Statistical Information.

摘要: We study the problem of multi-dimensional revenue maximization when selling $m$ items to a buyer that has additive valuations for them, drawn from (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume seller very restricted knowledge this prior: they only know mean $\mu_j$ and an upper bound $\sigma_j$ on standard deviation each item's marginal Our goal is design mechanisms achieve good against ideal optimal full distribution in advance. Informally, our main contribution tight quantification interplay between dispersity priors aforementioned robust approximation ratio. Furthermore, can be achieved by simple mechanisms. More precisely, show via separate price lotteries achieves $O(\log r)$ ratio where $r=\max_j(\sigma_j/\mu_j)$ maximum coefficient variation across items. If forced restrict ourselves deterministic mechanisms, guarantee degrades $O(r^2)$. Assuming independence item valuations, these ratios further improved pricing bundle. For case identical means variances, particular, get $O(\log(r/m))$ which converges optimality as number grows large. demonstrate above providing matching lower bounds. analysis resolves open gap work Azar Micali [ITCS'13]. As by-product, also how one directly use bounds improve extend previous results related parametric auctions et al. [SODA'13].