The Hardness of Dominant Strategy Mechanism Design, Revisited

概要

We study the communication complexity of \emph{dominant-strategy incentive-compatible} (DSIC) mechanisms for combinatorial auctions. For $γ\in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, γ)$, $\mathsf{DSIC_{XOS}}(m, γ)$, and $\mathsf{DSIC_{GS}}(m, γ)$ denote the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers, DSIC mechanism using at most $2^γ$ 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, γ) = Ω(m/γ)$, $\mathsf{DSIC_{XOS}}(m, γ) = Ω((m/γ)^{1/5})$, and $\mathsf{DSIC_{GS}}(m, γ) = Ω((m/γ)^{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, γ) = Θ(m/γ)$ due to the deterministic DSIC $O(m/γ)$-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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
The Hardness of Dominant Strategy Mechanism Design, Revisited

# 概要
We study the communication complexity of \emph{dominant-strategy incentive-compatible} (DSIC) mechanisms for combinatorial auctions. For $γ\in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, γ)$,…

# 原典
https://arxiv.org/abs/2610.06773

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。