text:
# Modeling Complex Domains of Actions and Change

## 1 Introduction and Background

Over the last decade several new frameworks for reasoning about actions and change have been proposed. Together with the original frameworks of the situation and event calculi, we have seen a number of different action description languages emerging with recent implemented prototype systems . Many of these languages have been motivated by the desire to have simple representation frameworks, with semantics that relate more directly to the natural intended meaning of their statements. They, therefore, aspire to provide high-level representations of domains that are close to their natural specification.

This paper studies the problem of modeling complex domains of reasoning about actions and change within high-level action description languages. It aims to expose the main problems involved in this representation task and to study the computational behaviour of the ensuing representations. It considers the Zoo domain, proposed at the Logic Modeling Workshop of the ETAI electronic communication forum , as one representative complex domain that frameworks of reasoning about actions and change should aim to capture.

A complex domain brings together a number of different problems associated with reasoning about actions and change, such as ramifications, non-determinism and concurrency. Although all these aspects have been extensively studied and several solutions have been proposed these studies are largely done for one problem in isolation and with little attention to the computational behaviour of these solutions. In this work we study how we can use the knowhow generated over the years in these separate problems, in order to represent complex and realistic domains that encompass together all these different features. Despite the fact that we will use a particular representation framework, that of the Language $``$, we believe that the results apply more generally. This language encompasses (partial) solutions to the main problems of reasoning about action and change that are based on the same principles used by most of the other approaches. Hence the findings of our work, especially those that refer to the representational task would apply to other formalisms as well.

In particular, we investigate two main issues of concern: (a) can we represent complex domains in a natural way using directly the given natural ontology of the problem domain and (b) what features of such a representation can affect (and how) its computational behaviour. Our method of study uses an empirical investigation through a series of controlled experiments. In some of these experiments we compare different representations by varying, for example, the basic ontology of the domain or the degree of use of indirect effect laws through domain constraints. In other experiments, we investigate the performance of a fixed representation as we vary the type of problems we consider, e.g by varying the degree of incompleteness of information in a scenario or by varying the complexity of the narrative with irrelevant action occurrences.

These experiments help to analyze the computational difficulties of the reasoning by exposing their main sources. In turn, they suggest methodological guidelines on how to develop complete representations of complex domains with improved computational properties.

In the rest of this section we present briefly the specific action description language that we will use in our modeling study. Section 2 studies the main problems faced in the task of representing a complex domain (by analyzing these for the Zoo domain). Section 3 discusses some of the experiments carried out to study the computational behaviour of representations and presents their main conclusions. Section 4 discusses the overall conclusions drawn from our work.

### 1.1 The Action Description Language $``$

Action description languages have been developed over the last years to provide high level representation frameworks for theories about actions and change. They generally do not have an explicit representation of the frame axioms and they have been extended to address the ramification and qualification problems. They have been motivated by the need to have simple representation frameworks with natural semantics that relate more directly to the natural interpretations of the domains.

We will consider the problem of modeling complex domains within the particular action description Language $``$ . The vocabulary of the Language $``$ consists of a set $`\mathrm{\Phi }`$ of fluent constants, a set of action constants, and a partially ordered set $`\mathrm{\Pi },`$ of time-points. This vocabulary depends each time on the domain being modeled. A fluent literal is either a fluent constant $`F`$ or its negation $`\neg F`$. In the current implementation of the language, the only time structure that is supported is that of the natural numbers, so we restrict our attention here mainly to domains of this type.

Domain descriptions in the Language $``$ are collections of the following types of statements (where $`A`$ is an action constant, $`T`$ is a time-point, $`F`$ is a fluent constant, $`L`$ is a fluent literal and $`C`$ is a set of fluent literals):

* t-propositions of the form: $`L\text{ }\text{holds-at}\text{ }T`$
* h-propositions of the form: $`A\text{ }\text{happens-at}\text{ }T`$
* c-propositions of the form: $`A\text{ }\text{initiates}\text{ }F\text{ }\text{when}\text{ }C`$ or, $`A\text{ }\text{terminates}\text{ }F\text{ }\text{when}\text{ }C`$
* r-propositions of the form: $`L\text{ }\text{whenever}\text{ }C`$
* p-propositions of the form: $`A\text{ }\text{needs}\text{ }C`$.

For the purposes of this paper it is sufficient to describe the semantics of the language in an informal way, giving the intended meaning of each type of sentence and describing the basic tenets of the reasoning supported. T-propositions record observations that particular fluents hold or do not hold at particular time-points. H-propositions state that particular actions occur at particular time-points. C-propositions state general “action laws” – the intended meaning of “$`A`$ initiates $`F`$ when $`C`$” is that “$`C`$ is a minimally sufficient set of conditions for an occurrence of $`A`$ to initiate $`F`$”. R-propositions, also called ramifications or domain constraints, serve a dual role in that they describe both static constraints between fluents and ways in which fluents may be indirectly affected by action occurrences. As a constraint this must be satisfied as a classical implication at any time point. The intended meaning of “$`L`$ whenever $`C`$” is that “at every time-point that $`C`$ holds, $`L`$ holds, and hence every action occurrence that brings about $`C`$ also brings about $`L`$”. P-propositions state necessary conditions for an action to occur.

The semantics of $``$ are based on a notion of a model of a domain $`D`$ that assigns a truth value to each fluent at each time point. A model encompasses two basic requirements:

Direct and indirect action laws, stated by c-propositions and through r-propositions respectively, are the only way to bring about a change (over time) in the truth value of a fluent, when an appropriate action occurs. This new value persists in time from then onwards, until another such point of change.

The model must satisfy as classical implications the r-propositions at each time point and as facts the t-propositions together with all the pre-conditions C at times T that follow from each p-proposition $`A\text{ }\text{needs}\text{ }C`$ and associated h-proposition $`A\text{ }\text{happens-at}\text{ }T`$.

Given a consistent domain $`D`$ and a query or goal $`G`$ comprising a set of t-propositions, we say that $`G`$ is a credulous or possible conclusion of $`D`$ iff there is a model of $`D`$ in which $`G`$ is true and that $`G`$ is a skeptical or necessary conclusion of $`D`$ iff $`G`$ is true in all models of $`D`$.

As an example, consider the following simple “bulb domain” with action constants SwitchOn, SwitchOff and Break and fluents Light and Normal:

$`\text{ }\text{SwitchOn}\text{ }\text{initiates}\text{ }\text{Light}\text{ }\text{when}\text{ }\{\text{Normal}\}`$
SwitchOff terminates Light
Break terminates Normal
$`\text{ }\neg \text{Light}\text{ }\text{whenever}\text{ }\{\neg \text{Normal}\}`$
$`\text{ }\text{SwitchOn}\text{ }\text{needs}\text{ }\{\neg \text{Light}\}`$
$`\text{ }\text{SwitchOn}\text{ }\text{happens-at}\text{ }2`$
$`\text{ }\text{Normal}\text{ }\text{holds-at}\text{ }0`$

This domain has as a skeptical conclusion Light holds-at $`4`$, but the conclusion is only credulous when we remove the last sentence.

The Language $``$ has been implemented  via an argumentation-based translation of the language. This system, called $``$-RES, can support directly a variety of modes of common sense reasoning such as: default persistence in credulous or skeptical form, assimilation of observations and their diagnosis possibly under incomplete information, as well as combinations of these. The computational model on which this is based integrates argumentation goal-oriented proofs for default persistence, together with classical theorem proving techniques for the satisfaction of the constraints expressed in a domain. It also employs a (weak) notion of syntactic relevance in order to help focus the computation to the relevant part of the theory.

This argumentation-based reformulation also extends the Language $``$ allowing its action laws to be treated as default laws.

## 2 Complex Domain Representations

In this section we study how the Zoo domain, defined at the Logic Modeling Workshop (LMW) , can be represented in the Language $``$. We will follow closely the presentation of the domain and guidelines given at LMW trying to address all the issues raised there. This section is therefore best read in conjunction with the documentation available at LMW. We will present the different aspects of representing such a complex domain, while trying to expose the main problems faced and choices made.

The LMW describes the Zoo domain as ”…a world containing the main ingredients of a classical zoo: cages, animals in the cages, gates between two cages, as well as gates between a cage and the exterior. In the Zoo world there are animals of several species, including humans. Actions in the world may include movement within and between cages, opening and closing gates, …, riding animals, etc.”

### 2.1 Background Landscape and Active Structure

Our first task is to represent the landscape and active structure of the domain i.e. describe the background information of the Zoo environment and the objects that populate it. This information is generally taken to be static, not changing over time.

For this type of information the Language $``$ has a simple facility of using constant fluents and declaring the static state of affairs for these at some initial time point (time 0). For example, we declare the known animals in the domain by a set of statements of the following form:

$`\text{ }animal()\mathrm{𝐢𝐬}\mathrm{\_}\mathrm{𝐜𝐨𝐧𝐬𝐭𝐚𝐧𝐭}`$
$`\text{ }animal(john)\text{ }\text{holds-at}\text{ }0`$
$`\text{ }animal(jane)\text{holds-at}\text{ }0`$
$`\text{ }animal(elly)\text{ }\text{holds-at}\text{ }0`$
$`\text{ }\mathrm{}`$

In addition, we can use ramification statements to represent static information that is derived from other such information e.g. that “an animal is large when it is an adult and belongs to a large species”:

$`\text{ }animal\mathrm{\_}is\mathrm{\_}large(A)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}is\mathrm{\_}adult(A),\text{ }animal\mathrm{\_}species(A,S),species\mathrm{\_}is\mathrm{\_}large(S)\}.`$

In the same way, we represent the zoo terrain by declaring all its positions and the neighbor relation via a constant fluent $`neighbor\mathrm{\_}pos(\mathrm{\_},\mathrm{\_})`$ and ramification statements to express its properties e.g. $`neighbor\mathrm{\_}pos(P_1,P_2)\text{ }\text{whenever}\text{ }\{neighbor\mathrm{\_}pos(P_2,P_1)\}`$ for the symmetry of this relation.

