Unconditional privacy in social choice

The aggregation of conflicting preferences is an important issue in human society and multiagent systems. Due to its universality, voting among a set of alternatives has a central role among preference aggregation mechanisms. We consider the most general case of voting in which the voters' rankings of alternatives are mapped to a collective ranking of alternatives by a so-called social welfare functional (SWF). Maintaining privacy of individuals' preferences is crucial in order to guarantee freedom of choice (e.g., lack of vote coercing and reputation effects), and to not facilitate strategic voting. We investigate whether unconditional full privacy can be achieved in preference aggregation, that is, privacy that relies neither on trusted third parties (or on a certain fraction of the voters being trusted), nor on computational intractability assumptions. More precisely, we study the existence of distributed protocols that allow voters to jointly determine the collective preference ranking without revealing further information. We prove that there exists no SWF that is non-dictatorial, Paretian, monotonic, and privately computable (any three of these properties can be achieved). Moreover, we show that replacing privacy with anonymity enables the joint computation of arbitrary symmetric SWFs.