论文标题
分开真实和非真实的组合拍卖的沟通复杂性
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
论文作者
论文摘要
我们提供了通过多项式交流的真实和非真实的组合拍卖可以实现的近似保证中的第一个分离。具体而言，我们证明，保证$（\ frac {3} {4} - \ frac {1} {1} {1} {240}+\ varepsilon）$的任何真实机制 - 对于两个具有$ m $ a $ m $项目的买家的近似值 - Dobzinski和Schapira [Soda 2006]和Feige [2009]已经众所周知，可以实现$ \ frac {3} {4} $ - $ poly（m）$ communication。 我们通过证明任何{同时}协议（{not}必然真实）来获得分离，该协议保证了$（\ frac {3} {4} {4} {4} - \ frac {1} {1} {240}+\ varepsilon）近似值 - 近似值需要通信$ \ exp（ω（ω）$ cdopsilon^$ cdot。 Dobzinski [Focs 2016]的税收复杂性框架将其扩展到所有真实的机制（包括交互式真实的机制）。
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(\frac{3}{4}-\frac{1}{240}+\varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $\exp(Ω(\varepsilon^2 \cdot m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [2009] is already known to achieve a $\frac{3}{4}$-approximation in $poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(\frac{3}{4}-\frac{1}{240}+\varepsilon)$-approximation requires communication $\exp(Ω(\varepsilon^2 \cdot m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).
