Algorithmic Mechanisms for Privacy, Truthfulness and Social Welfare

Speaker: Sampath Kannan, University of Pennsylvania

Abstract:

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.

Bio:

Sampath Kannan is the Henry Salvatori Professor and Chair of the Department of Computer and Information Science at the University of Pennsylvania. He obtained his undergraduate degree from the Indian Institute of Technology, Bombay, his Masters from Princeton University, and his Ph.D. from the University of California, Berkeley in 1989. His research interests are in the areas of Program Reliability, Streaming Computation, Computational Biology, and Algorithmic Game Theory. He is the author of over 150 papers, a few of which have been selected as best papers in the conferences in which they appeared.

Sampath Kannan served as Associate Dean for Academics in the School of Engineering and Applied Science at Penn between 2006 and 2008 and as Division Director for the Computing and Communication Foundations Division at NSF from 2008 to 2010. He  served as Associate Director for Theoretical Computer Science at the Simons Foundation from 2010 to 2013. He is a Fellow of the ACM and the recipient of the ACM SIGACT Distinguished Service Award. He is also the recipient of the Ford Motor Company Best Advisor award at Penn. He currently serves on the advisory board of DIMACS and on the committee to select the winner of the ACM-Infosys Award.