Arrow Research search

Author name cluster

Yoni Peleg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

AIJ Journal 2009 Journal Article

The learnability of voting rules

  • Ariel D. Procaccia
  • Aviv Zohar
  • Yoni Peleg
  • Jeffrey S. Rosenschein

Scoring rules and voting trees are two broad and concisely-representable classes of voting rules; scoring rules award points to alternatives according to their position in the preferences of the voters, while voting trees are iterative procedures that select an alternative based on pairwise comparisons. In this paper, we investigate the PAC-learnability of these classes of rules. We demonstrate that the class of scoring rules, as functions from preferences into alternatives, is efficiently learnable in the PAC model. With respect to voting trees, while in general a learning algorithm would require an exponential number of samples, we show that 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.

Details DOI

AAAI Conference 2007 Conference Paper

Learning Voting Trees

  • Ariel D. Procaccia
  • Yoni Peleg

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.

PDF Details