Title: Approximately Optimal Mechanism Design via Differential Privacy
Speaker: Kobbi Nissim, Microsoft AI and Ben-Gurion University
Date: Wednesday, October 20, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We show a generic construction of mechanisms that allows for approximate optimal implementation in dominant strategies of social welfare functions, without utility transfer, given that the social welfare function has bounded sensitivity to agent types. We demonstrate the applicability of our construction with respect to pricing and facility location. The mechanisms we design are optimal up to an additive factor of the order of magnitude of the square root of the optimum.
The construction is by mixing between two mechanisms - with high probability we actuate a random mechanism that reduces players influence
on the choice of the social alternative, while choosing the optimal outcome with high probability.
With the complementary probability we actuate a mechanism that is sub-optimal yet provides strong incentives to disclose the personal information.