Itzhak Gilboa

Larry Samuelson

David Schmeidler

Daron Acemoglu

Dirk Bergemann

Eddie Dekel

Drew Fudernberg

Gabi Gayer

Offer Lieberman

George Mailath

David Schmeidler May

Dynamics of Inductive Inference in a Unified Framework 1

We present a model of inductive inference that includes, as special cases, Bayesian reasoning, case-based reasoning, and rulebased reasoning. This unified framework allows us to examine how the various modes of inductive inference can be combined and how their relative weights change endogenously. For example, we establish conditions under which an agent who does not know the structure of the data generating process will decrease, over the course of her reasoning, the weight of credence put on Bayesian vs. non-Bayesian reasoning. We illustrate circumstances under which probabilistic models are used until an unexpected outcome occurs, whereupon the agent resorts to more basic reasoning techniques, such as case-based and rule-based reasoning, until enough data are gathered to formulate a new probabilistic model.

Introduction

Economic theory typically assumes that agents reason about uncertainty in a Bayesian way: they formulate prior probabilities over a state space and update them in response to new information according to Bayes' rule. This model is powerful, but does not always reflect the way that people think about uncertainty. In particular, when completely unexpected outcomes occur, people question their probabilistic models, relying on alternative reasoning techniques until perhaps developing a new probabilistic model.

For example, the New York Stock Exchange was closed for five days following the September 11, 2001 terrorist attacks on the United States. On the following Sunday, September 16, a leading economist was asked to predict the behavior of the Dow Jones Industrial Average on Monday. He did not respond by reasoning that "I used to attach (the quite small) probability ε to such attacks, and now I need only update this probability, and then apply my usual model of the stock market." Instead, there was a sense that the probabilistic model he would have used under normal circumstances was inappropriate for the present situation, and that he had to start from basics in reasoning about the future. He responded by invoking analogies to past cases in which the United States had been surprised by attack, most notably Pearl Harbor. (As it turned out, his prediction was quite accurate.)

Similarly, following the collapse of Lehman Brothers in September 2008, the head of a major investment firm confronted clients anxious to sell their assets, even assets that had already lost 90% of their value. Again, the analyst did not apply Bayes' rule to a prior that had taken into account a possible failure of Lehman Brothers. Instead, he argued that something totally unexpected had happened, and that "obviously, the models do not work." The analyst convinced his clients to hold such assets, invoking the simple rule that "an asset that has lost 90% of its value cannot lose much more." (His clients were convinced, and subsequently appreciated the advice.)

In both examples, one could, post-hoc, construct a prior probability distribution that allows the experts' reasoning to follow from Bayesian updating. However, such a description would say very little about the actual reasoning process of the agents involved, and (more importantly) would not be of much help in predicting their reasoning in the future. Our interest in this paper is in modeling the agents' actual reasoning processes, in the hope of better understanding when these processes generate probabilistic beliefs, which beliefs are likely to be formed by the agents, and how the agent might form beliefs when driven away from familiar probabilistic models. To do so, we need a model that can simultaneously describe probabilistic and non-probabilistic reasoning, as well as the dynamics by which weights shift between modes of reasoning.

We take it for granted that when statistical analysis is possible, rational agents will perform such analysis correctly. In contrast, our interest is in the way economists model agents who face problems that do not naturally lend themselves to statistical analysis. Predicting financial crises, economic growth, the outcome of elections, or the eruptions of wars and revolutions, are examples where it is difficult to define iid random variables and, more generally, where the assumptions of statistical models do not seem to be good approximations.

To set the context for our model, consider an agent who each year is called upon to predict the price of oil over the subsequent year. To keep this illustrating example simple, suppose the agent need only predict whether the average price will be higher or lower than the previous year's price. We can imagine the agent working for a hedge fund that is interested in whether it should bet for or against an increasing price.

To support her decision, the agent's research staff regularly compiles a list of data potentially relevant to the price of oil, as well as data identifying past values of the relevant variables and past oil prices. For our example, let us assume that the data include just two variables: a measure of the change in the demand for oil and a measure of the change in the severity of conflict in the Middle East. Each is assumed to take two values, indicating whether there has been an increase or decrease. Each year the agent receives the current changes in demand and in conflict, examines the data from previous years, and then predicts whether the price will increase or decrease. How do and how should agents reason about such problems?

Our model captures three types of reasoning. [START_REF] Akaike | An approximation to the density function[END_REF] The most common in economic modeling is Bayesian. The agent first formulates the set of possible states of the world, where a state identifies the strength of demand, the measure of conflict, and the price of oil, in each year over the course of her horizon. The agent then formulates a prior probability distribution over this state space. This prior distribution will reflect models and theories of the market for oil that the agent finds helpful, her analysis of past data and past outcomes in this market, and any other prior information she has at her command. Once this prior has been formulated, the agent's predictions are a relatively straightforward matter of applying Bayes' rule, as new observations allow her to rule out some states and condition her probability distribution on the surviving states. An alternative mode of reasoning is case-based. The agent considers past observations and predicts the outcome that appeared more often in those past cases that are considered similar. For example, predicting that following the September 11 attacks, the DJIA would change in a similar way to its change following Pearl Harbor would be considered case-based reasoning. If all past observations are considered equally similar, the case-based prediction is simply the mode, that is, the outcome that is most frequent in the database. If the agent uses a similarity function that puts all its weight on the most recent outcome, her prediction will simply be that outcome. [START_REF] Alquist | What do we learn from the price of crude oil futures?[END_REF] If the agent views the current state of conflict in the Middle East as a repetition of affairs in 1991 or in 2003, the agent will predict that there will soon be a war and an increase in the price of oil.

Finally, rule-based reasoning calls for the agent to base her predictions on regularities that she believes characterize the market for oil. For example, the agent may adopt a rule that any increase in the level of demand leads to an increase in the price of oil. Based on this and her expectation that the Chinese economy will continue to grow, the agent might reasonably predict that the price is about to rise.

The boundaries between the three modes of reasoning are not always sharp. Our focus is on the Bayesian approach. By "Bayesian reasoning" we refer to the common approach in economic theory, according to which all reasoning is Bayesian. Any source of uncertainty is modeled in the state space, and all reasoning about uncertainty takes the form of updating a prior probability via Bayes' rule. This paper presents (in Sections 2-3) a framework that unifies these three modes of reasoning (and potentially others), allowing us to view them as special cases of a general learning process. The agent attaches weights to conjectures. Each conjecture is a set of states of the world, capturing a way of thinking about how outcomes in the world will develop. The associated weights capture the relative influence that the agent attaches to the various conjectures. To generate a prediction, the agent sums the weight of all nontrivial conjectures consistent with each possible outcome, and then ranks outcomes according to their associated total weights. In the special case where each conjecture consists of a single state of the world, our framework is the standard Bayesian model, and the learning algorithm is equivalent to Bayesian updating. Employing other conjectures, which include more than a single state each, we can capture other modes of reasoning, as illustrated by simple examples of case-based and of rule-based reasoning.

Our model could be used to address either positive or normative questions. In this paper we focus on positive ones, describing how the reasoning process of an agent evolves as observations are gathered. Within the class of such questions, our model could be used to capture a variety of psychological biases and errors, but the focus of this paper is on the reasoning of an agent who makes no obvious errors in her reasoning. Such an agent may well be surprised by circumstances that she has deemed unlikely, that is, by "black swans," but will never be surprised by a careful analysis of her own reasoning. The optimality of this reasoning process is a normative question, which we do not address here.

Our main results concern the dynamics of the weight put on Bayesian vs. non-Bayesian reasoning. In Section 4.1 we suggest conditions under which Bayesian reasoning will give way to other modes of reasoning, and alternative conditions under which the opposite conclusion holds. Section 4.3 briefly discusses how probabilistic reasoning may emerge periodically, with other modes of reasoning used between the regimes of different probabilistic models. Section 5 concludes.

The Framework

The Environment

At each period t ∈ {0, 1, . . .} there is a characteristic x t ∈ X and an outcome y t ∈ Y . The sets X and Y are assumed to be finite and non-empty, with Y containing at least two possible outcomes. [START_REF] Bayes | An essay towards solving a problem in the doctrine of chances[END_REF] In predicting the price of oil, the characteristic x t might identify the type of political regime and the state of political unrest in various oil-producing countries, describe the extent of armed conflict in the Middle East, indicate whether new nuclear power plants have come on line or existing ones been disabled by accidents, describe the economic conditions of the major oil importers, summarize climate conditions, and so on. In our simplified example, Y has only two elements, {0, 1}, and each x = (x 1 , x 2 ) ∈ X has two components, each also taking values in {0, 1}, with a 1 in each case indicating an increase in the relevant variable.

We make no assumptions about independence or conditional independence of the variables across periods. In fact, for most of our analysis we do not assume any probability on the state space, so that independence of the variables cannot even be defined. The model can be augmented by assumptions about the underlying probability measure that drives the process, allowing one to state results about learning the "true" state of the world. While some of our examples below are of this nature, the general framework is silent on the actual data generating process.

A state of the world ω identifies the characteristic and outcome that appear in each period t, i.e., ω : {0, 1, ...} → X × Y . We let (ω X (t), ω Y (t)) denote the element of X × Y appearing in period t given state ω, and let

Ω = (X × Y ) ∞
denote the set of states of the world. In our example, a state identifies the sign of changes in the strength of demand, the level of conflict, and the price of oil in each period.

A period-t history

h t = (ω X (0), ω Y (0), . . . , ω X (t -1), ω Y (t -1), ω X (t))
identifies the characteristics (e.g., changes in the levels of demand and of conflict) and outcomes (e.g., changes in the price of oil) that have appeared in periods 0 through t -1, as well as the period-t characteristic, given state ω. We let H t denote all possible histories at period t. For a particular history h t we define the corresponding event

[h t ] = {ω ∈ Ω | (ω(0), . . . , ω(t -1), ω X (t)) = h t }
consisting of all states that are compatible with the history h t . In other words, [h t ] is the set of states whose period-t history matches h t , with different states in this set corresponding to different possible future developments. We define, for h t ∈ H t and Y ⊂ Y , the event

[h t , Y ] = {ω ∈ [h t ] | ω Y (t) ∈ Y }
consisting of all states that are compatible with the history h t and with a period-t outcome in the set Y .

In each period t the agent observes a history h t and makes a prediction about the period-t outcome, ω Y (t) ∈ Y . A prediction is a ranking of subsets in Y given h t . Hence, for h t ∈ H t there is a binary relation ht ⊂ 2 Y × 2 Y that ranks subsets of outcomes according to their plausibility.

Predictions

Predictions are made with the help of conjectures. Each conjecture is a subset A ⊂ Ω. A conjecture can represent a specific scenario, that is, a single state of the world, in which case A = {ω}. However, conjectures can contain more than one state, and thereby capture rules and analogies. In general, any reasoning aid one may employ in predicting y t can be described by the set of states that are compatible with it.

In principle, a conjecture could be any subset of Ω, but the set of all subsets of Ω is rather large and unwieldy. Nothing is lost by taking the set of conjectures to be the σ-algebra A generated by the events {[h t ]} t≥0,ht∈Ht . [START_REF] Bernoulli | Ars Conjectandi. Thurnisius[END_REF] To make predictions in period t, the agent first identifies, for any subset of outcomes Y ⊂ Y , the set of conjectures that have not been refuted by the history h t and that predict an outcome in Y . A conjecture A ∈ A has not been refuted by history h t if A ∩ [h t ] = ∅. The set of conjectures that have not been refuted by history h t and predict an outcome in Y is5

