Conférence de Sampath Kannan organisée par le département d'informatique.
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.
Sampath Kannan est professeur au département d'informatique et sciences de l'information de l'université de Pennsylvanie.Cliquer ICI pour fermer
Dernière mise à jour : 19/12/2013