Top

Social Choice and Welfare

Published in:

21-12-2017 | Original Paper

Privacy in implementation

Author: Ronen Gradwohl

Published in: Social Choice and Welfare | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In most implementation frameworks, agents care only about the outcome and not at all about the way in which it was obtained. Additionally, typical mechanisms for full implementation involve the complete revelation of all private information. In this paper I consider the problem of full implementation with agents who may prefer to protect their privacy. I show that privacy-protecting implementation, while typically impossible with normal-form mechanisms, is achievable with extensive-form mechanisms.

previous article On the redistributive power of pensions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

With full implementation, the desideratum is a mechanism in which all equilibria lead to socially optimal outcomes. For various surveys of this vast literature, see Jackson (2001), Maskin and Sjöström (2002), or Palfrey (2002).

In general, implementation theory solves two parallel problems: information aggregation and coordination amongst agents. Complete information simplifies by narrowing the focus to coordination. See, e.g., Gradwohl (2017) for a study of the effect of privacy concerns on information aggregation.

See, in particular, Maskin (1999) and Moore and Repullo (1988).

Section 6.3 discusses this extension.

For most of the results in this paper weaker assumptions suffice. One example of such an assumption is to associate intrinsic preferences with information-sensitive preferences when the set of possible types is \(S=\{R\}\).

Vartiainen (2007) gives conditions for subgame perfect implementation that are both necessary and sufficient.

I focus on implementations of SCFs and not SCCs for simplicity. In Sect. 6.2 I extend this discussion to SCCs.

This is similar in spirit to Dutta and Sen (2012), in which agents have a lexicographic preference for honesty.

It is well known that the use of certain dependencies can facilitate the design of mechanisms that would otherwise not be possible (e.g. Cremer and McLean 1988).

In particular, under this weakening the impossibility result may hold also in economic environments.

Abreu D, Sen A (1990) Subgame perfect implementation: a necessary and almost sufficient condition. J Econ theory 50(2):285–299CrossRef

Abreu D, Sen A (1991) Virtual implementation in nash equilibrium. Econometrica 59(4):997–1021CrossRef

Acquisti A, Taylor C, Wagman L (2016) The economics of privacy. J Econ Lit 54(2):442–492CrossRef

Aumann RJ (1976) Agreeing to disagree. Ann Stat 4(6):1236–1239CrossRef

Bernheim B (1994) A theory of conformity. J Political Econ 102(5):841–877CrossRef

Chen J, Micali S (2015) Mechanism design with possibilistic beliefs. J Econ Theory 156:77–102CrossRef

Chen Y, Chong S, Kash IA, Moran T, Vadhan S (2016) Truthful mechanisms for agents that value privacy. ACM Trans Econ Comput 4(3):13

Cremer J, McLean RP (1988) Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica 56(6):1247–1257CrossRef

Dinur I, Nissim K (2003) Revealing information while preserving privacy. In: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, pp 202–210

Dutta B, Sen A (2012) Nash implementation with partially honest individuals. Games Econ Behav 74(1):154–169CrossRef

Geanakoplos J, Pearce D, Stacchetti E (1989) Psychological games and sequential rationality. Games Econ Behav 1(1):60–79CrossRef

Ghosh A, Roth A (2011) Selling privacy at auction. In: Proceedings of the 12th ACM conference on Electronic commerce. ACM, pp 199–208

Glazer A, Konrad K (1996) A signaling explanation for charity. Am Econ Rev 86(4):1019–1028

Glazer J, Rubinstein A (1998) Motives and implementation: on the design of mechanisms to elicit opinions. J Econ Theory 79(2):157–173CrossRef

Gradwohl R (2017) Voting in the limelight. Econ Theory (forthcoming)

Gradwohl R, Smorodinsky R (2017) Perception games and privacy. Games Econ Behav 104:293–308CrossRef

Ireland N (1994) On limiting the market for status signals. J Public Econ 53(1):91–110CrossRef

Jackson M (2001) A crash course in implementation theory. Soc Choice Welf 18(4):655–708CrossRef

Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66(1):23–38CrossRef

Maskin E, Sjöström T (2002) Implementation theory. Handb Soc Choice Welf 1:237–288CrossRef

Matsushima H (2008a) Behavioral aspects of implementation theory. Econ Lett 100(1):161–164CrossRef

Matsushima H (2008b) Role of honesty in full implementation. J Econ Theory 139(1):353–359CrossRef

McSherry F, Talwar K (2007) Mechanism design via differential privacy. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science. IEEE Computer Society, pp 94–103

Miltersen P, Nielsen J, Triandopoulos N (2009) Privacy-enhancing auctions using rational cryptography. Adv Cryptol CRYPTO 2009:541–558

Moore J, Repullo R (1988) Subgame perfect implementation. Econometrica 56(5):1191–1220CrossRef

Muller E, Satterthwaite M (1977) The equivalence of strong positive association and strategy-proofness. J Econ Theory 14(2):412–418CrossRef

Naor M, Pinkas B, Sumner R (1999) Privacy preserving auctions and mechanism design. In: Proceedings of the 1st ACM conference on electronic commerce. ACM, pp 129–139

Nissim K, Orlandi C, Smorodinsky R (2012) Privacy-aware mechanism design. In: Proceedings of the 13th ACM conference on electronic commerce. ACM, pp 774–789

Palfrey T (2002) Implementation theory. Handb Game Theory Econ Appl 3:2271–2326

Postlewaite A, Wettstein D (1989) Feasible and continuous implementation. Rev Econ Stud 56(4):603–611CrossRef

Saijo T (1987) On constant maskin monotonic social choice functions. J Econ Theory 42(2):382–386CrossRef

Serrano R (2004) The theory of implementation of social choice rules. SIAM Rev 46(3):377–414CrossRef

Vartiainen H (2007) Subgame perfect implementation: a full characterization. J Econ Theory 133(1):111–126CrossRef

Vohra R (2012) Dynamic mechanism design. Surv Oper Res Manag Sci 17(1):60–68

Xiao D (2013) Is privacy compatible with truthfulness? In: Proceedings of the 4th conference on innovations in theoretical computer science, pp 67–86

Title: Privacy in implementation
Author: Ronen Gradwohl
Publication date: 21-12-2017
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 3/2018
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-017-1095-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2018

Inequality and inter-group conflicts: experimental evidence

Flexible level-1 consensus ensuring stable social choice: analysis and algorithms

Power at general equilibrium

Can religion explain cross-country differences in inequality? A global perspective

On the redistributive power of pensions