VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
Elchanan MosselChristos H. PapadimitriouMichael SchapiraYaron SingerPublished in: CoRR (2009)
Keyphrases
- vc dimension
- combinatorial auctions
- approximation algorithms
- worst case
- upper bound
- winner determination
- sample complexity
- lower bound
- np hard
- special case
- sample size
- mechanism design
- multi unit
- inductive inference
- concept classes
- resource allocation
- vickrey clarke groves
- compression scheme
- generalization bounds
- auction mechanisms
- strategy proof
- computational complexity
- multi dimensional
- bidding strategies
- mathematical programming
- euclidean space
- supply chain
- multi agent