Compilation and communication protocols for voting rules with a dynamic set of candidates
Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Monnot, Jérôme (2011), Compilation and communication protocols for voting rules with a dynamic set of candidates, in Apt, Krzysztof R., TARK 2011, ACM, p. 270
TypeCommunication / Conférence
Conference countryUNITED STATES
Book titleTARK 2011
Book authorApt, Krzysztof R.
MetadataShow full item record
Abstract (EN)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.
Subjects / Keywordscommunication protocols; voting; storage models; Multiagent systems
Showing items related by title and author.
Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Monnot, Jérôme; Xia, Lirong (2012) Article accepté pour publication ou publié