Learnability and rationality of choice

• 成果类型: Article
• 署名作者: Kalai, G
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/S0022-0531(03)00083-8
• 发表日期: 2003
• 页码: 104-117
• 关键词: choice; rationality; learnability; choice functions; testable implications

摘要

In this paper we study the learnability of the class of rationalizable choice functions using the basic concept of PAC-learnability from statistical learning theory. We prove that the class of rationalizable choice functions on N alternatives is learnable from O(N) examples and is optimal in terms of PAC-learnability among classes which are invariant under permutations of the elements. (C) 2003 Elsevier Science (USA). All rights reserved.