Learning Voting Trees

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.