Learning Voting Trees

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.

Authors

• Ariel D. Procaccia Harvard University
• Yoni Peleg Jeffrey S. Rosenschein

Keywords

No keywords are indexed for this paper.