We then reason with the Closed World Assumption on these static fluent predicates at time $`0`$ and project their truth value unchanged to any other time point. If complete information for a background fluent predicate is not known at $`0`$, then this predicate would not be declared as constant and thus would be interpreted under the Open World Assumption with the possibility to assume its truth value.

We note that the inherent propositional nature of the Language $``$ does pose some representational restrictions. We need for example to define the primary typing constants, which enumerate entities of the landscape and hence only domains with known predefined entities can be represented. In general, the underlying ontology of the language can be extended with a notion of sorted variables over a set of finite sorts. The details of this are not important for this work.

In this paper, we will assume that we have in the Zoo domain the basic types of animals, species, gates, locations and positions, defined as constant fluents, and that any variable (i=1,2,3,…) denoted by $`A_i,S_i,G_i,L_i,orP_i`$ has the respective type.

### 2.2 Action Effect Laws

Till now we have only been concerned with the static aspects of the representation of the domain i.e. representing information at one time slice. The central part of any domain of reasoning about actions and change is that of its Action laws specifying the effects of actions. In the Language $``$ action laws are represented directly via c-propositions. For example, the effect of the $`move\mathrm{\_}to\mathrm{\_}position(A,P)`$ action in the Zoo domain, that the animal “A” takes the position “P” is represented by:

$`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{initiates}\text{ }animal\mathrm{\_}pos(A,P)\text{ }\text{ }\text{when}\text{ }\{reachable(A,P)\}`$111Note that the current version of the $``$-RES system, that implements the Language $``$, requires that the typing of each variable of a fluent or action to be stated explicitly each time the fluent or action is used in a statement. Hence in $``$-RES this will written as: $`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{initiates}\text{ }animal\mathrm{\_}pos(A,P)\text{ }\text{ }\text{when}\text{ }\{animal(A),position(P),reachable(A,P)\}.`$ .

Here this effect law depends on the condition that at the time of the action the position “P” is reachable by “A”, namely that “P” is an adjacent position to the position of the animal “A” at the time of the action. This means that an instance of the action $`move\mathrm{\_}to\mathrm{\_}position(A,P)`$ could occur without successfully reaching “P”. Alternatively, we can remove this condition from the effect law and set it as a pre-condition for the action to occur via the statement:

$`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{needs}\text{ }\{reachable(A,P)\}.`$

This choice depends on how we wish to interpret the occurrence of events in a given narrative. If when given an event we mean that this event has successfully occurred, then this alternative is more appropriate and allows for more conclusions to be drawn, given an action occurrence. For example, we would include the statement

$`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{needs}\text{ }\{\neg rides(A,A_1)\}`$

to capture the requirement that a rider cannot perform the $`move\mathrm{\_}to\mathrm{\_}position`$ action at the time that s/he is riding. Under this interpretation of event occurrences this way of representing these preconditions allows us to draw more conclusions from knowledge that an action has occurred. If then, we are given that $`move\mathrm{\_}to\mathrm{\_}position(john,p_1)`$ happened at time T then we would conclude that $`john`$ is not riding any (known) animal at $`T`$. Depending on other information in the domain we maybe able to project this backward or forward in time.

The above law of change for the action $`move\mathrm{\_}to\mathrm{\_}position(A,P)`$ expresses a direct effect. This action can also have other effects, for example that a rider $`A_1`$ of the animal $`A`$ will also acquire the new position $`P`$, when $`A`$ moves to $`P`$. In comparison, this is not a direct effect but nevertheless, as argued in the recent literature (e.g. ), actions should be allowed to have such indirect effects. This poses a dilemma in the representation. Indirect effects could be represented either by explicit direct effect laws or via the domain constraints (or ramification statements) of the theory. In the above example we could have the additional direct laws:

$`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{initiates}\text{ }animal\mathrm{\_}pos(A_1,P)\text{ }\text{ }\text{when}\text{ }\{rides(A_1,A)\},`$
$`\text{ }move\mathrm{\_}to\mathrm{\_}position(A,P)\text{ }\text{terminates}\text{ }animal\mathrm{\_}pos(A,P_1)\text{ }\text{ }\text{when}\text{ }\{animal\mathrm{\_}pos(A,P_1)\}`$

for moving an animal’s rider along with the animal and terminating the animal’s current position, respectively. On the other hand, we could omit these, since the following domain constraints (stating that an animal’s rider always has the same position with the ridden animal and that an animal cannot be at two positions at the same time) would generate the required effects indirectly:

$`\text{ }animal\mathrm{\_}pos(A_1,P)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}pos(A,P),\text{ }rides(A_1,A)\},`$

$`\text{ }\neg animal\mathrm{\_}pos(A,P_1)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}pos(A,P),\text{ }P_1P\}.`$

However, such domain constraints are also needed in the representation to suitably restrict the assumptions that we might make while reasoning, when we have incomplete information in the theory.

Hence a dilemma emerges, either (1) to use direct laws to explicitly enumerate all possible effects of an action together with domain constraints which do not generate indirect effects, but simply act as integrity constraints for assumptions relating to incomplete fluents or (2) to use direct laws for the basic effects of an action and let the domain ramification constraints generate the other effects indirectly. We will see below that these two choices can be semantically different and that they differ in their computational performance.

### 2.3 Domain Constraints

To represent the whole Zoo domain we need to define all direct action laws for each of the type of actions together with their pre-conditions (as we have done above for $`move\mathrm{\_}to\mathrm{\_}position`$) and state the various domain constraints that the specification of the problem requires. In addition, to the domain constraints given above, we also have several other statements. For example, we have:

$`\text{ }false\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}species(A,human),\text{ }rides(A_1,A)\},`$

$`\text{ }\neg rides(A,A_1)\text{ }\text{whenever}\text{ }\{rides(A,A_2),A_1A_2\}`$

to capture the fact that a human cannot be ridden and to represent the fact that an animal cannot ride two animals at the same time. Here the first domain is written in this particular way as a denial to indicate that it is not necessary to produce indirect effects through it.

The domain constraints are also used to define various auxiliary dynamic predicates that we need, such as $`reachable`$ used above:

$`\text{ }reachable(A,P)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}pos(A,P_1),\text{ }neighbor(P_1,P)\},`$

$`\text{ }\neg reachable(A,P)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}pos(A,P_1),\text{ }\neg neighbor(P_1,P)\}`$

Note that here we do have the option (or dilemma) to define such dynamic predicates via direct effect laws of the actions, but this would be more complex and non-modular requiring the full enumeration of all cases where the fluent $`reachable`$ could be affected. Its definition through the above domain constraints and their indirect effects that they embody, provides a compact and modular way of representing such a dynamic predicate.

### 2.4 Issues in the choice of Representation

We return now to study in more detail the above dilemma and in particular how this is related to non-determinism in the domain and its representation. One of the actions of the Zoo domain, that of $`throwoff(A_1,A_2)`$, is specified to be non-deterministic. Animal $`A_1`$ throws off its back $`A_2`$ and the latter can land at any position reachable from their common position at the time of the throw. As there could be many such reachable positions and we do not know at which one the animal would fall this is a non-deterministic action. The argumentation semantics of the Language $``$ allows us to represent such a non-deterministic action law in the same way as any other law:

$`\text{ }throwoff(A_1,A_2)\text{ }\text{initiates}\text{ }animal\mathrm{\_}pos(A_2,P)\text{ }\text{ }\text{when}\text{ }\{reachable(A_2,P)\}.`$

This effect law does not contain any explicit qualifications to state that the animal would fall in one position only provided that it does not fall on anyone of the other (reachable) positions. This qualification is implicitly produced by the domain constraint that an animal cannot have two different positions at the same time. The combination of these two statements captures the non-determinism of the action. An inconsistency is not produced (although apparently it would be), because for each direct initiation of a particular position $`P`$ that the action law produces, the domain constraint then produces the indirect effect that all other positions are terminated. In this way each position can be chosen. Note that it is important that the blockage of the other positions is not captured simply by the static application of the constraint, but that at the same time the position of an animal changes to $`P`$ we also have a change with regards to all the other positions, namely they “begin to be false”.

We therefore see a useful need for the production of indirect effects, i.e. of change through the domain constraints. This provides a natural mechanism of implicit qualification of the several direct laws for a non-deterministic action. Alternatively, we would need to qualify explicitly the direct law with the condition that the animal can not be at any other position. This would be complex and difficult to express because the qualifications to the action law need to refer to the state of the world after the action has occurred.

The same behaviour can also be observed in the case of concurrent actions whose effects are contradictory. Consider for example the simultaneous occurrence of a $`getoff(A,A_1,P)`$ and a $`move\mathrm{\_}to\mathrm{\_}position(A_1,P_1)`$ action, at a time when the animal $`A`$ is riding another animal $`A_1`$. The first action requires that $`A`$ has the position $`P`$ as its direct effect, while the second action would give that $`A`$ has the different position $`P_1`$ since $`A`$ is riding $`A_1`$. Again, the above constraint that an animal can have only one position at a time, acts as a qualifier and splits this scenario in a non-deterministic way into two possibilities. In effect, in the first case $`A`$ manages to get off before $`A_1`$ moves, whereas in the second case $`A_1`$ moves first and then $`A`$ gets off. The domain constraint gives an implicit qualification to the two effect laws involved, in a way that would be very difficult (and unnatural) to represent explicitly.

Concurrent action scenaria also show the main difference between direct and indirect effect laws. Let us return to the indirect effect law that a rider acquires the same position of the animal that s/he is riding and compare it with its direct effect law counterpart as given above. A difference between the two laws shows up when we consider, for example, the concurrent $`getoff`$ and $`move\mathrm{\_}to\mathrm{\_}position`$ scenario, above. The direct law would allow the rider to move to the new position with the animal, whereas the indirect law would not generate this effect. This is because the condition of $`rides`$ in the direct law case needs to hold at the exact time of the action, while in the indirect law case this needs to hold at an infinitesimal time (or next time point) after this, so that both conditions in the ramification can hold together to produce its conclusion. Indeed, due to the simultaneous $`getoff`$ action, rides holds at the time of these actions, but not later as it is terminated by this action unconditionally. Hence, in this concurrent scenario we would not get the second possibility of the indirect generation of the rider moving with the animal.

