论文标题
以多单位VCG拍卖的近似储备价格击败贪婪
Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
论文作者
论文摘要
我们研究了与与之相关的买家的多单元急切VCG拍卖中寻找个性化储备价格的问题。此问题的输入是一组拍卖中提交的$ n $买家投标数据集。目的是找到一个储备价格的向量，每个买家一个，这最大化了所有拍卖的总收入。 Roughgarden和Wang（2016）表明，此问题是APX-HARD，但承认贪婪的$ \ frac {1} {2} $ - 近似算法。后来，Derakhshan，Golrezai和Paes Leme（2019）给出了一项基于LP的算法，以实现单个项目的（重要）特殊情况的（重要的）特殊情况，从而获得了0.68美元的应用，从而击败了贪婪。我们在本文中表明，Derakhshan等人的算法。实际上，对于一般的多项目问题，并没有击败贪婪。这就提出了一个问题，即一般问题是否接受一个更好的 - $ \ frac {1} {2} $近似。 在本文中，我们以肯定的方式回答了这个问题，并提供了多项式时间算法，其近似值明显更好，为0.63美元。我们的解决方案是基于一种新型的线性编程公式，为此我们提出了两种不同的圆形方案。我们证明，这两个中最好的和无保留的情况（全零矢量）是$ 0.63 $ - approximation。
We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset of submitted bids of $n$ buyers in a set of auctions. The goal is to find a vector of reserve prices, one for each buyer, that maximizes the total revenue across all auctions. Roughgarden and Wang (2016) showed that this problem is APX-hard but admits a greedy $\frac{1}{2}$-approximation algorithm. Later, Derakhshan, Golrezai, and Paes Leme (2019) gave an LP-based algorithm achieving a $0.68$-approximation for the (important) special case of the problem with a single-item, thereby beating greedy. We show in this paper that the algorithm of Derakhshan et al. in fact does not beat greedy for the general multi-item problem. This raises the question of whether or not the general problem admits a better-than-$\frac{1}{2}$ approximation. In this paper, we answer this question in the affirmative and provide a polynomial-time algorithm with a significantly better approximation-factor of $0.63$. Our solution is based on a novel linear programming formulation, for which we propose two different rounding schemes. We prove that the best of these two and the no-reserve case (all-zero vector) is a $0.63$-approximation.
