TY - GEN
T1 - Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees
AU - Qiu, Frederick
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2024 Owner/Author.
PY - 2024/6/10
Y1 - 2024/6/10
N2 - We consider truthful combinatorial auctions with items M = [m] for sale to n bidders, where each bidder i has a private monotone valuation function vi: 2M → ℝ+. Among truthful mechanisms, maximal-in-range (MIR) mechanisms (sometimes called VCG-based) achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication complexity necessary to achieve any approximation guarantee via an MIR mechanism. Specifically: Let MIRSubMod(m, k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with submodular valuations over m items. Then for all k = ω(log(m)), MIRSubMod(m,k) = ω(√m/(klog(m/k))). When we set k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from ω(m1/3/log2/3(m)) to ω(√m/log(m)). Additionally, MIRSubMod(m, k) = O(√m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. The mechanism also works for bidders with subadditive valuations. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(√m) to O(√m/log(m)). Let also MIRGen(m,k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with general valuations over m items. Then for all k = ω(log(m)), MIRGen(m, k) = ω(m/k). When k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from ω(m/log2(m)) to ω(m/log(m)). Additionally, MIRGen(m, k) = O(m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(m/√log(m)) to O(m/log(m)).
AB - We consider truthful combinatorial auctions with items M = [m] for sale to n bidders, where each bidder i has a private monotone valuation function vi: 2M → ℝ+. Among truthful mechanisms, maximal-in-range (MIR) mechanisms (sometimes called VCG-based) achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication complexity necessary to achieve any approximation guarantee via an MIR mechanism. Specifically: Let MIRSubMod(m, k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with submodular valuations over m items. Then for all k = ω(log(m)), MIRSubMod(m,k) = ω(√m/(klog(m/k))). When we set k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from ω(m1/3/log2/3(m)) to ω(√m/log(m)). Additionally, MIRSubMod(m, k) = O(√m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. The mechanism also works for bidders with subadditive valuations. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(√m) to O(√m/log(m)). Let also MIRGen(m,k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with general valuations over m items. Then for all k = ω(log(m)), MIRGen(m, k) = ω(m/k). When k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from ω(m/log2(m)) to ω(m/log(m)). Additionally, MIRGen(m, k) = O(m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(m/√log(m)) to O(m/log(m)).
KW - Combinatorial Auction
KW - Communication Complexity
KW - Maximal-in-Range
KW - VCG-Based
UR - https://www.scopus.com/pages/publications/85196612679
UR - https://www.scopus.com/pages/publications/85196612679#tab=citedBy
U2 - 10.1145/3618260.3649706
DO - 10.1145/3618260.3649706
M3 - Conference contribution
AN - SCOPUS:85196612679
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1192
EP - 1203
BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
A2 - Mohar, Bojan
A2 - Shinkar, Igor
A2 - O�Donnell, Ryan
PB - Association for Computing Machinery
T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024
Y2 - 24 June 2024 through 28 June 2024
ER -