A(h t , Y ) = {A ∈ A | ∅ = A ∩ [h t ] ⊂ [h t , Y ]} . (1)
The agent evaluates the relative likelihoods of outcomes Y and Y , at history h t , by comparing the sets A(h t , Y ) and A(h t , Y ). The agent makes this comparison by using a credence function ϕ ht . Formally, ϕ ht is a finite, nonzero σ-additive measure on a sigma-algebra E ⊂ 2 A to be defined shortly. [START_REF] Cover | Nearest neighbor pattern classification[END_REF] We interpret ϕ ht (A(h t , Y )) as the weight the agent attaches to conjectures consistent with the outcomes Y , and ϕ ht (A(h t , Y )) as the weight the agent attaches to conjectures consistent with the outcomes Y . [START_REF] De | Sul Significato Soggettivo della Probabilità[END_REF] To make predictions, the agent ranks Y as "at least as likely as" Y , denoted Y ht Y , iff

ϕ ht (A(h t , Y )) ≥ ϕ ht (A(h t , Y )). (2)
In Appendix B we provide a characterization of binary ("at least as likely as") relations over subsets of Y that can be represented by belief functions, as ht is by represented ϕ ht in (2). Intuitively, one may think of each conjecture A as an expert, who argues that the state of the world has to be in the event A. The weight ϕ ht ({A}) is a measure of the expert's reliability in the eyes of the agent. The agent listens to the forecasts of all experts and, when comparing two possible predictions Y and Y , chooses the prediction that commands higher total support from the experts. When an expert is proven wrong, he is asked to leave the room and his future forecasts are ignored. For example, upon reaching a history h t at which the input ω X (t) indicates that the demand for oil has declined, perhaps because of a worldwide recession, the oil analyst from Section 1 will discard all conjectures pertaining to the price of oil in conditions of currently expanding demand. The set of surviving conjectures A(h t ) may include a conjecture consistent with a decrease in the price of oil (perhaps because the recession has reduced demand) as well as a conjecture consistent with an increase in the price of oil (perhaps because the price increased during a previous recession that the analyst remembers vividly).

To complete this definition, we need to specify the σ-algebra E ⊂ 2 A over which the measures ϕ ht are defined. [START_REF] De | La prevision: Ses lois logiques, ses sources subjectives[END_REF] For convenience, the domain of the function ϕ ht will be the same σ-algebra E for each history h t , even though only a subset of conjectures, namely ∪ Y Y A(h t , Y ), is relevant for prediction at h t , and the definition of ϕ ht outside this set is irrelevant.

First, for each conjecture A ∈ A, it will be useful to be able to refer to its weight of credence as ϕ ht ({A}), which requires that {A} be a measurable set. Let E 0 be the σ-algebra generated by all such sets. Next, since predictions will be made by comparing the ϕ ht values of subsets of the type A(h t , Y ), we need to make sure that these are measurable. Let E 1 be the σ-algebra generated by all such sets. Finally, the set of singletons contained in a conjecture will also be of interest, and we let E 2 be the σ-algebra generated by all such sets.9 Summarizing:

σ-algebra

Generating sets

E 0 {A} for A ∈ A E 1 A(h t , Y ) for t ≥ 0, h t ∈ H t , Y ⊂ Y E 2 {{ω} |ω ∈ A } for A ∈ A .
We then define E as the σ-algebra that is generated by E 0 ∪E 1 ∪E 2 . A credence function ϕ ht is a (σ-additive) measure on E.

Using states of the world to represent possible outcomes is standard in decision theory, as is the summation of a function such as ϕ ht to capture beliefs, and the elimination of conjectures that have been proven wrong. The most obvious departure we have taken from the familiar framework of Bayesian updating is to allow conjectures that consist of more than one state. [START_REF] Fix | Discriminatory analysis. Nonparametric discrimination: Consistency properties[END_REF] To confirm this, Section 3.1 shows that if we restrict attention to singe-state conjectures, then we have the familiar framework of Bayesian reasoning. Expanding the framework to encompass multi-state conjectures is necessary if we are to capture case-based and rule-based reasoning (cf. Sections 3.2 and 3.3).

We have restricted attention to deterministic conjectures. One sees this in (1), where conjectures are either clearly compatible or clearly incompatible with a given history. This is obviously restrictive, as we are often interested in drawing inferences about theories that do not make sharp predictions. However, a framework in which the implications of the evidence for various conjectures is dichotomous simplifies the analysis by eliminating assessments as to which theories are more or less likely for a given history, in the process allowing us to focus attention on the resulting induction.

Updating

How does the agent learn in this model? We have already identified one avenue for learning, namely that refuted conjectures are thereafter excluded from consideration. If this were the only avenue for learning in our model, then the updating would precisely mimic Bayesian updating, and the only generalization from a standard Bayesian model would be the introduction of multi-state conjectures.

Our generalized model allows a second avenue for learning-the credence function ϕ ht can vary with the history h t . Collecting information allows the agent not only to exclude falsified conjectures, but to modify the weights she attaches to her surviving conjectures. This contrasts with Bayesian updating in a standard probability model, where unrefuted states retain their original relative weights, as well as with the notion of a likelihood function, which can only decrease in value as data are gathered.

We can obviously expect ϕ ht to vary with h t if the agent is initially unaware of some conjectures. Such a conjecture will be assigned a zero weight at the outset, but a positive weight at a history h t that brings the conjecture to mind. For example, it is possible that prior to September 11, 2001 the agent had not imagined that terrorists might fly commercial airliners into buildings. This unawareness is naturally captured by setting ϕ ∅ of related conjectures to zero. However, given a history h t that includes this attack, conjectures that involve similar attacks in the future may have a positive weight in ϕ ht .

Even without unawareness, ϕ ht may depend on the history h t . The com-peting conjectures in our model have different domains of application. Some conjectures make predictions at each period, while others only rarely hazard a prediction. Once we reach a history h t , shouldn't conjectures that have made many correct predictions along the way be upgraded in comparison to those who have hitherto said little or nothing? In effect, shouldn't the value ϕ ht ({A}) increase as A passes more prediction tests? For example, suppose that there are two possible outcomes (Y = {0, 1}) and that conjecture A makes predictions at each of the periods t = 0, ..., 100, while conjecture A makes a prediction only at t = 100. Conjecture A may be a market analyst who arrives at time t = 100 having pegged the market correctly in every period, while conjecture A may be a competing analyst who thus far has said nothing other than "can't tell." [START_REF] Fix | Discriminatory analysis. Nonparametric discrimination: Small sample performance[END_REF] It seems that the weight we attach to A at time t = 100 should be higher than that of A , even if at the outset the two analysts seemed equally reliable.

Rewarding conjectures (or experts) for passing more prediction tests does not require that ϕ ht depend on h t . Instead, these rewards can be built into a function ϕ that is independent of h t . In the example above, at time t = 0 the agent already knows that conjecture A will be irrelevant for the first 100 observations, and will join the game only at period t = 100. The agent can then build this comparison into the function ϕ ∅ , perhaps by assigning weights ϕ ∅ (A) = 100ϕ ∅ (A ), and can then simply use ϕ ∅ throughout. Thus, if at time t = 100 conjecture A is still in the game, it will have a much higher weight than would A , without any alteration in ϕ. [START_REF] Gilboa | Subjectivity in inductive inference[END_REF] In effect, if we know that conjecture A will take no chances until period 100 and so will then be allocated a small weight relative to whatever conjecture has in the meantime passed many prediction tests, we might as well downgrade A at the beginning.

Consider a somewhat more involved example in which conjecture A again makes predictions at every period, and A now makes predictions at periods t = 0 and t = 100, but remains silent in between. We may then want to assign the two conjectures equal weights at time t = 0, but adjust ϕ h 100 in order to give A credit for having made the intervening string of correct predictions, should both still be relevant at time t = 100. It seems as if simply adjusting [START_REF] Fix | Discriminatory analysis. Nonparametric discrimination: Small sample performance[END_REF] For example, we could have A = [1, . . . , 1 101 ] and A = {ω ∈ Ω : ω Y (100) = 1}.

ϕ ∅ and thereafter holding ϕ fixed will not accomplish both goals. However, we can indeed incorporate all of these considerations without allowing ϕ to depend on h t . The key is to note that the conjectures A and A can both be relevant at time t = 100 only if they make identical predictions at time t = 0. But if they make the same prediction at time t = 0, only the sum of their weights (and not their relative weighting) has any effect on predictions at t = 0. We can thus freely adjust ϕ ∅ (A) and ϕ ∅ (A ) in such a way that would not change predictions until time t = 0, but will give A more weight at time t = 100.

The more general point is that {ϕ ht } t≥0,ht∈Ht is under-identified by the rankings ht ⊂ 2 Y × 2 Y t≥0,ht∈Ht . Many different credence functions {ϕ ht } t≥0,ht∈Ht give rise to the same ranking of subsets (at each and every history). Indeed it turns out that any ranking that can be obtained by a history-dependent {ϕ ht } t≥0,ht∈Ht can also be represented by a history-independent ϕ: Proposition 1 Let {ϕ ht } t≥0,ht∈Ht be a collection of finite measures on (A, E). Then there exists a measure ϕ on (A, E) such that, at each h t and for every

Y , Y ⊂ Y , ϕ(A(h t , Y )) ≥ ϕ(A(h t , Y )) ⇐⇒ ϕ ht (A(h t , Y )) ≥ ϕ ht (A(h t , Y )).
It thus sacrifices no generality to work with a function ϕ that is unchanged as history unfolds. We accordingly hereafter drop the h t subscript on ϕ and work with an unchanging ϕ.

When ϕ is independent of history, the updating rule inherent in (1)-( 2) is equivalent to the Dempster-Shafer (cf. Dempster [9], Shafer [35]) updating of the belief function defined by ϕ, in face of the evidence [h t ]. (See Appendix B for details.) This updating rule has been axiomatized by Gilboa and Schmeidler [13] in the context of Choquet expected utility maximization. [START_REF] Gilboa | Updating ambiguous beliefs[END_REF]

Special Cases

The unified framework is sufficiently general as to capture several standard models of inductive reasoning.

Bayesian Reasoning

We first show that our framework reduces to Bayesian reasoning if one restricts attention to conjectures that consist of one state each.

Bayesian reasoning has been studied in many ways in many fields. [START_REF] Gilboa | Case-based decision theory[END_REF] The various manifestations of the Bayesian approach differ in several ways, such as the scope of the state space and the degree to which Bayesian beliefs are related to decision making, but they share two common ingredients: (i) uncertainty is always quantified probabilistically; and (ii) when new information is obtained, probabilistic beliefs are updated according to Bayes' rule.

To embed Bayesian reasoning in our framework, define the set of Bayesian conjectures to be

B = {{ω} | ω ∈ Ω} ⊂ A. (3)
Notice that B is an element of E. Moreover, for every history h t , the set of surviving or unfalsified Bayesian conjectures B(h t ) is given by

B(h t ) = {{ω} | ω ∈ [h t ]} ,
and it is in E as well.

A credence function ϕ is Bayesian if only Bayesian hypotheses matter in determining the weights of credence attached to a set of conjectures, i.e., if for any set E ∈ E, we have

ϕ(E) = ϕ(E ∩ B). (4)
In particular, among the conjectures contained in A, only those in B are assigned positive weight by a Bayesian credence function.

