Universally Utility-Maximizing Privacy Mechanisms
| dc.creator | Ghosh, Arpita | |
| dc.creator | Roughgarden, Tim | |
| dc.creator | Sundararajan, Mukund | |
| dc.date | 2008-11-18 | |
| dc.date | 2009-03-20 | |
| dc.date.accessioned | 2026-07-07T12:54:11Z | |
| dc.date.available | 2026-07-07T12:54:11Z | |
| dc.description | A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Privacy can be rigorously quantified using the framework of {\em differential privacy}, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a {\em geometric mechanism} $M^*$ -- a discrete variant of the simple and well-studied Laplace mechanism -- that is {\em simultaneously expected loss-minimizing} for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: {\em every} potential user $u$, no matter what its side information and preferences, derives as much utility from $M^*$ as from interacting with a differentially private mechanism $M_u$ that is optimally tailored to $u$. | |
| dc.description | rewritten for clarity, typos corrected | |
| dc.identifier | https://arxiv.org/abs/0811.2841 | |
| dc.identifier | http://arxiv.org/abs/0811.2841 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/223838 | |
| dc.subject | Databases | |
| dc.subject | Computer Science and Game Theory | |
| dc.title | Universally Utility-Maximizing Privacy Mechanisms | |
| dc.type | text |