We address the problem of designing communication protocols for voting rules when the set of candidates can evolve via the addition of new candidates. We show that the necessary amount of communication that must be transmitted between the voters and the central authority depends on the amount of space devoted to the storage of the votes over the initial set of candidates. This calls for a bicriteria evaluation of protocols. We consider a few usual voting rules, and three types of storage functions:  full storage , where the full votes on the initial set of voters are stored;  null storage , where nothing is stored; and  anonymous storage , which lies in-between. For some of these pairs (voting rule, type of storage) we design protocols and show that they are asymptotically optimal by determining the communication complexity of the rule under the storage function considered.
['Yann Chevaleyre', 'Jérôme Lang', 'Nicolas Maudet', 'Jérôme Monnot']
Compilation and communication protocols for voting rules with a dynamic set of candidates