Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees

我们考虑有 $n$ 个竞标人的 $M=[m]$ 物品的真实组合拍卖，其中每个竞标人 $i$ 拥有私人单调估值 $v_i:2^M \to R_+$。在真实机制中，最大范围（MIR）机制在所有先前研究的设置中，通过所有多项式通信确定性真实机制实现了最佳逼近保证。我们的工作解决了通过MIR机制实现任何逼近保证所需的通信问题。具体而言：让MIRsubmod$(m,k)$表示使用$m$个物品上的子模估值的出价人之间的$2^k$通信所能实现的最佳逼近保证。那么对于所有$k = \Omega(\log(m))$，MIRsubmod$(m,k) = \Omega(\sqrt{m/(k\log(m/k))})$。当$k = \Theta(\log(m))$时，这将多项式通信的MIR机制的先前最佳下界从$\Omega(m^{1/3}/\log^{2/3}(m))$提高到$\Omega(\sqrt{m}/\log(m))$。我们还有MIRsubmod$(m,k) = O(\sqrt{m/k})$。此外，我们的机制在值查询和简洁表示模型方面是最优的。当$k = \Theta(\log(m))$时，这将多项式通信的MIR机制的先前最佳逼近保证从$O(\sqrt{m})$提高到$O(\sqrt{m/\log(m)})$。让MIRgen$(m,k)$表示使用$m$个物品上的一般估值的出价人之间的$2^k$通信所能实现的最佳逼近保证。那么对于所有$k = \Omega(\log(m))$，MIRgen$(m,k) = \Omega(m/k)$。当$k = \Theta(\log(m))$时，这将多项式通信的MIR机制的先前最佳下界从$\Omega(m/\log^2(m))$提高到$\Omega(m/\log(m))$。我们还有MIRgen$(m,k) = O(m/k)$。此外，我们的机制在值查询和简洁表示模型方面是最优的。当$k = \Theta(\log(m))$时，这将多项式通信的MIR机制的先前最佳逼近保证从$O(m/\sqrt{\log(m)})$提高到$O(m/\log(m))$。

研究在组合拍卖中使用最大化范围（MIR）机制实现近似解的通信复杂度

使用MIR机制，在具有子模估值和一般估值的买家之间进行组合拍卖，可以实现最佳近似解，并确定了实现任何近似保证所需的通信复杂度

论文提出了一种新的MIR机制，可以实现最佳近似解，并在值查询和简洁表示模型方面进行了优化。实验结果显示，这种机制在通信复杂度方面比以前的机制更有效。

最近的相关研究包括：《近似机制设计中的组合拍卖》、《使用子模估值的组合拍卖的近似保证》、《组合拍卖中的最大化范围机制》等