We can confirm that our model captures Bayesian reasoning:

Lemma 1 Let p be a probability measure on (Ω, A). There exists a Bayesian credence function such that for every history h t , there is a constant λ > 0 for which, for every Y ⊂ Y and h t with p(B(h t )) > 0,

p(y t ∈ Y | [h t ]) = λϕ(A(h t , Y )).
Proof. Let the credence function be given by

ϕ(E) = p(E ∩ B). First note that E ∩ B is in A.
Hence, ϕ attaches to each set of Bayesian hypotheses a weight of credence equal to the prior probability attached to the set, and attaches to a general set of hypotheses a weight of credence equal to that of the Bayesian hypotheses it contains. Then ϕ is clearly Bayesian. It then remains to identify the normalization appropriate for history h t :

ϕ(A(h t , Y )) = p({ω : {ω} ∈ A(h t , Y )}) = p(B(h t )) p({ω : {ω} ∈ A(h t , Y )}) p(B(h t )) = p(B(h t ))p(y t ∈ Y | [h t ]) := λ -1 p(y t ∈ Y | [h t ]),
giving the result.

Bayesian reasoning is thus a special case of our framework: every Bayesian belief can be simulated by a model ϕ, and Bayesian updating is imitated by our process of excluding refuted conjectures. Apart from the normalization step, which guarantees that updated probabilities continue to sum up to 1 as conjectures are deleted but has no effect on relative beliefs, Bayesian updating is nothing more than the exclusion of refuted conjectures from further prediction.

Our model captures Bayesian reasoning via an assumption that only conjectures containing a single state enter the agent's reasoning. An agent whose credence function assigns positive weight to non-Bayesian conjectures (e.g., ϕ({A}) > 0 for some A ∈ A\B > 0) will not be "Bayesian" by any common definition of the term. For example, suppose that A = {ω 1 , ω 2 } and ϕ({A}) = δ > 0. Such an agent can be viewed as arguing, "I think that one of ω 1 or ω 2 might occur, and I put a weight δ > 0 on this conjecture, but I cannot divide this weight between the two states." Intuitively, this abandons the Bayesian tenet of quantifying all uncertainty in terms of probabilities. Formally, the corresponding rankings of subsets of outcomes, ht , may fail to satisfy de Finetti's [7, 8] cancellation axiom: it can be the case that, for two sets of outcomes, B, C, B ht C but not B\C ht C\B. In addition, if we use the credence function to make decisions by maximization of the Choquet integral of a utility function, the maximization will fail to satisfy Savage's [32] "sure-thing principle" (axiom P2). As a result, upon adding decisions to our model of beliefs, we would have a converse to Lemma 1: the decision maker will be Bayesian if and only if (4) holds. (See Appendix B for a definition of Choquet integration.)

Case-Based Reasoning

Case-based reasoning is also a special case of our model. [START_REF] Gilboa | Canonical Representation of Set Functions[END_REF] We first introduce a simple model of case-based reasoning in which casebased prediction is equivalent to kernel classification. [START_REF] Gilboa | A Theory of Case-Based Decisions[END_REF] The agent has a similarity function over the characteristics,

s : X × X → R + ,
and a memory decay factor β ≤ 1. Given history h t = h t (ω), a set of outcomes Y Y is assigned the weight

S(h t , Y ) = y∈Y t-1 i=0 β t-i s(ω X (i), ω X (t))1 {ω Y (i)=y} ,
where 1 is the indicator function of the subscripted event. Hence, the agent may be described as if she considered past cases in the history h t , chose all those that resulted in some period i with some outcome y ∈ Y , and added to the sum S(h t , Y ) the similarity of the respective characteristic ω X (i) to the current characteristic ω X (t). The resulting sums S(h t , Y ) can then be used to rank sets of possible outcomes Y .

If β = 1 and in addition the similarity function is constant, the resulting number S(h t , {y}) is proportional to the relative empirical frequency of y's in the history h t . If, on the other hand, β → 0, the maximizer of S(h t , •) will be the most recent observation, ω Y (t -1). Thus, when the similarity function is constant, case-based reasoning can be viewed as a simultaneous (and smooth) generalization of prediction by empirical frequencies on the one hand, and of prediction by recency on the other hand.

More interesting generalizations are possible when the similarity function isn't constant, and uses the information given in X to make more informed judgments.

The next observation states that the general framework presented in Section 2 can accommodate a special case of case-based reasoning:

Lemma 2 Let there be given s : X × X → R + and β ≤ 1. There exists a credence function ϕ such that, for every history h t , there is a constant λ > 0 for which, for every y ∈ Y ,

ϕ(A(h t , {y})) = λS(h t , y).
To prove this observation, we first define case-based conjectures. For every

i < t ≤ T -1, x, z ∈ X, let A i,t,x,z = {ω ∈ Ω | ω X (i) = x, ω X (t) = z, ω Y (i) = ω Y (t)}
and observe that it is the union of finitely many sets of the type [h t , Y ]. Hence A i,t,x,z ∈ A and {A i,t,x,z } ∈ E.

We can interpret this conjecture as indicating that, if the input data are given by x in period i and by z in period t, then periods i and t will produce the same outcome (value of y). Notice that in contrast to the Bayesian conjectures, a single case-based conjecture consists of many states: A i,t,x,z does not restrict the values of ω X (k) or ω Y (k) for k = i, t. Let the set of all conjectures of this type be denoted by

CB = {A i,t,x,z | i < t ≤ T, x, z ∈ X } ⊂ A. (5)
A credence function ϕ is case-based if, for every set E ∈ E, we have

ϕ(E) = ϕ(E ∩ CB). (6)
Thus, among the conjectures contained in the set A, only those in CB are assigned positive weight by a case-based credence function.

Once the set of conjectures CB has been defined, the proof of Lemma 2 is straightforward:

Proof. Given a similarity function s and β ≤ 1, let

ϕ({A i,t,x,z }) = c t β (t-i) s(x, z) (7)
where c t > 0 is chosen so that ϕ(CB) is finite, say, c t = t -2 . Let, for E ∈ E,

ϕ(E) = {A i,t,x,z }∈E ϕ({A i,t,x,z }).
Consider a history h t = h t (ω) and a prediction y ∈ Y . To calculate ϕ(A(h t , {y})) observe first that, at h t , only the conjectures A i,t,ω X (i),ω X (t) | i < t are unrefuted and yield predictions that are included in the singleton {y}. Hence, only t conjectures will affect the prediction {y}, corresponding to the t possible case-based conjectures of the form A i,t,ω X (i),ω X (t) (with i = 0, 1, ..., t -1).

It is then immediate that ϕ(A(h t , {y})) = c t S(h t , y).

In general, we could define similarity relations based not only on single observations but also on sequences, or on other more general patterns of observations, and could define predictions over nonsingleton sets. Such higherlevel analogies can also be captured as conjectures in our framework. For instance, the agent might find history h t similar to history h i for i < t, because in both of them the last k periods had the same observations. This can be reflected by conjectures including states in which observations (i-k +1), ..., i are identical to observations (t -k + 1), ..., t, and so forth.

Rule-Based Reasoning

The model can accommodate many other forms of reasoning, often referred to as "rule-based reasoning." [START_REF] Gilboa | Inductive inference: An axiomatic approach[END_REF] These other modes of reasoning are again characterized by conjectures or "rules" to which they attach weights of credence. This section provides some examples.

The rule "the price of oil always rises" corresponds to the conjecture [START_REF] Gilboa | Inductive inference: An axiomatic approach[END_REF] We draw the name "rule-based" from earliest models of reasoning, dating back to Greek philosophy and its study of logic, focusing on the rules of deduction and the concept of proof. The rise of analytical philosophy, the philosophy of mathematics, and artificial intelligence greatly extended the scope of rule-based reasoning, including its use for modeling human thinking, as in the introduction of non-monotonic (McCarthy [24], McDermott and Doyle [25], Reiter [29]), probabilistic (Nilsson [26]), and a variety of other new logics.

A = {ω ∈ Ω | ω Y (t) = 1 ∀t} .
There are many states in this conjecture, featuring different sequences of changes in the values of the level of demand and conflict.

Our framework can also encompass association rules, or rules that can be expressed as conditional statements. For example, consider the rule "if the level of conflict has risen, so will the price of oil." This rule can be described by

A = {ω ∈ Ω | ω X 2 (t) = 0 or ω Y (t) = 1 ∀t} . (8)
(Recall that ω X 2 (t) indicates whether there was an increase in the index of conflict, and ω Y (t) an increase in the price of oil.) The rule "an increase in conflict implies an increase in the price of oil" is then read as "either there will be less conflict, or more expensive oil, or possibly both." [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF] An association rule will be excluded from the set A(h t , Y ) as soon as a single counter-example is observed. Thus, if history h t is such that for some i < t we observed an increase in the level of conflict that was not followed by a rise in the price of oil, the conjecture (8) will not be used for further analysis. When an association rule is unrefuted, it may or may not affect predictions, depending on whether its antecedent holds. If the antecedent of a rule is false, the rule becomes vacuously true and does not affect prediction. However, if (in this example) we do observe a rise in the level of conflict, ω X 2 (t) = 1, the rule has bite (retaining the assumption that it is as yet unrefuted). Its weight of credence ϕ will be added to the prediction that the price of oil will rise, ω Y (t) = 1, but not to the prediction that it will not, ω Y (t) = 0.

Our framework also allows one to capture functional rules, stating that the value of y is a certain function f of the value of x, such as [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF] Holland's [18] genetic algorithms address classification problem where the value of y is to be determined by the values of x = (x 1 , ..., x m ), based on past observations of x and y. The algorithm maintains a list of association rules, each of which predicts the value of y according to values of some of the x j 's. For instance, one rule might read "if x 2 is 1 then y is 1" and another, "if x 3 is 1 and x 7 is 0 then y is 0." In each period, each rule has a weight that depends on its success in the past, its specificity (the number of x j variables it involves) and so forth. The algorithm chooses a prediction y that is a maximizer of the total weight of the rules that predict this y and that apply to the case at hand. The prediction part of genetic algorithms is therefore a special case of our framework, where the conjectures are the association rules involved. However, in a genetic algorithm the set of rules does not remain constant, with rules instead being generated by a partly-random process, including crossover between "parent genes," mutations, and so forth.

A = {ω ∈ Ω | ω Y (t) = f (ω X (t)) ∀t} .

Combined Models

The previous subsections illustrate how our framework can capture each of the modes of reasoning separately. Its main strength, however, is in being able to smoothly combine such modes of reasoning, simply by considering credence functions ϕ that assign positive weights to sets of conjectures of different types.

For example, consider an agent who attempts to reason about the world in a Bayesian way. The agent has a prior probability p over the states of the world, Ω. However, she also carries with her some general rules and analogies. Assume that she employs a model ϕ such that ϕ (B) = 1 -ε (where ε > 0) with weight allocated among the Bayesian conjectures according to

ϕ ({{ω} | ω ∈ A}) = (1 -ε) p (A)
(for all A ∈ A) and the remaining weight ε is split among case-based and rule-based conjectures. If ε is small, then the non-Bayesian conjectures will play a relatively minor role in determining the agent's initial predictions, and will continue to do so as long as the history unfolds along a path that is sufficiently likely under the the prior p. But what happens if the reasoner faces a surprising outcome, such as the September 11 attacks or the Lehman Brothers' collapse?

If the agent had assigned the outcome zero probability, Bayesian updating will not be well-defined. In this case, the non-Bayesian conjectures will determine the agent's predictions. For example, in the face of the September 11 attack, the agent might discard Bayesian reasoning and resort to the general rule that "at the onset of war, the stock market plunges." Alternatively, the agent may resort to analogies, and predict the stock market's behavior based on past cases such as the attack on Pearl Harbor.

Even if the outcome in question had a nonzero but very small prior probability, non-Bayesian reasoning will again be relatively more important. Conditional probabilities are now well-defined and can be used, but the formerly negligible non-Bayesian conjectures will now be much more prominent. This can be interpreted as if the reasoner has a certain degree of doubt about her own probabilistic assessments, captured by the weight ε > 0 put on non-Bayesian conjectures. This process will be formalized in the sequel.

How Would We Know and Why Would We Care?

We have noted in Section 3.1 that an agent who attaches weight to non-Bayesian conjectures will generate rankings ht that are observably non-Bayesian. However, Proposition 1 also notes that the agent's predictions may be consistent with many credence functions ϕ. Indeed, it is easy to see that, if the agent is asked simply to identify the most likely singleton in Y after each history, then any given sequence of such predictions can be explained by either Bayesian or other methods of reasoning. [START_REF] Hume | An Enquiry Concerning Human Understanding[END_REF] Why should we care, then, about the mode of reasoning the agent employs?

The answer is that different modes of reasoning might explain a given dataset of predictions ex post, yet provide different predictions ex ante. For example, if we knew that the agent were Bayesian, we would try to use her past predictions to estimate her prior, and use it to forecast her posterior. [START_REF] Jeffrey | Subjective Probability: The Real Thing[END_REF] By contrast, if the agent were known to be a case-based reasoner, her past predictions would be used to estimate her similarity function. Thus, the same dataset of observations might be compatible with both assumptions about the mode reasoning, but it might lead to different predictions under these assumptions.

This is a manifestation of a more general point: when comparing different paradigms, one often cannot expect to have a simple experiment that identifies the correct one. Within each paradigm many theories may be developed, which can, post hoc, explain given data. However, the simplest theory within one paradigm might lead to rather different predictions than the corresponding theory within another paradigm. In other words, if we augment paradigms with a method for selecting theories within them (say, the simplest theory that fits the data), the choice of a paradigm will have observable implications.

Dynamics of Reasoning Methods

When is Bayesian Reasoning Fragile?

Under what conditions will Bayesian reasoning survive as evidence accumulates, and when will the agent turn to other modes of reasoning? Our answer is that Bayesian reasoning will wither away if the agent's prior is not sufficiently informative.

Assumptions

We start by assuming that at least some weight is placed on both Bayesian and case-based reasoning:

Assumption 1 ϕ(B), ϕ(CB) > 0.
There can be many other types of conjectures that get non-zero weight according to ϕ. The specific inclusion of case-based reasoning is a matter of convenience, born out of familiarity. We explain in Section 4.1.2 how this assumption could be reformulated to make no reference to case-based conjectures.

Next, we think of the agent as allocating the overall weight of credence in a top-down approach, first allocating weights to modes of reasoning, and then to specific conjectures within each mode of reasoning. First consider the weight of the Bayesian conjectures, ϕ(B). We are interested in an agent who knows relatively little about the process she is observing. An extreme case of such ignorance is modeled by a uniform prior:

ϕ (B(h t )) ϕ (B(h t )) = 1, (9)
for any pair of histories of the same length, h t and h t . We can relax this assumption, requiring only that the probability assigned to any particular history cannot be too much smaller than that assigned to another history of the same length. Thus, one may assume that there exists M > 1 such that, for every t and every h t , h t ∈ H t ,

ϕ (B(h t )) ϕ (B(h t )) < M. (10)
We weaken this condition still further, allowing M to depend on t, and assume only that the ratio between the probabilities of two histories cannot go to infinity (or zero) too fast as we consider ever-larger values of t. Formally, Assumption 2 There exists a polynomial P (t) such that, for every t and every two histories

h t , h t ∈ H t , ϕ(B(h t )) ϕ(B(h t )) ≤ P (t).
Assumption 2 is still strong-it will be violated if, as is often assumed in Bayesian models, the agent believes she faces successive iid draws, say, ω Y (t) = 1 in each period with probability p > 0.5. [START_REF] Dennis | Introduction to Probability and Statistics from a Bayesian Viewpoint[END_REF] In this case the agent knows a great deal about the data generating process, being able to identify the process up to the specification of a single parameter. In contrast, our message is that Bayesian reasoning will fade when the agent knows relatively little about the data generating process. However, sub-section 4.1.4 shows that a similar (but somewhat more cumbersome) result holds in the iid case as well.

We make an analogous assumption regarding the way that the weight of credence is distributed among the various case-based conjectures. It would suffice for our result to impose a precise analog of Assumption 2, namely that there is a polynomial Q(t) such that, for any t and any pair of case-based conjectures A i,t,x,z and A i ,t ,x z , we have

ϕ({A i,t,x,z }) ϕ({A i ,t ,x ,z }) ≤ Q(t). (11)
However, suppose (analogously to (7)) that there exists a similarity function s : X × X → R + , a decay factor β ∈ (0, 1], and a constant c > 0 such that, for every i < t and every x, z ∈ X,

ϕ({A i,t,x,z }) = cβ t-i s(x, z). (12)
In this case, the characteristics x, z ∈ X determine the relative weights placed on the case-based conjectures involving information of a given vintage (i.e., a given value of t -i), with β ≤ 1 ensuring that older information is no more influential than more recent information. This formulation is rather natural, but it violates (11) if β < 1, as the relevance of older vintages then declines exponentially. Fortunately, there is an obvious and easily interpretable generalization of ( 11) that allows us to encompass (12).

Assumption 3 There exists a polynomial Q(t) such that

• for every i, i , t, t , x, x and z, z with t -i = t -i , and t < t,

ϕ({A i ,t ,x ,z }) ϕ({A i,t,x,z }) ≤ Q(t), (13)
• and for every t, x, z ∈ X and i < i < t,

ϕ({A i,t,x,z }) ϕ({A i ,t,x,z }) ≤ Q(t). (14)
Condition (13) stipulates that within a set of conjectures based on similarities across a given time span (i.e., for which t -i = t -i ), the agent's weights of credence cannot be too different. Condition (14) stipulates that when comparing similarities at a given period t, based on identical characteristics but different vintages, the older information cannot be considered too much more important than more recent information. Typically, we would expect older information to be less important and hence this constraint will be trivially satisfied.

Result

The following result establishes that under Assumptions 1-3, in the long run the agent puts all of her weight on non-Bayesian (rather than on Bayesian) conjectures.

For the statement of the result we need a notation for the case-based conjectures that are relevant at history h t :

CB(h t ) = CB∩ (∪ y∈Y A(h t , {y})) . Proposition 2 Let Assumptions 1-3 hold. Then at each ω ∈ Ω, lim t→∞ ϕ (B(h t )) ϕ (CB(h t )) = 0.
Hence, the Bayesian component of the agent's reasoning will wither away. As we noted in Section 3.5, the resulting shifting weights of credence can give rise to predictions that could not be rationalized by a Bayesian model. The Bayesian part of the agent's beliefs converges to the truth at an exponential rate as evidence is accumulated (that is, as t grows): within the Bayesian class of conjectures, the probability of the true state relative to the probability of all unrefuted states grows exponentially with t. How is this fast learning reconciled with Proposition 2? The conditional probability of the true state increases at an exponential rate not because its numerator (the weight attached to the true state) increases, but because its denominator (the total probability of all unrefuted states) decreases at an exponential rate. But this is precisely the reason that the weight of the entire class of Bayesian conjectures tapers off and leaves the stage to others, such as the case-based conjectures. As t grows, the weight of Bayesian conjectures that remain unrefuted by history h t , ϕ (B(h t )), becomes an exponentially small fraction (given Assumption 1) of the original weight of all Bayesian conjectures, ϕ (B). In contrast, the number of case-based conjectures at period t is only a polynomial (in t), and hence there is no reason for the weight of those that make predictions at history h t to decrease exponentially fast in t. The relative weight placed on Bayesian conjectures thus declines to zero.

It follows that a similar result would hold if we were to replace the class of case-based conjectures with any other class of conjectures that grows polynomially in t and that provides some non-tautological prediction for each h t , provided an assumption similar to Assumption 3 holds. Therefore, we do not view this result as proving the prevalence of case-based reasoning. Rather, the result highlights the fragility of Bayesian reasoning. Case-based reasoning is simply a familiar example of a mode of reasoning with the requisite properties.

Recall that case-based prediction can be viewed as generalizing the prediction of the modal outcome in the past, as well as the prediction of the most recent outcome. While we again emphasize that the role of case-based reasoning in this argument could be filled by many alternatives, we find it unsurprising that an agent who does not know much about the data generating process may use simple statistical techniques, predicting outcomes that have been observed most often or most recently. Our result describes a possible mechanism by which this may happen, for reasons unrelated to bounded rationality or to cognitive or computational limitations.

Weights of Credence

Proposition 2 is driven by the fact that there are fewer case-based conjectures than there are Bayesian ones. In order for a relatively small class of conjectures to have unrefuted representatives at each history, it must be the case that many of these conjectures make no predictions at many histories. In a sense, conjectures from the smaller class may be viewed as saving their ammunition and picking their fights selectively.

The obvious question is then: Are the Bayesian conjectures treated fairly by our assumptions on the function ϕ? Specifically, if, at time t, the agent compares the Bayesian conjectures to the case-based ones, she will find that each of the former (that is still in the game) has made t successful predictions, whereas each of the surviving case-based conjectures has made no predictions at all. Shouldn't the tested conjectures get more weight than the untested ones? Shouldn't the credence function ϕ be updated to reflect the fact that some conjectures have a more impressive track record than others? Section 2.3 explained that it sacrifices no generality to work with a function ϕ that is never revised as history unfolds. This simply refocuses the question in terms of the a priori assignment of weights, in the process directing attention to Assumption 3. Should we not make the weight of case-based conjectures of the form A i,t,x,z decline exponentially fast in t (violating Assumption 3), to give the Bayesian ones a fair chance, as it were?

We believe there are some obvious circumstances in which the answer is negative. Suppose that all of the Bayesian conjectures get the same weight, satisfying an extreme version of Assumption 2. It then cannot help but be the case that some of them are still unrefuted by history h t : by construction, there had to be states of the world that are compatible with h t . The agent knew at time t = 0 that, whatever history materializes at time t, some Bayesian conjectures will be in the game. In this case, there is no reason to artificially increase the relative weight of these conjectures upon reaching history h t , as if they were a priori selected. Adopting the equivalent but a priori convention of decreasing the weight of the case-based conjectures at an exponential or even faster rate strikes us as similarly unjustified, being tantamount to committing to a Bayesian approach that one knows is both tautologically true and without content. [START_REF] Marinacci | Decomposition and Representation of Coalitional Games[END_REF] Another way to look at this problem is the following. Let the agent ask herself at time 0, how much weight is given (a priori) to all conjectures of a given type that will be relevant for prediction at time t. For the Bayesian conjectures the answer is independent of t: when we sum across all possible histories, we always get the same number, ϕ (B), because the union of the relevant conjectures across all histories of length t is the set of all Bayesian conjectures, B, for all t. For the case-based conjectures the situation is quite different: when we consider t = t , the set of conjectures that will be relevant at some history h t is disjoint from the corresponding set for t . Indeed, we have observed that the total weight of all conjectures that may be relevant at time t has to tend to zero, whereas the corresponding weight for the Bayesian conjectures in a constant. From this viewpoint, the Bayesian conjectures have an inherent advantage. Thus, it seems reasonable to require that, at the very least, the vanishing sequence of weights of case-based conjectures not vanish too fast, and this is what Assumption 3 states.

