Learning the decisions of small committees
AbstractA 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by The Center for the Study of Rationality, Hebrew University, Jerusalem in its series Discussion Paper Series with number dp332.
Length: 24 pages
Date of creation: Aug 2003
Date of revision:
This paper has been announced in the following NEP Reports:
- NEP-ALL-2004-08-02 (All new papers)
- NEP-CBE-2003-09-08 (Cognitive & Behavioural Economics)
- NEP-DCM-2004-08-02 (Discrete Choice Models)
- NEP-GTH-2003-09-08 (Game Theory)
- NEP-POL-2003-09-08 (Positive Political Economics)
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.
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.