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 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 an approximate correlated equilibrium of the complete-information game: i.e., there exists a way to select an approximate correlated equilibrium of the complete information game for each realization of types such that each player is approximately incentivized to opt-in and follow the mediator's suggested action. If the game is a congestion game, then the same result holds using only weak mediators (i.e. each player is approximately incentivized to opt-in, report her type truthfully and then follow the mediator's suggested action). Our result follows from a novel application of differential privacy, in particular, a variant we propose called joint differential privacy.