The iid Case

An obvious case in which Assumption 2 is violated occurs when the agent believes that she observes an iid process. Suppose, for example, that Y = {0, 1} and the agent believes the y t are iid Bernoulli random variables, i.e., y t ∼ B(p). Then Assumption 2 holds only if p = 0.5, because the ratio of single states' probabilities involves exponentials of p and (1-p). Nonetheless, a conclusion very similar to that of Proposition 2 still holds.

Consider the state space Ω endowed with the σ-algebra Σ defined by the variables (x t , y t ) t≥0 . A probability measure µ on Σ is a non-trivial conditionally iid measure if, for every x ∈ X there exists λ x ∈ ∆(Y ) such that (i) for every h t = ((x 0 , y 0 ) , . . . , (x t-1 , y t-1 ) , x t ), the conditional distribution of Y given h t according to µ is λ xt ; and (ii) λ x is non-degenerate for every x ∈ X. The next assumption states that the Bayesian part of the agent's beliefs is weight of the competing case-based conjectures exponentially fast in t. Equivalently, the agent might arrange at the beginning of the game to cause the weight placed on case-based conjectures A i,t,x,z to decrease very quickly in t, allowing the lone Bayesian conjecture to rule the roost if it survives, while retaining the relative weights on the surviving case-based conjectures so that their predictions are unaffected in the event the Bayesian hypothesis is falsified. Notice, however, that this manipulation is unnecessary. If the initial weight attached to Bayesian hypotheses is large, the weight will remain large, as there are no falsified Bayesian hypotheses to melt away. In this case, Bayesian reasoning survives even without help in the form of declining case-based weights.

governed by such a measure:

Assumption 4 There exists a non-trivial conditionally iid measure µ such that, for every

A ∈ Σ ϕ ({{ω} | ω ∈ A}) = µ(A)ϕ(B)
Thus, this assumption states that the weight of the Bayesian conjectures, ϕ(B), is divided among them in a way that is proportional to the measure µ. [START_REF] Matsui | Expected utility and case-based reasoning[END_REF] We can now state Proposition 3 Let Assumptions 1,3, and 4 hold, and let µ be the measure of Assumption 4. Then

µ lim t→∞ ϕ (B(h t )) ϕ (CB(h t )) = 0 = 1.
Proposition 3 states that, µ-almost surely, the weight of the Bayesian hypotheses relative to that of the case-based ones will converge to zero. Thus, an agent who has Bayesian beliefs µ, and who puts some weight ε > 0 on the case-based beliefs in a way that corresponds to Assumption 3, will, according to her own beliefs, converge to be non-Bayesian. Importantly, even if the agent were right about the Bayesian part of her beliefs, she would still predict that her own reasoning will become non-Bayesian.

The proof of Proposition 3 mimics that of Proposition 2. The key observation is that there are exponentially many histories for any given frequencies of outcomes, provided that these frequencies are non-trivial. For example, if |X| = 1, Y = {0, 1} and we consider a history of length t, there is but one history in which there are 0 y's that are equal to 1, and O(t k ) histories in which there are k such y's. But there are exponentially many histories in which the relative frequency of 1 is close to pt. That is, t pt is exponential in t if p = 0, 1. More generally, since µ is assumed to be non-trivial conditionally iid (that is, since the conditional distributions λ x are assumed to be non-degenerate), apart from a set of µ measure zero, any history at time t has exponentially many other histories that are just as likely.

Observe that a similar result would hold in case the agent only believes that the variables y t , given each value of x, are exchangeable. Indeed, the very definition of exchangeability, involving all possible permutations, hints at the dangers of exponential blow-up. To prove such a result, one need only make sure that sufficiently many permutations result in different histories h t .

Along similar lines, the conclusion of Proposition 2 holds also if Assumption 2 fails but there exists γ < 1 such that, for some polynomial P (t), for every t and every h t , ϕ(B t (h t )) ≤ γ t P (t). ( 15)

If Assumptions 1 and 3 also hold, then the relative weight on Bayesian conjectures will decline to zero. On the other hand, an agent who is resolutely Bayesian will handle iid variables just as one would expect.

Example 1 Suppose that X is degenerate, say, X = {0}, Y = {0, 1}, and that ϕ(B) = 1. Suppose this Bayesian's prior is a nondegenerate mix of two prior distributions. One of these predicts that each y t is drawn from the Bernoulli distribution B(p) and one from the Bernoulli distribution B(q). Then if the observations are indeed iid draws from B(p), the relatively weight that the agent places on this distribution will almost surely (according to the true distribution) converge to one. The agent will eventually predict optimally, predicting y t = 1 in each period if p > .5, and y t = 0 otherwise.

Agents who are convinced they should be Bayesian thus exhibit familiar behavior. In light of this, how will an agent reason who is reasonably confident that she faces an iid process, but is uncertain about the parameter? Much depends on what is meant by "reasonably confident," a judgment manifested in the agent's credence function.

Example 2 Suppose that X is degenerate, Y = {0, 1}, and that the weights of credence the agent attaches to Bayesian conjectures are consistent with the various y t being drawn iid from a Bernoulli distribution. If the agent is sufficiently confident of her iid hypothesis as to attach zero weights of credence to all other conjectures, she will be familiarly and resolutely Bayesian throughout. If she hedges her bets by attaching some weight to case-based conjectures, in accordance with Assumption 3, then the weight she attaches to Bayesian conjectures will decline to zero. Indeed, the agent can be assured at the beginning of the process that this will happen. Alternatively, suppose the agent attaches credence to case-based hypotheses, but attaches weights that cause ϕ({A i,t,x,z }) to decline exponentially (violating Assumption 3). Suppose again the Bayesian prior is a nondegenerate mix of two prior distributions, one predicting that each y t is drawn from the Bernoulli distribution B(p) and one predicting draws from the Bernoulli distribution B(q). Then if the weights ϕ({A i,t,x,z }) decline appropriately, the weight of Bayesian hypotheses will increase to one if the data are indeed generated by B(p) or B(q), but in other cases (e.g., data drawn from B(r) for some r = p, q) the Bayesian prior will slip into insignificance and case-based reasoning will prevail. They agent will thus remain Bayesian if her Bayesian prior contains the correct date generating process, but will otherwise slip into case-based reasoning.

Example 2.5 We can provide a simple illustration. Consider again the simplest case of X = {0}, Y = {0, 1}. Assume that y t are iid, where y t = 1 with probability p.

Consider the set of states

B i,y = {ω ∈ Ω | ω Y (t) = y ∀t ≥ i }
for i ≥ 0 and y ∈ Y . Hence, each collection of states B i,y is identified by a given period i and outcome y, and predicts that from period i on, only outcome y will be observed.

The agent attaches weights to all of the Bayesian conjectures in the set i≥0,y∈Y B i,y .

The weight attached to the states in B i,0 ∪ B i,1 is given by ξ2 -i , evenly distributed among such states. (The factor ξ is a normalization, to ensure weights sum to unity.) There are 2 i such hypotheses, so that the weight of a single such hypothesis is 2 -2i . Notice that (15) holds, so that the weights attached to Bayesian hypotheses are consistent with Bayesian reasoning withering away.

If weight is attached only to Bayesian hypotheses, then obviously Bayesian reasoning will survive. If Assumption 3 holds, then Bayesian reasoning will disappear. We examine a middle case here.

Because there are no x values to consider, the case-based conjectures are simply

A i,t = {ω ∈ Ω | ω Y (i) = ω Y (t)} ,
and the set of all case-based conjectures is

CB = {A i,t | i < t} .
The weight attached to the case-based hypothesis in A i,t is given by ξ2 -2t (obviating Assumption 3). Now consider a history h t ending with a run of either y = 0 of y = 1 of length . The total weight of case-based hypotheses is 2 -2t . Among the Bayesian hypotheses, there survives a hypothesis from the B(t -, 0) ∪ B(t -, 1), with weight 2 -(t-). The weight placed on Bayesian hypotheses is thus at least 2 -(t-), and the weight of Bayesian hypotheses relative to case-based hypotheses is at east 2 . As the history unfolds, with probability one there will occur arbitrarily long strings of identical values of y, at which point the relative weight of Bayesian hypotheses will be arbitrarily large. At the same time, strings will periodically be broken, restoring the Bayesian and case-based hypotheses to an equal footing. Hence, from time to time there will emerge a Bayesian hypotheses that is accepted, only to collapse at some subsequent point. In other words, even if the data are completely random, it should be expected that theories would rise and fall every so often, with casebased reasoning being more prominent between regimes of different theories.

Observe that the balance of weights between the two modes of reasoning is driven by the success of Bayesian reasoning. This reflects the intuition that people would like to understand the process they observe, and that such "understanding" means a simple, concise theory that explains the data. If such a theory exists, agents will tend to prefer it over case-based reasoning. But when all simple theories are refuted, agents will resort to case-based reasoning.

When will Bayesianism Prevail?

If we had worked with the stronger version of Assumption 2 given by ( 9), we would have the expected (though perhaps reassuring) result that Bayesian reasoning disappears when the Bayesian prior is so diffuse that a Bayesian could not possibly learn anything. However, Assumption 2 allows Bayesian priors that will in turn allow learning, and yet still give way to other sorts of reasoning. Section 4.1.4 shows that Assumption 2 can be weakened yet further. When will Bayesian reasoning remain useful in the long run, or even dominate other reasoning methods?

Example 3 Suppose the agent believes that she nearly knows the true state of the world. We capture this by letting there be some ω, ϕ({ω}) = 1 -ε (and hence allowing Assumption 2 to fail). If, on top of this, the agent is also correct in her focus on state ω, then (that is, at state ω) the weight attached to Bayesian conjectures will never dip below 1 -ε. In other words, if the agent believes she knows the truth, and happens to be right, her Bayesian beliefs will remain dominant.

Example 4 A slightly less trivial example is the following. Suppose the agent believes she faces a cyclical process, but is uncertain of its period. To capture these beliefs in a simple model, let us consider only Bayesian and case-based reasoning. In addition, let X = {0} and Y = {0, 1}, so that all periods have the same observable features, and they only differ in the binary variable the agent is trying to predict. For k ≥ 1, let ω k ∈ Ω be defined by

ω k Y (t) = 0 2mk ≤ t < (2m + 1)k m = 0, 1, 2, ... 1 (2m + 1)k ≤ t < (2m + 2)k m = 0, 1, 2, ... .
Thus, for k = 1 the process is 01010101..., for k = 2 it is 001100110011... and so forth.

Let the agent's beliefs satisfy

ϕ( {ω k } ) = 1 -ε 2 k and ϕ T ( {ω}|ω / ∈ ω k |1 ≤ k ) = 0.
Thus, the agent splits all the weight of the Bayesian conjectures among the conjectures ω k and leaves no weight to the other Bayesian beliefs. [START_REF] Mccarthy | Circumscription-A form of non-monotonic reasoning[END_REF] Once again, Assumption 2 fails. The remaining weight, ε, is split among the casebased conjectures.

