Learning the decisions of small committees
A committee is a collection of members, where every member has a linear ordering on the alternatives of a finite ground set X. The committee chooses between pairs of alternatives drawn from X by a simple majority vote. The committee’s choices induce a preference relation on X. In this paper, we study the possibility of learning preference relations of small committees from examples. We prove that it is impossible to precisely learn the preference relation of a committee before seeing all its choices, even if a teacher guides the learner through the learning process. We also prove that a learner can approximately learn the preference relation of a committee from a relatively few random examples.
|Date of creation:||Aug 2003|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.ratio.huji.ac.il/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Rubinstein, Ariel, 1996. "Why Are Certain Properties of Binary Relations Relatively More Common in Natural Language?," Econometrica, Econometric Society, vol. 64(2), pages 343-55, March.
- Kalai, Gil, 2003. "Learnability and rationality of choice," Journal of Economic Theory, Elsevier, vol. 113(1), pages 104-117, November.
When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp332. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama)
If references are entirely missing, you can add them using this form.