The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders

We study the communication complexity of welfare maximization in combinatorial auctions with bidders from either a standard valuation class (which require exponential communication to explicitly 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. Specifically:

Let n be the number of subadditive/XOS bidders. We show that for SA ∪ Succ (the union of subadditive and succinct valuations):

• There is a polynomial communication 3-approximation algorithm.

• As n → ∞, there is a matching 3-hardness of approximation, which (a) is larger than the optimal approximation ratio of 2 for SA [Fei09], and (b) holds even for SA ∪ SM (the union of subadditive and single-minded valuations).

• For all n ≥ 3, there is a constant separation between the optimal approximation ratios for SA ∪ SM and SA (and therefore between SA ∪ Succ and SA as well).

Similarly, we show that for XOS ∪ Succ:

• There is a polynomial communication 2-approximation algorithm.

• As n → ∞, there is a matching 2-hardness of approximation, which (a) is larger than the optimal approximation ratio of e/(e -1) for XOS [DNS10], and (b) holds even for XOS ∪ SM.

• For all n ≥ 2, there is a constant separation between the optimal approximation ratios for XOS ∪ SM and XOS (and therefore between XOS ∪ Succ and XOS as well).