论文标题
在（in） - 组合买家的贝叶斯收入最大化
On the (in)-approximability of Bayesian Revenue Maximization for a Combinatorial Buyer
论文作者
论文摘要
我们认为，收入最大化的单卖商，将$ M $物品出售给单个买家，其价值$ v（\ cdot）$是从已知的分配$ d $ dupport $ k $中获取的。 Cai等人的一系列作品。确定，当每个$ v（\ cdot）$支持$ d $的每个$ v $是加法或单位听点（或$ c $ - 按需）时，可以在$ \ operatorname {poly}（m，k）$ time中找到收入最佳拍卖。 我们表明，甚至超出了这一点，即使是基于基质的估值（合适的总替代品）也导致了近似的强硬度。具体而言，即使在$ M $项目和$ k \ leq m $支持$ d $的情况下，也无法实现$ 1/m^{1- \ varepsilon} $ - 对于任何$ \ varepsilon> 0 $的近似值，即在基于Matroid的n np（随机）$（随机）$（随机性）$（随机性）$（随机性）多个$（除非$ 1/k $ -Approximation是微不足道的）。 Cai等人的主要技术贡献是从收入最大化$ \ Mathcal {v} $中的收入最大化，以优化类$ \ Mathcal {V} $中的两个值之间的差异。我们的主要技术贡献是在另一个方向（对于广泛的估值类别）上的黑盒减少，确定其减少基本上是紧张的。
We consider a revenue-maximizing single seller with $m$ items for sale to a single buyer whose value $v(\cdot)$ for the items is drawn from a known distribution $D$ of support $k$. A series of works by Cai et al. establishes that when each $v(\cdot)$ in the support of $D$ is additive or unit-demand (or $c$-demand), the revenue-optimal auction can be found in $\operatorname{poly}(m,k)$ time. We show that going barely beyond this, even to matroid-based valuations (a proper subset of Gross Substitutes), results in strong hardness of approximation. Specifically, even on instances with $m$ items and $k \leq m$ valuations in the support of $D$, it is not possible to achieve a $1/m^{1-\varepsilon}$-approximation for any $\varepsilon>0$ to the revenue-optimal mechanism for matroid-based valuations in (randomized) poly-time unless NP $\subseteq$ RP (note that a $1/k$-approximation is trivial). Cai et al.'s main technical contribution is a black-box reduction from revenue maximization for valuations in class $\mathcal{V}$ to optimizing the difference between two values in class $\mathcal{V}$. Our main technical contribution is a black-box reduction in the other direction (for a wide class of valuation classes), establishing that their reduction is essentially tight.
