Separating the communication complexity of truthful and non-truthful combinatorial auctions
Separating the communication complexity of truthful and non-truthful combinatorial auctions
复制标题
区分真实和非真实组合拍卖的通信复杂性
DOI：
10.1145/3357713.3384267
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Weinberg, S. Matthew
中科院分区：
文献类型：
--
作者：
Assadi, Sepehr;Khandeparkar, Hrishikesh;Saxena, Raghuvansh R.;Weinberg, S. Matthew
我们证明了第一次分离的近似保证可实现的真实和非真实的组合拍卖多项式通信。具体地说，我们证明任何真实的拍卖保证两个具有XOS估值的买家的（34 - 1240+ ε 2·m）-近似需要exp（Ω（ε2·m））通信，而Feige [J.Comput.2009]的非真实拍卖已经知道在（m）通信中实现34-近似。我们通过证明任何同时拍卖获得真实拍卖的下限，（不一定是真实的），这保证了（34−1240+ε）-近似需要通信exp（Ω（ε2·m）），然后应用Dobzinski [FOCS 2016]的税收复杂性框架将下限扩展到所有真实拍卖（包括交互式真实拍卖）。
We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34−1240+є)-approximation for two buyers with XOS valuations overmitems requires exp(Ω(ε2·m)) communication whereas a non-truthful auction by Feige [J. Comput.2009] is already known to achieve a 34-approximation in (m) communication.We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34−1240+ε)-approximation requires communication exp(Ω(ε2·m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).
登录
查看更多内容
具有子模估值的真实组合拍卖的不可能结果
影响因子：
2.5
作者：
Shahar Dobzinski;Jan Vondrák
通讯作者：
Jan Vondrák
解决与两个次级买家的组合拍卖的通信复杂性
DOI：
10.1109/focs.2019.00025
发表时间：
2019
期刊：
Foundations of Computer Science
影响因子：
--
作者：
Ezra, Tomer;Feldman, Michal;Neyman, Eric;Talgam-Cohen, Inbal;Weinberg, Matt
通讯作者：
Weinberg, Matt
从查询复杂度到计算复杂度
DOI：
--
发表时间：
2012
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Shahar Dobzinski;J. Vondrák
通讯作者：
J. Vondrák
DOI：
--
发表时间：
2016
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Shahar Dobzinski
通讯作者：
Shahar Dobzinski
改进的次加性组合拍卖的真实机制：打破对数障碍
DOI：
10.1137/1.9781611976465.40
发表时间：
2020
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Sepehr Assadi;Thomas Kesselheim;Sahil Singla
通讯作者：
Sahil Singla