In this way we see that direct laws can be stronger than a corresponding indirect effect law and in fact could be used to break non-determinism when we do not want this. To see this better and show its significance for the task of modeling a domain, let us consider a case where the non-determinism could exist as a result of the occurrence of one action alone. Consider the domain constraint that two animals at different positions cannot ride each other:

$`\text{ }\neg rides(A,A_1)\text{ }\text{whenever}\text{ }\{animal\mathrm{\_}pos(A,P),\text{ }animal\mathrm{\_}pos(A_1,P_1),P_1P\}.`$

This would then give indirect effects of the termination of riding when we perform actions that change the position of the rider alone (such as $`getoff`$ or $`throwoff`$). But it would also give the indirect effect that riding is terminated when the animal moves and hence it changes its position relative to its rider. In fact, adding the above ramification to the representation and performing an action $`move\mathrm{\_}to\mathrm{\_}position(A_1,P_1)`$, at a time point where the animal $`A_1`$ is ridden by another animal, results in two possibilities: either the rider comes off and is at the original position of $`A_1`$, or the rider stays on and is at the new position $`P_1`$ where the animal has moved to. With regards to the effect of the action $`move\mathrm{\_}to\mathrm{\_}position(A_1,P_1)`$ on the position of the rider the action is non-deterministic.

In this case we do not want this and we have a preference for the rider to move along with the animal that it rides. We can achieve this preference in a natural way by explicitly stating the preferred effect through a direct effect law. Despite the fact that we have a domain constraint that gives, as an indirect effect, that the rider moves along with the animal, we also represent this explicitly by a direct initiation law for the action $`move\mathrm{\_}to\mathrm{\_}position(A,P)`$, i.e. we keep both sentences in the dilemma presented above in this section. This then blocks the indirect effect of terminating the riding by the movement of the animal as the required condition for this, namely that the rider is at a different position immediately after the action, cannot now be supported due to the strong argument of changing its position to that of the animal’s new position through the new direct law and the constraint that the rider can only have one position at a time. The explicit statement of the direct law has given preference to it.

In summary, we see that the ramifications and their indirect effects provide an implicit form of qualification through the general constraint properties of the domain. This means that the theory treats its effect laws as default laws where one can qualify another through these constraints. The direct effect laws set out preferences amongst conflicting possibilities. The redundancy of repeating an indirect law as a direct law as well, forms a natural way of setting a preference. We give emphasis to effects by articulating them explicitly.

### 2.5 An example Scenario

Closing this section, we show how a particular scenario can be represented. A scenario is given by stating events, i.e. specific instances of actions that occurred (through h-propositions) and observations, that is values of fluents at specific time points (through t-propositions). For example,

$`\text{ }throwoff(elly,john)\text{ }\text{happens-at}\text{ }1`$
$`\text{ }move\mathrm{\_}to\mathrm{\_}position(john,p1)\text{ }\text{happens-at}\text{ }2`$
$`\text{ }mount\mathrm{\_}animal(john,dumpo)\text{ }\text{happens-at}\text{ }3`$
$`\text{ }reachable(john,p1)\text{ }\text{holds-at}\text{ }2`$

represents the scenario that $`elly`$ threw off $`john`$, who then observed that position $`p1`$ was reachable, moved to position $`p1`$, and then mounted $`dumpo`$. In this scenario we would reason to $`rides(john,elly)`$ at time 1 or 0 as a necessary (or skeptical) conclusion, but that $`animal\mathrm{\_}pos(john,p2)`$ at time 2, where $`p2`$ is any neighbor of $`p1`$, is a possible (or credulous) conclusion. At time 4 onwards we can conclude that $`rides(john,dumpo)`$ is necessarily true. But if we are given also that $`move\mathrm{\_}to\mathrm{\_}position(dumpo,p3)\text{ }\text{happens-at}\text{ }3`$, then $`rides(john,dumpo)`$ at 4 will only be a possible conclusion. Observing that $`animal\mathrm{\_}pos(john,p3)\text{ }\text{holds-at}\text{ }5`$ i.e that $`john`$ and $`dumpo`$ have the same position then $`rides(john,dumpo)`$ at 4 would be a necessary conclusion.

## 3 Computational Behaviour of Representations

In this section we study empirically, via suitable controlled experiments, the computational behaviour of a representation and try to ascertain what factors of the representation might or might not affect this behaviour. We have conducted two major types of experiments: (a) given a fixed representation of the Zoo domain, we have examined various scenaria that differ in the amount of given information, its relevancy to the queries and the type of queries performed, and (b) given some fixed scenarios and queries, we have examined various representations that differ on the extend the action effects are represented directly/indirectly and on the richness of the vocabulary used. The basic scale of the domains on which we have carried these experiments is of the order of 3 thousand ground clauses per time point. A scenario typically spans over 3-6 time points.

As the representative results222All numbers shown in the tables of this paper are in seconds measured on a Pentium II, 266 MHz, PC. The absolute value of these times are not important as the purpose of the experiments is to compare different cases. presented in figure 1 suggest, increasing the information in a scenario can affect positively the computational performance, even if the extra information given explicitly in the scenario is a necessary conclusion of this.

These experiments have also shown that it is possible to use simple syntactic relevancy checks to focus the computation to the relevant (w.r.t. the query at hand) part of the domain. In fact, the experiments have helped us develop further a semantically enhanced notion of relevancy that neutralizes to some extent the effect of additional irrelevant information in the scenario. Figure 2 shows that the addition of irrelevant actions in a scenario does not have a significant impact on the computation. The stability under irrelevant information also depends strongly on the type of representation used and the choice of vocabulary, as we will see below in the second class of experiments. Finally, as expected in some cases, particularly in scenarios with a lot of missing information, skeptical queries can be significantly slower than the corresponding credulous queries.

As mentioned above, the second class of experiments considers changes in the representation. Figure 3 compares the computational behaviour between representations which use direct effect laws to a different degree. In general, using only direct laws gives a significantly better computational performance than a representation that uses to a maximum indirect effect laws. We should note though, as we have seen in section 2, that the first representation cannot always fully capture the domain e.g. the non-determinism of conflicting concurrent actions. In such cases, this becomes inconsistent and is unable to return an answer. It is also noteworthy, that when effect laws are duplicated in the representation both directly and indirectly, the behaviour varies from being as good as a representation that primarily uses direct effects, to being worse than a representation that primarily uses indirect effects. This depends mostly on whether the specific laws that are duplicated as direct laws can generate a large number of additional indirect effects.

Another series of experiments has examined the effects on the computational behaviour of using an enriched, more specific vocabulary of the domain in the representation. Starting from a minimally sufficient vocabulary, we have developed a number of other equivalent representations using more specialized vocabularies that separate explicitly different specific cases for an action, e.g. the single action fluent $`move\mathrm{\_}to\mathrm{\_}position`$ is replaced by $`move\mathrm{\_}in\mathrm{\_}cage`$, $`enter\mathrm{\_}cage`$ and $`exit\mathrm{\_}cage`$. Similarly, we can distinguish explicitly in the vocabulary some of the fluent properties e.g. those that refer to the (2 dimensional) position on the floor from the properties that refer to the third dimension off the floor. We have found that a representation that uses, in this way, a carefully selected ontology and proper typing can significantly improve its computational efficiency. This occurs mainly by reducing the number of assumptions (sometimes impossible ones) from being considered in the reasoning.

With regards to the issue of scaling of the computational behaviour of the representations, our experiments suggest that the representation that maximizes the use of direct effect laws scales up relatively well. These are preliminary results, tested only on small sized domains that contain up to a maximum of 15 positions in the terrain, corresponding to around 25,000 ground clauses. Representations with non-minimal use of indirect effect laws scale up poorly.

In general, our empirical study has revealed two main computational bottlenecks: (a) the number of additional consequences drawn from the conclusions of a query that need to be considered to ensure that the query can be consistently satisfied in the whole domain and (b) the number of counter-proofs (counter-arguments) that are generated via persistence on an assumption needed to prove the query. Our experiments have helped us address (at least partly) these difficulties. The enhanced notion of relevancy, which helps us avoid unnecessary re-computation of known consequences and a (non-minimal) choice of vocabulary that distinguishes explicitly different scenaria, can result in significant improvement of computational behaviour. Another potential source of improvement can come from the way we use direct and indirect effect laws. Generally, the more use of direct laws the better the performance, but there is a trade off here with the reduction in modularity and readability of a representation that uses direct laws extensively. In some cases the computational gain is relatively small to justify this and a representation that combines the use of these two types of effect laws is overall better.

We have also begun to examine the same problems using a different computational model in place of the argumentation based model used so far. We have translated the Language $``$ to a SAT theory so that we can then employ a SAT solver for query answering. This translation is not complete and supports only a restricted class of domains. In particular, it does not support domains with non-deterministic actions, or concurrent actions that generate conflicting effects nor domains in which the ramifications form cycles. Initial results indicate that the SAT-based approach has a more stable behaviour. They also indicate that it scales up better as we increase the number of actions in a scenario, but not so as we increase the number of positions in the terrain of the Zoo domain. An interesting difference of the SAT-based approach is the fact that it is difficult to employ relevancy notions in it. Some simple forms of relevancy can be used, but this requires that for each query we need to translate the relevant part of the domain theory afresh and this can have an adverse effect on its performance.

## 4 Related Work and Conclusions

We have studied how to model complex domains of action and change based on the theoretical foundations that the community at large has developed over the last decade. In particular, we have addressed the challenge set by the Logic Modeling Workshop , to apply this theory in modeling complex domains that encompass together many different aspects of the problem. As in the related work of  our work shows that the existing frameworks of action description languages are sufficiently expressive to meet this representational challenge.

Moreover, applying this otherwise well understood theory of reasoning about actions and change to capture complex domains has helped to expose more clearly some problems. For example, it has shown a link between non-determinism and an implicit qualification of effect laws via the domain constraints where the explicit representation of an indirect effect law as a direct law can give this higher priority. As mentioned in the introduction, we believe that these considerations are independent of the particular framework that we have used to carry out our study and that they would apply also to other approaches that are based on the same underlying principles for developing a theory for reasoning about actions and change. Differences may arise in the computational aspects of the different frameworks. For this reason we have concentrated more on comparison experiments and have tried to exposed inherent computational problems. Also the propositional nature of the particular framework that we have used could be limiting in the static aspects of the representation, i.e. in the ability to represent knowledge at any single time or situation. But this does not affect the ability to represent the dynamic aspects of a problem domain. At this initial stage of the study we believe that it is methodologically correct to de-couple these two aspects and examine at a later stage how they would affect each other.

Our study of the computational behaviour of representations has suggested some methodological guidelines for modeling complex domains that can help us control their computational performance. These include the balanced use of direct and indirect effect laws and the adoption of an appropriate vocabulary as presented in the previous section. To cross check these comparison results it would be useful to study similar experiments using other languages, e.g. using the Causal Calculator  with its SAT based computation. We also need to study how other mechanisms, external to the reasoning, can help focus more the computation to the relevant part of the theory.

More work is needed to understand better what factors can influence the computational performance of a representation and how this would scale up. We also need to develop a stricter methodology on how to choose a vocabulary for a complex domain that would give it good computational properties. In our work so far this choice was mostly motivated by the natural common sense reasoning that we as humans apply to the domain and our use of a specific vocabulary for it. In fact, a distinction between “natural” and “formal” (or compact) representations emerges, where the first type of representation uses a non-minimal enriched vocabulary which helps it encode directly in the domain qualitative solutions to computational problems (e.g. the geometry of a terrain) and thus results to a better computational behaviour. This and its possible link to qualitative reasoning in AI is an interesting problem for future study.

Our work has been mainly motivated with trying to understand a natural computational model of human common-sense reasoning and how this is affected both by issues of representation and methods of computation. In the future we plan to investigate, through a series of cognitive experiments, how natural are these representations and how well they capture the human common sense reasoning in the domain of action and change.

#### Acknowledgements

This work was partly supported by the European Union KIT project CLSFA (9621109) and IST project SOCS (IST-2001-32530).


format: text

text:
# Relaxation to steady states and dynamical exponents in deposition models

## I Introduction

Statistical deposition models have attracted much attention in the last years because they may describe real systems’ features by representing the basic growth mechanisms as simple stochastic processes, thus neglecting the details of the microscopic interactions . Some examples are the Family model , the restricted solid-on-solid ($`RSOS`$) model of Kim and Kosterlitz  and the ballistic deposition ($`BD`$) model . The former one is representative of the Edwards-Wilkinson ($`EW`$) universality class  of linear growth, while the other ones are representative of the Kardar-Parisi-Zhang ($`KPZ`$) class  of non-linear growth. More complex models involve the competition among deposition, diffusion and aggregation  and may represent quantitatively real systems’ features.

Often one is interested in surface properties, then the main quantity to be measured is the interface width of the deposit. If deposition occurs in a $`d`$-dimensional substrate of length $`L`$, then the interface width at time $`t`$ is defined as

$$W(L,t)=\left[\frac{1}{L^d}\underset{i}{}\left(h_i\overline{h}\right)^2\right]^{1/2}$$
(1)
or as

$$\xi (L,t)=\left[\frac{1}{L^d}\underset{i}{}\left(h_i\overline{h}\right)^2\right]^{1/2}.$$
(2)
In Eqs. (1) and (2), $`h_i`$ is the height of column $`i`$, the bar in $`\overline{h}`$ denotes a spatial average and the angular brackets denote a configurational average, i. e., an average over many realizations of the noise. $`W`$ and $`\xi `$ have different values but the same scaling properties, then in the following any definition or discussion concerning $`W`$ is also valid for $`\xi `$.

At early times, in the so-called growth regime, the interface width increases as

$$Wt^\beta ,$$
(3)
while at long times finite-size effects lead to its saturation at

$$W_{sat}(L)W(L,t\mathrm{})L^\alpha .$$
(4)
Relations (3) and (4) are included in the dynamic scaling relation proposed by Family and Vicsek ,

$$W=L^\alpha f\left(tL^z\right),$$
(5)
in which $`f`$ is a scaling function and the dynamical exponent $`z`$ is given by

$$z=\frac{\alpha }{\beta }.$$
(6)
In Eq. (5), the argument of the scaling function is a ratio of the deposition time and the crossover (or saturation) time $`\tau L^z`$.

