The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Mechanism Design via Differential Privacy
Abstract
We study the role that privacy-preserving algorithms, which prevent the leakage of specific information about participants, can play in the design of mechanisms for strategic agents, which must encourage players to honestly report information. Specifically, we show that the recent notion of differential privacv, in addition to its own intrinsic virtue, can ensure that participants have limited effect on the outcome of the mechanism, and as a consequence have limited incentive to lie. More precisely, mechanisms with differential privacy are approximate dominant strategy under arbitrary player utility functions, are automatically resilient to coalitions, and easily allow repeatability. We study several special cases of the unlimited supply auction problem, providing new results for digital goods auctions, attribute auctions, and auctions with arbitrary structural constraints on the prices. As an important prelude to developing a privacy-preserving auction mechanism, we introduce and study a generalization of previous privacy work that accommodates the high sensitivity of the auction setting, where a single participant may dramatically alter the optimal fixed price, and a slight change in the offered price may take the revenue from optimal to zero.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Power and Centrality: A Family of Measures
Bonacich, P. (1987) · American Journal of Sociology · doi:10.1086/228631 · Cited by 5,165
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
(2008) · Choice Reviews Online · doi:10.5860/choice.45-5628 · Cited by 2,725
New spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,288
Alon, N. (1986) · Combinatorica · doi:10.1007/bf02579166 · Cited by 1,137
Tutte, W. T. (1963) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s3-13.1.743 · Cited by 1,114
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Fiedler, M. (1975) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1975.101357 · Cited by 1,042
Security-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 969
A Lower Bound for the Smallest Eigenvalue of the Laplacian
Cheeger, J. (2015) · Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31) · doi:10.1515/9781400869312-013 · Cited by 961
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 931
Osserman, R. (1978) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1978-14553-4 · Cited by 864
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609407 · Cited by 849
On the density of families of sets
Sauer, N. (1972) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(72)90019-2 · Cited by 844
λ1, Isoperimetric inequalities for graphs, and superconcentrators
Alon, N., & Milman, V. D. (1985) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(85)90092-9 · Cited by 839
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
Practical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797
Self-citationApproximate counting, uniform generation and rapidly mixing Markov chains
Sinclair, A., & Jerrum, M. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90067-9 · Cited by 735
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 660
An r-Dimensional Quadratic Placement Algorithm
Hall, K. M. (1970) · Management Science · doi:10.1287/mnsc.17.3.219 · Cited by 522
Algorithmic mechanism design (extended abstract)
Nisan, N., & Ronen, A. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301287 · Cited by 476
Spielman, D. A., & Teng, S. (2014) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090771430 · Cited by 462
Spectral partitioning works: planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (1996) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548468 · Cited by 393
Isoperimetric numbers of graphs
Mohar, B. (1989) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(89)90029-4 · Cited by 331
Truthful approximation mechanisms for restricted combinatorial auctions
Mu’alem, A., & Nisan, N. (2008) · Games and Economic Behavior · doi:10.1016/j.geb.2007.12.009 · Cited by 317
The value of knowing a demand curve: bounds on regret for online posted-price auctions
Kleinberg, R., & Leighton, T. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238232 · Cited by 290
Competitive auctions and digital goods
Goldberg, A. V., Hartline, J. D., & Wright, A. (2001) · doi:10.5555/365411.365768 · Cited by 257
Explicit Concentrators from Generalized N-Gons
Tanner, R. M. (1984) · SIAM Journal on Algebraic Discrete Methods · doi:10.1137/0605030 · Cited by 247
Towards a characterization of truthful combinatorial auctions
Lavi, R., Mu’alem, A., & Nisan, N. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238230 · Cited by 236
Spectral partitioning works: Planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.07.020 · Cited by 209
Conductance and convergence of Markov chains-a combinatorial treatment of expanders
Mihail, M. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63529 · Cited by 175
Isomorphism of graphs with bounded eigenvalue multiplicity
Babai, L., Grigoryev, D. Y., & Mount, D. M. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 · doi:10.1145/800070.802206 · Cited by 160
Online learning in online auctions
Blum, A. L., Kumar, V. S., Atri Rudra, B., & Wu, F. T. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.012 · Cited by 159
Archer, A. F., & Eva Tardos, D. (n.d.) · Cited by 150
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
Archer, A. F., Papadimitriou, C. H., Talwar, K., & Eva Tardos, D. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129086 · Cited by 146
Self-citationMechanism Design via Machine Learning
Balcan, M.-F., & Blum, A. L. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.50 · Cited by 129
Elkind, E., Sahai, A., & Steiglitz, K. (2004) · ePrints Soton (University of Southampton) · doi:10.5555/982792.982900 · Cited by 120
Incentive-compatible online auctions for digital goods
Bar-Yossef, Z., Hildrum, K. W., & Wu, F. T. (2002) · doi:10.5555/545381.545506 · Cited by 98
Collusion-Resistant Mechanisms for Single-Parameter Agents
Goldberg, A. V., & Hartline, J. D. (2004) · doi:10.5555/1070432.1070518 · Cited by 85
Manasse, M. S., McSherry, F., & Talwar, K. (2007) · Cited by 67
Self-citationSpectral techniques in graph algorithms
Alon, N. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054322 · Cited by 57
Goldberg, A. V., & Hartline, J. D. (2003) · doi:10.5555/644108.644145 · Cited by 56
Distributed algorithmic mechanism design: recent results and future directions
Feigenbaum, J., & Shenker, S. J. (2002) · doi:10.1145/570811.570812 · Cited by 37
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542
EEG Emotion Recognition Using Dynamical Graph Convolutional Neural Networks
Song, T., Zheng, W., Song, P., & Cui, Z. (2020) · IEEE Transactions on Affective Computing · doi:10.1109/taffc.2018.2817622 · Cited by 1,597
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
Metadata
- Authors
- McSherry, F., & Talwar, K.
- Venue
- 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
- Publisher
- IEEE
- Published
- 2007-10
- Pages
- 94-103
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2123820077
- Cited by
- 1,371
- References
- 46
- FWCI
- 13.44
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.