Universally Optimal Privacy Mechanisms for Minimax Agents

Summary: Proves the geometric mechanism is universally optimal for all minimax (risk-averse) information consumers for any fixed count query, generalizing prior Bayesian-only optimality to a broader consumer class. Also yields collusion-resistant multi-level privacy releases when agents rationally combine mechanism output with side information. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1513
Venue: PODS
Year: 2010
Pagerank: 5.3166398e-05
Overall Rank: 9,135 | 37.33%
DOI: 10.1145/1807085.1807105

Incoming Non-self Citations Over Time

Authors

1. Mangesh Gupte (Rutgers University)
2. Mukund Sundararajan (Google)

BibTeX Citation

@inproceedings{gupte_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Universally Optimal Privacy Mechanisms for Minimax Agents}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807105},
        doi = {10.1145/1807085.1807105},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gupte, Mangesh and Sundararajan, Mukund},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,701	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	5.7980998e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
4,732	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	6.5343833e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,809	Privacy in Data Systems	2003	PODS
2	10,335	A General Framework for Per-record Differential Privacy	2026	SIGMOD
3	3,974	Epistemic Privacy	2008	PODS
4	7,639	Budget Sharing for Multi-Analyst Differential Privacy	2021	VLDB
5	1,295	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB
6	9,486	Minimizing Minimality and Maximizing Utility: Analyzing Method-based attacks on Anonymized Data	2010	VLDB
7	6,701	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD
8	10,964	Balancing Privacy and Utility in Correlated Data: A Study of Bayesian Differential Privacy	2025	VLDB
9	4,407	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS
10	1,746	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB