Decentralized voting with unconditional privacy

The aggregation of conflicting preferences is a key issue in multiagent systems. Due to its universality, voting has a central role among preference aggregation mechanisms. Voting among a set of alternatives can be used for such diverse tasks as choosing a joint plan in a multiagent system, determining a leader in a group of humans or agents, or voting among different resource or task allocations. Maintaining privacy of individuals' votes is crucial in order to guarantee freedom of choice (e.g., lack of vote coercing and reputation effects), and not facilitate strategic voting. We investigate whether unconditional full privacy can be achieved in voting, 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 (such as the hardness of factoring). In particular, we study the existence of distributed protocols that allow voters to jointly determine the outcome of an election without revealing any information but the election outcome. We show the impossibility of reaching unconditional full privacy for a variety of the most common voting schemes ranging from simple veto voting to the single transferable vote scheme. On the positive side, we propose several distributed protocols that privately compute the outcome of common voting schemes while only revealing a limited amount of information.