{"ID":2832332,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.06585","arxiv_id":"2512.06585","title":"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 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 $\\cup$ SC (the union of subadditive and succinct valuations): (1) There is a polynomial communication $3$-approximation algorithm; (2) As $n \\to \\infty$, there is a matching $3$-hardness of approximation, which (a) is larger than the optimal approximation ratio of $2$ for SA, and (b) holds even for SA $\\cup$ SM (the union of subadditive and single-minded valuations); and (3) For all $n \\geq 3$, there is a constant separation between the optimal approximation ratios for SA $\\cup$ SM and SA (and therefore between SA $\\cup$ SC and SA as well). Similarly, we show that for XOS $\\cup$ SC: (1) There is a polynomial communication $2$-approximation algorithm; (2) As $n \\to \\infty$, there is a matching $2$-hardness of approximation, which (a) is larger than the optimal approximation ratio of $e/(e-1)$ for XOS, and (b) holds even for XOS $\\cup$ SM; and (3) For all $n \\geq 2$, there is a constant separation between the optimal approximation ratios for XOS $\\cup$ SM and XOS (and therefore between XOS $\\cup$ SC and XOS as well).","short_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 explicitly state, such as subadditive or XOS), or arbitrary succinct valuations (which can be fully described in polynomial communicatio...","url_abs":"https://arxiv.org/abs/2512.06585","url_pdf":"https://arxiv.org/pdf/2512.06585v1","authors":"[\"Frederick V. Qiu\",\"S. Matthew Weinberg\",\"Qianfan Zhang\"]","published":"2025-12-06T22:39:06Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}