Samuel Marchal

Jérôme François

Cynthia Wagner

Thomas Engel

Semantic Exploration of DNS

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

DNS (Domain Name System) [START_REF] Mockapetris | Rfc 1035: Domain names -implementation and specification[END_REF] is critical for the well functioning of Internet as it is mainly used for locating a host in the Internet based on a human readable name. Service availability is improved by dynamic reallocation to another machine without changing the DNS name. However, this mechanism is also employed by attackers to improve the robustness and the efficiency of the attacks [START_REF] Perdisci | Detecting malicious flux service networks through passive analysis of recursive dns traces[END_REF]. Hence, DNS has recently gained interest from the security community and especially the naming scheme for discovering malware hosting domains [START_REF] Perdisci | Detecting malicious flux service networks through passive analysis of recursive dns traces[END_REF].

This paper focuses on DNS probing, i.e. guessing domains that are in use. This is an alternative to IP address scanning, which is fastidious and quite visible whereas DNS requests go through intermediate DNS servers, which hide the attackers. An attacker commonly uses dictionaries to probe existing domain names and aims to discover the networking organization, as well as potential vulnerable hosts. A common example is to check the hostnames of common services like FTP (File Transfer Protocol) or SSH (Secure Shell) by probing domains such as ftp.example.com. In [START_REF] Kamra | The effect of dns delays on worm propagation in an ipv6 internet[END_REF], the authors show that DNS scanning allow to identify potentially vulnerable IPv6 addresses quicker than with a classical random IP scanning due to the large address space, they apply this technique to ease the spread of worms in IPv6 Internet.

Thus, penetration testing and security assessment are based on an initial recon by discovering subdomains and hosts. With a proper DNS configuration, this cannot be gathered directly and therefore requires brute-forcing. In this paper, the DNS brute forcing tool is semantically extended since we have observed that human based names usually follow semantic schemes. This includes the word semantic as well as numerical semantics (series of numbers) of DNS names.

The paper is organized as follows. Section 2 presents DNS. An overview of the semantic exploration system and SDBF (Smart DNS Brute-Forcer) [START_REF] Wagner | Sdbf: Smart dns brute-forcer[END_REF] is given in section 3. Semantic extensions are covered in section 4. Our approach is assessed in section 5. Related work is presented in section 6 and conclusions are drawn in section 7.

DNS Background

To keep the paper self-contained, this is a short overview of DNS, but the reader may read [START_REF] Mockapetris | Rfc 1034: Domain names -concepts and facilities[END_REF][START_REF] Mockapetris | Rfc 1035: Domain names -implementation and specification[END_REF][START_REF] Mockapetris | Development of the domain name system[END_REF] for further explanation.

The main objective of DNS is to provide a map between human readable and remainable names to IP addresses. The organization of DNS is hierarchical with a root server at the top and dedicated authoritative servers for each subdomain. Assuming the domain name www.uni.lu, lu is the top level domain (TLD) which is the parent of all .lu subdomains (second level domain) including uni.lu. The third level domain is www.uni.lu. When a user needs the IP address of www.uni.lu, the first step is to query a recursive DNS server, usually maintained by his operator. This server is responsible to find the host by iteratively querying the authoritative servers of the subdomains. So, it starts by asking a root server which replies back with the DNS server in charge of the lu domain. The recursive DNS server of the client can also contact it to know, which server is in charge of uni.lu. Finally, when uni.lu is queried, it returns the IP address of www.uni.lu, which is then forwarded to the client by the recursive server.

DNS messages are mainly composed of Resource Records (RRs), which refers to different types of resolution. For the most common one the type is A or AAAA for getting the IPv4 or IPv6 address corresponding to a domain name. PTR are defined to enable inverse resolution (IP address to name).

A DNS name uses a dotted format to separate several components, i.e. a sequence of labels. In this paper, label i refers to the i th component, starting from the right. Thus, the top level domain is defined by label 0 . For example, www.uni.lu has three labels: label 0 = lu, label 1 = uni, label 2 = www. Even if a recent extension allows non-ASCII characters [START_REF] Faltstrom | Internationalizing Domain Names in Applications (IDNA)[END_REF], this paper doesn't consider them, as most of domains are still composed only of ASCII characters.

Exploration of DNS

System Overview

Our approach aims to automatically discover DNS names, and in particular, some subdomains of a domain by generating labels. Assuming a domain d, most of the current techniques rely on testing labels sequentially, l, stored in a dictionary (www, ns, ftp, smtp, etc. but also atlanta, boston, host, etc.) by concatenating the label l with the domain d to form a new subdomain l.d. In this paper, our prior tool SDBF [START_REF] Wagner | Sdbf: Smart dns brute-forcer[END_REF] is used to generate new names after a learning stage. Samples are required to learn how valid labels of domain names look like. They

(3)