Next suppose that the agent is right in her belief that the process is indeed cyclical (starting with a sequence of 0's). Thus, the data generating process chooses one of the states ω k . At this state, once we get to period t = k, all the Bayesian conjectures ω k for k = k are refuted. In contrast, the conjecture ω k is not refuted at any t. Consequently, at ω k , for every t ≥ k, the total weight of the Bayesian conjectures remains 1-ε 2 k . The total weight of the case-based conjectures converges to 0, resulting in the Bayesian mode of reasoning remaining the dominant one (for large t). Clearly, this will only be true at the states ω k . At other states the converse result holds, because all Bayesian conjectures will be refuted and case-based reasoning will be the only remaining mode of reasoning.

Example 5 Considering the same set-up, X = {0} and Y = {0, 1}, let us limit attention to the first T periods. Consider a Bayesian agent who has a uniform belief over the average

ȳT = 1 T T -1 t=0 ω Y (t)
and, given ȳT , a uniform distribution over all the corresponding states. Thus, the agent puts a weight of 1 T +1 on the sequence 1, 1, ..., 1, but only a weight of 1 T (T +1) on each sequences with (T -1) 1's and a single 0, and a weight o(T -3 ) on each sequence with two 0's, and so forth.

The total weight of all case-based conjectures is a convergent series. This implies that the weight of all the case-based conjectures that are relevant at T has to decline to zero at a rate that is faster than 1 T . Hence, if the agent observes the sequence 1, 1, ..., 1, she will put more weight on the Bayesian conjecture that can be described also by the rule "ω Y (t) = 1 for every t." However, if the agent observes one exception to this rule, the Bayesian conjecture that predicts only 1's will have a weight that is o(T -2 ). The more exceptions one observes, the lower is the weight of the Bayesian conjectures.

If the rate of decline of the weight of case-based conjectures in polynomial in T , say, o(T -k ) for k > 1, then finitely many exceptions to the rule "y is always 1" will suffice to switch to case-based reasoning. (Observe, however, that this reasoning is likely to make similar predictions: if all but k times one has observed y t = 1, the modal prediction will still be y T = 1.) If, by contrast, the weight of case-based conjectures decreases exponentially fast in T , even very spotty patterns will keep the Bayesian conjectures on par with the case-based ones.

In summary, for Bayesian reasoning to prevail, the reasoner's Bayesian beliefs must be sufficiently informative (i.e., must contain the truth and must not be too diffuse), and the reasoner must have sufficient confidence in those Bayesian beliefs (e.g., build quickly declining weights of credence into the case-based conjectures relevant to successive periods). Economic models typically ensure this confidence by assuming that the agent entertains only Bayesian conjectures. We emphasize that our purpose is not to criticize either Bayesian reasoning or models based on Bayesian reasoning. Rather, our point is that the same characteristics that make Bayesian reasoning work well for a committed Bayesian can make it fragile in the hands of a tentative Bayesian.

Probabilistic Reasoning

Our main result establishes conditions under which Bayesian reasoning is fragile. However, it does not imply that when the weight of the Bayesian conjectures becomes negligible (relative to the weight of all unrefuted conjectures), probabilistic reasoning will be forever discarded. Instead, case-based and rule-based reasoning may subsequently give way to a new probabilistic model. Specifically, if at history h t ϕ (B(h t )) is low (relative to, say, ϕ (CB(h t ))), it is still possible that at a certain continuation of h t , h t with t > t, the agent will again form beliefs that put a high weight on singleton hypotheses consistent with h t . As Proposition 1 indicates, this process is consistent with a single, history-independent ϕ.

The dynamics of our model can thus capture the type of reasoning raised in Section 1. Given a certain history h t above, the agent forms probabilistic beliefs that can be thought of as a Bayesian model given h t . Such beliefs cannot be guaranteed to assign a high probability to all eventualities. The agent may have failed to seriously consider certain black swans, and some of them will have very low probability. As a result, the agent may find herself at a point where she mistrusts her model, and resorts to case-based and rulebased reasoning in its stead. However, at some subsequent t > t , the agent beliefs may again effectively form a new probabilistic model.

It is easier to generate such "conditionally Bayesian" models than a single, a priori Bayesian model, for two related reasons: first, a model that starts at a history h t has to consider only a subset of the events that a comprehensive Bayesian model deals with. If the time horizon is finite, the number of states one needs to assign probability to decreases exponentially fast as t grows, which means that the probability assignment task becomes easier. Second, as t grows, there are more data on the basis of which such probability assignments may be done. Indeed, if one considers the Bayesian model, one has to assign probabilities to many states with no data at all, out of thin air as it were. By contrast, for sufficiently large t, the agent may find regularities in the data that may suggest a new probabilistic model for the remaining periods.

At the same time, any probabilistic model generated after some history h t will eventually face the same difficulty: whatever the finite history used for its formulation, it will become negligible relative to the size of the state space as one looks further into the future. Hence, one should expect that, apart from simple statistical problems, no probabilistic model will ever be the "correct" one. Rather, the agent will be cycling between periods in which she has a satisfactory probabilistic models, and periods in which black swans are observed and model uncertainty reigns. In such periods, case-based and rulebased reasoning are needed to make predictions, and, eventually, to formulate new probabilistic models.

To illustrate this, consider again the simplest example with no predicting variables, say, X = {0}, and Y = {0, 1}. Suppose that the agent believes that the data generating process on {0, 1} N follows a probabilistic model given by a measure ρ (defined on the standard σ-algebra on {0, 1} N ). However, certain periods in the past might have been exceptional -say, periods of wars, financial crises, and so forth. Hence, the agent does not believe that ρ is necessarily the appropriate probability measure to be assigned to Ω. She only believes that after a certain history, the continuation of the process will be governed by ρ. In other words, ρ is the conditional belief on Ω given a history h t (with conditional state space that is also {0, 1} N ).

Assume further that the agent does not presume that she can assign probabilities to the initial period, in which wars, financial crises, and the like disrupt her prediction. She does not pretend to have probabilistic beliefs over the length of time at which the process will finally stabilize and be govern by ϕ. Rather, she awaits to see periods of relative calm, in which y = 1, and she assigns weight to rules of the type "if y i = 1 for the last k periods, we may finally see the periods governed by ρ."

Let R k,s stand for the conjecture that, after the first time in which k consecutive 1's were observed, the process will follow a state s ∈ {0, 1} N . Explicitly,

R k,s =        ω ∈ Ω ∃t ω Y (i) = 1 t -k ≤ i < t ω Y (i) = s(i -t) t ≤ i (ω Y (i)) i<t-1 does not contain a sequence of k 1's        .
(Observe that R k,s ∩R k ,s may be non-empty for s = s if k = k . However, s = s does imply that R k,s and R k,s are disjoint for every k.)

Let us assume that the agent assigns to the conjectures {R k,s } s a total weight Q(k) = k -2 and that ρ, when applied to Ω, satisfies 2. The weight of the "rule-based" conjectures will be given by

ϕ({R k,s } s∈A ) = Q(k)ρ(A) for a measurable A ⊂ {0, 1} N .
Apart from these conjectures, the agent will be assumed to assign positive weight also to the case-based conjectures,

A i,t = {ω ∈ Ω | ω Y (i) = ω Y (t)} ,
and assume that their weight is

ϕ({A i,t }) = Q(t)/t
that is, that the total weight of the case-based conjectures at time t is Q(t) = t -2 and that this weight is divided equally among the periods preceding t. In particular, Assumption 3 holds.

Consider a history h t . Every sequence of 1's in it initiates a rule R k,s . However, since Assumptions 2 and 3 hold, the probabilistic reasoning embodied by the rules {R k,s } s,k≤t will give way to the case-based reasoning as in Proposition 2. To be precise, fix t and consider the reasoning at history h t with t > t. There are up to t different sets of conjectures {R k,s } s∈{0,1} N that affect the agent's reasoning in a probabilistic way, but since the weight of each of them decreases exponentially fast with t , in the long run the weight of all of them combined will be negligible relative to the weight of the case-based conjectures.

However, as t grows, new sets of conjectures {R k,s } s∈{0,1} N might join the game. Assume that t is large and that the longest sequence of 1's in h t is of length k << t. When, at some point, k + 1 1's are observed, the weight of the probabilistic reasoning in {R k+1,s } s∈{0,1} N will be Q(k + 1), and it will overwhelm the weight of the case-based reasoning, Q(t). Moreover, this phenomenon is likely to recur. Suppose, for the sake of the argument, that the true data generating process of y t is uniform (and iid). Considering a given length k, we may ask when will a sequence of k 1's will first appear. With very high probability, this will occur at time t which is exponentially larger than k. At such a history h t , the agent will reason mostly by the probabilistic reasoning ρ. Over time, when t > t grows, this probabilistic reasoning will decline in weight, but, with probability 1, new probabilistic models will be developed later on.

Thus, our framework may capture non-trivial dynamics between casebased and rule-based reasoning. Moreover, it can describe how probabilistic theories may be re-developed as history unfolds. Under the assumptions of Proposition 2, a prior distribution that has been formed at time t = 0 will have a negligible effect on reasoning in the long term. Yet, conditional probabilistic models might be re-formulated, capturing the agents beliefs that she can make probabilistic predictions from a certain time on.

Concluding Remarks

Methods for Generating Conjectures

In many examples ranging from scientific to everyday reasoning, it may be more realistic to put weight ϕ not on specific conjectures A, but on methods or algorithms that generate them. For example, linear regression is one such method. When deciding how much faith to put in the prediction generated by the OLS method, it seems more plausible that agents put weight on "whatever the OLS method prediction came out to be" rather than on a specific equation such as "y t = 0.3 + 5.47x t ."

One simple way to capture such reasoning is to allow the carriers of weight of credence to be sets of conjectures, with the understanding that within each set a most successful conjecture is selected for prediction, and that the degree of success of the set is judged by the accuracy of this most successful conjecture. The following example illustrates.

Suppose that the agent is faced with a sequence of datasets. In each dataset there are many consecutive observations, indicating whether a comet has appeared (1) or not (0). Different datasets refer to potentially different comets.

Now assume that the agent considers the general notion that comets appear in a cyclical fashion. That is, each dataset would look like 0, 0, ..., 0, 1, 0, 0, ..., 0, 1, ... where a single 1 appears after k 0's precisely. However, k may vary from one dataset to the next. In this case, the general notion or "paradigm" that comets have a cyclical behavior can be modeled by a set of conjecturesall conjectures that predict cycles, parametrized by k. If many comets have been observed to appear according to a cycle, the general method, suggesting "find the best cyclical theory that explains the observations" will gain much support, and will likely be used in the future. Observe that the method may gain credence even though the particular conjectures it generates differ from one dataset to the next.

Single-Conjecture Predictions

This paper is concerned with reasoning that takes many conjectures into account and aggregates their predictions. Alternatively, we may consider reasoning modes that focus on a most preferred conjecture (among the unrefuted ones) and make predictions based on it alone. For example, if we select the simplest theory that is consistent with the data, we obtain Wittgenstein's [40] definition of induction. [START_REF] Mcdermott | Non-monotonic logic I[END_REF] If, by contrast, we apply this method to casebased conjectures, we end up with nearest-neighbor approaches (see Cover and Hart [6] and Fix and Hodges [10, 11]) rather than with the case-based aggregation discussed here. Y ) are unrefuted and nontautological, and the total weight that they assign to a subset of outcomes Y is by construction c ht ϕ ht (A(h t , Y )). The coefficient c ht is chosen so that the total weight assigned by ϕ to all conjectures converges, which would be the case, for instance, if ht∈Ht c ht = t -2 .

Proof of Proposition 2

We start by showing that, because the ratio of weights assigned to specific histories of the same length t is bounded by a polynomial of t, the weight of each particular such history is bounded by this polynomial divided by an exponential function of t.

Consider a period t and a history h t . If ϕ(B(h t )) > η, then, since for every h

t , h t ∈ H t , ϕ(B(h t )) ≤ P (t)ϕ(B(h t )), for every h t , ϕ(B(h t )) ≥ ϕ(B(h t )) P (t) > η P (t) Observe that |H t | ≥ d t for d = |X||Y | > 1. Hence ϕ(B) > d t η P (t)
and ϕ(B) < 1 implies η < P (t) d t Since this is true for every η such that η < ϕ(B(h t )), we conclude that

ϕ(B(h t )) ≤ P (t) d t . (16)
We now turn to discuss the weight of the case-based conjectures that are relevant for prediction at h t . We wish to show that this weight cannot be too small. First, observe that the set of case-based conjectures is countable. Denote the total weight of the case-based conjectures whose second period is τ by S τ . Explicitly,

S τ = τ -1 i=0 x,z∈X ϕ ({A i,τ ,x ,z }) Then, ϕ (CB) = ∞ τ =1 S τ .
Choose T large enough so that

T τ =1 S τ > ϕ (CB) 2 . ( 17a
)
¿From now on, assume that t ≥ T . Consider a conjecture A (t-1),t,x,z ∈ CB and assume that ϕ A (t-1),t,x,z < ξ. By (13) (of Assumption 3) we have that, for all t < t, x , z ϕ A (t -1),t ,x ,z < ξQ(t).

By ( 14) (of that Assumption), we know that for all i < t < t, and all x , z ,

ϕ ({A i,t ,x ,z }) < ϕ A (t -1),t ,x ,z Q(t) < ξ [Q(t)] 2 .
The overall number of case-based conjectures whose second period is t ≤ t is |X| 2 t 2 . Since the weight of each is less than ξ [Q(t)] 2 we conclude that their total weight satisfies

T τ =1 S τ < ξ [Q(t)] 2 |X| 2 t 2
and, using (17a) we obtain

ϕ (CB) 2 < T τ =1 S τ < ξ [Q(t)] 2 |X| 2 t 2 . Define R(t) = 2 [Q(t)] 2 |X| 2 t 2
and observe that it is a polynomial in t. Thus, we have

ξ > ϕ (CB) R(T ) .
Since this holds for any ξ such that ξ > ϕ A (t-1),t,x,z , it has to be the case that ϕ A (t-1),t,x,z ≥ ϕ (CB) R(t) .

We observe that at h t there are precisely t case-based conjectures that are unrefuted and non-tautological, and among them there is one of the type A (t-1)t,x,z (that is, the one defined by x = ω X (t -1) and z = ω X (t)). It follows that

ϕ (CB(h t )) ≥ ϕ A (t-1),t,x,z ≥ ϕ (CB) R(t) . (18)
Combining ( 16) and ( 18) we obtain

ϕ (B(h t )) ϕ (CB(h t )) < P (t)R(t) ϕ(CB)d t
where the expression on the right clearly converges to 0 as t → ∞.

Appendix B: Belief Functions

This appendix is devoted to a brief introduction to Dempster-Shafer's Theory of Belief Functions, as well as its relationship to Choquet expected utility. It contains some definitions and well-known facts, as well as one result (Proposition 4) which is, to the best of our knowledge, new.

Capacities and Qualitative Capacities

Let there be a finite and non-empty set Y . Recall that in our model, Y denotes the outcomes that may be observed at each period.

The space of set functions on Y is defined by

V = v : 2 Y → R | v (∅) = 0 . A capacity is a set function v ∈ V that is monotone with respect to set inclusion, that is, that satisfies v (A) ≤ v (B) whenever A ⊂ B (for A, B ⊂ Y ), and that satisfies v (Y ) = 1. A binary relation ⊂ 2 Y ×2
Y is a qualitative capacity if (where denotes the asymmetric part of ) (i) is a weak order; (ii) is monotone with respect to set inclusion, that is, B A whenever A ⊂ B;

(iii) is a non-trivial: Y ∅.

A relation is persistently monotone, or p-monotone for short, if, for every S ⊂ T ⊂ Y , and every R ⊂ Y such that R ∩ T = ∅, if S ∪ R S, then T ∪ R T . This condition states that, if an event R makes a non-null marginal contribution to another event S, R will make a non-null marginal contribution to any larger event T (in the sense of set inclusion). Thus, p-monotonicity has the flavor of a condition of non-decreasing marginal contribution, stated in the ordinal language, which only allows us to distinguish between null and non-null marginal contributions. Observe that if one has a quantitative measure of marginal contributions by a capacity v, the nondecreasing marginal contribution condition would say that, for every S, T, R as above, v(T ∪ R) -v(T ) ≥ v(S ∪ R) -v(S), which is the familiar condition called convexity, super-modularity, or 2-monotonicity.

Another way to view p-monotonicity is provided by the following lemma. In all three conditions, (ii)-(iv), we have A ⊂ B and thus, by monotonicity, we know that B A. The additional condition of p-monotonicity says that if there is some evidence that B\A might occur-as implied by the antecedent of (ii), (iii), or (iv)-then B has to be strictly more likely than A. Clearly, the mapping M : V → V defined by M (v) = φ v is linear bijection from V onto itself, and so is its inverse M -1 . In particular, if a set of Möbius transforms C is convex, so is its corresponding set of set functions M -1 (C) and vice versa.

Möbius Transforms and Belief Functions

A capacity v is a belief function if and only if its Möbius transform is non-negative. Alternatively, one may define a set function v to be totally monotone if

v (A) ≥ B A (-1) |A|-|B| v (B)
for all A ⊂ Y , and define a belief function to be a totally monotone capacity. The bijection of the Möbius transform was first studied, to the best of our knowledge, by Shapley [36]. [START_REF] Nilsson | Probabilistic logic[END_REF] Dempster [9] introduced the concept of a belief function to capture the degree of belief in events without requiring additive probabilities (see also Shafer [35]). In Dempster's interpretation, v (A) is a measure of the total belief in an event A, whereas φ v (A) is a measure of the direct evidence for A itself, above and beyond any evidence for (proper) subsets of A.

Möbius transforms were more generally studied by Rota [31]. Generalizations to infinite state spaces were obtained by Gilboa and Schmeidler [15], and by Marinacci [22]. The former deals with representation using only "unanimity games" but cannot guarantee countable additivity of the representation (that is, of the measure that generalizes φ v above). Marinacci generalizes unanimity games to games defined on filters, and guarantees countable additivity on that space.

Representations

A capacity v ∈ V represents a relation ⊂ 2 Y × 2 Y iff, for every A, B ⊂ Y , A B ⇔ v(A) ≥ v(B)
We mention without proof:

Remark 1 A relation can be represented by a capacity if and only if it is a qualitative capacity.

We first prove the following proposition, and then explain how this identifies the binary relations ht that can be represented via credence functions via (1)- (2). Conversely, assume that is a p-monotone qualitative capacity. We wish to construct a belief function v that represents it. We will construct a totally monotone set function v that represents , and then (because, by the representation, we have v (Y ) > 0), this v can be normalized to be a belief function.

The basic idea of the proof is straightforward. Assume, first, that there are no ∼-equivalences (apart from the trivial ones), that is, that all equivalence classes are singletons. In this case, we order the events according to and assign to them weights φ v inductively. Thanks to monotonicity, all subsets of a set A appear before it in the ranking, and thus, when we come to set v(A), the total weight assigned to its proper subsets is already given, and we only need to make sure that φ v (A) is high enough to make v(A) larger than v(B) for any B that precedes A in the ranking. Notice that this proof does not rely on p-monotonicity of ; indeed, in the absence of ties, p-monotonicity is implied by monotonicity.

In the general case, however, an ∼-equivalence class may contain several sets, and, importantly, also sets A, B such that A ⊂ B. This means that one cannot assign a value to φ v (A) without also affecting v(B), which should still equal v(A). As a result the argument is a little more delicate, and makes use of p-monotonicity of .

Let (A 1 = ∅, A 2 , A 3 , ..., A 2 n = Y ) be an enumeration of 2 Y such that A i A i+1 for i < 2 n . Let the equivalence classes of ˜be (E 1 , ..., E K ) with E k = {A i } i∈E k where E k = {i k , ..., i k+1 -1} (with i k+1 ≥ i k +1). Clearly, if

A i ∈ E k and A i ∈ E k , then A i A i iff k ≥ k .
We will define v and φ v on ∪ k≤j E k , by induction on j = 1, ..., K, so that v represents on ∪ k≤j E k . Observe that, by monotonicity, if A i ∈ E k , and D ⊂ A, then D ∈ E k for k ≤ k. Hence the values of v on ∪ k≤j E k define those of φ v on ∪ k≤j E k and vice versa.

For j = 1, we define, for all A ∈ E 1 , φ v (A) = 0, which, by monotonicity, implies φ v (D) = 0 for every D ⊂ A and thus also v (A) = 0.

Assume, then, that v and φ v have been defined for ∪ k≤j E k , so that v represents on ∪ k≤j E k , and consider E k+1 . Let E k+1 = {A i } i∈E k+1 . For i ∈ E k+1 , let

α i = D⊂A i ,D / ∈E k+1 φ v (D) .
Thus, α i is a lower bound on the value v(A i ), obtained by the φ v already assigned to subsets of A i . All subsets D ⊂ A i such that D ≺ A i are included in the summation above, but there may be other subsets D ⊂ A i such that D ∼ A i (that is, D ∈ E k+1 ). We will define φ v (A i ) ≥ 0 so that, for all i ∈ E k+1 ,

v (A i ) = M k ≡ max i∈E k+1 α i + 1.
For a given i ∈ E k+1 , if A i is a minimal set (with respect to set inclusion) in E k+1 , set φ v (A i ) = M k -α i and otherwise (i.e., if there exists h ∈ E k+1 , h = i, such that A h A i )

φ v (A i ) = 0.
We now wish to show that, for every i ∈ E k+1 , v (A i ) = M k . Consider

Lemma 3

 3 Let be a qualitative capacity. The following are equivalent (i) is p-monotone: For every S ⊂ T ⊂ Y , and everyR ⊂ Y such that R ∩ T = ∅, if S ∪ R S, then T ∪ R T . (ii) For every A ⊂ B ⊂ Y , for every C ⊂ Y , if B ∩ C A ∩ C, then B A. (iii) For every D ⊂ A ⊂ B ⊂ Y , if D ∪ (B\A) D, then B A. (iv) For every A ⊂ B ⊂ Ω, for every E ⊂ B, if E A ∩ E, then B A.Proof. (i) implies (ii): Assume that is p-monotone and let there be givenA⊂ B and C. Define S = A∩C, T = A, and R = (B ∩ C) \A. Then S ⊂ T , R ∩ T = ∅. Since S ∪ R = B ∩ C A ∩ C = S we should also have T ∪ R T -where T ∪ R = A ∪ (B ∩ C) and T = A. By monotonicity, B A ∪ (B ∩ C) and thus B A. (ii) implies (iii): Given D ⊂ A ⊂ B ⊂ Y , set C = D ∪ (B\A), so that B ∩ C = D ∪ (B\A) and A ∩ C = D. Since D ∪ (B\A) D, we have B ∩ C A ∩ C, and B A follows. (iii) implies (iv): Given A ⊂ B ⊂ Ω and E ⊂ B, define D = A ∩ E. We know that E D. Clearly, E ⊂ D ∪ (B\A). Hence, by monotonicity, D ∪ (B\A) E D and B A follows. (iv) implies (i): Given S ⊂ T ⊂ Y and R ⊂ Y with R ∩ T = ∅, define A = T , E = S ∪ R, and B = T ∪ R. Then A ∩ E = S. We know that S ∪ R S and thus E A ∩ E. (iv) implies that B A, that is, T ∪ R T .

  Given a set function v ∈ V , we can define another set function byφ v (A) = B⊂A (-1) |A|-|B| v (B) .The set function φ v is referred to as the Möbius transform of v. We can represent a set function v ∈ V by its Möbius transform as as follows: for every A ⊂ Y , v (A) = B⊂A φ v (B) .

Proposition 4 A

 4 relation can be represented by a belief function if and only if it is a p-monotone qualitative capacity.Proof. Assume that v is a belief function that represents . By Remark 1, is a qualitative capacity. To see that it is p-monotone, let there be givenE ⊂ F ⊂ Y , and G ⊂ Y such that G ∩ F = ∅ and E ∪ G E. Hence v (E ∪ G) > v (E) and thus D⊂E∪G φ v (D) > D⊂E φ v (D) which means that there exists D ⊂ E ∪ G, D E such that φ v (D) > 0. Since D ⊂ E ∪ G we also have D ⊂ F ∪ G. However, D F because D ∩ G = ∅ and G ∩ F = ∅.This means that v (F ∪ G) > v (F ) also holds, and F ∪ G F .

  Define, for each h t and for every Y Y ,ϕ ({[h t , Y ] ∪ [h t ] c }) = c ht ϕ ht (A(h t , Y ))for every conjecture of the form{[h t , Y ] ∪ [h t ] c },and set ϕ(F) = 0 where F is the set of all conjectures that are not of this form, and c ht > 0 is to be determined. Observe that the conjecture [h t , Y ] ∪ [h t ] c is unrefuted (because it contains [h t , Y ], and hence is consistent with the observed history)and non-tautological (because Y Y )only at h t . Hence, at history h t , only conjectures of the form [h t , Y ] ∪ [h t ] c (with Y

	6 Appendix A: Proofs
	6.1 Proof of Proposition 1

In personal conversation, a hedge fund principal indicated that his fund used all three methods of reasoning introduced in this section in predicting the likelihood of mortgage defaults.

Indeed, Alquist and Kilian[START_REF] Alquist | What do we learn from the price of crude oil futures?[END_REF] find that the best prediction of the future price of oil is the current price.

The extension to infinite sets X and Y can be carried out with no major difficulties.

Note that this is the same σ-algebra generated by {[h t , Y ]} t≥0,ht∈Ht,Y ⊂Y and that it contains all singletons, i.e., {ω} ∈ A for every ω ∈ Ω.

Observe that the conjectures ∅ and Ω are never included in A(h t , Y ) for any Y Y . The impossible conjecture ∅ is not compatible with any history h t , whereas the certain conjecture Ω is tautological at every history h t .

There is no loss of generality in taking ϕ ht to be a probability measure, but it economizes on notation to refrain from imposing this normalization. For example, we thereby avoid the need to constantly make special provision for cases in which denominators are zero.

[START_REF] De | Sul Significato Soggettivo della Probabilità[END_REF] The weighting function ϕ ht is equivalent to a belief function in the Dempster-Shafer theory of evidence(Dempster [9], Shafer[START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]). See Appendix B for a brief introduction.

Recall that a conjecture A is an element of the σ-algebra A over the set of states Ω. An element of E is a set of conjectures, and hence is an element of a σ-algebra over the set 2 A of sets of states.

The collection E 0 contains every set of the form {ω}, but {{ω} |ω ∈ A } may be uncountable, and so must be explicitly included in the definition of the σ-algebra E. Doing so ensures, for example, that the set of Bayesian conjectures is measurable.

[START_REF] Fix | Discriminatory analysis. Nonparametric discrimination: Consistency properties[END_REF] In the process, the notion of compatibility needs to be adapted: whereas a single state ω is compatible with historyh t if ω ∈ [h t ], a (possibly multistate) conjecture A is compatible with history h t if A ∩ [h t ] = ∅.

Alternatively, if A predicts incorrectly during some of the first 100 periods, it will subsequently be excluded and hence this choice of ϕ ∅ will not interfere with further predictions.

The Dempster-Shafer updating rule, explained in Appendix B, is a special case of Dempster's rule of combination. We mention in passing that it does not suffer from common criticisms of the Dempster-Shafer theory, such as those leveled by Voorbraak[START_REF] Voorbraak | On the justification of Dempster's rule of combination[END_REF].

Bayesian reasoning appeared explicitly in the writings of Bayes[START_REF] Bayes | An essay towards solving a problem in the doctrine of chances[END_REF], with precursors from the early days of probability theory such as Bernoulli[START_REF] Bernoulli | Ars Conjectandi. Thurnisius[END_REF]. Beginning with the work of de Finetti and his followers, it has given rise to the Bayesian approach to statistics (see, for example, Lindley[START_REF] Dennis | Introduction to Probability and Statistics from a Bayesian Viewpoint[END_REF]). Relying on the axiomatic approach of Ramsey[START_REF] Frank | Truth and probability[END_REF], de Finetti[START_REF] De | Sul Significato Soggettivo della Probabilità[END_REF][START_REF] De | La prevision: Ses lois logiques, ses sources subjectives[END_REF], and Savage[START_REF] Savage | The Foundations of Statistics[END_REF], it has grown to become the dominant approach in economic theory and in game theory. The Bayesian approach has also made significant headways in computer science and artificial intelligence, as in the context of Bayesian networks(Pearl [27]). Within the philosophy of science, notable proponents of the Bayesian approach include Carnap[START_REF] Carnap | The Continuum of Inductive Methods[END_REF] and Jeffrey[START_REF] Jeffrey | Subjective Probability: The Real Thing[END_REF].

Analogical reasoning was explicitly discussed by Hume[START_REF] Hume | An Enquiry Concerning Human Understanding[END_REF], and received attention in the twentieth century in the guise of case-based reasoning (Riesbeck and Schank[START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF], Schank[START_REF] Roger | Explanation Patterns: Understanding Mechanically and Creatively[END_REF]), leading to the formal models and axiomatizations of Gilboa and Schmeidler[14,

[START_REF] Gilboa | A Theory of Case-Based Decisions[END_REF][START_REF] Gilboa | Inductive inference: An axiomatic approach[END_REF].[START_REF] Gilboa | A Theory of Case-Based Decisions[END_REF] See Akaike[START_REF] Akaike | An approximation to the density function[END_REF] and Silverman[START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF].

Relatedly, Matsui[START_REF] Matsui | Expected utility and case-based reasoning[END_REF] demonstrated that expected utility maximization and casebased decision theory lead to equivalent sets of feasible outcomes.

[START_REF] Jeffrey | Subjective Probability: The Real Thing[END_REF] Naturally, such a task requires additional assumptions on the structure of the prior probability.

For an easy illustration of this failure, observe that the ratio of the probabilities of a string of t successive 1's and a string of t successive 0's is (p/(1-p)) t , and hence exponential in t.

At the other extreme, suppose that only one Bayesian conjecture is given positive weight by ϕ. In this case, at time t, if this conjecture is still unrefuted, the agent might indeed wish to put an exponentially high relative weight on it, that is, to shrink the total

Observe that µ is defined over subsets of Ω (that are in Σ) whereas ϕ is defined over subsets of such subsets, and the assumption only deals with the subsets that contain only singletons {ω}. Observe also that Assumption 4 remains silent about the distribution of the x's.

Observe that these Bayesian beliefs can also be readily described as rule-based beliefs. We suspect that this is not a coincidence. When Bayesian beliefs violate Assumption 2, it is likely to be the case that they reflect some knowledge about the data generating process, which can also be viewed as believing in a class of rules.

See Solomonoff[START_REF] Ray | A formal theory of inductive inference I[END_REF], who suggested to couple this preference for simplicty with Kolmogorov complexity measure to yield a theory of philosophy of science. Gilboa and Samuelson[START_REF] Gilboa | Subjectivity in inductive inference[END_REF] discuss the optimal selection of the preference relation over theories in this context.

Set functions were used in the theory of transferable utility coalitional games. In this context, Shapley[START_REF] Shapley | A Value for n-Person Games[END_REF] showed that the unanimity games form a linear basis for the space of games, and that, when a game v is described as the linear combination of the unanimity games, φ v (B) is the coefficient of the unanimity game on B.

ERC Grant 269754 are gratefully acknowledged. National Science Foundation grant SES-0850263 is gratefully acknowledged.

first i such that A i is a minimal set in E k+1 . Obviously,

Next consider i such that A i is not a minimal set in E k+1 . Define

, then, by p-monotonicity and Lemma 3, A i B, which is known to be false because A i , B ∈ E k+1 (and thus

(Note that B i is a minimal set in E k+1 and thus φ v (B i ) has been defined above, while, for all C ∈ F i \ {B i } we have just defined φ v (C) = 0.) We wish to show that

In particular, D / ∈ E k+1 and this implies that D ∈ ∪ k≤j E k , and, by the induction hypothesis,

and by p-monotonicity and Lemma 3, A B, which is known not to be the case. We therefore conclude that -also in the case D / ∈ E k+1 -we have φ v (D) = 0. This concludes the proof that v

It remains to be noted that the function v thus constructed represents on ∪ k≤j E k+1 .

Observe that a corollary of this proposition is that a qualitative capacity (on a finite set) can be represented by a p-monotone capacity if and only if it can be represented by a belief function.

Every Y ⊂ Y corresponds to an event [h t , Y ] ∈ E 1 . Hence, for every history h t and p-monotone qualitative capacity, we can define a function ϕ ht that assigns weight to conjectures of the form [h t , Y ] (and to no other conjectures), so as to ensure that ϕ ht induces a belief function on 2 Y that represents ht . Conversely, any nontrivial, σ-additive measure on E induces a belief function on 2 Y , and hence represents a p-monotone qualitative capacity.

The predictions ht that can be represented by a credence function via (1)-( 2) are precisely those for which ht is a p-monotone qualitative capacity, for each h t .

Belief Updating

Dempster [9] defined the combination of two belief functions, designed to merge information from two sources. A special case of such a combination is the situation in which one source states that a certain event, B, has occurred. This piece of information is modeled by the belief function v such that φ v (B) = 1.

It is well-known that Dempster's rule of combination in this case becomes

which is known as the Dempster-Shafer updating rule for a capacity v. Clearly, if v is additive, this rule reduces to Bayesian updating. Gilboa and Schmeidler [13] approached the problem of updating capacities axiomatically, identifying reasonable axioms that characterize this rule.

Bayesian Beliefs

Assume that v is used for decision making via maximization of Choquet integration of a non-negative utility function u, as proposed and axiomatized in Schmeidler [34]. That is, decisions are taken so as to maximize

In this case, the decision maker maximizes expected utility (specifically, satisfies Savage's axiom P2) iff v is additive.