Most numerical works on deposition models focus on the calculation of exponents $`\alpha `$ (Eq. 4) and $`\beta `$ (Eq. 3) - see e. g. the summary of numerical results in Ch. 8 of Ref. . The calculation of $`\alpha `$ requires the identification of the steady-state regime, in which $`W`$ saturates. Eventually, the extrapolation of effective exponents is essential, such as in the $`BD`$ model . The calculation of $`\beta `$ depends on the definition of the growth regime, which must be a region of high linear correlation in a $`\mathrm{log}W\times \mathrm{log}t`$ plot. Finding such region may be very difficult for $`d2`$ due to small lattice lengths . The usual methods to estimate exponent $`z`$ are based on data collapse of the scaled quantities appearing in Eq. (5) or on the scaling of the structure factor $`S(k,t)h(k,t)h(k,t)`$ ($`h(k,t)`$ is the Fourier transformation of the surface height $`h(x,t)`$. In a recent work, Kim et al presented a method to estimate $`z`$ from the exponential decay of a relaxation function, starting the growth process from a sinusoidal surface . In $`d=1`$, they obtained estimates for the Family, the $`RSOS`$ and the Krug models which were consistent with the expected universality classes . However, for the most common problem of deposition in a flat surface, a precise definition of the crossover time $`\tau `$ and a method to estimate $`z`$ accurately are still lacking.

It is also important to recall that there are controversies on the universality classes of various statistical growth models even in $`d=1`$ . At this point, the development of reliable techniques to estimate critical exponents is also helpful.

The aim of this work is to analyze the convergence of the scaling function in Eq. (5) to an asymptotic constant value (consistently with Eq. 4) and to propose and test methods to estimate crossover times and the exponent $`z`$.

First we will consider the Family, the $`RSOS`$ and the $`BD`$ models in $`d=1`$. We will show that the typical decay of $`W`$ to its saturation value is exponential, which uniquely defines the crossover or saturation time $`\tau `$. Then we will present a method to calculate a characteristic time $`\tau _0`$ that is proportional to $`\tau `$, and we will estimate the exponent $`z`$ from $`\tau _0`$. The reliability of the method will be proved with comparisons with exact results for the corresponding hydrodynamic equations.

We will also consider the Family and the $`RSOS`$ models in $`d=2`$. Results for the $`RSOS`$ model confirm the exponential decay of $`W`$ to the saturation value and give $`z1.6`$. Estimates of the exponent $`\alpha `$, obtained from $`W_{sat}`$ data, are in good agreement with the prediction of Marinari et al  that $`\alpha <0.4`$ for $`KPZ`$ in $`d=2`$. For the Family model, we will consider the expected dynamic scaling hypothesis, which involves a $`W\mathrm{log}L`$ growth, and we will show results consistent with $`z=2`$. A recent numerical work  showed large discrepancies from that value, using data collapse techniques, which proves the relevance of the methods presented here.

The rest of this paper is organized as follows. In Sec II we present the results of simulations in $`d=1`$ for the Family, the $`RSOS`$ and the $`BD`$ models, show the exponential decay of $`W`$ to its saturation value and the methods to calculate $`z`$. In Sec. III we present the simulations’ results of the Family and the $`RSOS`$ models in $`d=2`$, including estimates of exponent $`\alpha `$ for the $`RSOS`$ model. In Sec. IV we summarize our results and present our conclusions.

## II Definition of the models and results in one-dimensional substrates

First we recall the definition of the models studied here.

In the Family model , a column of the deposit is randomly chosen and the incident particle searches for the smallest height in its neighborhood. If no neighboring column has a smaller height than the column of incidence, the particle sticks at the top of this one. Otherwise, it sticks at the top of the column with the smallest height among the neighbors. If two or more neighbors have the same minimum height, the sticking position is randomly chosen among them.

In the $`RSOS`$ model , the incident particle may stick at the top of the column of incidence if the differences of heights of all pairs of neighboring columns do not exceed $`\mathrm{\Delta }H_{MAX}=1`$. Otherwise, the aggregation attempt is rejected.

In $`BD`$, the incident particle follows a straight trajectory perpendicular to the surface and sticks upon first contact with a nearest neighbor occupied site. It leads to the formation of a porous deposit, contrary to the previous solid-on-solid models.

In all models, a time unit corresponds to the deposition of $`L`$ particles. We simulated them in one-dimensional substrates with lengths $`L=2^n`$, with integer $`7n11`$ ($`128L2048`$). For each $`L`$, typically $`10^4`$ different deposits were generated, and very long steady-state regions were observed.

In order to obtain reliable estimates of $`W_{sat}`$, we computed it over different time ranges to ensure that it was fluctuating around an average value, and not increasing systematically in time (the latter possibility would suggest that the steady-state region was not attained yet). $`W_{sat}`$ was obtained with accuracy smaller than $`0.2\%`$ in all cases, which enables the calculation of the deviation from $`W_{sat}`$,

$$\mathrm{\Delta }W\left(t\right)W_{sat}W\left(t\right),$$
(7)
also with good accuracy.

In Fig. 1a we show $`\mathrm{log}\mathrm{\Delta }W\times t`$ for the Family model in $`L=1024`$, and in Fig. 1b we show $`\mathrm{log}\mathrm{\Delta }W\times t`$ for the $`RSOS`$ and $`BD`$ models, also in $`L=1024`$. In Figs. 2a and 2b we show $`\mathrm{log}\mathrm{\Delta }\xi \times t`$ in the same systems. It clearly shows an exponential decay of $`W`$ and $`\xi `$ to $`W_{sat}`$ and $`\xi _{sat}`$, in the form

$$\mathrm{\Delta }W\left(t\right)=A\mathrm{exp}\left(t/\tau \right),$$
(8)
with constants $`A`$ and $`\tau `$. The estimates of relaxation times shown in Figs. 1 and 2 were obtained from fits of the data in regions of high linear correlation. For the other lengths $`L`$, similar linear behaviors in $`\mathrm{log}\mathrm{\Delta }W\times t`$ plots were obtained.

The calculation of $`\tau `$ from those plots has some disadvantages. For instance, $`\tau `$ has to be estimated in different time ranges, in order to avoid spurious effects of an arbitrary choice of the fitting region. Thus we searched for an alternative method, as described below, which is not based on similar data fits.

The scaling relation (5) and Eq. (8) imply that the amplitude $`A`$ of Eq. (8) is proportional to $`L^\alpha `$. Consequently, when approaching the steady-state region, the scaling function of Eq. (5) may be written as

$$f(x)=ab\mathrm{exp}\left(x\right),$$
(9)
with constant $`a`$ and $`b`$. If a characteristic time $`\tau _0`$ is defined from

$$W\left(\tau _0\right)=kW_{sat},$$
(10)
with constant $`k`$, then

$$\tau _0=\tau \mathrm{ln}\left[\frac{b}{a\left(1k\right)}\right],$$
(11)
i. e., $`\tau _0`$ is proportional to the crossover time $`\tau `$. The estimates of $`\tau _0`$ from Eq. (10) always had higher accuracy than the relaxation times obtained from $`\mathrm{log}\mathrm{\Delta }W\times t`$ plots (typically for a factor $`3`$).

We considered two possible values of the constant $`k`$ in Eq. (10), $`k_1=11/e=0.6321\mathrm{}`$ and $`k_2=0.8`$. The first choice would give $`\tau _0=\tau `$ if $`a=b`$ (Eqs. 9 and 11), which seems to be approximately valid for $`BD`$. The effective exponents $`z_L`$ were obtained from

$$z_L=\frac{\mathrm{ln}\left[\tau _0\left(L\right)/\tau _0\left(L/2\right)\right]}{\mathrm{ln}2},$$
(12)
and must be independent of the particular choice of the constant $`k`$.

In Figs. 3a and 3b we show $`z_L`$ versus $`1/L`$ for the three models using $`k=k1`$ and $`k=k_2`$, respectively, in the calculation of $`\tau _0`$ (Eq. 10). $`W`$ data were used, but the effective exponents obtained from $`\xi `$ are nearly the same. The uncertainties in $`W_{sat}`$ are responsible for the error bars, thus results with $`k=k_1`$ (larger $`\mathrm{\Delta }W`$) are more accurate.

In all cases shown in Figs. 3a and 3b, $`z_L`$ converges to the exactly known values as $`L\mathrm{}`$. In the Family and in the $`RSOS`$ models, $`z=2`$  and $`z=3/2`$  are recovered with small finite-size corrections. In $`BD`$, $`1/L`$ corrections to $`z_L`$ lead to expected $`z=3/2`$  asymptotic value. It is interesting to notice that these corrections in $`BD`$ are weaker than the corrections found in effective exponents $`\beta _L`$ and $`\alpha _L`$ in Ref. , which proves the relevance of developing methods to estimate $`z`$ independently. Moreover, this result complements that systematic study of $`BD`$ in $`d=1`$, which discussed the discrepancies in numerical estimates of critical exponents and the controversies on the equivalence of $`BD`$ and the $`KPZ`$ theory .

## III Results in two-dimensional substrates

First we consider the $`RSOS`$ model in $`d=2`$. Simulations were performed for lengths $`32L512`$, with a small number of realizations (nearly $`10^3`$) in the largest lattices. The exponential decay of $`\mathrm{\Delta }W\left(t\right)`$ is confirmed in Fig. 4a for lattices of length $`L=512`$. In Fig. 4b we show $`z_L`$ versus $`1/L`$, which gives the asymptotic estimate $`z=1.60\pm 0.05`$. This result is consistent with several previous estimates of critical exponents for that model .

Using $`W_{sat}`$ data, we were also able to obtain finite-size estimates of the exponent $`\alpha `$:

$$\alpha _L=\frac{\mathrm{ln}\left[W_{\mathrm{}}\left(L\right)/W_{\mathrm{}}\left(L/2\right)\right]}{\mathrm{ln}2}.$$
(13)
In Figs. 5a and 5b we show $`\alpha _L`$ versus $`1/L`$ obtained from $`W`$ and $`\xi `$ data, respectively. Both sets of data strongly suggest an asymptotic exponent $`\alpha <0.4`$, which agrees with simulations of Marinari et al , who obtained $`\alpha =0.393\pm 0.003`$. However, it disagrees with the proposal of $`\alpha =0.4`$ based on an operator product expansion , which suggests further investigations on these lines.

For the Family model, it is expected the dynamic scaling relation

$$W^2=A\mathrm{ln}\left[Lf\left(t/\tau \right)\right]$$
(14)
where $`f`$ is a scaling function and $`A`$ is constant. As $`x\mathrm{}`$, it is expected that $`f(x)a`$, with constant $`a`$. The characteristic time $`\tau _0`$ defined from Eq. (10) is not proportional to $`\tau `$ anymore. Then, in order to define a characteristic time $`\tau _1`$ which is proportional to $`\tau `$ in this system, we consider

$$\delta W^2W_{sat}^{}{}_{}{}^{2}W\left(\tau _1\right)^2=C,$$
(15)
with constant $`C`$.

The characteristic times $`\tau _1`$ were calculated using Eq. (15) with $`C=0.03`$. The effective exponents $`z_L`$ were also obtained from Eq. (12). In Figs. 6a and 6b we show $`z_L`$ versus $`1/L`$ obtained from $`W`$ and $`\xi `$ data, respectively. In both cases, $`z_L`$ converges to $`z=2`$ as $`L\mathrm{}`$, in agreement with the $`EW`$ theory. Our result is significantly better than the value $`z1.63`$, obtained in Ref.  using data collapse methods, which again proves the reliability of our method.

## IV Summary and conclusion

We proposed and tested methods to estimate crossover times of interface width scaling and the dynamic exponent $`z`$. We showed that the typical decays of $`W`$ or $`\xi `$ to their saturation values are exponential, which uniquely defines the crossover or saturation times $`\tau `$. In order to estimate $`z`$ with accuracy, we used a characteristic time $`\tau _0`$ that is proportional to $`\tau `$, according to the Family-Viczek scaling. The reliability of the method was proved by testing it with the Family, the $`RSOS`$ and $`BD`$ models in $`1+1`$ dimensions, in which dynamic exponents of the $`EW`$ and the $`KPZ`$ theory were obtained. The Family and the $`RSOS`$ models in $`d=2`$ were also considered. For the $`RSOS`$ model, the exponential decay of $`W`$ is confirmed, and $`z1.6`$ was obtained. Moreover, estimates of saturation widths suggest that $`\alpha <0.4`$, in agreement with a recent prediction of large scale simulations . For the two-dimensional Family model, the expected dynamic scaling hypothesis lead to an alternative definition of the characteristic time $`\tau _0`$, and the exact value $`z=2`$ was recovered.

The relevance of our methods to estimate dynamical exponents is also proved by comparisons with previous results for related systems. For instance, using data collapse of relaxation functions and the expected scaling of $`W`$ at $`t=L`$, $`z=1.55`$ was obtained for Eden clusters  and $`z=1.57`$ for the single-step model  in $`d=1`$. Both systems are in the $`KPZ`$ class (exact $`z=1.5`$). These difficulties were pointed out in the paper of Kim et al , who proposed a method to measure $`z`$ from the scaling of a relaxation function and an initial sinusoidal surface. Although the efficiency of their method was clearly stated, working with a flat surface is the most usual initial situation in theoretical works and is more suitable for real applications. Moreover, with our method, one is able to calculate three exponents, $`\alpha `$, $`z`$ and $`\beta `$, using the same set of data. The relevance of each one to determine the universality class of a particular model may depend on several factors, such as the strength of finite-size corrections. Thus we expect that this work may be useful for further studies of surface growth models.

###### Acknowledgements.

This work was partially supported by CNPq and FINEP (brazilian agencies). The author thanks the Department of Theoretical Physics at Oxford University, where part of this work was done, for the hospitality.


text:
# Symbolic Dynamics for Discrete Adaptive Games

## I Discrete Adaptive Games

### I.1 Introduction

In the last few years, physicists have become very interested in discrete games. In these models, a finite number of players or agents pick from a finite set of actions (possibly varying from agent to agent), at discrete times, and receive rewards that depend on their own and the other agents’ actions. Each agent chooses according to a rule called its strategy; if agents have more than one strategy available, they use a meta-strategy to chose among them.

As described, the setting fits classical game theory von Neumann and Morgenstern (1944); Gintis (2000), with its assumption of so-called substantive rationality — the agents have rational, accurate expectations, enjoy common knowledge of the structure of the game, and act so as to maximize their reward. Casual observation suggests this is not a good model of human behavior, and indeed experimental psychology Kahneman et al. (1982) and experimental economics Camerer (1995) both reject it decisively. Failing substantive rationality, one turns to some form of bounded rationality Simon (1996) — agents still pursue goals, but are limited by finite knowledge and finite cognitive capacities, and so cannot, in general, maximize anything. Bounded rationality is the subject of a rich literature in the social sciences, which encompasses both abstract models Rubinstein (1999), some of which exploit familiar methods of statistical physics Young (1998), and a rapidly-growing experimental literature, which includes its own array of models Klein (1998); Zsambok and Klein (1997); Gigerenzer et al. (1999); Gigerenzer and Selten (2001). While the econophysical literature almost exclusively considers boundedly-rational agents, it never builds upon other work on bounded rationality. For instance, one of the best-supported meta-strategies is that of satisficing, in which an agent searches over its options and takes the first one it finds with a satisfactory reward Simon (1955, 1956, 1982). We are unable to find a single paper which employs this notion. Econophysical strategies are all, so far as we know, of the following form. Each agent remembers a simple summary statistic (e.g., the best action to have taken) for each of the last $`m`$ turns of the game. For each such history, a strategy specifies an action to take. Rather than maximizing, or even satisficing, they employ adaptive meta-strategies tending to select strategies that did well in the recent past.

These caricatures or toy models have been studied since the 1980s, because, it is said, they (1) shed light on real learning and mutual adaptation, and (2) show surprisingly complex behavior. In this paper, we examine two forms this complexity is held to take — deterministic chaos, which is a sort of dynamical complexity, and formally measured complexity, specifically the amount of information embedded in the system. The rest of this section describes the most popular discrete adaptive games, the minority game and the El Farol Bar problem. The next section introduces the tools from symbolic dynamics, particularly subshifts of finite type, which we will use to pry open the mechanisms of these games. We show that the games are non-chaotic, and put linear upper bounds on their complexities. We discuss how to extend our results to games with either memories of unlimited length, or noisy play. We then consider what you must do to a game to make it chaotic, if you want it to be chaotic. In closing, we suggest a way to reconcile our findings with common observations on these games.

### I.2 Examples: El Farol and the Minority Game

The best-loved game in econophysics is the minority game of Challet and Zhang Challet and Zhang (1997), the subject of a rapidly growing literature (see http://www.unifr.ch/econophysics/minority/). There are $`N`$ agents, each of which can make only one of two moves: play “0” or play “1”. If most agents play 0, then those who play 1 win, and vice-versa. ($`N`$ is always odd.) Each player remembers whether 0 or 1 won on each of the last $`m`$ turns. Strategies, again, are rules mapping histories to actions; each agent has $`s`$ of them. In effect, strategies must predict what most players will do, and then do the opposite. Agents keep track of how many times each of their strategies would have won, and use the strategy with the best record over the time it can remember. (Note that psychologists have studied human performance in just such discrete prediction situations since the 1950s, without finding anything resembling this learning mechanism Myers (1976).) Ties between strategies are broken randomly or pseudo-randomly, say by assigning strategies a random order at the beginning of the game.

Traditionally, the minority game has been studied either using the brute empiricism of simulations, or with statistical-mechanical methods, particularly those employing the thermodynamic limit. Recently, Jefferies, Johnson et al. have introduced methods owing more to dynamical systems, e.g., de Bruijn graphs over possible sequences of winning outcomes Jefferies et al. (2002a, b). Our approach here is related to theirs, but is even more deterministic, and more microscopic.

The minority game descends from W. B. Arthur’s El Farol Bar Problem Arthur (1994). There are 100 people in Santa Fe who go out to bars; El Farol is the only good bar. Normally, those who go there are better off than those who stay home and watch the stars. But El Farol is small, and if more than 40 people go, crowding makes the bar-goers worse off than stay-at-at-homes. Everyone knows how many people went to the bar on each of the last $`m`$ nights. Strategies, again, map histories to actions — staying home or going to the bar.

Rather than statistical mechanics, the traditional approaches to the El Farol problem are those of evolutionary adaptation and inductive behavior. Many have sought to show that either the population of agents co-evolves a set of mutually-tolerable strategies, or that a ceaseless evolutionary arms race forces everyone to “run as fast as they can just to stay in place” Arthur (1994); Gintis (2000).

## II Symbolic Dynamics, Shifts

Symbolic dynamics is one of the basic analytical methods of nonlinear dynamics and complex systems, and as such its elements are discussed in standard introductory textbooks on those subjects (e.g., Refs. Guckenheimer and Holmes (1983); Devaney (1992); Alligood et al. (1996); Hilborn (1994); Wiggins (1990); Badii and Politi (1997)). Strangely, however, it does not seem to have been applied to discrete adaptive games before. We therefore give a few words of motivation, before presenting some basic notions and results. Readers whose curiosities are aroused will find Refs. Wiggins (1990) and Badii and Politi (1997) particularly nice introductions, emphasizing uses in nonlinear dynamics and complexity, respectively. Refs. Kitchens (1998) and Hao and Zheng (1998) more advanced treatments.

### II.1 Why Symbolic Dynamics?

The essence of symbolic dynamics is substituting strings of discrete characters or symbols for trajectories in an original continuous state space. Motion in the original space corresponds simply to shifting along the string. This idea goes back to work by Morse and others in the 1930s. One of its first great successes came in a paper by Smale Smale (1965) which introduced his famous “horseshoe”, and established the geometry of what we now call chaotic dynamics. Smale first constructed a differentiable, invertible map $`f`$ on a two-dimensional manifold $`M`$ , which, while it has a very simple functional form, has almost impossibly complicated geometric behavior. He then connected it to the full binary shift map $`\sigma `$ on infinite sequences of 0s and 1s — that is, the map which simply substitutes the symbol at position $`i+1`$ for that at position $`i`$. The dynamics of $`\sigma `$ are very easy to grasp. In particular, it is easy to see that it has a countable infinity of periodic points of arbitrarily high period, an uncountable infinity of non-periodic points, and a dense orbit. (Recall that rational numbers, which are countable, have repeating binary representations, while irrational numbers, which are uncountable, never repeat.) The great trick, then, was to show that the horseshoe map $`f`$ and the shift map $`\sigma `$ were topologically conjugate. That is, he found a continuous function $`\varphi `$ from a subset of the manifold $`M`$ to the sequence space $`\mathrm{\Sigma }`$ which was one-to-one and onto, and which commuted with the two maps. (Symbolically, $`\varphi f=\sigma \varphi `$.) This meant that the dynamical properties of the horseshoe map could be read off directly from those of the shift map.

The attraction of symbolic dynamics should now be clear: we can, so to speak, factor the dynamics of interest into a clean, simple shift map ($`\sigma `$), and a messier, but less material, conjugacy map ($`\varphi `$). If, for instance, we could show that the shift map and the minority game are topological conjugate, or discern the mechanisms that prevent them from being conjugated, the dynamics of the minority game itself would be much more plain to us.

### II.2 Basic Notions

We now will quote the relevant standard results without proofs, which may be found in e.g. Ref. Kitchens (1998). Begin with a finite or countable alphabet $`X`$ of symbols. From these we make strings or words over $`X`$, which are symbol sequences, $`x_0x_1x_2\mathrm{}x_n`$. Our shift space is a set of semi-infinite words, $`x=x_0x_1x_2\mathrm{}x_i\mathrm{}`$ (i.e. we will be concerned with sequences on only one side of the decimal point). The dynamics are given by a shift operator $`T`$: $`Tx=x_1x_2\mathrm{}`$. That is, $`(Tx)_i=x_{i+1}`$. The orbit of a point is its set of future iterates, $`\{x,Tx,T^2x,\mathrm{}\}`$.

It is useful, and perhaps comforting, to invoke linear operators at this point. Let $`A`$ be a square 0-1 matrix, with as many rows as $`X`$ has symbols. Define a shift space $`X_A`$ where $`x`$ is allowed iff $`i`$, $`A_{(x_i)(x_{i+1})}=1`$. Then $`X_A`$ is a subshift of finite type and the matrix $`A`$ corresponds to the shift operator $`T`$. We can also represent $`X_A`$ with a directed graph $`G_A`$, where there is one node for each symbol, and an edge from $`i`$ to $`j`$ iff $`A_{ij}=1`$. Then $`xX_A`$ iff it is a path through $`G_A`$. The transition matrix is one-many if there are symbols $`i,j,k`$ such that $`A_{ij}=1`$ and $`A_{ik}=1`$ but $`jk`$. $`A`$ is many-one if there are $`i,j,k`$ such that $`A_{ik}=1`$ and $`A_{jk}=1`$ but $`ij`$. And $`A`$ is one-one if it is neither many-one nor one-many.

We now have a space $`X_A`$ of sequences, and some of the properties of this space will be useful later on. First, the standard metric between two sequences (points) $`x`$ and $`y`$ in the shift space is

$`d(x,y)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1\delta (x_i,y_i)}{2^i}},`$ (1)
where $`\delta (a,b)`$ is the Kronecker delta. Thus if $`x_i=y_i`$ for all $`iM`$, then $`d(x,y)2^M`$. Conversely, if $`d(x,y)<2^{M+1}`$, then $`x_i=y_i`$ for all $`iM`$. From this it follows that the sequence space, equipped with the standard metric, is compact, totally disconnected and perfect (i.e., it is closed, and every point is a limit point).

### II.3 Entropies and Lyapunov Exponents

It is now useful to deal with notions defining growth rates of a given space and spreading rates along orbits. This will be achieved via standard entropies and Lyapunov exponents borrowed from ergodic theory. In general, not all words are allowed, i.e., not every semi-infinite word is in the shift space. Likewise, many of the sequences are never seen due to the particulars of the shift operator. If $`W(L)`$ is the number of allowed words of length $`L`$, the topological entropy is

$`h`$ $`=`$ $`\underset{L\mathrm{}}{lim}{\displaystyle \frac{1}{L}}\mathrm{log}W(L).`$ (2)
That is, $`h`$ is the asymptotic exponential rate of growth in the number of allowed words. It measures the degree of exponential spreading in the dynamics. Normally, of course, that is measured by the Lyapunov exponents. Assuming those can be defined, the largest Lyapunov exponent $`\lambda _1h`$. (For specific conditions under which the Lyapunov exponents exist, see Refs. Ruelle (1982); Pesin (1977); Katok (1980).)

The topological entropy gives equal weight to every possible word, no matter how improbable. If we wish to give more weight to the more probable strings, it is natural to start with the entropy over words of length $`L`$,

$`H(L)`$ $``$ $`\mathrm{log}\mathrm{Pr}(x_1^L)`$ (3)
where $``$ denotes expectation. This is the mean amount of information, in bits, required to specify a word of length $`L`$ generated by the dynamics. We then define the metric entropy rate or Kolmogorov-Sinai entropy as

$`h_\mu `$ $``$ $`\underset{L\mathrm{}}{lim}{\displaystyle \frac{H[L]}{L}}.`$ (4)
In addition to being an important invariant of the dynamical system, the metric entropy rate can be thought of as the rate of information production — the rate at which new information is produced by the dynamics. Clearly, $`hh_\mu `$ Katok and Hasselblatt (1995). Under certain conditions on $`f`$ Ruelle (1978); Margulis (1969); Pesin (1977), $`h_\mu `$ is equal to the sum of the positive Lyapunov exponents; more generally it is a lower bound on their sum. Thus, a positive $`h_\mu `$ guarantees the existence of at least one positive Lyapunov exponent. The proofs of these assertions are somewhat complicated results from ergodic theory, well-summarized in Ref. Katok and Hasselblatt (1995).

### II.4 Chaos

We adopt the standard topological definition of chaos, due to Devaney Banks et al. (1992). A compact set $`\mathrm{\Lambda }`$, invariant under $`T`$, is chaotic if $`T`$ is topological transitive on $`\mathrm{\Lambda }`$, and its periodic orbits are dense in $`\mathrm{\Lambda }`$. Topological transitivity means that the trajectory of any open set in $`\mathrm{\Lambda }`$ eventually visits every other open set in $`\mathrm{\Lambda }`$ — we can get from one part of the region to any other. Together with the requirement of dense periodic orbits, this implies sensitive dependence on initial conditions. One can imagine the chaotic trajectories wandering between (but never on) the dense periodic orbits. Note that the periodic orbits, while dense, are not stable or attracting Smale (1967). In fact, sensitive dependence on initial conditions, which we have just established, in turn implies exponential separation of nearby orbits, at least under fairly weak conditions, and hence a positive Lyapunov exponent and positive entropy rates. These, accordingly, constitute the numerical or experimental signatures of chaos.

For subshifts of finite type, all of this can be related to the matrix $`A`$ (or the corresponding graph) very directly. $`X_A`$ is transitive if it has dense orbits. (N.B., not necessarily dense periodic orbits.) $`X_A`$ is irreducible if for every pair of indices $`i`$ and $`j`$, there is some $`l>0`$ for which $`\{A^l\}_{ij}>0`$. (This is the same as $`G_A`$ being strongly connected.) Now, if $`X_A`$ is irreducible, then either it is transitive or it consists of a single periodic orbit. Likewise, if $`X_A`$ is transitive, then $`A`$ is irreducible.

## III The Minority Game as a Shift Map

To do one iteration of the minority game, we need to know two things. (1) The history of the last $`m`$ rounds — which action won on each of them. (2) The “gains” of all the strategies possessed by the agents — the number of times each strategy predicted the winning action in the last $`m`$ rounds. These facts fix the action of each agent, and so the winner of the round. That is, the next state of the game is a deterministic function of its present state. (In what follows, “state” will always mean the global state of the game, never the state of an individual agent.)

Since each state variable takes only finitely many values, we can map the state as a whole into a finite alphabet. We order the states and their alphabetic symbols however we like. Then we build a square matrix $`A`$, where $`A_{ij}=1`$ if $`j`$ follows $`i`$, and $`=0`$ otherwise. $`X_A`$ defines a subshift of finite type over states of the minority game, and every run of the minority game is an allowed orbit of this subshift. We could write down $`A`$ in some detail, but shan’t.

Suppose memory for gains extends back indefinitely. Then the state comes from a countably infinite alphabet, rather than a finite one, but the subshift is still deterministic (many-one).

In the finite-memory case, the lack of chaos is elementary once we realize that there are only finitely many states; the full apparatus of symbolic dynamics is over-kill. There are only finitely many symbols, so every string will eventually repeat a symbol. But each symbol has a unique successor, so after the first repetition, the string just repeats a single word. Hence every orbit is eventually periodic.

The topological entropy rate is zero. The first symbol of a string fixes all subsequent ones, so $`L`$, $`W(L)=W(1)`$, and $`h=0`$ by Eq. 2.

## IV Complexity in the Minority Game

Before we can say quantitative things about the complexity of a model, we must pick a complexity measure, of which there are many Badii and Politi (1997). When people have discussed the complexity of discrete games at all, they have picked the Kolmogorov complexity or “algorithmic information content” Li and Vitanyi (1993). Kolmogorov introduced this concept as part of a definition of “randomness” relying on purely combinatorial notions, part of a long-standing program of research in the foundations of probability von Plato (1994). The Kolmogorov complexity $`K(w)`$ of a finite string $`w`$ is the length of the shortest computer program which will produce that string as its output and then stop111We will ignore some subtleties relating to the choice of programming language, which do not affect the argument. Because any string can be produced by a program like print ‘‘w’’, the complexity of any string cannot be more than its length plus a constant (the length of the “print” instruction). On the other hand, some strings can be produced by programs which are much shorter than themselves, e.g., a string of a million 0s can be produced by iterating the command print ‘‘0’’ a million times. A random strings, roughly speaking, is one which cannot be generated by any program significantly shorter than the string itself. More exactly, if $`x_1^L`$ are the first $`L`$ symbols of an infinite word, and $`K(x_1^L)/n1`$, then all the properties which are true of a sequence of independent, identically distributed random variables are true of the symbols in the infinite word. For deep reasons connected with the existence of uncomputable numbers, there can be no general procedure for computing the Kolmogorov complexity of arbitrary strings, nor are there any known procedures which give well-controlled approximations Li and Vitanyi (1993); Cover and Thomas (1991). However, if the symbols are generated by an ergodic process, there is an easy expression for the expected rate of growth in the complexity Brudno (1978): $`K(x_1^L)/Lh_\mu `$ as $`L\mathrm{}`$. This is another illustration of the fact that $`h_\mu `$ measures the rate of information production.

While, as we have said, there is no real way to compute the Kolmogorov complexity, several papers in the physics literature have attempted to calculate it for games Mansilla (1997, 2000a, 2000b) and even for real markets Mansilla (2001); Mantegna and Stanley (2000), with the claim Mantegna and Stanley (2000) that the high complexity they obtain shows that financial time series contain much valuable information. Pace these authors, had they actually been able to calculate the algorithmic information content, a high value of it would indicate that the systems they considered were basically random, because this is just what Kolmogorov complexity means.

Assuming one wants a notion of “complex” which is not the same as “random”, what should a good complexity measure be like? As mentioned, many measures have been proposed Badii and Politi (1997), but there is some consensus about what features a good measure should have. It should be low for both highly ordered and highly random systems; it should be calculable; and it should have a clear dynamical meaning, rather than just being a number for its own sake Feldman and Crutchfield (1998). To our knowledge, only one measure satisfies all these criteria, the statistical complexity of Crutchfield and Young Crutchfield and Young (1989), a fully formalized and operational version of Grassberger’s Grassberger (1986) conjectural “true measure complexity”. It is the amount of information about the past of the system needed for maximally accurate prediction of its future Shalizi and Crutchfield (2001).

We get the statistical complexity by finding the causal states of the system: each causal state is a distinct distribution for future events, conditional on the past of the system. Abstractly, we find the conditional distribution $`\mathrm{Pr}(x_1^{\mathrm{}}|x_{\mathrm{}}^0)`$ for each past $`x_{\mathrm{}}^0`$, and group pasts with the same distribution into states. The probability of a state is then the sum of the probabilities of all the pasts assigned to it, and the distribution conditional on the state is just the same as the distribution conditional on the individual pasts. (In practice, we use a number of recursive tricks to approximate the causal states from finite data, while only looking at the conditional distribution of the next symbol Shalizi et al. (2002).) The statistical complexity $`C_\mu `$ is simply the entropy (uncertainty in bits) of the causal states $`=_ip_i\mathrm{log}_2p_i`$, where $`p_i`$ is the probability of the $`i^{\mathrm{th}}`$ causal state. This is maximized when all causal states are equally probable. In the case of a periodic process, each phase is a causal state, and each state is equally probable, so $`C_\mu =\mathrm{log}_2P`$.222For non-periodic processes, $`2^{C_\mu }`$ is the geometric average of the expected recurrence times of the causal states, i.e., still the average amount of time needed to return to a state after leaving it.

We have just seen that the minority game has only periodic orbits, so to get $`C_\mu `$, we just need the period. Start with just one strategy per agent. After the system has seen every possible history, it must repeat itself, so $`P2^m`$. Now give each agent several strategies. The number of ways agents can deploy strategies is $`Ss^N`$. When we’ve gone through every possible history, the agents could be using different strategies than before. But once we’ve seen all deployments of strategies, we must be back where we started. Thus $`PS2^ms^N2^m`$. Even these bad estimates give us

$`C_\mu `$ $``$ $`m+N\mathrm{log}_2s`$ (5)
The complexity grows linearly with memory and population at most. We get this growth rate only with complete (combinatorial) independence — an agent’s strategy selection is constrained neither by the selections of other agents, nor even by the global history!

In a number of recent papers, Savit, Parunak and collaborators Savit et al. (2002, 2003); Parunak et al. (2002) have considered a complexity measure closely related to the statistical complexity (they do not give it a name). In essence, following Savit and Green (1991), they treat two pasts as belong to the same state if and only if they they lead to the same unique next symbol, whereas statistical complexity requires only that they lead to the same distribution of future symbols. The two complexities coincide for periodic processes. In the presence of noise, however, the method of Savit et al. will be forced to rely on longer and longer histories, until it finds ones that look deterministic simply because of undersampling, and their complexity will diverge logarithmically in the size of their data set Marton and Shields (1994). The statistical complexity, however, is well-behaved in the presence of noise (see Section VI below).

## V Infinite Memory for Gains

People sometimes play the minority game with an infinite memory for gains — agents remember the number of times each strategy has won since the beginning of the game, rather than just in the last $`m`$ turns. Then the alphabet is countably infinite. But what matters are the difference in strategies’ gains, and if those are bounded, the finite-state arguments take over. Even when differences in gains are unbounded, the shift map is many-one, so there is just a single 1 in each row of the transition matrix $`T`$.

The topological entropy rate of a countable-state shift is (Kitchens, 1998, Observation 7.2.10)

$`h`$ $`=`$ $`\underset{n\mathrm{}}{lim\; sup}{\displaystyle \frac{1}{n}}{\displaystyle \underset{j}{}}(T^n)_{ij},`$ (6)
independent of $`i`$. From many-oneness, the sum in Eq. 6 is always exactly 1, so $`h=0`$.

Let us consider also the question of exponential spreading.

The distance between points in the standard metric is at most 2. $`d(x,y)=2`$ iff $`x_iy_i`$ for all $`i`$. In that case, $`d(T^nx,T^ny)=2`$ for all $`n`$, so maximally-separated points stay maximally separated. On the other hand, if the distance between $`x`$ and $`y`$ is less than 2, then at some position, $`k`$, $`x_k=y_k`$. By the many-oneness of the shift, if $`j>k`$, $`x_j=y_j`$. Therefore, the distance between the iterates of $`x`$ and $`y`$ shrinks until it hits 0. Distance never increases; spreading of any sort, never mind exponential spreading, is impossible.

The distance between any two distinct periodic points is always maximal; that is, given two periodic points $`x`$ and $`y`$, if $`xy`$, then $`x_iy_i`$ for all $`i`$. To see this, consider first the case of two points on the same periodic cycle, of period $`P`$. For some $`0<L<P`$, $`T^L(x)=y`$. Suppose that, for some $`k`$, $`x_k=y_k`$. Then $`T^kx=T^ky=T^{k+L}x`$, so $`T^kx`$ is periodic with period $`L<P`$, which is absurd. Now consider points on two distinct periodic cycles. Suppose there were a $`k`$ such that $`x_k=y_k`$. Then $`T^k(x)=T^k(y)`$. Hence there is a point, $`T^k(x)`$, belonging both to the $`x`$ cycle and the $`y`$ cycle. But this is absurd, because the cycles are distinct.

Suppose periodic points were dense. Then for any point $`x`$ and any distance $`ϵ>0`$, there would be a periodic point $`yx`$ such that $`d(x,y)ϵ`$. But if $`x`$ is itself periodic, then we have just seen that $`d(x,y)=2`$ no matter what periodic point $`y`$ we chose. Therefore periodic points are not dense. Chaotic maps have dense periodic points, so this shift map isn’t one.

## VI Noise

Traditionally, the minority game is played somewhat noisily — either players chose strategies with some degree of randomness, or the move they make, once they have chosen a strategy, is somewhat random. This makes the game amenable to statistical-mechanical treatment, a point which has been thoroughly explored elsewhere. Here, we will see that it can make the entropy rate positive, but does not increase the complexity.

The usual types of noise imposed in discrete games change them from deterministic maps into Markov chains. This means we can represent the state of the game at one time as a function of the state at the previous time, and a sequence of stationary, independent noise variables, i.e., $`x_{t+1}=f(x_t,\eta _t)`$, where $`\left\{\eta _t\right\}`$ are IID random variables which are also independent of the $`x_t`$. The Markov property of the sequence $`\left\{x_t\right\}`$ also means that its entropy rate (metric or topological) is just the entropy of $`x_{t+1}`$ conditional on $`x_t`$ Cover and Thomas (1991); Kitchens (1998). That is, $`h_\mu =H[x_{t+1}|x_t]`$, and similarly for $`h`$. Now, applying some basic results of information theory (Cover and Thomas, 1991, ch. 2),

$`H[x_{t+1}|x_t]`$ $`=`$ $`H[f(x_t,\eta _t)|x_t]`$
$``$ $`H[x_t,\eta _t|x_t]`$
$`=`$ $`H[\eta _t|x_t]=H[\eta _t]`$
Or, in words: because the only source of randomness is the noise, the entropy rate of the states must be no more than the entropy of the noise. A parallel argument holds for the topological entropy. Nothing in the process amplifies the noise.

Now let us consider the statistical complexity. Recall that a causal state is a distinct distribution of the system’s future behavior, conditional on its past. For noise of the sort described, the present state of the game determines the distribution of future symbols, independent of any other feature of the past of the system. So the present symbol fixes the causal state. The noise could make some causal states more likely than others (reducing the complexity), or could even lead to two symbols having the same distribution over future orbits, merging them into a single causal state (again lowering the complexity). Adding noise simplifies matters, if it does anything at all.

## VII Conclusions

We analyzed the global behavior of discrete adaptive games, using symbolic dynamics. These games are not chaotic, and the most popular ones are actually of low complexity, at most linear in the number of agents.

The crucial obstacles to chaos were that the state of the minority game can be summarized in a discrete alphabet, and that the evolution of those states is many-one. Our results will apply, mutatis mutandis, to any deterministic adaptive game of which this is true, for instance, the El Farol problem, and various discrete market models. To repeat, this is not an artifact of discretizing continuous models, but a feature of deliberately discrete ones. Nothing depends on the meta-strategy; our results hold with learning, imitation, evolution, etc., so long one implements them non-anticipatively.

### VII.1 Exponential Spreading versus Exponential Transients

Anyone who looks at a simulation of the minority game sees an intricate, hard-to-predict process — we certainly do. Scientists trained in nonlinear dynamics naturally look to exponential divergence of orbits to explain these observations. We have seen that there is no such divergence in the standard, noiseless version of these games; there are three ways to get it.

* Hidden information. If only some agents have access to a (changing) outside source of information, then there can be apparent transitivity in the game, and so deterministic chaos. A neat example is the Brock-Hommes asset-trading model Brock and Hommes (1998, 1997, 1999), where agents get simple adaptive strategies for free, but must pay for rational expectations of future prices.
* Add noise. As we’ve seen (Sec. VI), this certainly allows exponential divergence, but in a trivial way, and at a cost in complexity.
* Coupling to chaos. Break ties using a chaotic shift map, or something similar. Often this will make the game chaotic.

Only the first of these mechanisms has any economic relevance. In real markets, information is expensive, but transparency is prohibitively expensive, and so hidden information is ubiquitous. Exploring the consequences of this is an important problem of great economic interest; indeed, the problem is common across almost all social situations. The other methods, by contrast, are “unphysical,” lacking in substantive content. Of course, hidden information cannot explain the phenomenology of games in which it is absent, but it is no less interesting on that account.

What however does account for that phenomenology? We suggest that the answer is exponentially fast divergence, but rather exponentially slow convergence. For the minority game, it is numerically well established that relaxation times grow exponentially with $`m`$ Marsili and Challet (2001). What is less appreciated is that, in high-dimensional dynamical systems, the approach to the attractor can be so slow that it is never reached in simulations, at least not within the lifespan of ordinary experimenters (but see Dyson (1979)). In systems formed by coupling smaller dynamical systems, such as the agents in our games, the duration of the transient epoch often grows exponentially with the number of agents Crutchfield and Kaneko (1988). The attractors and their invariant distributions are irrelevant; what matters is the structure of the attractor basin Wuensche and Lesser (1992) and the quasi-stationary transient distribution it produces Crutchfield (1988). Once recognized, these long transients are actually a feature of discrete adaptive games, since the social systems they are supposed to model are essentially never in an invariant state, but always “in transition”333This does not mean they are never in equilibrium, in the economists’ sense, however.. The transients are, however, bad news for methods based on either ergodic or thermodynamic limits. Quantities like the entropy rate and the Lyapunov exponents, which are rigorously defined only in the limit, loose much of their interest.

### VII.2 Directions for Future Work

The motive for studying models like the minority game should not be that they are complex systems in some formal sense. In any area of modeling, formal constructs acquire interest from their ability to help resolve problems of physical relevance — that is, here, social relevance. We have argued that such constructs as algorithmic complexities and stationary and thermodynamic limits have not demonstrated such relevance here, and are unlikely to do so in the future. By contrast, the distinctively transient dynamics of such systems, especially their basin structure, hold great promise for understanding the origins of complex behavior we see in these games. The hope of econophysics is that these models portray, in stylized miniature, key aspects of real mutual adaptation and social interaction, and that studying the portrait will help us understand the original. This is not an outlandish hope, since profound insights have come from studying the equally-stylized Prisoners’ Dilemma Axelrod (1984), and a host of other, less famous models Simon (1996); Gintis (2000); Schelling (1978) have illuminated the collective life of political, boundedly-rational animals. We hope that the discrete adaptive games of econophysics will take their place in this set. The contribution of econophysics, it seems to us, be to assimilate the rich body of empirical findings and models of individual choice and learning, and say something distinctive and illuminating about how large numbers of such boundedly-rational agents interact.

### Acknowledgments

We thank Sam Bowles, Sven Brueckner, Jim Crutchfield, Dee Dechert, Richard Gonzalez, Cars Hommes, Matt Jones, Cris Moore, Scott Page, Van Parunak, Robert Savit, Kris Shalizi, Clint Sprott and Libby Wood for valuable conversation and suggestions. CRS also thanks Kris Shalizi for being perfect. Our work at SFI was supported by the Dynamics of Learning program, under DARPA cooperative agreement F30602-00-2-0583, and CRS’s work at Ann Arbor by a grant from the James S. McDonnell Foundation.