Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension

DOI10.1137/15M1045971zbMath1410.91244OpenAlexW2783140482MaRDI QIDQ4602545

Michael Schapira, Amit Daniely, Gal Shahaf

Publication date: 31 January 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1045971

zbMATH Keywords

auctionsVC dimensionAGT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence of submatrices with all possible columns
• Bundling equilibrium in combinatorial auctions
• Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
• A generalization of Sauer's lemma
• The communication requirements of efficient allocations and supporting prices
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Truth revelation in approximately efficient combinatorial auctions
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• Scale-sensitive dimensions, uniform convergence, and learnability
• On the Power of Randomization in Algorithmic Mechanism Design
• An impossibility result for truthful combinatorial auctions with submodular valuations
• Truthful randomized mechanisms for combinatorial auctions

This page was built for publication: Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension