Money as a Medium of Exchange in an Economy with Artificially Intelligent Agents

1. Introduction¶

Kiyotaki & Wright (1989) studied how three classes of rational agents would interact within a Nash-Markov equilibrium in a world of repeated ‘Wicksell triangles’. This paper studies how a collection of artificially intelligent agents would learn to coordinate their activities if they were thrust into the economic environment described by Kiyotaki and Wright. Our agents’ behavior is determined by Holland (1975) classifier systems.^[1]

Thus, while Kiyotaki and Wright studied stationary equilibria in which beliefs about ‘media of exchange’ are consistent with trading patterns, we study economies in which particular commodities emerge as media of exchange. We also study an economy (Economy C) in which a good from which no agent derives utility emerges as fiat money. We want to learn whether our artificially intelligent agents can learn to play a Markovian Nash equilibrium of the Kiyotaki-Wright model. When there are multiple Nash equilibria (e.g., the ‘fundamental’ and ‘speculative’ equilibria of Kiyotaki and Wright), we want to know whether the system might converge to some but not others of these equilibria. In addition, if classifier systems do converge to Nash-Markov equilibria, they might be used to compute equilibria in other economies for which it is difficult to obtain analytic solutions. To this end, we also study enlarged versions of the Kiyotaki-Wright model.

A classifier system is a collection of potential decision rules, together with an accounting system for selecting which rules to use. The accounting system credits rules generating good outcomes and debits rules generating bad outcomes. The system is designed to select a ‘co-adaptive’ set of rules that work well over the range of situations that an agent typically encounters. In a multiple-agent environment like Kiyotaki and Wright’s, the range of situations encountered by one agent depends on the actions taken by other agents. This means that the collections of rules used by the collection of agents must co-adapt jointly.

We study two sorts of classifier systems, with the distinction between them being induced by the fact that for many problems enumerating all possible rules would require a very long list. The first kind of classifier system is one in which a complete enumeration of all possible rules is carried along. For many problems, it is not feasible to use a complete enumeration classifier system because the state and action spaces are so large that the set of all possible rules is much too big. For us, a complete enumeration is tractable because the Kiyotaki-Wright model has low-dimensional state and action spaces.

The second kind of classifier system is designed for situations in which it is not efficient to carry along a complete enumeration of decision rules. In this case, a modified version of the genetic algorithm of Holland is used as a device for periodically eliminating some rules and injecting new rules into the population of rules to be operated on by the accounting system. The genetic-algorithm version of the classifier models learning in the face of unforeseen contingencies. When an unprecedented state arises which is not covered by the existing set of rules, the system contains a procedure for manufacturing and experimenting with new rules that apply in the new situation. Even though it is feasible for us to work with a complete enumeration of rules, we also study the genetic-algorithm version of the classifier.^[2]

In this paper, we set up classifier systems for the Kiyotaki-Wright environment and simulate them on a computer. We also formulate definitions of equilibrium and stability for classifier systems, and pose some convergence questions. Although we suggest possible convergence theorems, we prove no theorems in this paper. 2. The Kiyotaki-Wright Environment describes the Kiyotaki-Wright environment. 3. Classifier Systems for the Kiyotaki-Wright Environment describes the classifier systems without genetics. 4. Classifier Systems for Supporting Kiyotaki and Wright’s Stationary Equilibria describes behavior in the stationary equilibria of Kiyotaki and Wright and also the types of classifier systems that could support that behavior. 5. Concepts of Convergence for Classifier Systems Playing Games defines stability criteria for sets of classifier systems, and discusses how these definitions can be used to formulate questions about whether systems of classifier systems converge to a stationary equilibrium. 6. Incomplete Enumeration Classifiers and the ‘Genetic Algorithm’ describes classifier systems operating with genetics. 7. Simulation Results describes our simulations of systems of classifier systems. In addition to the economies studied by Kiyotaki and Wright (including one with fiat money), we study an economy with five types of agents and five goods. 8. Conclusions concludes the paper.

2. The Kiyotaki-Wright Environment¶

There are three types of agents, with types being indexed by $i = 1, 2, 3$. Type $i$ agents get utility only from consuming type $i$ good. Type $i$ agent has access to a technology for producing type $i^*$ good, where $i^* \neq i$. We initially specify $(i, i^*)$ according to Kiyotaki-Wright’s ‘model A’, namely, as follows:

This specification assumes no ‘double coincidence of wants’ and seems to call for a multilateral trading arrangement. All goods are indivisible. Each agent can store one and only one unit of only one good from one period to the next. When an agent of type $i$ consumes good $i$ at time $t$, he immediately produces good $i^*$, which he carries over to the next period. The net utility to an agent of type $i$ of consuming good $y$ and producing good $i^*$ is given by $u_i(y)$. We assume that an agent of type $i$ does not know his utility function, but does recognize utility when he experiences it. The goods are costly to store. Storing good $k$ ($k = 1, 2, 3$) from $t$ to $t+1$ imposes costs at $t$ of $s_k$. Following Kiyotaki and Wright, we assume that $s_3 > s_2 > s_1 > 0$. We summarize this cost function by saying that $s(y)$ is the one-period cost of storing one unit of good $y$. We assume that individuals do not know this cost function, but that they do recognize costs when they bear them.

The economy and each agent within it live forever. There are large and equal numbers of agents of each type. We modify Kiyotaki and Wright’s model by assuming that each agent cares about his long-run average level of utility. (Kiyotaki and Wright assumed that agents have preferences ordered by expected discounted future utilities.) Each period, there is a random matching process that assigns each and every agent in the economy to a pair with one and only one other agent in the economy. The random matching technology matches agents without regard to type. Only pairs of agents matched together can trade at a point in time.

The economy begins at $t = 0$ with agents being endowed with an arbitrary and randomly generated initial distribution of holdings of goods. At each date $t \geq 0$, each agent $i$ has to make two decisions sequentially. First, given the good he is holding and given the good held by the partner with whom he is matched at $t$, he must decide whether to propose to trade. Trade occurs only if both parties propose to do so. Second, the agent must decide whether or not to consume the good with which he exits the trading process. If he doesn’t consume, he simply carries the good into period $t + 1$, experiencing cost $s_k$. If an agent of type $i$ does consume good $y$ at $t$, he experiences net utility $u_i(y_t)$, produces good $i^*$, and experiences carrying costs $s_{i^*}$. We assume that $u_i(k) = 0$ if $k \neq i$ and $u_i(i) = u_i > 0$. We follow Kiyotaki and Wright both in adopting their specification of the physical environment and in considering only Markov strategies, but we drop the assumption of rational agents. Instead, our agents are assumed to be ‘artificially intelligent’, in the sense that they use versions of the classifier system introduced by Holland (1986).

Before describing the classifier systems used by our agents, we introduce some notation for naming agents and for describing the state of each individual agent in the economy. There is a collection of agents $\mathscr{A} = \{1, 2, \ldots, A\}$. A typical element of $\mathscr{A}$ is denoted $a$. Kiyotaki and Wright assumed that there was a continuum of each type of agent, while we assume that there is a finite number of each type. The first $A_1$ agents are of type I, the next $A_2$ are of type II, and the following $A_3$ are of type III. Here $A = 3A_i$.

At the beginning of time $t$, agent $a$ is carrying good $x_{at}$. The variable $x_{at}$ characterizes the pre-match state of agent $a$ at time $t$. There is a random matching process which each period matches each agent $a \in \mathscr{A}$ with a distinct agent $\rho_t(a) \in \mathscr{A}$. For each agent in each period, the matching process induces a function $\rho_t(a): \mathscr{A} \rightarrow \mathscr{A}$. After the matching process, the pre-trade state of agent $a$ is $(x_{at}, x_{\rho_t(a)t})$. The pair $(x_{at}, x_{\rho_t(a)t}) = z_{at}$ records what agent $a$ is carrying and what the agent $\rho_t(a)$ with whom $a$ is matched at $t$ is carrying.

At $t$, after being matched with agent $\rho_t(a)$, agent $a$ decides whether or not to propose to trade. We let $\lambda_{at}$ denote the trading decision of agent $a$ at time $t$, where

Similarly, $\lambda_{\rho_t(a)t}$ summarizes the trading decision of the agent $\rho_t(a)$ with whom $a$ is paired at $t$. Trade takes place if and only if $\lambda_{at} \cdot \lambda_{\rho_t(a)t} = 1$.

Let $x_{at}^+$ denote the post-trade (but pre-consuming decision) holdings of agent $a$ at $t$. We then have that

After leaving the trading process with holdings $x_{at}^+$, agent $a$ must decide whether to consume $x_{at}^+$ or to carry it into the next period. We let $\gamma_{at}$ denote the consumption decision of agent $a$ at $t$ where

If agent $a$ decides to consume, he automatically produces good $f(a)$, which he carries into $(t + 1)$. From the specification of $i^*$ as a function of $i$ described above for Kiyotaki and Wright’s model A, we have that $f(a)$ is a good of type 2 if $a$ is a type I agent, $f(a)$ is a good of type 3 if $a$ is a type II agent, and $f(a)$ is a good of type 1 if $a$ is a type III agent. It follows that beginning-of-period holdings of $a$ at time $t + 1$ are described by^[3]

3. Classifier Systems for the Kiyotaki-Wright Environment¶

We now describe the classifier systems that agents use to make their trading and consumption decisions.^[4] Agents sequentially use two interconnected classifier systems each period. A first trading classifier system receives input in the form of the pre-trade state $z_{at} = (x_{at}, x_{\rho_t(a)t})$. This classifier system determines the trading decision $\lambda_{at}$, which interacts with the trading decision $\lambda_{\rho_t(a)t}$ of the agent $\rho_t(a)$ with whom $a$ is paired at $t$ to determine $x_{at}^+$ [see eq. (2)]. A second consumption classifier system takes $x_{at}^+$ as input and determines the consumption decision $\gamma_{at}$. The two classifier systems are used sequentially in this way each period, and their accounting systems are interconnected in ways to be described below.

A classifier system consists of the following objects:

1. A collection of trinary strings, called ‘classifiers’.

2. A system for interpreting or decoding the strings or classifiers as instructions mapping states into decisions. The first part of a string encodes a particular state or condition, while the second part encodes a particular action. Thus, an individual classifier or string is just an encoding of a single (state, action) pair. For a given state, there can be many classifiers present in a classifier system.

3. A list of ‘strengths’ attached to each classifier at each point in time $t = 0, 1, \ldots$

4. A system for reading in external messages or ‘states’ and for determining the set of classifiers that are pertinent, i.e., the set of classifiers whose ‘conditions’ are satisfied or ‘matched’ at that state. For a given state, the system can sometimes contain several classifiers with distinct actions.

5. An ‘auction system’ for determining which of the pertinent classifiers is allowed to make a decision at $t$. Among all classifiers whose condition part matches the actual state at $t$, the ‘highest bidder’ in the auction actually ‘makes the decision’ in real time.^[5]

6. An accounting system for updating the strengths of the collection of classifiers in response to the net rewards that flow into the system as a result of the decisions that are made.

And possibly:

7. A genetic algorithm for introducing new strings and extinguishing old strings. This algorithm will be called whenever states are encountered for which no existing classifiers have their conditions met. The algorithm may also be applied from time to time as a device to promote experimentation.

We now describe each of these elements as applied to the Kiyotaki-Wright environment. We first consider an exchange classifier system, which maps the pre-trade state $z_{at}$ into a trading decision. This classifier system consists of a list of trinary strings of length 7. The first three digits represent own storage, the next three represent trading partner’s storage, and the seventh represents the trading decision.

The coding is written in the trinary alphabet $(1, 0, \text{\#})$, where $\text{\#}$ means ‘don’t care’. For the trading decision, the code is in the binary alphabet $(1, 0)$, where 1 means trade, while 0 means don’t trade.

To illustrate how the codes in Table 1 are applied to encode particular trading classifiers, we consider the following two classifiers:

The first classifier instructs an agent who is carrying good 1 and who is matched with someone carrying good 3 to offer to trade. The second classifier instructs an agent who is carrying good 1 not to trade if he is matched with someone who is not carrying good 3.

The exchange classifier system of agent $a$ consists of a list of such classifiers. Let $e = 1, 2, \ldots, E_a$ index this collection of classifiers. A given classifier system has a fixed number of classifiers. For the exchange classifier system, how many distinct classifiers are possible? Evidently, $3^3 \times 3^3 \times 2 = 1458$. However, most of these classifiers are redundant in the sense that only a subset of them is needed to represent all possible trading decision rules defined on the state space $z_{at} = (x_{at}, x_{\rho_t(a)t})$ when there are three goods. All rules can be written in terms of pairs of conditions drawn from Table 1. Thus, only $6 \times 6 \times 2 = 72$ strings are required to represent the complete set of possible rules for this system.

Assigned to each exchange classifier $e \in \{1, 2, \ldots, E_a\}$ is a strength, denoted $S_e^a(t)$. The strength $S_e^a(t)$ evolves over time in a way determined by the accounting system. The strengths attached to classifiers are used to determine the decisions made by the classifier system at $t$. For a given state or ‘condition’ $z_{at} = (x_{at}, x_{\rho_t(a)t})$, there is a collection of classifiers within the classifier system whose conditions are satisfied. We denote the set of such classifiers by $M_e(z_{at})$, defined as

The members of $M_e(z_{at})$ form a class of potential ‘bidders’ in an ‘auction’ whose purpose is to determine which classifier makes the decision of agent $a$ at time $t$. When state $z_{at}$ is encountered at time $t$ by agent $a$, the classifier belonging to $M_e(z_{at})$ that has the highest strength makes the decision. Let $e_t(z_{at})$ denote the index of the classifier to be used in deciding whether to trade at $t$. Then,

We denote the action (trade or no trade) taken by classifier $e_t(z_{at})$ as $\lambda_{at}$. Equations (5) and (6) describe the ‘auction system’ by which the highest strength rule that applies in a given state is given the right to decide for agent $a$ at $t$.

Because the trade and consumption classifier systems will be making payments to one another, we have to describe the consumption classifier system before describing the accounting system that updates strengths of the trade classifier system. The consumption classifier system is a collection of trinary strings of length 4. The first three positions encode $x_{at}^+$ using the same code that was described in Table 1. The condition part of the strings is written in terms of the trinary alphabet $(0, 1, \text{\#})$. The fourth position of a consumption string is the ‘action’ part, taking values of 1 (meaning consume) and 0 (meaning don’t consume).

We let consumption classifier strings be indexed by $c \in \{1, 2, \ldots, C_a\}$. The strength assigned to classifier $c$ of agent $a$ is $S_c^a(t)$. By virtue of eq. (2), the state $x_{at}^+$ can be expressed in terms of $z_{at} = (x_{at}, x_{\rho_t(a)t})$. Therefore it suffices to denote the set of ‘matched’ classifiers by $M_c(z_{at})$, where

Let $c_t(z_{at})$ denote the classifier that makes the consumption decision at $t$. The highest-strength classifier gets to make the decision:

Given the decisions determined by (6) and (8), $x_{at}^+$ evolves according to the law of motion (4).

3.1 Counters and Strength Evolution¶

We attach to each exchange classifier $e$ a ‘counter’ $\tau_e^a(t)$ which records the cumulative number of times that classifier $e$ has won the auction as of date $t$. We shall change the strength of classifier $e$ only when it actually wins the auction and thereby gets to make the exchange decision, which is why we need the counter $\tau_e^a(t)$. The counter $\tau_e^a(t)$ for classifier $e$ is defined recursively in terms of the indicator $I_e^a(t)$, which records whether classifier $e$ wins the auction:

Notice that we initialize the counter of each classifier at unity. The strength of classifier $e$ at $t$ will be represented as $S_e^a(t) = S_{e\tau_e^a(t)}^a$.

Similarly, we attach to each consumption classifier $c$ a ‘counter’ $\tau_c^a(t)$ which records the cumulative number of times that classifier $c$ has won the auction as of date $t$. The counter $\tau_c^a(t)$ is defined by

The strength of classifier $c$ at $t$ will be represented as $S_c^a(t) = S_{c\tau_c^a(t)}^a$.

3.2 Bid Functions and Strength Updates¶

The counters $\tau_e^a(t)$ and $\tau_c^a(t)$ induce a transformation of time in terms of which the strengths of classifiers $c$ and $e$ are updated. At date $t$, a strength $S_{c\tau_c^a(t)}^a$ is attached to classifier $c$, while a strength $S_{e\tau_e^a(t)}^a$ is attached to classifier $e$ of agent $a$. At date $t$, if classifier $e$’s condition is matched [i.e., if $e \in M_e(z_{at})$], then classifier $e$ makes a bid of $b_1(e)S_e^a(t)$, where $b_1(e)$ is a positive fraction that can depend on $e$. If classifier $e$ wins the auction, its bid will be deducted from its strength. The winning bid will be allocated to augment the strength of other classifiers whose actions drove the system to the state that satisfied $e$’s condition. We choose the particular bid function

where $b_{11}$ and $b_{12}$ are positive constants adding up to less than one, and $\sigma_e$ is a fraction which is proportional to the specificity of a particular classifier. In particular, we choose $\sigma_e = 1/(1 + \text{number of \#'s in the string})$. Similarly, we define a function $b_2(c)$ with $\sigma_c = 1/(1 + \text{number of \#'s in the string})$. By the above choices of $b_1(e)$ and $b_2(c)$, we favor specific rules over more general rules that can be activated by a particular state. When $c \in M_c(z_{at})$, classifier $c$ makes a bid of $b_2(c)S_c^a(t)$.

Only winning classifiers pay their bids by having them deducted from their strengths. The bid of the winning exchange classifier at $t$ is paid to the winning consumption classifier at $t - 1$, which is the classifier that is to be credited with setting the time $t$ state to $z_{at}$. The bid of the winning consumption classifier at $t$ is paid to the winning exchange classifier at time $t$, which is to be credited with setting the post-exchange state at $t$ at $x_{at}^+$, thereby giving the winning consumption classifier a chance to bid.

We represent these payments in terms of the following difference equations:

In (14), $U_a(\gamma_{ct}^a)$ is the external payoff when the winning consumption classifier $c$ makes final consumption decision $\gamma_{ct}^a$. If the post-exchange state at $t$ is $x_{at}^+$, then we have

There are several features of (14) and (15) that bear emphasizing. First, these are recursive formulas that make $S_{c\tau_c^a(t)}^a$ and $S_{e\tau_e^a(t)}^a$ averages of past payoffs (external rewards plus bids received from other classifiers) minus payments (bids made to other classifiers). Use of cumulative average net payoffs in this way (as opposed to total payoffs) is a departure from the existing literature on classifiers. Second, notice how the term $\sum_e I_e^a(t) b_1(e) S_{e\tau_e^a(t)}^a$ expresses the condition that only the winning exchange classifier at $t$ pays the winning consumption classifier at $t - 1$. Third, notice how the use of the counters $\tau_e^a(t)$ and $\tau_c^a(t)$ causes changes to be made only to the strengths attached to the winning classifiers.

Figure 1 illustrates how the exchange and consumption classifier systems interact for an individual of type I. Suppose that the state at time $t$ is encoded 010 100. This means that the type I individual is storing good 2 and has been matched with someone who is storing good 1. The individual has two classifiers whose conditions are matched, one with strength 50, the other with strength 10. The strength 50 classifier makes the decision, which is ‘1’, namely, offer to trade. If the individual’s trading partner also offers to trade, the individual exits the trading process with state 100, which is the input into type I’s consumption classifier. With this input, there are two consumption classifiers whose conditions are matched, one with strength 80 that says ‘consume’, the other with strength -1 that says ‘don’t consume’. The individual consumes, initiating an external payoff. The bold lines indicate the flows of payoffs. In addition to the external payoff to the winning consumption classifier, there is a payment from the winning consumption classifier at $t$ to the winning exchange classifier at $t$, and a payment from the winning exchange classifier at $t$ to the winning consumption classifier at $t - 1$.

With (14), (15), and (16), we have completed our description of the classifier system for agent $a$ when that classifier system contains a complete enumeration of possible rules. Our version of the Kiyotaki-Wright model is formed by assuming that each agent $a$ of type $i$ uses the same classifier system to make decisions.^[6] Thus, we can replace $a$ superscripts and subscripts in the descriptions of strengths by $i$’s. We start with a set of initial strengths $S^i(0)$ for $i = 1, 2, 3$. We temporarily introduce the index $T$ to index calendar time, while $t$ now temporarily indexes the cumulative number of matches which have occurred rather than calendar time. Our artificially intelligent agents then interact as follows for each $T = 1, 2, \ldots, L$, where $L$ is the length of our simulation. All $A$ agents are randomly matched into $A/2$ pairs. For each pair $(a, a')$, the exchange and classifier systems for agents whose types are $a$ and $a'$, respectively, are used mutually to determine the trading and consumption decisions of agents $a$ and $a'$. After the consumption decisions have been made for the pair, the counters and the strengths of the classifier systems for both types of agents are updated according to (10), (12), (14), and (15). Also, after each pair has played, the synthetic time counter $t$ is augmented by one. After all $A/2$ pairs have played, the counter $T$ is augmented by one, and the entire process is repeated. The counter $T$ records the passage of physical time, while the counter $t$ records the cumulative number of matches that have occurred. The outcomes of all matches $t \in [(T-1)(A/2) + 1, T(A/2)]$ are interpreted as having occurred during period $T$.

In 7. Simulation Results, we shall be interested in recording various frequency distributions across agents as a function of calendar time. That is, there will be distinct frequency distributions of, e.g., holdings of goods across agents for each date in calendar time. At the risk of confusion, we choose to index calendar time by $t$ (rather than $T$) in subsequent sections.

4. Classifier Systems for Supporting Kiyotaki and Wright’s Stationary Equilibria¶

4.1 The Fundamental Equilibrium¶

For their model A, Kiyotaki and Wright define as the fundamental equilibrium the trading pattern defined by the triangle depicted in Figure 2. In this trading pattern, good 1, which has the lowest storage cost, serves as the general medium of exchange. In terms of storage, agents of type I only store good 2, which they exchange only for good 1; agents of type III only store good 1, which they exchange only for good 3; and agents of type II half of the time store good 1, which they exchange for good 2, and half of the time good 3, which they exchange for good 1.

We can characterize equilibria in terms of a set of probabilities that describe holding and exchanging patterns. We define

We denote by $\Pi_t$ the entire set of probabilities defined in (17) for all $i, k, j$. Associated with Kiyotaki and Wright’s stationary equilibrium is a time-invariant $\Pi_t = \Pi$. In Table 2 we display the $\Pi$’s for the fundamental equilibrium of Kiyotaki and Wright’s model A.

The $(i,j)$ entry in Table 3 is the triple $(\pi_i^e(j1), \pi_i^e(j2), \pi_i^e(j3))$, representing the probability that a type $i$ agent holds $j$, meets an agent with $k$, and trades. Note that $\pi_i^e(jk)$ here denotes the joint holding-meeting-trading probability, where $j$ indexes the good held and $k$ the good of the trading partner; this differs from the conditional exchange probability $\pi_{it}^e(kj)$ defined in (17), which conditions on holding $k$ and denotes exchanging $k$ for $j$.

Note: A question mark denotes sequential equilibrium strategies for events of zero probability. The $(i,j)$ entry in the table is the triple $(\tilde{\pi}_i^e(j1|j), \tilde{\pi}_i^e(j2|j), \tilde{\pi}_i^e(j3|j))$, representing the probability that a type $i$ agent is willing to exchange good $j$ for goods 1, 2, or 3 respectively, given that $i$ is holding $j$.

Table 5 shows that in any stationary equilibrium, each type of agent consumes only its own desired good.

We now describe how the strategies that support Kiyotaki and Wright’s ‘fundamental equilibrium’ can be represented as a classifier system. For the classifiers we introduce the following additional notation. Let $e^i_{k,j,d}$ denote the exchange classifier for a type $i$ agent that reads ‘If I am storing good $k$ and I meet an agent with good $j$, then my exchange decision is $d$’; $d \in \{0, 1\}$. Similarly, specific consumption classifiers for type $i$ agents are of the form $c^i_{k,d}$ for ‘If, at the end of the exchange subperiod, I am storing good $k$, then my consumption action is $d$’. For more general rules, we use the subindex $-j$ to denote ‘not good $j$’ and $\text{\#}$ to denote ‘any good’. That is, $e^1_{2,-1,0}$ is the classifier for type I agents that reads ‘If I am storing good 2 and I meet an agent not carrying good 1, then do not trade’, and $c^1_{\text{\#},0}$ is a classifier for type I that reads ‘No matter what I am storing at the end of the exchange subperiod, do not consume’.

We can simplify the study of classifier systems by considering only a small complete set of rules. For type I agents these rules are: $e^1_{2,1,1}$; $e^1_{2,-1,0}$; $e^1_{3,1,1}$; $e^1_{3,-1,0}$; $c^1_{1,1}$; $c^1_{-1,0}$. If $\{e^1_{2,1,1}; e^1_{2,-1,0}; c^1_{1,1}; c^1_{-1,0}\}$ are the only classifiers being used by agents of type I, we can say that type I agents support the fundamental equilibrium. We can also describe classifiers for type II and type III agents that support the fundamental equilibrium. These are, for type II: $e^2_{3,1,1}$; $e^2_{3,2,1}$; $e^2_{3,-1,0}$; $e^2_{1,-2,0}$; $c^2_{2,1}$; $c^2_{-2,0}$; and for type III: $e^3_{1,3,1}$; $e^3_{1,-3,0}$; $c^3_{3,1}$; $c^3_{-3,0}$.

It is useful to define formally the sense in which these fixed lists of classifiers support Kiyotaki and Wright’s fundamental equilibrium. Let $D_a$ be a fixed set of classifiers (exchange and consumption classifiers) for agent $a$. Let the set $D_a$ have no redundancies in the sense that for every state $z_{at}$, $D_a$ uniquely determines actions. Then the fixed set of classifiers $D_a$ represents a strategy for agent $a$ defined on $z_{at}$. We use the following definition of optimality for a fixed set of classifiers:

Definition. Given the probability distributions $\Pi$ and fixed sets of classifiers of the other agents $D_{a'}$, for all $a' \neq a$, a fixed set of classifiers $D_a$ is said to be optimal for agent $a$ if there exists no other set $\tilde{D}_a$ which yields higher long-run average utility for agent $a$.

A stationary Nash equilibrium can then be defined as follows:

Definition. A stationary Nash equilibrium is a set of probability distributions $\Pi$ and fixed sets of classifiers $D_a$, $a = 1, \ldots, A$, such that:

1. Given $\Pi$ and $D_{a'}$, for $a' \neq a$, $D_a$ is optimal for agent $a$.

2. $\{D_a, a = 1, \ldots, A\}$ and the random matching technology imply that $\Pi_t = \Pi$ for all $t$.

This definition is just an alternative representation of Kiyotaki and Wright’s definition in terms of fixed lists of classifiers.

Table 6 illustrates the sequence of events under the circumstance that the only active (i.e., auction-winning) classifiers are those that support the fundamental equilibrium for agents of type I. A natural question is whether the classifier systems of the three types of agents will actually converge to a situation in which the fundamental equilibrium of Kiyotaki and Wright is supported. Before introducing some concepts that will help us think about this question, we shall briefly describe another kind of equilibrium of Kiyotaki and Wright’s model and the kind of classifier system that could support it.

4.2 Kiyotaki and Wright’s ‘Speculative Equilibrium’¶

Kiyotaki and Wright show that for their model A the trading pattern associated with a fundamental equilibrium is not the only possible one in equilibrium. They show that there can occur a speculative equilibrium with a trading pattern depicted in Figure 3.

Kiyotaki and Wright establish a condition under which the unique stationary rational-expectations equilibrium is a fundamental equilibrium. The condition, for the limiting case as the discount rate converges to zero, is that the following inequality is satisfied:^[7]

In the speculative equilibrium, Table 7 depicts the flow of events in the stationary rational-expectations equilibrium for a classifier system of a type I agent. Notice that the flows depicted reduce to a set of fundamental classifiers if the dotted link is removed, i.e., if type I agents decide not to trade good 2 for good 3.

Note: The asterisk (*) denotes the speculative move that distinguishes this from the fundamental equilibrium.

In 7. Simulation Results we shall provide an example of a simulated classifier economy where (18) is not satisfied ($u_1$ is too high), but where nevertheless when agents start with a complete set of classifiers (with homogeneous strengths), the classifier systems converge to the fundamental equilibrium and not to the speculative equilibrium. Before turning to these simulations, we define some notions of stability that are designed to distinguish alternative senses in which a set of classifier systems may be said to converge.

5. Concepts of Convergence for Classifier Systems Playing Games¶

Given the decision rules being employed by other agents, (14)-(15) for agent $a$ forms a system of stochastic difference equations in the strengths $S^a(t)$. Since the classifier systems of the three types of agents $i = 1, 2, 3$ are operating simultaneously, the behavior of the entire system is determined by the system of difference equations (14)-(15) for agent types $i = 1, 2, 3$. Let $S^i(t)$ denote the strengths for an agent of type $i$. It is natural to inquire whether the system formed by (14)-(15) for $a = i = 1, 2, 3$ converges to a stationary point in the space of strengths, and if it does so, whether that stationary point supports the fundamental equilibrium of Kiyotaki and Wright.

Although we have not yet carried out an analysis of the convergence of this system, it seems useful at this point to report our ideas about how such an analysis could be structured. In this section we indicate how ideas from the stochastic-approximation literature might be used to study convergence in the space of strengths.^[8]

From the stochastic-approximation literature,^[9] we know that any limit points $(S_c^*, S_e^*)$ must satisfy

for all $c$ and $e$. For a given $a$ we define the solutions $(S_c^*, S_e^*)$ of (20) as a stationary set of strengths for agent $a$. Given a stationary set of strengths for agent $a$, one can determine the set of classifiers $\{e, c\} = W_a(z_{at})$ that would win the auction for each $z_{at}$. If $a$ has the fixed set of classifiers $W_a(z_{at}) = D_a$, where $D_a$ is the fixed set of classifiers that supports $a$’s behavior in a Nash equilibrium, then the stationary set of strengths associated with $W_a(z_{at})$ can be said to support the stationary Nash equilibrium behavior of agent $a$.

These definitions inspire several questions. First, given stationary sets of strengths for agents of types 1, 2, 3, is it true that $W_a(z_{at}) = D_a$ for a type $i$ agent, for each $i = 1, 2, 3$? That is, does a stationary set of strengths for the classifier systems for agents of type $i = 1, 2, 3$ support a stationary Nash equilibrium?

Second, given fixed sets of classifiers $D_a$ for $a$ of type $i = 1, 2, 3$ that support a stationary Nash equilibrium, do these sets of classifiers imply the existence of a set of strengths $S_a$ for $a$ of type $i = 1, 2, 3$ that solve (20)? That is, is every Nash equilibrium supported as a stationary point in strengths?

Third, if we let the classifier systems of agents of type $i = 1, 2, 3$ run in real time, does the joint system formed by (14)-(15) for agents of each type converge almost surely, and if so, to which solution of (20) does it converge? We know from the theory of stochastic approximation that if it converges, it must converge to solutions of (20).

Associated with the third of these questions is the notion of global asymptotic stability. In future work, we plan to apply results from the stochastic approximation literature to study the global asymptotic stability of versions of our interacting classifier systems.

We also intend to study a form of stability that is distinct from and weaker than global asymptotic stability. This form of stability is summarized in the following:

Nash-like stability test. Take a stationary equilibrium fixed by $\Pi$. Place a single agent of a given type $i$ in the environment formed by the fixed probabilities $\Pi$. Let a classifier system for that single agent operate until it converges. Check to see whether it converges to imply the collection of classifiers $D_a$ for an agent $a$ of type $i$ which are required to support the equilibrium probabilities. In this experiment, in running the classifier system for the single agent, the decision rules of all other agents of his type are being held fixed at their equilibrium values. This experiment is to be repeated for a single agent of each type.

In the remainder of this paper, we shall not pursue the formal analysis of the stability and convergence questions formulated above.^[10] Instead, we shall report computer simulations. In these computer simulations, convergence can be based either on the limiting behavior of the strengths, as indicated above, or on the convergence of key aspects of the empirical frequency distribution of holdings $\Pi_t$, which we defined in 4. Classifier Systems for Supporting Kiyotaki and Wright’s Stationary Equilibria.

6. Incomplete Enumeration Classifiers and the ‘Genetic Algorithm’¶

We now describe how the classifier system is modified when we deal with systems in which there is not a complete enumeration of rules. In order to complete the system, two aspects must be added to the above description of the classifier system under complete enumeration. The first is a way of generating an initial population of rules. The second is a way of deleting old rules from the system and adding new rules to the system. To generate the initial population of rules, we simply use a random number generator to generate bit strings by choosing successive bits independently.

The process of adding new rules and deleting old ones is accomplished by adding four major operations to the previous description of the workings of the classifier system. We call these steps ‘creation’, ‘diversification’, ‘specialization’, and ‘generalization’, respectively.

Creation: The creation operation is activated when there is no classifier matching the current state $z_{at}$, i.e., $M_e(z_{at})$ is empty. In this case, a new classifier is created with its condition part defined by the current state and its action part randomly selected. A ‘weak’ classifier from the set of all classifiers is deleted to keep the number of classifiers constant.

Diversification: The diversification operation is designed to inject sufficient diversity into the range of actions called for by different classifiers in a given situation. For the exchange classifier, this step occurs at the stage at which $z_{at}$ has been observed and the set $M_e(z_{at})$ has been constructed. Recall that $M_e(z_{at})$ is the set of exchange classifiers whose condition parts match $z_{at}$. If all $e \in M_e(z_{at})$ have the same action (0 or 1), the diversification operation creates a classifier encoding the specific state $z_{at}$ and an action opposite to that taken by the other classifiers in $M_e(z_{at})$. The strength of the winning classifier is assigned to this new classifier. This new classifier is added to the system, while simultaneously a ‘weak’ classifier from the set $M_e(z_{at})$ is deleted from the system. The weakness of a classifier is measured in terms of a combination of strength and cumulated number of times the classifier has won the bidding in the past. The diversification operation is used each time the classifier system is called upon. Notice that if this step were to be added to a complete enumeration system, it would have no effect on the population of rules because sufficient diversity is present from the beginning.

Specialization: The specialization operation is called randomly with a probability that we choose to be diminishing over time. The random variable governing specialization calls this step into action just after the winning bid has been determined. The winning classifier is checked to determine whether there are any $\text{\#}$'s in its condition part. A new classifier is synthesized by exposing each $\text{\#}$ in the condition part to a probability of being switched to a 0 or a 1, whichever one specifically encodes the particular $z_{at}$ that was just observed or matched. This new and (probably) more specific rule is then used to replace a weak rule from the set $e \in M_e(z_{at})$ [or $c \in M_c(z_{at})$ in the case of the consumption classifier], where weakness is measured by a combination of strengths and cumulative number of times the auction has been won.

Generalization: The fourth step, which we call generalization, is a version of a ‘genetic algorithm’. This step is called randomly, according to a probability that we specify to be declining through time. At a point when the step is called, the process is initiated by generating two distinct populations of classifiers: ‘potential parents’ and ‘potential exterminants’. The potential parents are chosen to be a population of classifiers of specified size. They are chosen according to a ‘fitness criterion’ that weights strength and cumulative number of times that the classifier won the auction. The potential exterminants are chosen to be a population of specified size, whose members are of low fitness as measured by a fitness criterion weighting strengths and cumulative victories in past bidding.

From the population of potential parents, a specified number of pairs of parents are randomly drawn to engage in ‘mating’ for the purpose of creating children. How a pair of parents mates can be illustrated for two exchange classifiers, which are bit strings of length 7, as depicted in Figure 4.

The pair mates in two steps. First the pair draws two random integers uniformly distributed on $[1, 7]$. The two integers signify the positions between bits depicted in Figure 4. Next, a Bernoulli random variable with probability 0.5 is drawn, assuming values of ‘in’ or ‘out’. If ‘in’ is drawn, we focus on the bits between the two lines, i.e., the bits inside the randomly drawn interval. If ‘out’ is drawn, we focus on the bits outside the randomly drawn interval. Within the interval of focus, we complete the mating process via the following version of genetic crossover. For each of the parent strings in the area of focus, we change to a $\text{\#}$ any bits for which the parent strings disagree. (Here, $\text{\#}$ agrees with either 0 or 1, while 0 disagrees with 1). This process produces two children. The children are each assigned strengths that are the average of their parents’ strengths. The children are introduced into the population of classifiers. For each child added to the population, a randomly selected individual from the population of ‘potential exterminants’ is deleted from the population.

This completes our description of the algorithm to be used for updating the classifier system when we deal with an incomplete enumeration classifier system. In the simulations to be reported in 7. Simulation Results, we shall employ both complete and incomplete enumeration classifier systems.

7. Simulation Results¶

The sets of parameters defining the economies under study are summarized in Table 8.

Notes: Utility levels $u_i$ are set equal for $i = 1, 2, 3$. CS denotes ‘classifier system’. ‘F’ implies fixed enumeration and ‘R’ implies randomly generated rules.

7.1 Economy A1¶

Economy A1.1 (Economy A1 with complete enumeration of classifiers) shows that the distribution of holdings rapidly converges to the stationary equilibrium distributions. Similarly, the exchange and consumption strategies implemented by the system of winning classifiers virtually coincide with the equilibrium strategies. In Table 10, and in all subsequent tables of empirical frequencies, the frequencies reported are ten-period moving averages ending at the indicated time periods.^[11]