Last class, we proved that to accomplish this task, it would be sufficient to design an algorithm that:
- Satisfied (joint) differential privacy, and...
- Computed an (asymptotic) Nash equilibrium of the complete information game induced by reported types.
We also took a brief detour into private algorithmic techniques, and learned how to privately maintain a count on a stream of numbers.
This class, we partially implement this agenda. We define large games and congestion games, and give an algorithm for privately computing Nash equilibrium in large congestion games, which uses our newly learned ability to count. We conclude that in such games, with the help of a weak mediator, we can enjoy the nice properties of the pure strategy Nash equilibria of these games in the complete information setting, even in incomplete information settings when player types can be arbitrary (i.e. not necessarily drawn from any prior distribution).
There remains one more lecture in this series -- we will show that if we strengthen the power of our weak mediators somewhat, by giving them the ability to verify reported player types, then we can extend these results to arbitrary large games (i.e. not necessarily congestion games) by privately computing correlated equilibria.