Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916186895155200 |
|---|---|
| author | Qiu, Frederick V. Weinberg, S. Matthew |
| author_facet | Qiu, Frederick V. Weinberg, S. Matthew |
| contents | We consider truthful combinatorial auctions with items $M = [m]$ for sale to $n$ bidders, where each bidder $i$ has a private monotone valuation $v_i : 2^M \to R_+$. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication 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 $2^k$ communication between bidders with submodular valuations over $m$ items. Then for all $k = Ω(\log(m))$, MIRsubmod$(m,k) = Ω(\sqrt{m/(k\log(m/k))})$. When $k = Θ(\log(m))$, this improves the previous best lower bound for poly-comm. MIR mechanisms from $Ω(m^{1/3}/\log^{2/3}(m))$ to $Ω(\sqrt{m}/\log(m))$. We also have MIRsubmod$(m,k) = O(\sqrt{m/k})$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(\sqrt{m})$ to $O(\sqrt{m/\log(m)})$.
Let also MIRgen$(m,k)$ denote the best approximation guarantee achievable by an MIR mechanism using $2^k$ 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 poly-comm. MIR mechanisms from $Ω(m/\log^2(m))$ to $Ω(m/\log(m))$. We also have MIRgen$(m,k) = O(m/k)$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(m/\sqrt{\log(m)})$ to $O(m/\log(m))$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00831 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees Qiu, Frederick V. Weinberg, S. Matthew Computer Science and Game Theory We consider truthful combinatorial auctions with items $M = [m]$ for sale to $n$ bidders, where each bidder $i$ has a private monotone valuation $v_i : 2^M \to R_+$. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication 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 $2^k$ communication between bidders with submodular valuations over $m$ items. Then for all $k = Ω(\log(m))$, MIRsubmod$(m,k) = Ω(\sqrt{m/(k\log(m/k))})$. When $k = Θ(\log(m))$, this improves the previous best lower bound for poly-comm. MIR mechanisms from $Ω(m^{1/3}/\log^{2/3}(m))$ to $Ω(\sqrt{m}/\log(m))$. We also have MIRsubmod$(m,k) = O(\sqrt{m/k})$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(\sqrt{m})$ to $O(\sqrt{m/\log(m)})$. Let also MIRgen$(m,k)$ denote the best approximation guarantee achievable by an MIR mechanism using $2^k$ 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 poly-comm. MIR mechanisms from $Ω(m/\log^2(m))$ to $Ω(m/\log(m))$. We also have MIRgen$(m,k) = O(m/k)$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(m/\sqrt{\log(m)})$ to $O(m/\log(m))$. |
| title | Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2404.00831 |