Universally optimal privacy mechanisms for minimax agents
Proc. ACM SIGMOD, ACM, Indianapolis, Indiana (2010), pp. 135-146
Mangesh Gupte, Mukund Sundararajan
There are two standard models of utility considered in decision theory: Bayesian and minimax. Ghosh et. al. show that a certain "geometric mechanism" gives optimal utility to all Bayesian information consumers. In this paper, we prove a similar result for minimax information consumers. Our result also works for a wider class of information consumers which includes Bayesian information consumers and subsumes the result from .
We model information consumers as minimax (risk-averse) agents, each endowed with a loss-function which models their tolerance to inaccuracies and each possessing some side-information about the query. Further, information consumers are rational in the sense that they actively combine information from the mechanism with their side-information in a way that minimizes their loss. Under this assumption of rational behavior, we show that for every fixed count query, the geometric mechanism is universally optimal for all minimax information consumers.
Additionally, our solution makes it possible to release query results, when information consumers are at different levels of privacy, in a collusion-resistant manner.