  A mediator is a mechanism that can only suggest actions to players, as a
function of all agents' reported types, in a given game of incomplete
information. We study what is achievable by two kinds of mediators, "strong"
and "weak." Players can choose to opt-out of using a strong mediator but cannot
misrepresent their type if they opt-in. Such a mediator is "strong" because we
can view it as having the ability to verify player types. Weak mediators lack
this ability--- players are free to misrepresent their type to a weak mediator.
We show a striking result---in a prior-free setting, assuming only that the
game is large and players have private types, strong mediators can implement
approximate equilibria of the complete-information game. If the game is a
congestion game, then the same result holds using only weak mediators. Our
result follows from a novel application of differential privacy, in particular,
a variant we propose called joint differential privacy.
