Ariel D. Procaccia, Aviv Zohar, Yoni Peleg, Jeffrey S. Rosenschein
Binary voting trees provide a succinct representation for a large and prominent class of voting rules. In this paper, we investigate the PAC-learnability of this class of rules. We show that, while in general a learning algorithm would require an exponential number of samples, if the number of leaves is polynomial in the size of the set of alternatives then a polynomial training set suffices. We apply these results in an emerging theory: automated design of voting rules by learning.
Subjects: 7.1 Multi-Agent Systems; 12. Machine Learning and Discovery
Submitted: Apr 22, 2007