Mechanism design in large games: incentives and privacy

By Michael Kearns, Mallesh M. Pai, Aaron Roth, Jonathan Ullman. 2012

190 citations recorded by the source corpus.

We study the problem of implementing equilibria of complete information games in settings of incomplete information, and address this problem using "recommender mechanisms." A recommender mechanism is one that does not have the power to enforce outcomes or to force participation, rather it only has the power to suggestion outcomes on the basis of voluntary participation. We show that despite these restrictions, recommender mechanisms can implement equilibria of complete information games in settings of incomplete information under the condition that the game is large---i.e. that there are a large number of players, and any player's action affects any other's payoff by at most a small amount. Our result follows from a novel application of differential privacy. We show that any algorithm that computes a correlated equilibrium of a complete information game while satisfying a variant of differential privacy---which we call joint differential privacy---can be used as a recommender mechanism while satisfying our desired incentive properties. Our main technical result is an algorithm for computing a correlated equilibrium of a large game while satisfying joint differential privacy. Although our recommender mechanisms are designed to satisfy game-theoretic properties, our solution ends up satisfying a strong privacy property as well. No group of players can learn "much" about the type of any player outside the group from the recommendations of the mechanism, even if these players collude in an arbitrary way. As such, our algorithm is able to implement equilibria of complete information games, without revealing information about the realized types.

Subfields: Economics and Econometrics, Management Science and Operations Research, Safety Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Safety Research

Citations in the corpus

Differentially Private Distributed Constrained Optimization (2014, methodology): “[17], Rogers and Roth [23], and Hsu et al.”
The Economics of Privacy (2016, background): “12 Kearns et al. (2014) study the design of mechanisms that satisfy the computer science criterion of differential privacy (Dwork 2006)—put simply, the notion of being able to distinguish one agent (a consumer) from another in a dataset of consumer characteristics with only a low probability.”
The Algorithmic Foundations of Differential Privacy (2014, background): “Kearns Pai, Roth, and Ullman showed how differential privacy could be used to derive asymptotically truthful equilibrium selection mechanisms [54] by privately computing correlated equilibria in large games.”
Differentially Private Matrix Completion, Revisited (2017, methodology): “To alleviate this concern, we consider a relaxed but natural DP notion (for recommendation systems) called joint differential privacy (Kearns et al., 2014).”
Technical Privacy Metrics (2015, background): “a with few points of interest, we may need a larger radius compared to an urban area to achieve the same level of privacy [26]. 5.4.8 Joint Differential Privacy.The idea of joint differential privacy [77] is that an individual’s private data can be disclosed to the individual him/herself, but not to”