# Robust Mediators in Large Games

arXiv: https://arxiv.org/abs/1512.02698 · HTML: https://mlsanity.com/paper/1512.02698/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2015.

## Built on by (most cited first, 7 of 7)

- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [Mediated Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.08419/) (2023)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [On Differentially Private Online Predictions](https://mlsanity.com/paper/2302.14099/) (2023)
- [Towards Optimal Differentially Private Regret Bounds in Linear MDPs](https://mlsanity.com/paper/2504.09339/) (2025)
- [Learning Recommender Mechanisms for Bayesian Stochastic Games](https://mlsanity.com/paper/2505.22979/) (2025)

## Abstract (arXiv)

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.