The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders
Abstract
We study the communication complexity of welfare maximization in combinatorial auctions with bidders from either a standard valuation class (which require exponential communication to state, such as subadditive or XOS), or arbitrary succinct valuations (which can be fully described in polynomial communication, such as single-minded). Although succinct valuations can be efficiently communicated, we show that additional succinct bidders have a nontrivial impact on communication complexity of classical combinatorial auctions.
Fields of Study & Subjects
Auction Theory and Applications
Game Theory and Applications
Game Theory and Voting Systems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 2134–2162
- Publication date
- 1 January 2026
- Language
- EN