PIMS-UVic Distinguished Lecture: Sampath Kannan

Mechanism design is the problem of computing an optimal allocation of resources under criteria such as social welfare or revenue. The problem is more challenging than algorithm design because the inputs have to be elicited from selfish agents who may be able to derive an advantage by lying. A standard approach to overcome this challenge is to design incentive-compatible mechanisms where truth-telling is a dominant strategy or at least a Nash equilibrium. In this work we are concerned with another reason that strategic agents may lie - to protect the privacy of their data. This is a relatively new concern in the field of mechanism design. What is needed are mechanisms that are incentive-compatible and protect the privacy of data. We show that if the goal is social welfare then this is possible - nearly optimal social welfare can be achieved in general while protecting the privacy of the data. One the negative side, the exponential mechanism is not always computationally efficient. Efficiency has to be proved on a problem-by-problem basis.

In the last part of the talk we briefly describe how even when privacy is not a goal in itself, it can be used as a tool to design (nearly) incentive- compatible mechanisms where none were known to exist. We also show an example where we need to greatly relax the notion of privacy in order to have a realizable mechanism at all.

This is joint work with Zhiyi Huang. The last part is joint work with Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Steven Wu.