caa a22 4500 445358661 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00493-011-2528-4 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2528-4 Limitations of VCG-based mechanisms [Elektronische Daten] [Shahar Dobzinski, Noam Nisan] We consider computationally-efficient truthful mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We present a novel technique for setting lower bounds on the approximation ratio of this type of mechanisms. Our technique is based on setting lower bounds on the communication complexity by analyzing combinatorial properties of the algorithms. Specifically, for combinatorial auctions among submodular (and thus also subadditive) bidders we prove an $$\Omega \left( {m^{\tfrac{1} {6}} } \right)$$ lower bound, which is close to the known upper bound of $${\rm O}\left( {m^{\tfrac{1} {2}} } \right)$$ , and qualitatively higher than the constant factor approximation possible from a purely computational point of view. János Bolyai Mathematical Society and Springer Verlag, 2011 Dobzinski Shahar Department of Computer Science, Cornell University, Ithaca, USA aut Nisan Noam The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel aut Combinatorica Springer-Verlag 31/4(2011-11-01), 379-396 0209-9683 31:4<379 2011 31 493 https://doi.org/10.1007/s00493-011-2528-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2528-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dobzinski Shahar Department of Computer Science, Cornell University, Ithaca, USA aut NATIONALLICENCE 700 1- Nisan Noam The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/4(2011-11-01), 379-396 0209-9683 31:4<379 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer