Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

DOI10.1145/2746539.2746597zbMath1321.68303arXiv1412.6265OpenAlexW2963138504MaRDI QIDQ2941531

Gal Shahaf, Amit Daniely, Michael Schapira

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.6265

zbMATH Keywords

mechanism designhardnessalgorithmic game theoryincentive compatible computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ A simple and fast algorithm for convex decomposition in relax-and-round mechanisms ⋮ Setting lower bounds on truthfulness ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension