On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations
Shahar DobzinskiJan VondrákPublished in: CoRR (2012)
Keyphrases
- combinatorial auctions
- social welfare
- objective function
- winner determination
- approximation algorithms
- resource allocation
- single item
- greedy algorithm
- mechanism design
- multi unit
- np hard
- worst case
- multi unit combinatorial auctions
- set covering
- multi item
- computational complexity
- mathematical programming
- special case
- bidding strategies
- auction mechanisms
- linear programming
- supply chain
- multi objective
- auction protocol
- lower bound