Jérôme Lang, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh
Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i.e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.
Subjects: 7.1 Multi-Agent Systems; 11. Knowledge Representation
Submitted: Oct 16, 2006