@booklet {kalai-laroc2001,
	title = {Learnability and Rationality of Choice},
	howpublished = {Discussion Papers},
	year = {2001},
	month = {8},
	publisher = {Journal of Economic Theory 113 (2003), 104-117},
	abstract = {The purpose of this paper is to examine the extent to which the concepts of individual and collective choice unsed in economic theory desribe "predictable" or "learnable" behavior. Given a set X of N alternatives, a choice function c is a mapping which assigns to nonempty subsets S of X an element c(S) of S. A rational choice function is one for which there is a linear ordering on the alternatives such that c(S) is the maximal element of S according to that ordering. Using the basic concept of PAC-learnability from statistical learning theory we define a class of choice functions on a ground set of N elements as learnable if it is possible to predict, with small amount of error, the chosen element from a set A after viewing a "few examples." Here, "few" means a polynomial number in N. Learnability is quite a strict condition on a class of choice functions. The main point we discuss in this regard are: The class of rational choice function can be learned quickly and efficiently. Various natural classes of choice functions, which represent indidivual choices and strategic choices of several interacting agents, are learnable. The class of rational choice functions has superior learnability properties in comparison to other classes. We make the conjecture that classes of choice functions that represent a genuine aggregation of individual choices in a large society are never learnable. We also ask to what extent learnability can replace or reinforce the rationality hypothesis in some economic situations.},
	url = {/files/db261.pdf},
	author = {Gil Kalai}
}
