Combinatorial Auctions and Approximation Mechanisms
Stub. Combinatorial auction design (single-minded bidders, Walrasian equilibrium, bidding languages, iterative/ascending auctions, communication complexity) and computationally efficient approximation mechanisms for single- and multi-dimensional domains. (AGT ch. 11-12)
Merges the two chapters on selling multiple heterogeneous items: Blumrosen and Nisan’s treatment of combinatorial auction design (single-minded bidders, Walrasian equilibrium and its LP relaxation, bidding languages, iterative auctions, communication complexity lower bounds, ascending auctions) with Lavi’s treatment of approximation when exact incentive compatibility is too expensive to compute (single-dimensional job scheduling, multidimensional combinatorial auctions, impossibility results, alternative solution concepts).
Outline (TODO — flesh out each)
- The single-minded bidder case
- Walrasian equilibrium and the LP relaxation
- Bidding languages; iterative auctions and the query model
- Communication complexity of combinatorial auctions
- Ascending auctions
- Single-dimensional domains: approximation for job scheduling
- Multidimensional domains: approximate combinatorial auctions
- Impossibilities of dominant-strategy implementability
- Alternative solution concepts under computational constraints