(3') (4)
(5)

(6) (7) (8)
Fig. 1. System overview are collected through a passive DNS platform [START_REF] Weimer | Passive DNS replication[END_REF], which consists in monitoring and storing requests sent and replies received by a recursive DNS server. In our case, only valid names i.e. with valid DNS replies, are stored in a database.

Two key ideas have emerged from observations we made during our personal experience, as well as by mining the passive DNS database:

subdomains of the same domain are semantically related, in particular end hosts. For example, using planets, cities, countries, or character names of cartoons is a frequent habit of network administrators, a domain may present sequential patterns. For example, enumeration is a standard naming convention within a company or a university that leads to hostnames like room1-pc1, room1-pc2, room2-pc1, ns1, ns2, etc.

As shown in figure 1, the two main steps for discovering the DNS names are:

the construction of an initial list of names using SDBF [START_REF] Wagner | Sdbf: Smart dns brute-forcer[END_REF] (2) or a dictionary based-approach (3') the extension of that list by exploiting the semantics of names ( 5)-(8)

SDBF

Features The main features in SDBF are based on linguistic parameters. We assume an input list (1) of DNS names N = {n 1 , ..., n P }, a set of DNS label levels L = {l 1 , ..., l S }, a set of used characters C = {c 1 , ..., c M } and a set of n-grams, G x = {x 1 , ..., x T }.

The statistical features include: #wlen n -the number of DNS names with n labels, #wlen i,j -the number of labels of the i th level (with i ∈ L) having j characters, #f irstchar i,j -the number of labels at the i th level (with i ∈ L) starting with character j ∈ C and #ngram i,j,k -the number of times that a character j ∈ C is succeeded by k ∈ C at the i th level with i ∈ L.

These features are transformed into distributions as follows ((2) in figure 1):

the distribution for domain lengths (in label levels):

distwlen(X = j) = #wlen j k #wlen k (1)
the distribution of the lengths of labels (in number of characters) for a given level l:

distwlen l (X = j) = #wlen l,j k #wlen l,k (2)
the distribution of the first characters of labels for a given level l:

distf irstchar l (X = j) = #f irstchar l,j k #f irstchar l,k (3)
the N-gram distribution for a certain level l and a character c is given by:

ngram l,c (X = i) = #ngram l,c,i k ngram l,c,k (4)
N-gram Model: N-grams [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF] are successive character sequences of length n ∈ N, extracted from a string. For example, an n-gram with n = 2 is called bigram. Consider the following DNS name, test.uni.lu, bigrams can be: te, es, st, un, ni, lu... For generating the names of labels, the different estimated distributions are applied to a Markov chain. A Markov chain is defined for each label level, l, as a set of states S={s 1 ,s 2 ,...,s r } representing the characters that have been observed at this level. The probability of the transition between the two nodes representing by the two characters c i and c j is equivalent to ngram l,ci (X = c j ). By applying k steps, this model allows to generate a label of k characters.

An example for the n-gram model Markov chain is given in figure 2. This means, the probability that a character 'u' is followed by character 'n' is 0.4 and the probability that an 'i' is followed by another 'i' is only 0.2.

Name generation: Once the system is trained, SDBF can generate new names to probe, by first defining how long the new name should be in terms of number of labels. To achieve this, a random number following the distribution of number of labels, (distwlen), is generated. As SDBF is designed to be highly customizable, this value can also be set by the user. The same process is applied to determine the length of labels in characters for each label l to generate: distwlen l . Again, the user can set the value. Finally, for a label with a length k, the first character will be generated following the distribution of the first characters corresponding

n i !" #$%" #$&" #$'" #$(" #$)" #$*" +,-.," Fig. 2.
Markov chain for n-grams As the Markov chain is limited to a fixed set of transition, some transitions are not possible. For instance, if the bigram "sn" was never observed, the word "snt" could not be generated. To strengthen the discovery, we consider that a transition between any two pairs of characters is possible with a probility . For this, the other tansitions probabilities are slightly decreased to keep the sum of probabilities for outgoing transitions equal to one.

Because it is common usage to scan a domain, the user can set fixed parts for a domain. For example, the objective may be fixed to discover all domains following the *.uni.lu or ns.*.lu or www.*.*.

Once names are generated, (3) in figure 1, their existence is checked by the name checker (4), which makes a DNS query. This formally corresponds to a function valid(D) returning the valid domains of a set D.

Semantic extension

As illustrated in figure 1, the semantic module takes as input a list of names, where the validity has been checked [START_REF] Crawford | Kwyjibo: automatic domain name generation[END_REF]. The goal is to extend this list of discovered names by analyzing individual labels. There are two modules, DISCO and the incremental module that can be used individually or combined together, whereas the splitter module is an optional preprocessing step.

Similar names

The first semantic extension aims to discover names that are similar or related. These are distinct notions [START_REF] Budanitsky | Evaluating wordnet-based measures of lexical semantic relatedness[END_REF]. Similarity refers to words having a close meaning (for example, notebook and laptop). Semantic relatedness refers to words sharing the same semantic field like mars and venus, which are different planets. As claimed by Kilgraff et. al [START_REF] Kilgarriff | Thesauruses for natural language processing[END_REF], these usual notions impliy a manual analysis to establish relationships between words that limits its applicability and its extension to further language or semantic domain.

In this paper, we leverage DISCO (extracting DIStributionally related words using CO-occurrences) [START_REF] Kolb | Experiments on the difference between semantic similarity and relatedness[END_REF], which is based on an efficient and accurate method for approximating automatically (based on leanring samples) these two notions within one metric, called the similarity afterwards. DISCO considers the distance between two words within a window by defining ||w, r, w ||, the number of times the word w occur after r words after the word w, where -3 ≤ r ≤ 3. For example, table 1 represents windows centered on services. The window is moving along all the database samples to compute the counting that is transformed into frequencies, i.e. f (w, r, w ), by dividing by the total number of counted co-occurences for any ||w, r, w ||.

Intuitively, two words w 1 and w 2 are considered similar, if both of them have many co-occurrences with the same words, in particular, if the positions the latter regarding w 1 and w 2 are similar. DISCO uses the following definition, initially proposed in [START_REF] Lin | Automatic retrieval and clustering of similar words[END_REF]:

sim(w 1 , w 2 ) =
(r,w)∈T (w1)∩T (w2) I(w 1 , r, w) + I(w2, r, w)

(r,w)∈T (w1) I(w 1 , r, w) + (r,w)∈T (w2) I(w 2 , r, w)

where I(w, r, w ) is the mutual information between w and w [9] and T (w) all the pairs (r, w ) where I(w, r, w ) is positive. Assuming a domain d including the label l, the objective is to find similar labels l . The exploration goes into two directions. The first one is the horizontal exploration, which may be adjusted by lim h . This corresponds to select the most lim h similar words from DISCO. This result is set into a new set of labels Expl H (l, lim h ) which are tested by the Name Checker (figure 1) by concatenating with unmodified labels (other levels). By this, a new set is obtained, denoted by V alid(Expl H (l, lim h )).

The second exploration examines the vertical dimension by looking for additional similar names starting from this new set. The limit of the vertical explo-

position -3 -2 -1 0 +1 +2 +3 sample 1 a client
uses services of the platform sample 2 the platform provides services to the client ||services, -3,

a|| = 1 ||services, -3, the|| = 1 ||services, -2, client|| = 1 ||services, -2, platf orm|| = 1 ||services, -1, uses|| = 1 ||services, -1, provides|| = 1 ||services, 1, of || = 1 ||services, 1, to|| = 1 ||services,2,the|| = 2 ||services, 3, client|| = 1 ||services, 3, platf orm|| = 1 Table 1.
Example of co-occurrence counting (2 windows centered on services) ration is set by lim v and is defined by repeating the previous process lim v times with new discovered valid names:

Expl V (l, lim v ) =    ∅ if lim v = 0 l ∈Expl H (l,lim h ) V alid(Expl H (l , lim H )) if lim v = 1 l ∈Expl V (l,limv-1) V alid(Expl H (l , lim H )) otherwise (6)
In order to reduce the search space only validated labels are considered for further extensions, as noticed by the use of V alid in the equation [START_REF] Dagon | Global internet monitoring using passive dns[END_REF]. The vertical exploration stops once no new correct labels are found. So, lim v does not need to be manually set, which improves the easy use of our tool.

The vertical exploration is actually recursive and highlighted in figure 1 by the loop ( 5)-( 6)-( 7)- [START_REF] Hao | An internet wide view into DNS lookup patterns[END_REF]. Figure 3 represents a subset of a real probing by starting from the label surf, the horizontal exploration reveals unsuccessful (surfing, skate) and successful (rugby, soccer...) labels. Then, the vertical exploration entails a horizontal extension for each of the latter.

Incremental discovery

In many cases, machines and services are replicated and/or respect a systematic naming scheme as for example pc1, pc2, etc. Assuming that one of them has been discovered, the others can be generated by finding out the numerical components and using the following heuristic: test all possible values (including ) for each individual digit. This limits the exploration to a number of the same or of smaller power of ten (0 to 9 will in the previous example). Preliminary experiments have shown that increasing the search range to bigger numbers does not improve the results while, the overhead highly increases.

Splitter

Labels of DNS names can be composed of several words like linuxserver or linux-server. Applying DISCO on such names cannot provide any results since it performs over single words. Therefore, the labels have to be divided automatically in advance. Using a list of separating characters, as for instance "-" is too restricted and our tools refer to the word segmentation method described in [START_REF] Segaran | Beautiful Data: The Stories Behind Elegant Data Solutions[END_REF]. The process is recursive by successively dividing the label in 2 parts, to find the best combination, i.e. with the maximum probability, of the first word and the remaining part. Therefore, a label l is divided in 2 parts for each position i and the probability is computed:

P (l, i) = P word (pre(l, i))P (post(l, i)) (7)
where pre(l, i) returns the substring of l composed of the first i characters and sub(l, i) of the remaining part. P word (w) returns the probability of having the word W equivalent to its frequency in a database of text samples.

Additionally, the splitter modules can also discover the incremental part of a domain. A label like computer23 is split as computer and 23 which is helpful for the first step of the incremental process (see previous subsection). This may also detect non numerical increments, as observed in our database (servera, serverb, etc.), which can be incremented afterwards using ASCII codes.

Evaluation

Methodology

Assuming a domain d, dictionary based techniques probe by iterating over a set of labels, l, to form the hostname l.d. In the current evaluation, SDBF is configured similarly and two dictionary-based tools are also tested: Fierce1 and DNSenum2 . Both are included in Backtrack [START_REF]Backtrack linux -penetration testing distribution[END_REF], a Linux distribution designed for digital forensics and penetration testing. The dictionary from Fierce includes only 1 895 words, whereas the one from DNSenum includes 266 930 entries. Hence, SDBF was configured to generate as many labels as DNSenum. The reader should refer to [START_REF] Wagner | Sdbf: Smart dns brute-forcer[END_REF] for an evaluation of these tools without semantic extension. The main result is that SDBF and Fierce provide the best results, but all of them are complementary, i.e. they do not find the same names.

Based on the discovered names, new ones are probed using the semantic extensions with one of the following strategies:

-Similar names (DISCO) -Similar names (DISCO) + Splitter -Similar names (DISCO) + Splitter + Incremental discovery Except if mentioned, the last one is applied. The original databases provided with the semantic tools [START_REF] Kolb | Experiments on the difference between semantic similarity and relatedness[END_REF][START_REF] Segaran | Beautiful Data: The Stories Behind Elegant Data Solutions[END_REF], like Wikipedia3 , are used to train them.

The targeted domains in our experiment are extracted from the top 50 websites ranked by Alexa (www.alexa.com), where only 19 domains have been selected such as google.com, ebay.com, baidu.com... This selection discards domains performing wildcarding i.e. these domains will always respond positively to DNS requests regardless of the query. Furthermore, similar domains with different TLD have also been discarded, since hostname results are similar in this case. For example, google has no less than twelve domain names with different TLDs in the top 50 Alexa. We also choose five popular domains from Luxembourg including the one of our university (uni.lu) which is probed from internal network. All these domains are presented in figure 5.

Main metrics

In our experimental evaluation we consider Init i with i ∈ {SDBF, DN Senum, F ierce}, the initial list of discovered domains for each tool and we also define: For the evaluation, we present N ew i with i ∈ {SDBF, DN Senum, F ierce, overall} the set of new discovered domains thanks to every initial dataset Init i . Assuming |S| as the cardinality of a set S, the improvement is defined as:

Init overall = Init SDBF ∪ Init DN Senum ∪ Init F ierce (8)
%Imp i = |N ew i | |Init i | , i ∈ {SDBF, DN Senum, F ierce, overall} (9)
It represents the percentage of new discovered names regarding to the initial dataset. A significant value of %Imp i shows that our method is able to find new hostnames which previous methods have not found, even when they are combined.

Exploration Parameters

Horizontal search: The horizontal search may be configured by adjusting lim h , which limits the exploration to the top lim h similar words, as noticed in section 4. On the one hand, we can assume that the more words we have and test, the more hostnames we find. On the other hand, each DNS request is expensive in time and this may lead to the detection of the DNS probe. Figure 4(a) represents the evolution of the hostname discovery regarding lim h , which varies between 1 and 200. The plotted metric, ImpH i,h represents the proportion of new discovered names when lim h = h compared to lim h -1. Assuming %Imp i,h , the value of %Imp i when lim h = h, we define:

ImpH i,h = %Imp i,h if h = 1 %Imp i,h -%Imp i,h-1 otherwise (10)
Figure 4(a) shows that having an exploration limit higher than 40 words does not significantly improve the results. That is why we set lim h to 40 but, in case a deep domain investigation is required, by increasing it, it can still discover new names, as the curves are still positive. Besides, performances are equivalent, whatever the initial tool is. Vertical search: As our probing method is based on previous discovered hostnames, we can launch it over new hostnames, gathered by the different process iterations. This number of performed probes is called the vertical depth and fixed through lim v . The process also stops once no new generated names are valid (see section 4). In our case, this leads to a maximal number of 5 iterations. Figure 4(b) represents the ratio of discovered names compared to the maximum (lim V = 5). Between 55 and 80 % of the domain names are found in the first iteration and more than 95 % before the fourth one, so we can reasonably limit the probe to three iterations.

Gain evaluation

Figure 5 shows the result of our probe, made on 24 domain names using DISCO with the previously tuned parameters. Regarding the individual improvements, in many cases the number of discovered hostnames is doubled (%imp > 100) or even more. For instance with the original dataset from SDBF, the number of names related to domains, as go.com, msn.com or google.com, is increased by more than 100 %, moreover for ebay.com, we reach an improvement of more than 200 % for both, SDBF-and Fierce-based intialization. Similar results can be observed for DNSenum and the mean improvement over the 24 domains is between 84% and 102% as shown in Table 2.

Furthermore, this tool provides a real solution to discover new hostnames that existing solutions are unable to find, even if all the three other tools are combined (overall in table 2). For instance, a global improvement of 55% for ebay.com, 51% for google.com or 30% on the overall domains set is observed.

This proves the usefulness and accuracy of semantic exploration as the most common hostnames have already been discovered by one of the initial tools (SDBF, Fierce or DNSenum). From a domain name such as mars.pt.lu, merkur.pt.lu and jupiter.pt.lu have been found or from kangaroo.apple.com, we discover camel.apple.com, porcupine.apple.com and piglet.apple.com. Our first assumption deduced from observations that hostnames are attributed by human and by this, a semantic relation exists between hostnames, proves correct.

Strategy evaluation

As introduced in section 5.1, different strategies are tested by combing DISCO (SN -similar names), the splitter and the incremental modules. Figure 6 shows the efficiency of each startegy initialized with SDBF. We clearly see that Similar Names leads to discover the main part of new DNS names, as curves of other strategies mainly coincide with the one from Similar Names. The second observation is that Splitter provides few signs of improvement to Similar Names and Incremental Discovery (ID) brings some results, especially for the domain livejasmin.com. In fact through this method, the hostname news10.livejasmin.com leads to discover 31 new hosts (newsX with X ∈ {1; 9} ∪ {11; 32}). Therefore, the strategy has to be carefully chosen. For fast probing of many domains, only the DISCO based extension should be used, but if the objective is to probe deeply one domain, all of them to be combined, since each of them may improve the results.

Overhead

The overhead is defined as the number of additional DNS requests (#probes). As previously mentioned, SDBF and DNSenum require more than 250 000 DNS probes to produce their results. In Figure 7, we can observe that our method always needs to perform less than 100 000 DNS requests, but this discovery is based on a list established by a prior tool. The biggest probes are made for the biggest initial datasets (ebay.com, msn.com, baidu.com) but, half of the domains require less than 20 000 probes. Figure 8(a) shows that the Similar names module has a quite steady ratio of probes per initial name (between 200 and 500 requests). The efficiency of this module, as we can see in figure 8(b), is also steady, it discovers around 1 domain name for 200 probes. Other modules perform less requests than the previous one, as we can see in figure 8(a), but figure 8(b) shows that applying Splitter is less efficient than Similar names, whereas Incremental discovery needs to perform very few probes to discover new domains.

These results show that our method is far less expensive than initial ones (at least 4 times for SDBF or DNSenum) for approximatively discovering the same number of domain names (section 5.4). As a basis the Similar names module should be used, which provides the steadiest results although, the efficiency of the other tools is dependent of the targeted domain.

Related work

In DNS research, major works deal with the detection of DNS attacks as for example, fast-flux, spamming, anomalies in DNS traces,... and present mots various defensive measures for these threats. Statistical evaluation is used in [START_REF] Antonakakis | A centralized monitoring infrastructure for improving dns security[END_REF], respectively whitelists and classifiers are referred to, to detect anomalous patterns in RR data for rervealing poisoning attacks. The authors in [START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF] describe a large-scale passive DNS tool, where features are used to detect anomalies, as for example euclidean distances between entries to identify changes in the lifetimes of domains, etc. In [START_REF] Perdisci | Detecting malicious flux service networks through passive analysis of recursive dns traces[END_REF], suspicious flux networks are detected by passively capturing DNS traffic. The data evaluation is based on the Jaccard index, similar to [START_REF] Hao | An internet wide view into DNS lookup patterns[END_REF]. To classify the services, the authors refer to supervised learning, where the C4.5 algorithm is used to separate malicious flux and benign services. In [START_REF] Plonka | Context-aware clustering of dns query traffic[END_REF], the authors perform analysis and visualization of DNS traffic in different modes, off-line, near-real-time and real-time by combining aggregation to clustering. In [START_REF] Dagon | Global internet monitoring using passive dns[END_REF], the authors show that regular expressions improve filtering capabilities for malicious domain detection and provide more accurate results than black-lists.

In this paper, a more semantic approach is used to explore domains in the Net. Natural language processing (NLP) techniques emerged in the research areas of forensics and security. In [START_REF] Crawford | Kwyjibo: automatic domain name generation[END_REF], an automatic domain name generator is constructed by combining different NLP techniques, as for example by using a syllable to construct new passwords or usernames. A major difference to this work is, in [START_REF] Crawford | Kwyjibo: automatic domain name generation[END_REF] full words are generated. By using different statistical tools, as Kulback-Leibler divergence or Levenshtein edit distances, domain names related to botnets can be detected [START_REF] Yadav | Detecting algorithmically generated malicious domain names[END_REF]. In the same context of generating new passwords is the work presented in [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF]. Here, a new approach relying on probabilistic context-free grammar is used to generate rules in order to crack passwords.

Conclusion

In this paper, DNS brute forcing tools are enhanced by using semantics, i.e. the average improvement is higher than 80%. When combined with SDBF, the tool only needs a passive DNS database and a set of text samples like Wikipedia. Hence, it may easily be applied and it can be continuously reinforced since the previous databases are continuously evolving. Depending on the context, this paper has assessed the benefit of different strategies, as well as the implied overhead. Future work will deal with distributed probing.

Fig. 3 .

 3 Fig. 3. Example semantic exploration from surf.apple.com

Fig. 4 .

 4 Fig. 4. Vertical and horizontal depth analysis (average overall domain)

Fig. 5 .

 5 Fig. 5. Efficiency of semantic exploration

Fig. 6 .Fig. 7 .

 67 Fig. 6. Efficiency of the different semantic extension when initialized with SDBF Fig. 7. Number of probes per domain to discover |N ewi|

( a )Fig. 8 .

 a8 Fig. 8. Ratio of probes due to each individual module

Name Statistics a v l Markov Chains + SDBF Input Data: www.example.com www.uni.lu ... Generated names: ns1.bluemoon.lu pluton.uni.lu officehost.net.com fake.uni.lu ... DNS server DISCO Word Splitter Hostname Dictionary 1234... Increment Module Name Checker DNS Lookups Valid names: ns1.bluemoon.lu pluton.uni.lu officehost.net.lu ... + + Semantic module New Generated names: ns2.bluemoon.lu mars.uni.lu workhost.net.com ... (1)

Table 2 .

 2 Probing results -top 10 and over all domains

			SDBF			Fierce			DNSenum		Overall
	Domains	|Init| |N ew| %Imp |Init| |N ew| %Imp |Init| |N ew| %Imp |Init| |N ew| %Imp
	livejasmin.com 24	39	162	20	14	70	18	14	77	37	33	89
	ebay.com		284	230 115 257	223 185 225	121 284 158	55
	google.com	69	125	181	84	87	103	83	108	130 149	77	51
	vdl.lu	15	15	100	11	13	118	16	12	75	23	11	47
	amazon.com	78	82	105	55	72	130	75	75	100 132	52	39
	msn.com	207 281	135 196 246	125 236 223	94	372 140	37
	baidu.com	369 243	65	178 280	157 238 253	106 478 157	32
	microsoft.com 115 121	105	91	90	98	97	98	101 189	56	29
	apple.com	141 128	90	65	116	178 130 106	81	241	70	29
	ask.com	88	82	93	78	65	83	79	71	89	135	40	29
	all domains 2057 1739	84 1520 1558 102 1788 1565	87 3170 954	30

http://ha.ckers.org/fierce/

http://code.google.com/p/dnsenum/

http://www.wikipedia.org


I Xausa

R Baier

M Gerdts

M Gonter

C Wegwerth

AVOIDANCE TRAJECTORIES FOR DRIVER ASSISTANCE SYSTEMS VIA SOLVERS FOR OPTIMAL CONTROL PROBLEMS *

Keywords: sensitivity analysis, direct discretization methods, optimal control, reachable sets AMS subject classifications. 90C31, 49K40, 49M37

Avoidance trajectories for driver assistance systems is an important and active field of research in car industry. Assistance systems with active braking maneuvers rely on car models, e.g. the single-track model, which are modeled as control problems. The formulation of suitable objective functions serves as a tool to realize collision detection and avoidance. In two scenarios for overtaking maneuvers, an optimal trajectory is computed via fixing a secure target state or by computing reachable sets from the initial starting point. First numerical experiments show approximations to optimal trajectories, controls and reachable sets. The sensitivity analysis in both, the optimal trajectory and the reachable set, reveal parameters that significantly influence the solution.

1. Scenarios for Avoidance Trajectories. Over the years many passive and active safety systems have been developed for modern passenger cars with the aim to reduce the number of casualties in traffic accidents. In contrast to passive safety systems (chassis, airbags, seat belts), semi-active safety systems and driver assistance systems become active in critical situations before an accident occurs and intend to prevent accidents. Next to the required technical devices, intelligent software systems and algorithms play a crucial role. Future developments in active steering are one of the motivations for the study here presented. In this view the main tasks are to reliably indicate future collisions and -if possible -to provide escape trajectories if such exist. Such investigations are modeled as optimal control problems where the chosen car model and the scenario play a central role.

A simplifying assumption in this paper made to derive the single-track car model (a detailed presentation is provided in [START_REF] Gerdts | A variable time transformation method for mixed-integer optimal control problems[END_REF]) is that the rolling and pitching behavior of the car body can be neglected, that is, the roll angle and the pitch angle are small. These assumptions justify the replacement of the two wheels on the front and rear axle by a virtual wheel located in the center of the respective axle. Furthermore, due to the simplifying assumptions it can be presumed that the car's center of gravity is located on the roadway and therefore, it is sufficient to consider the motion of the car solely in the horizontal plane. The car model includes the two control variables u := (w δ , F B ) with control bounds

w δ,min ≤ w δ ≤ w δ,max (steering velocity), F B,min ≤ F B ≤ F B,max (braking force). (1.1)
Note that negative values of F B stand for acceleration and positive values specify braking. The vector z of the state variables consists of the car's center of gravity (x, y), yaw angle ψ, yaw angle rate w ψ , velocities x = v x and y = v y in x-and ydirection, respectively, steering angle δ, that is z = (x, y, ψ, v x , v y , w ψ , δ) . The state dynamics z (t) = f (z(t), u(t)) for a.e. t ∈ [0, t f ] is given by the following system of differential equations

       x = (F x cos(ψ) -F y sin(ψ)) /m, y = (F x sin(ψ) + F y cos(ψ)) /m, ψ = ( f F sf cos(δ) -r F sr + f F f sin(δ)) /I zz , δ = w δ . (1.2)
Herein, m, I zz , f , r are constants and F x , F y , F sf , F sr , F f , F r are nonlinear functions of the state z, which are subject to the state constraints

(F sf , F f ) ≤ F max,f , (F sr , F r ) ≤ F max,r (Kamm's circle). (1.3)
As a first step we look at two model scenarios which are easier than other ones, like cross traffic scenarios, that will be investigated in the future. For both scenarios a secure final state is defined by the following boundary constraints ensuring that the avoiding car at t f moves parallel to the x-direction of the road:

v y (t f ) = 0, ψ(t f ) = 0. (1.4)
Moreover, we need to impose a state constraint so that the car stays on the road:

road down + width car 2 ≤ y(t) ≤ road up - width car 2 . (1.5)
Herein, road down , road up , and width car are given constants.

Scenario 1: A stationary obstacle located at the position (x obstacle , y obstacle ) on the road relative to the avoiding car, which drives at a prescribed speed, has to be avoided: avoiding car stationary obstacle Within this scenario a secure region for the y-coordinate at the car's terminal position is given by y(t f ) ≥ y target := y obstacle + width obstacle 2 + width car 2 + 0.3, (1.6) where 0.3 is a safety margin and y obstacle and width obstacle are constants. The avoidance maneuver terminates if x(t f ) = d, where d is either fixed or an optimizable parameter indicating the initial distance between avoiding car and obstacle.

Scenario 2: An overtaking maneuver on a rural road is considered. The avoiding car has initiated the overtaking maneuver for obstacle 1 next to it with some relative velocity, while another car (obstacle 2) is blocking the opposite direction. Here a safety region for the avoiding car is characterized by the following state and boundary constraints:

(x(t), y(t)) -(x obstacle1 , y obstacle1 ) ≥ length obstacle2 2 + length car 2 + 0.3, (1.7) y(t f ) ≤ y target := y obstacle2 - width obstacle2 2 - width car 2 -0.3. (1.8)
Herein, x obstacle1 , y obstacle1 , length obstacle2 , length car , y obstacle2 , width obstacle2 are given constants. The avoidance maneuver terminates if x(t f ) = d 2 , where d 2 is either fixed or an optimizable parameter indicating the initial distance between avoiding car and obstacle 2. Likewise d 1 denotes the fixed or optimizable initial distance of the avoiding car to obstacle 1.

Let q denote d (Scenario 1) or (d 1 , d 2 ) (Scenario 2), respectively, in case these parameters are not fixed but optimizable. The resulting optimal control problems (OCPs), which model the two scenarios, have the following structure (the objective function will be specified in Section 2):

min ϕ(z(t f ), t f , q) + t f 0 f 0 (z(t), u(t))dt s.t. (1.1)-(1.5), given initial state z(0) = z 0 , (1.6) and x(t f ) = d for Scenario 1 resp. (1.7)-(1.8) and x(t f ) = d 2 for Scenario 2.
(1.9)

2. Computational Approaches for Avoidance Trajectories. Once an obstacle has been detected by suitable sensors (e.g. radar, lidar), the following approaches can be used to decide in the model whether a collision is going to happen or not.

Approach 1: Compute an (optimal) trajectory to a secure final state. The objective function is a linear combination of the final time t f , the steering effort, and q, that is

ϕ(z(t f ), t f , q) + t f 0 f 0 (z(t), u(t))dt = c 1 t f + c 2 q + c 3 t f 0 w δ (t) 2 dt with appropriate constants c 1 , c 2 , c 3 ≥ 0.
Since sometimes it is not clear whether a collision can be avoided at all, a constraint violation minimization technique is employed, for instance the function in equation (1.7) is maximized instead of being a hard state constraint.

The role of the steering effort term in the objective function is to calculate a driver friendly trajectory. This becomes clear whenever we look at the controls in Figure 2.1, where the task was to minimize the steering effort with fixed distances, i.e. c 1 = c 2 = 0, c 3 = 1. The controls appear to be more regular than in Figure 2.2, where the task was to minimize initial distances, i.e. c 1 = c 3 = 0, c 2 = 1.

The minimization of the initial distances represents the last point where the avoiding car can still avoid the collision. Figure 2.2 shows that the trajectory is shorter than that trajectory where the initial distance is not minimized, see Fig. Approach 2: Compute (projected) reachable set from initial position. The reachable set is characterized by distance functions of certain grid points g h in state space. For each grid point g h in some bounding box containing the reachable set, an OCP is solved via the minimization of the distance of the endpoint z(t f ) of a trajectory to g h plus a regularization term involving the steering effort.

Let ẑ(t f ; g h ) denote the endpoint of the optimal trajectory which is close to some grid point g h and has initial value z(0) = z 0 . An approximation of the reachable set is then given by the union of all grid points g h sufficiently close to ẑ(t f ; g h ),

R h (t f ) ≈ g h : ẑ(t f ;g h )-g h ≤Ch {g h }, C > 0 suitable, (2.1)
i.e. those belonging to an O(h)-neighborhood of g h , see [START_REF] Baier | A computational method for non-convex reachable sets using optimal control[END_REF][START_REF] Baier | Approximation of reachable sets using optimal control algorithms[END_REF].

The reachable sets and the trajectory funnels are calculated for an initial velocity of v = 35m/s in Figure 2.3. The dotted points of the reachable set correspond to different free final times. Due to the initial speed and the end conditions (1.4), no other grid points from the dashed bounding box can be reached by the avoiding car. 3. Sensitivity Analysis. In case of errors in the initial state owing to sensor we intend to perform a sensitivity analysis for this specific problem to study the influence of parameters on the solution (trajectory and controls) and on the reachable set of the perturbed OCP.

Sensitivity in Optimal

Trajectory. With regard to the optimal trajectory we study problem (1.9) subject to the differential equation z (t) = f (z(t), u(t)) and the perturbed initial value given by z(0) = (x(0), y(0), ψ(0), v x (0), v y (0), w ψ (0), δ(0)) =: (x 0 (p), y 0 (p), ψ 0 (p), v x,0 (p), v y,0 (p), w ψ,0 (p), δ 0 (p)) =: (p 1 , p 2 , p 3 , p 4 cos(p 3 ), p 4 sin(p 3 ), 0, 0, 0) =: z 0 (p).

(3.1)

The perturbation parameter p = (p 1 , . . . , p 4 ) models sensor perturbations that enter the mathematical model owing to measurement errors in the initial values. The vector p is used for sensitivity analysis and will denote perturbation parameters that enter the problem, but are not optimized.

Let L ∞ ([0, t f ], R nu ) × R np (u, p) → z(u, p)(•) ∈ W 1,∞ ([0, t f ],
R nz ) denote the control and parameter to state mapping, which maps a given control u and a given parameter p to the corresponding state trajectory z(u, p). The aim is to investigate the dependence of the solution with respect to p with two different approaches: Approach 1: Fiacco-Sensitivity. The first approach called Fiacco-Sensitivity is based on a parametric sensitivity analysis of the optimal solution of the optimal control problem (1.9) with respect to p, compare [3, Section 3.2 and 4.2]. To this end let û = û(p) and ẑ := z(û(p), p) denote the optimal solution of the optimal control problem (1.9) with (3.1) for a nominal parameter p. Then, the Fiacco These sensitivities can be computed using the linearized necessary Karush-Kuhn-Tucker conditions in an optimal solution (ẑ, û). An approximation to the optimal perturbed trajectory is given by

z(û(p), p)(•) ≈ ẑ(•) + dz dp (û, p)(•)(p -p). (3.3)
An example of Fiacco-perturbed trajectories according to (3.3) with respect to parameter p i , i = 1, . . . , 4, is presented in Figure 3.1. The six trajectories depicted in each picture show the nominal trajectory and its perturbation with respect to p 1 , . . . , p 4 and w.r.t. all parameters combined. We see that a perturbation p 3 in the yaw angle has the largest influence on the trajectory. Perturbations of the initial position and velocity do not have significant influence on the trajectory. The two pictures in the first row show Scenario 1 with a perturbation of -0.1 and 0.1, respectively. The two pictures in the second row show Scenario 2 with a perturbation of -0.1 and 0.1, respectively.

Approach 2: ODE-Sensitivity. The second approach called ODE-Sensitivity investigates the dependence of the solution of the initial value problem on p for a fixed (optimal) control û and the nominal parameter p. To this end let û = û(p) be given and let ẑ := z(û, p) denote the corresponding solution of the initial value problem

z (t) = f (z(t), û(t)), z(0) = z 0 (p).
Then, the ODE-Sensitivity of the state is defined as

S(•) := ∂z ∂p (û, p)(•).
Note that this is just the partial derivative of the state mapping w.r.t. p for a fixed control and not the total derivative as in (3.2). An approximation to the perturbed trajectory is obtained similar as in (3.3). The ODE-Sensitivity is given by solving the sensitivity differential equation

S (t) = f z (ẑ(t), û(t))S(t), S(0) = dz 0 dp (p).
An example of ODE-perturbed trajectories with respect to each parameter p i , i = 1, . . . , 4, is illustrated in Figure 3.2. The six trajectories depicted in each picture show the nominal trajectory and its perturbation with respect to p 1 , . . . , p 4 and w.r.t. all parameters combined. We see that a perturbation p 3 in the yaw angle has the largest influence on the trajectory. Perturbations of the initial position and velocity do not have significant influence on the trajectory. The two pictures in the first row show Scenario 1 with a perturbation of -0.1 and 0.1, respectively. The two pictures in the second row show Scenario 2 with a perturbation of -0.1 and 0.1, respectively. In Scenario 1 a crash occurs whenever we have negative perturbation, in this specific case in parameter p 3 . In Scenario 2 for negative or positive perturbation of parameter p 3 the car violates the state constraint (1.5).

Sensitivity in Trajectory Funnels and Reachable Sets.

A method to investigate the dependence of the reachable set on p uses the optimal control approach for reachable sets shown in Approach 2. We can perform a sensitivity analysis of the corresponding optimal control problem w.r.t. the perturbation parameter p at the nominal parameter p for each of the optimal solutions ẑ(t f ; g h , p) with Fiacco-or ODE-Sensitivities. Hence, an approximation of the reachable set for p in (2.1) can be obtained by linearization during the calculation of the reachable set for the nominal parameter:

R h (t f , p) ≈ g h : ẑ(t f ;g h , p)+ẑ p (t f ;g h , p)(p-p)-g h ≤Ch {g h }, C > 0 suitable,
where ẑ p denotes one of the previously discussed Fiacco-or ODE-Sensitivities. Left pictures show the non-perturbed trajectories (nominal parameters), then the approximations by Fiaccoand ODE-Sensitivity with a positive perturbation of 0.1 w.r.t. all combined parameters (Scenario 1) and a negative perturbation of -0.1 w.r.t. all combined parameters (Scenario 2). The ODEsensitivity leads to bigger perturbations of the trajectory funnel for both scenarios than the Fiacco one. In the latter scenario even infeasible trajectories are created. Reachable sets for Scenario 1 (first row) and Scenario 2 (second row): Left pictures show the non-perturbed trajectories (nominal parameters), then the approximations by Fiacco-and ODE-Sensitivity with a positive perturbation of 0.1 w.r.t. all combined parameters (Scenario 1) and a negative perturbation of -0.1 w.r.t. all combined parameters (Scenario 2). The ODE-sensitivity leads to bigger perturbations of the trajectory funnel for both scenarios than the Fiacco one. In the latter scenario some points from the reachable sets are infeasible.

  2.1.

Fig. 2 . 1 .Fig. 2 . 2 .

 2122 Fig. 2.1. Scenario 1 (top row) and Scenario 2 (bottom row): Minimization of the steering effort. The frames in the pictures on the right indicate the avoiding car and the obstacles. Note the different scales in x-and y-direction.

Fig. 2 . 3 .

 23 Fig. 2.3. Figures in the first row concern Scenario 1, figures in the second row refer to Scenario 2.

  Fig.3.1. The six trajectories depicted in each picture show the nominal trajectory and its perturbation with respect to p 1 , . . . , p 4 and w.r.t. all parameters combined. We see that a perturbation p 3 in the yaw angle has the largest influence on the trajectory. Perturbations of the initial position and velocity do not have significant influence on the trajectory. The two pictures in the first row show Scenario 1 with a perturbation of -0.1 and 0.1, respectively. The two pictures in the second row show Scenario 2 with a perturbation of -0.1 and 0.1, respectively.

  Fig.3.2. The six trajectories depicted in each picture show the nominal trajectory and its perturbation with respect to p 1 , . . . , p 4 and w.r.t. all parameters combined. We see that a perturbation p 3 in the yaw angle has the largest influence on the trajectory. Perturbations of the initial position and velocity do not have significant influence on the trajectory. The two pictures in the first row show Scenario 1 with a perturbation of -0.1 and 0.1, respectively. The two pictures in the second row show Scenario 2 with a perturbation of -0.1 and 0.1, respectively. In Scenario 1 a crash occurs whenever we have negative perturbation, in this specific case in parameter p 3 . In Scenario 2 for negative or positive perturbation of parameter p 3 the car violates the state constraint (1.5).

Figures 3 . 3 - 3 . 4

 3334 show trajectory funnels, i.e. several solutions reaching different endpoints, and reachable set approximations for the two scenarios.

Fig. 3 . 3 .

 33 Fig.3.3. Trajectory funnels for Scenario 1 (first row) and Scenario 2 (second row): Left pictures show the non-perturbed trajectories (nominal parameters), then the approximations by Fiaccoand ODE-Sensitivity with a positive perturbation of 0.1 w.r.t. all combined parameters (Scenario 1) and a negative perturbation of -0.1 w.r.t. all combined parameters (Scenario 2). The ODEsensitivity leads to bigger perturbations of the trajectory funnel for both scenarios than the Fiacco one. In the latter scenario even infeasible trajectories are created.

Fig. 3 .

 3 Fig.3.4. Reachable sets for Scenario 1 (first row) and Scenario 2 (second row): Left pictures show the non-perturbed trajectories (nominal parameters), then the approximations by Fiacco-and ODE-Sensitivity with a positive perturbation of 0.1 w.r.t. all combined parameters (Scenario 1) and a negative perturbation of -0.1 w.r.t. all combined parameters (Scenario 2). The ODE-sensitivity leads to bigger perturbations of the trajectory funnel for both scenarios than the Fiacco one. In the latter scenario some points from the reachable sets are infeasible.

* This work has been supported by the European Union Seventh Framework Programme [FP7-PEOPLE-2010-ITN] under grant agreement 264735-SADCO.


Alfredo Di Tillio
email: alfredo.ditillio@unibocconi.it

Itzhak Gilboa
email: tzachigilboa@gmail.com

Larry Samuelson
email: larry.samuelson@yale.edu

Dov Samet

The Predictive Role of Counterfactuals *

The predictive role of counterfactuals

The Predictive Role of Counterfactuals 1 Introduction

A counterfactual is a conditional statement whose antecedent is known to be false. For example, "If the Iranian hostages had been released before the US presidential election in 1980, President Carter would have been reelected" and "Even if the Iranian hostages had been released before the US presidential election in 1980, President Carter would not have been reelected" are both counterfactuals.

Counterfactuals are common in everyday parlance and they seem to play an important role in the way people reason about social, economic, and political phenomena. It is somewhat surprising that people can reason about counterfactuals and come up with arguments about them that are acceptable to others. After all, counterfactual statements cannot be empirically validated. And yet, some counterfactuals appear to be more reasonable than others. For example, one may ask what would have happened had the US government rescued Lehman Brothers in 2008, and find that some predictions make more sense than others. Moreover, the ranking of such predictions appears to be relevant to predicting the consequences of future bail-out decisions. What is the mechanism that allows such reasoning? How does counterfactual reasoning help rational agents form beliefs and make predictions?

In this note we extend a model of belief formation to encompass counterfactuals. In the context of this model, we can ask how counterfactuals can be used for prediction. Specifically, suppose that history provides compelling evidence for the truthfulness of a counterfactual belief. In this case, this belief can be added to the set of observations, as if it were actually experienced, and thereafter used for further predictions. Our central result is that a logically omniscient agent finds no benefit in using this type of counterfactual reasoning to make predictions.

The next subsection is devoted to a clearer definition of the problems we are concerned with. It is followed by a brief description of some fields of study that deal with counterfactuals, attempting to place this note in the context of the literature. We then proceed, in Section 2, to present our model, building on the unified model of induction presented in [START_REF] Gilboa | Dynamics of Induction in a Unified Model[END_REF]. Section 3 deals with prediction with the aid of counterfactuals. The centerpiece of this section is the aforementioned impossibility result, showing that counterfactuals cannot add anything to a logically omniscient agent's predictive ability. Section 4 is devoted to a general discussion, and, in particular, to the extent to which counterfactuals can be valuable in enhancing the prediction of boundedly rational agents.

Modeling Counterfactuals

Our first task is to construct a model that will integrate counterfactuals with ordinary representations of non-counterfactual belief formation. Not all counterfactuals are created equal in this respect. It is helpful to consider three examples:

1. What would have happened had a person put her hand in the fire for several seconds?

2. What would have happened had President Bush, in September 2008, decided to save Lehman Brothers from bankruptcy?

3. What would have happened had the force of gravity not existed?1

All three counterfactual questions are similar in form and logical structure. But they differ in terms of our ability to reason about them. Question 1 is the simplest. Assuming that the person in question did not put her hand in the fire, we have no direct empirical evidence of what would have happened had she done so. But we have plenty of evidence regarding similar cases, as well as a rather good understanding of the underlying rules and mechanisms involved, so that we have no difficulty answering this question. This is the type of counterfactual question we routinely resolve when identifying the consequences of decisions in repeated, known contexts.

Question 3 is quite different. We have no empirical evidence from worlds remotely similar to ours without gravity. Everything we know in the natural sciences would have to be re-evaluated in order to answer this question. Question 3 is so difficult to reason about, that it does not pose a serious theoretical problem: the only reasonable answer is that we don't have any idea what would have happened in this case.

Question 2 represents an intermediate case. Like Question 3, we cannot claim to have a large database of similar situations whose outcomes were actually observed. The financial crisis of 2008 is a unique event in history. The crisis of 1929 may have many similar features, but the two are not identical, and other crises take us yet further afield. Moreover, financial crises are global events that cannot be isolated and studied independently of each other: the very fact that the crisis of 1929 occurred before that of 2008 had an effect on the course of the latter. To complicate things further, it is doubtful that we have figured out the rules that govern the behavior of the world economy to the same extent that we have understood the laws that govern fire and its effect on the human body. Question 2 thus cannot be answered with scientific certainty as can Question 1. Nonetheless, Question 2 is not a matter of science-fiction speculation as is Question 3. We have some ways of reasoning about the effects of financial bail-out decisions, and often allude to counterfactual bail-out cases when debating current policy.

We seek a model that can describe the generation of counterfactual beliefs, preferably in a way that is akin to the generation of non-counterfactual beliefs. As a test of reasonability, we would like the model to show how, with a reasonable choice of parameters, one gets (i) a more or less unique, deterministic answer to Question 1; (ii) complete ignorance when it comes to Question 3; and (iii) some intuitive though speculative reasoning about Question 2. Moreover, we would like the model to be able to describe how counterfactual beliefs, such as the answer to Question 2, might be updated as (factual) history unfolds, so that an agent might feel more or less confident about counterfactual statements given information that has been gathered while these statements were already known to be counter-factual.

We are then particularly interested in the way counterfactuals are used for prediction. There are situations in which counterfactuals appear to be useless, either because their consequents are too unclear, or because they do not add much to existing knowledge. For instance, Question 3 leaves too much room for speculation to be useful in prediction.2 On the other hand, Question 1 is easy to answer, but such an answer is likely to simply confirm predictions that already follow from factual observations. By contrast, Question 2 appears to be more interesting: it seems to lie in the middle ground where it is sufficiently familiar so that something can be said about it, and yet sufficiently novel so that reasoning about it would teach us something new.

Related Literature

Counterfactual reasoning comes in many forms, and it has been studied in different disciplines. The following is but a brief survey, highlighting the way our study merges with or differs from other approaches.

Philosophy. Starting with the work of [START_REF] Stalnaker | A Theory of Counterfactuals[END_REF] and [START_REF] Lewis | Counterfactuals[END_REF], philosophers and logicians have studied the logic of counterfactuals, distinguished among types of counterfactuals, and considered their semantics. The formal model we present here employs a state space and is thus semantic in nature. In contrast to the philosophy literature, however, we do not insist on a syntactic model of counterfactuals. Our focus is on the process by which counterfactuals help form beliefs. Finally, we deal only with one type of counterfactual, namely, with the beliefs one has at the present about the evolution of history along paths not taken.

Decision theory. The point of departure for decision theory is a function that maps combinations of acts and states into consequences. This function is typically taken to be so obviously basic as to be passed over without further notice. In practice, much of the work in making a decision (or in offering expert advice in support of a decision) revolves around identifying these consequences. Doing so requires counterfactual reasoning. When crossing a road one engages in reasoning by conditional statements of the type, "If I cross the road in front of the car, I will get hit", as well as "If I wait to cross until after the car has passed, I will be safe" and so forth. Once the decision has been made, all but one of such statements will linger in the agent's mind as counterfactuals. As is common in the philosophical literature, we will often refer to such statements as "counterfactuals" even before the truth value of their antecedent has been determined.

Any model of reasoning about decision making is thus also a model of reasoning about counterfactuals. Indeed, it is here that we gain most of our intuition about counterfactuals. Our suspicion that answers to Question 1 (in Section 1.1) will be useful while those to Question 3 will be useless arises out of thinking about how these questions will help us make decisions. However, our interest in counterfactuals is not motivated by the observation that people often remember the reasoning behind their decisions. Instead, we are motivated by the observation that counterfactual beliefs are often revised as additional observations are gathered, even after the antecedent is known to be false, and then used as inputs for subsequent belief formation. Thus, one might say, "Given my experience in the past 20 years, I believe that, had I chosen a different career, I would have been better off", and may utter this statement in the midst of advice about current choices. Put differently, one of the special features of counterfactuals is that our beliefs in them are continually updated and revised in light of new information, even after the conditional statement has been classified as counter -factual.

Psychology. Psychological studies suggest that counterfactual beliefs can have a significant impact on the way that actual outcomes are evaluated, and on the resulting affective reactions. In particular, the salience of alternative scenarios can play a role in the evaluation of actual ones. For example, Medvec, Maday, and Gilovich (1995) argue that Olympic bronze medal winners tend to be more pleased with their outcome than silver medal winners, because for the former the salient alternative consequence may be not to get a medal at all, whereas for the latter the salient alternative is often the gold medal. Specifically, the winner of a silver medal may engage in thinking along the lines of "Had I only done... I would have won the gold", whereas such counterfactual thoughts are less likely to burden the bronze medalist. Our focus is not on the emotional implications of counterfactual reasoning. Rather, we focus on the cognitive aspects, namely, how counterfactual reasoning is conducted and used.

Statistics. Statisticians often encounter a problem of missing data. Suppose there are multiple observations of variables {X 1 i , ..., X m i , Y i }, but certain variables haven't been measured in certain observations. Restricting attention to observations for which all variables have been measured wastes some of the information in the data, while working with all of the information gives rise to a collection of missing-variables difficulties. In response, missing data are "filled in" using techniques such as kernel estimation, and are then used for further analysis.

Counterfactuals play a similar role in forming beliefs. Indeed, one may argue that, broadly construed, each problem can embed the other. A missing datum could be viewed as an answer to the question "what would we observe if we were to measure that which we didn't?", and so questions about missing data can be couched as counterfactuals. Conversely, any counterfactual could also be viewed as an observation that one would have liked to have but doesn't. Specifically, we might observe the outcome of act a and wonder what would have resulted from other acts b, c... Each such act could be viewed as another observation, with different X values and with an unobserved Y value.

Despite the formal equivalence between "filling in" missing data and counterfactual reasoning, our focus here is quite different than that usually encountered in statistics. We are interested in cases in which an observation is counterfactual because the variables {X 1 i , . . . , X m i } did not occur, and therefore Y i was not observed. It is rarely the case in statistics that the "outcome", namely the dependent variable Y , is being conjectured for values of the dependent variables that also do not appear in the data.

History. Counterfactuals are essential to the study of history. For example, consider the statement, "If General McClellan had pursued his advantage at Antietem, the American Civil War have ended a year earlier". Professionals as well as laypeople analyze history by comparing actual scenarios to counterfactual ones, pointing to possible causal relationships, which are, in turn, used to learn from historical events and to make predictions. Yet, the use and interpretation of such counterfactual statements is controversial (cf. [START_REF] Bunzl | Counterfactual History: A User's Guide[END_REF]). The model we present below is most closely related to this use of counterfactuals, though it is clearly too theoretical to make a substantive contribution to the historical debate. Our model provides a theoretical framework for examining how people use counterfactuals, including (but not limited to) historical counterfactuals, to form beliefs and make predictions about likely outcomes in their current situation.

The Framework

The Unified Model

We adopt the unified model of induction of [START_REF] Gilboa | Dynamics of Induction in a Unified Model[END_REF]. 3 In each period, an agent makes predictions about the value of a variable y based on some observations x. She has a history of observations of past x and y values to rely on. We make no assumptions about independence or conditional independence of the variables across periods, or any other assumption about the data generating process.

Let the set of periods be T ≡ {0, 1, 2, . . . , T }. At each period t ∈ T there is a characteristic x t ∈ X and an outcome y t ∈ Y . The sets X and Y are finite and non-empty. 4 The set of all states of the world is

Ω = {ω : T → X × Y } .
For a state ω and a period t, let ω(t) = (ω x (t), ω y (t)) denote the element of X × Y appearing in period t. Let

h t (ω) = (ω(0), . . . , ω(t -1), ω x (t))
denote the history of characteristics and outcomes in periods 0 through t -1, along with the period-t characteristic, given state ω.

For a history h t , define

[h t ] = {ω ∈ Ω | (ω(0), . . . , ω(t -1), ω x (t)) = h t } .
Thus, [h t ] is the event consisting of all states that are compatible with the history h t . Similarly, for h t and a subset of outcomes Y ′ ⊂ Y , we define the event

[h t , Y ′ ] = {ω ∈ [h t ] | ω y (t) ⊂ Y ′ } ,
consisting of all states that are compatible with the history h t and with the next outcome being in the set Y ′ .

In each period t ∈ T, the agent observes a history h t and makes predictions about the period-t outcome, ω y (t) ∈ Y . A prediction is a ranking of subsets in Y given h t .

Predictions are made with the help of hypotheses. A hypothesis is an event A ⊂ Ω. A hypothesis can represent a theory, an association rule, an analogy, or in general any reasoning aid one may employ in predicting y t . Indeed, any such reasoning tool can be described extensively, by the set of states that are compatible with it. Let A denote the set of all hypotheses, and so A = 2 Ω .

The agent makes use of these hypotheses with the help of a model. Formally, a model is a function φ : A → R + , where φ(A) is interpreted as the weight attached to hypothesis A for the purpose of prediction. The function φ is extended to subsets of hypotheses additively.

Given a history h t , a hypothesis A that is disjoint from [h t ] (i.e., a hypothesis that has been refuted by h t ) should not be taken into consideration in future predictions. Fixing a history h t and a subset of outcomes Y ′ ⊂ Y , the set of hypotheses in A that have not been refuted by h t and that predict the outcome will be in Y ′ is:

A(h t , Y ′ ) = {A ∈ A | ∅ = A ∩ [h t ] ⊂ [h t , Y ′ ]} .
(1)

Observe that the hypotheses in A(h t , Y ′ ) are various events, many pairs of which may not be disjoint. Given a model φ : A → R + , the total weight assigned to the hypotheses that are unrefuted by h t and consistent with an outcome in Y ′ is thus given by φ

(A(h t , Y ′ )) = A∈φ(A(ht,Y ′ )) φ(A).
The agent's prediction is then a ranking of the subsets of Y , with Y ′ considered more likely than

Y ′′ if φ(A(h t , Y ′ )) > φ(A(h t , Y ′′ )).

Counterfactual Beliefs

We now extend the unified model to capture counterfactual beliefs. Assume that history h t has materialized, but the agent wonders what would happen at a different history, h ′ t ′ . We focus on the case

[h t ] ∩ [h ′ t ′ ] = ∅ in which, at h t , h ′ t ′ is indeed counter-factual.
A(h ′ t ′ , Y ′′ |h t ) = A ∈ A A ∩ [h t ] , A ∩ [h ′ t ′ ] = ∅ A ∩ [h ′ t ′ ] ⊂ [h ′ t ′ , Y ′′ ] . ( 2
)
If it is the case that [h t ] ∩ [h ′ t ′ ] = ∅ these beliefs will be referred to as counterfactual. 6 Observe that the hypotheses in A(h ′ t ′ , Y ′′ |h t ) are required to have a non-empty intersection with [h t ] and with [h ′ t ′ ] separately, but not with their intersection. Indeed, in the case of counterfactual conditional beliefs this intersection is empty.

Let us see how the definition given above captures intuitive reasoning in Questions 1-3 in the Introduction. Begin with Question 1, namely, what would happen to an agent who were to put her hand in the fire. The agent has not done so, and thus h t specifies the choice to refrain from the dangerous act. However, when the agent (or at outside observer) contemplates a different history, h ′ t ′ , in which the hand were indeed put in the fire, there are many hypotheses that suggest that the hand would burn. One such hypothesis is the general rule "objects put in the fire burn", which presumably received a positive φ value at the outset and has not be refuted since. 7 There are also many case-based hypotheses, each of which suggesting an analogy between the present case and a particular past case. Since in all past cases hands put in fires burned, each of these hypotheses suggests that this would be the outcome in the present case as well. In short, there is plenty of evidence about Question 1, captured in this framework both as general rules and as specific analogies, where practically all of them suggest the natural answer.

Consider now Question 3. What would have happened were gravity not to hold? There are many possible rules one can conjecture in this context, such as "without gravity no atoms would have existed" or "without gravity, only light atoms would have existed". However, in contrast to the rule "objects put in fire burn", none of these rules has been tested in the past, and they are all vacuously unrefuted. Thus, all of the conceivable rules remain with their original (and arbitrary) φ value, without the empirical mechanism allowing us to sift through the multitude of rules and find the unrefuted ones. Clearly, [START_REF] Gilboa | Dynamics of Induction in a Unified Model[END_REF], we do not deal here with probabilistic rules, though such an extension would obviously make the model more realistic.

6 If [h t ] ∩ [h ′ t ′ ] = ∅, then either h t and h ′ t ′ are identical, or one is prefix of the other. If h t is a prefix of h ′ t ′ , then A(h ′ t ′ , Y ′′ |h t ) = A(h ′ t ′ , Y ′′ ),

while the reverse inclusion gives

A(h ′ t ′ , Y ′′ |h t ) = A(h t , Y ′′ ). 7 As in
in this question analogical reasoning will be of no help as well. The history we observed consists only of cases in which gravity held. In this sense, all these cases are dramatically different from the hypothetical case in which gravity does not hold. Thus, a reasonable analogical reasoning would suggest that there is no similarity between the past and hypothetical cases to be able to generate a meaningful belief.

Finally, we turn to the interesting case of Question 2. In September 2008 the US government decided not to bail out Lehman Brothers. At that point, the actual history h t and the hypothetical one, in which the government decided otherwise, h ′ t ′ , part forever:

[h t ]∩[h ′ t ′ ] = ∅.
Yet, there are hypotheses A that are compatible with both, that is, that satisfy

A ∩ [h t ] , A ∩ [h ′ t ′ ] = ∅.
One such hypothesis may be the rule "When the government bails out all large financial institutions confidence in the market is restored". Let us assume, for the sake of the argument, that such a rule is well-defined and holds in the observed history h t . In this case, this rule will predict that, at h ′ t ′ , confidence in the market will be restored. Alternatively, one may point to a rule that says "The government bails out a small number of institutions, and thereafter begins a crisis", predicting that a bail-out would not have averted the crisis. Along similar lines, one may also use analogical reasoning to generate the belief given h ′ t ′ . For example, one case-based hypothesis holds that the problem of 2008 is similar to that of the previous year, and had the US government bailed out Lehman brothers, as it bailed out mortgage banks in 2007, the crisis would have been averted, as it was in 2007. Similarly, one might cite other cases in which a bailout did not avert a crisis.

Thus, counterfactual beliefs are generated by considering hypotheses that are simultaneously consistent with the observed and with the counterfactual history. In Question 1, practically all such hypotheses point to the natural conclusion: were the hand put in fire, it would burn. In our notation, φ(A(h ′ t ′ , {noburn}|h t )) = 0 whereas φ(A(h ′ t ′ , {burn}|h t )) > 0. In Question 3, there are no useful hypotheses to consult: no similar cases are known, and, relatedly, none of the conceivable rules one might imagine has been tested. Thus, the weight φ(A(h ′ t ′ , {y}|h t )) would reasonably be the same for any prediction y. (Indeed, it might be most reasonable to have a function φ for which this weight is zero.) By contrast, in Question 2, there are hypotheses with positive weights that have been tested in the actual history (A ∩ [h t ] = ∅) and that make predictions at the counterfactual history (A ∩ [h ′

t ′ ] = ∅). Some of them suggest that a bail-out would have averted the crisis, some suggest the opposite.

The relative weight assigned to these classes of hypotheses would determine the counterfactual belief.

Observe that our model can also explain how the belief in a counterfactual conditional statement changes as new evidence is gathered, even after the statement's antecedent is known to be false. For example, assume that John is about to take an exam, and decides to study rather than party. Having observed his choice, we may not know how likely it is that he would have passed the exam, had he decided to party. But if we get the new piece of information that he failed the exam, we are more likely to believe that he would have failed, had he not studied. In our model, this would be reflected by the addition of a new observation to the factual history t , which rules out certain hypotheses and thereby changes the evaluation of the counterfactual at h ′ t ′ .

Bayesian Counterfactuals

Gilboa, Samuelson, and Schmeidler (2010) define the set of Bayesian hypotheses to be

B = {{ω} |ω ∈ Ω } ⊂ A.
Each of the Bayesian hypotheses fully specifies a single state of the world. A Bayesian agent will satisfy

φ(A\B) = 0, that is, φ(A) = 0 if |A| > 1.
As discussed in [START_REF] Gilboa | Dynamics of Induction in a Unified Model[END_REF], this reflects the Bayesian commitment not to leave any uncertainty unquantified. A Bayesian agent who expresses some credence in a hypothesis (event) A, should take a stance on how this event would occur, dividing all the weight of credence in A among its constituent states.

The following is immediate (cf. ( 2)) but worthy of note.

Observation 1 If φ(A\B) = 0 then, whenever [h t ] ∩ [h ′ t ′ ] = ∅ φ(A(h ′ t ′ , Y ′′ | h t )) = 0 for all Y ′′ ⊂ Y .
Thus, a Bayesian agent has nothing to say about counterfactual questions. This result is obvious because a Bayesian agents assigns positive weight only to singletons, that is, to hypotheses of the type A = {ω}, and no such hypothesis can simultaneously be consistent with both h t and h ′ t ′ . Hence, the history that has happened, h t , rules out any hypothesis that could have helped one reason about the history that didn't happen, h ′ t ′ . Intuitively, this is so because the Bayesian approach does not describe how beliefs are formed, by reasoning over various hypotheses. Rather, it presents only the bottom line, that is, the precise probability of each state. In the absence of the background reasoning, this approach provides no hint as to what could have resulted from an alternative history. Indeed, Bayesian accounts of counterfactuals either dismiss them as meaningless, or resort to additional constructions, such as lexicographic probabilities.

Counterfactual Predictions

We now ask how counterfactuals can help make predictions, essentially by adding information to the agent's database.

Imagine an agent has observed history h t . In the absence of counterfactuals, she would make predictions by comparing weights of credence φ(A(h t , Y

(h ′ t ′ , Y ′′ | h t )
is nonempty only for Y ′′ = {y 0 }. Thus, the agent is certain that, had h ′ t ′ been the case, y 0 would have resulted. The counterfactual question posed by h ′ t ′ |h t is then analogous to Question 1 in Section 1.1, with an obvious answer. In this case, she can add the hypothetical observation [h ′ t ′ , {y 0 }] to her database, and continue to generate predictions based on the extended database, as if this observation had indeed been witnessed. This "extended database" cannot be described by a history, because no history can simultaneously describe the data in h t and in h

′ t ′ (recall that [h t ] ∩ [h ′ t ′ ] = ∅).
However, the agent can use both the actual history h t and the hypothetical observation [h ′ t ′ , {y 0 }] to rule out hypotheses and sharpen future prediction.

More generally, assume that the conditional beliefs φ(A(h ′ t ′ , Y ′′ | h t )) are positive only for a subset of outcomes Y 0 ⊂ Y and subsets thereof, i.e.,

φ(A(h ′ t ′ , Y 0 |h t )) > 0 (3) φ(A(h ′ t ′ , Y ′′ |h t )) > 0 ⇒ Y ′′ ⊂ Y 0 , (4)
so that the agent is absolutely sure that, had h ′ t ′ materialized, the outcome would have been in Y 0 . Thus, no other subset of Y competes with outcomes in Y 0 for the title "the set of outcomes that could have resulted had h ′ t ′ been the case". We are then dealing with a counterfactual analogous to question 2 in Section 1.1) (with the previous paragraph dealing with the special case in which Y 0 = {y 0 }). In this case the agent adds to the database the hypothetical observation that h ′ t ′ results in an outcome in Y 0 . Now the agent uses the information that history h t has occurred, and the counterfactual information that history h ′ t ′ would have resulted in an outcome from Y 0 , to winnow the set of hypotheses to be used in prediction. In particular, the hypotheses used the the agent include:

• All hypotheses that are consistent with h t but not with h ′ t ′ . Indeed, since h ′ t ′ did not materialize, it cannot make a claim, as it were, to rule out hypotheses that are consistent with observations.

• All hypotheses that are consistent with each of h t and h ′ t ′ , provided that they are consistent with the counterfactual prediction Y 0 (satisfying (3)-( 4)).

In other words, define the new set of hypotheses relevant for evaluating the set of outcomes Y ′ at history h t , given counterfactual information [h ′ t ′ ], to be

A(h t , Y ′ |h ′ t ′ , Y 0 ) = A ∈ A ∅ = A ∩ [h t ] ⊂ [h t , Y ′ ] A ∩ [h ′ t ′ ] ⊂ [h ′ t ′ , Y 0 ] . (5)
The agent then uses φ to rank the sets A(h t , Y ′ |h ′ t ′ , Y 0 ), for various values of Y ′ , and then to make predictions.8

Our model allows us to consider agents who are not Bayesian, but are nonetheless rational. This is important, as Observation 1 ensures that there is no point in talking about counterfactual predictions made by Bayesians. Indeed, we view the model as incorporating the two essential hallmarks of rationality: the consideration of all states of the world, capturing beliefs by a comprehensive, a priori model φ containing all the information available to the agent, and the drawing of subsequent inferences by deleting falsified hypotheses. An agent who is rational in this sense need not be Bayesian, which is to say that the agent need not consider only singleton hypotheses. In this case, counterfactuals are potentially valuable in making predictions.

Our result is that counterfactual reasoning adds nothing to prediction:

Proposition 1 Assume that [h t ] ∩ [h ′ t ′ ] = ∅ and that Y 0 satisfies (3)-(4). Then, for every Y ′ ⊂ Y , φ(A(h t , Y ′ )) = φ(A(h t , Y ′ |h ′ t ′ , Y 0 )). ( 6
)
Predictions made without the counterfactual information (governed by φ(A(h t , Y ′ )) thus match those made with the counterfactual information (governed by

φ(A(h t , Y ′ |h ′ t ′ , Y 0 ))
. Thus, the counterfactual information has no effect on prediction. The (immediate) proof of this result consists in observing that, for Y 0 to include all possible predictions at h ′ t ′ , it has to be the case that, among the hypotheses consistent with h t , the only ones that have a positive φ value are those that are anyway in A(h t , Y ′ |h ′ t ′ , Y 0 ). 9 This result has a flavor of a "cut-elimination" theorem (Gentzen, 1934-5): 10 it basically says that, if a certain claim can be established with certainty, and thereby be used for the proof of further claims, then one may also skip the explicit statement of the claim, and use the same propositions that could be used to prove it to directly deduce whatever could follow from the unstated claim. Clearly, the models are different, as the cut-elimination theorem deals with formal proofs, explicitly modeling propositions and logical steps, whereas our model is semantic, and deals only with states of the 9 Formally, it is obvious that 4), it must be that φ(A) = 0.

A(h t , Y ′ |h ′ t ′ , Y 0 ) ⊂ A(h t , Y ′ ), since the first condition in the definition of A(h t , Y ′ |h ′ t ′ , Y 0 ) is precisely the definition of A(h t , Y ′ ). Suppose the hypothesis A is in A(h t , Y ′ ) but not in A(h t , Y ′ |h ′ t ′ , Y 0 ) ⊂ A(h t , Y ′ ). Then, from (5), it must be that A ∩ [h ′ t ′ ] is not a subset of [h ′ t ′ , Y 0 ]. But then, from (3)-(
10 We thank Brian Hill for this observation.

world and the events that do or do not include them. Yet, the similarity in the logic of the results suggests that Proposition 1 may be significantly generalized to different models of inference.

Discussion

4.1 Why do Counterfactuals Exist?

Proposition 1 suggests that counterfactuals are of no use in making predictions, and hence for making better decisions. At the same time, we find counterfactual reasoning everywhere. Why do counterfactuals exist? We can suggest three reasons.

Lingering decisions. Section 1.2 noted that counterfactuals are an essential part of connecting acts to consequences, and hence in making decisions.

The counterfactuals we encounter may simply be recollections of this prediction process, associated with past decisions. Before the agent knew whether h t or h ′ t ′ would materialize, it was not only perfectly legitimate but necessary for her to engage in predicting the consequences of each possible history. Moreover, if the distinction between h t and h ′ t ′ depends on the agent's own actions, then it would behoove her to think how each history would evolve (at least if she has any hope to qualify as rational). Thus, the agent would have engaged in predicting outcomes of both h t and h ′ t ′ , using various hypotheses. Once h t is known to be the case, hypotheses consistent with both histories may well still be vivid in the agent's mind, generating counterfactual beliefs. According to this view, counterfactual beliefs are of no use; they are simply left-overs from previous reasoning, and they might just as well fade away from memory and make room for more useful speculations.

New information. We assumed that counterfactual outcomes are "added" to the database of observations only when they are a logical implication of the agent's underlying model. However, one might exploit additional information to incorporate counterfactual observations even if they are not logical implications of the model φ. For example, as mentioned above, statisticians sometimes fill in missing data by kernel estimation. This practice relies on certain additional assumptions about the nature of the process generating the data. In other words, the agent who uses φ for her predictions may resort to another model, φ, in order to reason about counterfactuals. The additional assumptions incorporated in the model φ may not be justified, strictly speaking, but when data are scarce, such a practice may result in better predictions than more conservative approaches. In fact, our results suggest that such a practice may be useful precisely because it relies on additional assumptions.

It is, however, not clear that adding such "new information" is always rational. Casual observations suggest that people may support their political opinions with counterfactual predictions that match them. It is possible that they first reasoned about these counterfactuals and then deduced the necessary political implications from them. But it is also possible that some of these counterfactuals were filled in in a way that fits one's pre-determined political views. Our analysis suggests that the addition of new information to a database should be handled with care.

Bounded rationality. We presented a model of logically omniscient agents. While logical omniscience is a weaker rationality assumption than the standard assumptions of Bayesian decision theory, it is still a restrictive and often unrealistic assumption. Our agent must be able to conceive of all hypotheses at the outset of the reasoning process and capture all of the information she has about these hypotheses in the function φ. Nothing can surprise such an agent, and nothing can give her cause to change her model φ as a result of new observations. Given the vast number of hypotheses, this level of computational ability is hardly realistic, and it accordingly makes sense to consider agents who are imperfect in their cognitive abilities. For such an agent, a certain conjecture may come to mind only after a counterfactual prediction Y 0 at h ′ t ′ is explicitly made, and only then can the agent fill in some parts of the model φ. According to this account, counterfactual predictions are a step in the reasoning process, a preparation of the database in the hope that it would bring to mind new regularities.

In this bounded-rationality view, discussions about counterfactuals are essentially discussions about the appropriate specification of φ. An agent may well test a particular possibility for φ by examining its implications for counterfactual histories, leading to revisions of φ in some cases and enhanced confidence in others. The function φ lies at the heart of the prediction model, so that counterfactuals here are not only useful but perhaps vitally important to successful prediction. In a sense, this view of counterfactuals takes us back to [START_REF] Savage | The Foundation of Statistics[END_REF], who viewed the critical part of a learning process as the massaging of beliefs that goes into the formation of a prior belief, followed by the technically trivial process of Bayesian updating. The counterpart of this massaging in our model would be the formation of the function φ. Whereas in most models of rational agents this function simply springs into life, as if from divine inspiration, in practice it must come from somewhere, and counterfactuals may play a role in its creation.

Extension: Probabilistic Counterfactuals

The counterfactual predictions we discuss above are deterministic. It appears natural to extend the model to quantitative counterfactuals. In particular, if the credence weights φ(A(h ′ t ′ , Y ′ |h t )) happen to generate an additive measure (on sets of outcomes Y ′ ), they can be normalized to obtain a probability on Y , generating probabilistic counterfactuals along the lines of "Had h ′ t ′ been the case, the result would have been y ∈ Y with probability p(y|h ′ t ′ , h t )". Probabilistic counterfactuals of this nature can also be used to enrich the database by hypothetical observations. Rather than claiming that one knows what would have been the outcome had h ′ t ′ occurred, one may admit that uncertainty about this outcome remains, and quantify this uncertainty using counterfactuals. Further, one may use the probability over the missing data to enhance future prediction. However, under reasonable assumptions, a result analogous to Proposition 1 would hold. For instance, if the agent makes predictions by taking the expected prediction given the various hypothetical observations, she will make the same probabilistic predictions as if she skipped the counterfactual reasoning step.

A Possible Application: Extensive Form Games

Consider an extensive form game with a choice of a strategy for each of the n players. Assume for simplicity that these are pure strategies, so that it is obvious when a deviation is encountered. 11 Should a rational player follow her prescribed strategy? This would depend on her beliefs about what the other players would do, should she indeed follow it, but also what they would do if she were to deviate from her strategy. How would they reason about the game in face of a deviation?

For concreteness, assume that player I is supposed to play a at the first node of the game. This is part of an n-tuple of strategies whose induced play path is implicitly or explicitly assumed to be common belief among the players.12 Player I might reason, "I should play a, because this move promises a certain payoff; if, by contrast, I were to play b, I would get . . . "-namely, planning to play a, the player has to have beliefs about what would happen if she were to change her mind, at the last minute as it were, and play b instead.

This problem is related, formally and conceptually, to the question of counterfactuals. Since player I intends to play a, she expects this to be part of the unfolding history, and she knows that so do the others. However, she can still consider the alternative b, which would bring the play of the game to a node that is inconsistent with the "theory" provided by the n-tuple of strategies. Differently viewed, we might ask the player, after she played a, why she chose to do so. To provide a rational answer, the player should reason about what would have happened had she chosen to do otherwise. The answer to this counterfactual question is, presumably, precisely what the player had believed would have happened had she chosen b, before she actually made up her mind.

Our model suggests a way to derive counterfactual beliefs from the same mechanism that generates regular beliefs. For example, consider the backward induction solution in a perfect information game without ties. Assume that for each k there is a hypothesis A k "All players play the backward induction solution in the last k stages of the game". These hypotheses may have positive φ values based on past plays of different games, perhaps with different players. Suppose that this φ is shared by all players.13 For simplicity, assume also that these are the only hypotheses with positive φ values. At the beginning, all players believe the backward induction solution will be followed. Should a deviation occur, say, k stages from the end of the game, hypotheses A l will be refuted for all l ≥ k. But the deviation would leave A k-1 , ..., A 1 unrefuted. If the player uses these hypotheses for the counterfactual prediction, she would find that the backward induction solution

5

  If the agent were at h ′ t ′ , she would simply apply (1) to identify the hypotheses consistent with [h ′ t ′ ]. But the agent is not actually at the history h ′ t ′ : she has observed h t , and should take this latter information into account. Hence, the agent should consider only those hypotheses that are compatible with h t , namely, only those A's such that A ∩ [h t ] = ∅. Therefore, the belief in outcomes Y ′′ Y resulting from history h ′ t ′ conditional on history h t is φ(A(h ′ t ′ , Y ′′ |h t )), with

  ′ )), for various values of Y ′ . Now suppose she endeavors to supplement the information at her disposal by asking, counterfactually, what would have happened at history h ′ t The agent first uses her counterfactual beliefs to associate a set of outcomes Y ′′ to the counterfactual history h ′ t ′ . She then adds the counterfactual information [h ′ t ′ , Y ′′ ] to her data set. This counterfactual information may allow her to discard some hypotheses from consideration, thereby sharpening her predictions. What set of outcomes Y ′′ should she associate with history h ′ t ′ ? To consider an extreme case, suppose that A

′ , where [h t ] ∩ [h ′ t ′ ] = ∅.

Questions 1 and 3 are classical examples given by Hume (1748).

Fortunately, Question

also does not seem to be relevant to any practical problem. We suspect that the fact that nothing can be said about it is related to its irrelevance.

We work with a special case of[START_REF] Gilboa | Dynamics of Induction in a Unified Model[END_REF] model that allows us to make the argument with a minimum of technical clutter. We present the model here, leaving most issues of motivation and interpretation to the original paper.

No conceptual problems arise in extending the analysis to infinite sets X, Y or T, but we avoid a collection of technical complications by working with finite sets.

We do not distinguish in the formal model between the questions "what would happen if... were not the case" and "what would have happened if... had not been the case".

We have added the result of a single counterfactual consideration to the reasoner's database. Adding multiple counterfactuals is a straightforward elaboration.

When one considers mixed (or behavioral) strategies, one should also consider some statistical tests of the implied distributions in order to make sure that the selection of strategies constitutes a non-vacuous theory.

See Aumann (1995),[START_REF] Samet | Hypothetical knowledge and games with perfect information[END_REF],[START_REF] Stalnaker | Knowledge, belief and counterfactual reasoning in games[END_REF],[START_REF] Battigalli | Hierarchies of conditional beliefs and interactive epistemology in dynamic games[END_REF].

Such a model only involves beliefs about other players' behavior. To capture higherorder beliefs one has to augment the state space and introduce additional structure to model the hierarchy of beliefs.

gratefully acknowledges ISF Grant 396/10 and ERC Grant 269754; Larry Samuelson gratefully acknowledges NSF grant SES-0850263.