Aaron Roth 

Department of Computer Information Science

"Mechanism Design in Large Games: Incentives and Privacy"

 

Abstract

We consider -large games-, which, like commuter traffic or stock investing, are strategic interactions among many players, each of whom has only a small affect on the welfare of others. One might like to design mechanisms in such games to suggest equilibrium play to the participants, but there are two potential concerns. The first concerns privacy: the computation of an equilibrium may reveal sensitive information about the utility function of one of the agents (i.e. his destination for that days drive, or his stock portfolio). The second concerns incentives: it may be beneficial for one of the agents to misreport his utility function to cause the mechanism to select a preferred, purported "equilibrium" of the reported game. We show how differential privacy can be brought to bear to solve both of these problems: we give a privacy preserving mechanism for computing the equilibria of a large game, which in turn implies an approximately truthful equilibrium selection mechanism.

 

This is joint work with Michael Kearns, Mallesh Pai, and Jon Ullman.

 

 

Refreshments will be served on the

2nd Floor Mezzanine Level

outside Wu & Chen

immediately following the talk.

____________________________________________________________________________