Metraipolis › archive › dc_92b2ef4d1898
The Hardness of Dominant Strategy Mechanism Design, Revisited — arXiv:2610.06773
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.06773
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:29:28.758Z
- SHA-256 of the archived text
cd73255e9881a57d352546a9012dc2c6cfb5da3decadebe371691446692dda01- Stable URL of this page
https://metraipolis.com/documento/dc_92b2ef4d1898
How to cite
The Hardness of Dominant Strategy Mechanism Design, Revisited — arXiv:2610.06773 — arXiv, https://arxiv.org/abs/2610.06773 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_92b2ef4d1898 (Metraipolis archive dc_92b2ef4d1898, sha256 cd73255e9881a57d352546a9012dc2c6cfb5da3decadebe371691446692dda01)
BibTeX
@misc{dc92b2ef4d1898,
title = {The Hardness of Dominant Strategy Mechanism Design, Revisited — arXiv:2610.06773},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.06773},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_92b2ef4d1898; sha256 cd73255e9881a57d352546a9012dc2c6cfb5da3decadebe371691446692dda01},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.06773. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the communication complexity of \emph{dominant-strategy incentive-compatible} (DSIC) mechanisms for combinatorial auctions. For $\gamma \in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, \gamma)$, $\mathsf{DSIC_{XOS}}(m, \gamma)$, and $\mathsf{DSIC_{GS}}(m, \gamma)$ denote the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers, DSIC mechanism using at most $2^\gamma$ communication over $m$ items, for general monotone, XOS, and gross substitutes (GS) valuations, respectively. We give a unified proof that shows $\mathsf{DSIC_{GEN}}(m, \gamma) = \Omega(m/\gamma)$, $\mathsf{DSIC_{XOS}}(m, \gamma) = \Omega((m/\gamma)^{1/5})$, and $\mathsf{DSIC_{GS}}(m, \gamma) = \Omega((m/\gamma)^{1/7})$. The GS lower bound answers an open question of~\cite{DobzinskiRV22}: although poly-communication welfare maximization for GS valuations admits a poly-communication deterministic truthful mechanism via VCG, no good approximation is possible in poly-communication for deterministic DSIC mechanisms. Additionally, the general lower bound establishes that $\mathsf{DSIC_{GEN}}(m, \gamma) = \Theta(m/\gamma)$ due to the deterministic DSIC $O(m/\gamma)$-approximation of~\cite{QiuW24}. We also obtain several results in the two-bidder setting. We show that attaining a $1.0001$-approximation for two weighted matroid-rank valuations (a subclass of GS) with a universally DSIC mechanism requires exponential communication. On the other hand, we give a poly-communication $(1+\sqrt{5})/2 \approx 1.618$-approximation for two submodular bidders using a universally DSIC mechanism. Prior to this work, it was not known whether even a poly-communication universally truthful mechanism could beat a $2$-approximation for two submodular valuations, nor whether a poly-communication universally DSIC mechanism could beat a $2$-approximation for two weighted matroid rank valuations.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.06773 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:25:35.324Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).