#   On the Hardness of Dominant Strategy Mechanism Design 

 



####  calendar\_today Date and Time 

 **November 18, 2022** 

 01:00PM - 02:30PM EST 

####  pin\_drop Location 

 **SEC 1.413, & streamed via Zoom at: https://harvard.zoom.us/j/95184948637?pwd=bXBIc2U5MEZ0QmRUb01WQ0o0SXRCdz09**  



 

 



 

 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](https://urldefense.proofpoint.com/v2/url?u=https-3A__harvard.zoom.us_j_95184948637-3Fpwd-3DbXBIc2U5MEZ0QmRUb01WQ0o0SXRCdz09&d=DwMFaQ&c=WO-RGvefibhHBZq3fL85hQ&r=ZOP6tLIqLOHbdgCvrXjUlPta0tw7K_-ivqiItQhh6LQ&m=uemT-QaXqD-uZoJfnEDBB7fwnG8degFjLcw_feqXyNQZG71xSOqe-0AecMessqsq&s=E2-8kK_ehQrtwK7rLiKTj82Ok3C235FTyCn5lVBc7SU&e=)

 Also, next week is Thanksgiving, so there will be no EconCS seminar.



 

 



 

 See also:- [ Fall 2022 Econ CS Seminars ](/taxonomycalendarseminar/fall-2022)
 
 

 Share on:- [     Facebook ](#)
- [     Twitter ](#)
- [     Linkedin ](#)
 


 Save: [ Add to calendar calendar\_today ](https://econcs.seas.harvard.edu/node/1657421/event-feed.ics)  Copy link link