Date:
Location:
Shiri Ron (Weizmann Institute) will be speaking in-person:
On the Hardness of Dominant Strategy Mechanism Design
Abstract:
We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in an ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size.
We then study the approximation ratios achievable by dominant strategy mechanisms. For combinatorial auctions with general valuations, we show that no dominant-strategy mechanism achieves an approximation ratio of m^{1−\eps}, where m is the number of items. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones.
Joint work with Shahar Dobzinski and Jan Vondrak.
Here is the Zoom link again for those who are not able to make it in-person:
https://harvard.zoom.us/j/95184948637?pwd=bXBIc2U5MEZ0QmRUb01WQ0o0SXRCdz09
Also, next week is Thanksgiving, so there will be no EconCS seminar.