Computational Economics 8: 1-26, 1995. 9 1995KluwerAcademic Publishers. Printed in the Netherlands.

Computational systems for qualitative economics KARL R. LANG 1, JAMES C. MOORE 2 and ANDREW B. WHINSTON 3 llnstitut fiir Wirtschaflsinformatik und Operations Research, Free University of Berlin, Germany 2Department of Economics, Purdue University Indiana, USA 3Department of Management Science and Information Systems, The University of Texas at Austin, USA

(ReceivedJune 1993)

1. Introduction

When dealing with partially known economic systems, there are several approaches one might take in coping with incomplete and uncertain knowledge. Quantitative analysis confines itself to well known mathematical structures, like linear equation systems or mathematical optimization models, and tries to find an approximate model that is close enough to the true model to give useful insights. Stochastic methods treat system variables as random, or impose error terms in order to cover the true relationships. The latter approach requires additional assumptions about the probability distribution of random variables which is often beyond available knowledge. For that reason, and to keep the model tractable, random variables are usually chosen to be normally distributed; a commitment that has to be justified. Quantitative approaches have the advantage of producing precise results, but frequently one lacks confidence in the appropriateness of the underlying model. Precise answers, on the other hand, are often not of primary interest when conducting economic studies; qualitative information like signs, ranges and directions of change of goal variables can be sufficient for satisfactorily explaining and predicting economic systems. Reasoning with partially known systems has a long tradition in economics and is often referred to as qualitative economic analysis. In many situations most of the knowledge at hand is of a qualitative nature; for example, knowledge of the signs or possibly magnitudes of variables rather than exact numerical values, or partial knowledge of the shape of functional relationships (e.g., slope, curvature, monotonicity). Especially for analyzing equilibrium systems, economists have developed techniques to derive qualitative restrictions on the system's reaction to changes of the original system that are, lacking complete quantitative information, specified qualitatively as well (Samuelson (1947), Lancaster (1962), Gorman (1964), and Ritschard (1983)). Unfortunately, these qualitative methods work well only on small systems. For more complicated problems, qualitative economics traditionally resorts to some kind of ad hoc reasoning, or employs expertise on the relative importance of different effects, and simplifies the model by neglecting effects of second order magnitude.

2

KARL R. LANG ET AL.

Because qualitative economic analysis had been essentially developed prior to the era of modem computer technology, it was limited by the absence of computational power. Recent research in qualitative reasoning, a new field that has emerged from artificial intelligence, see Bobrow (1985) and Weld and deKleer (1990), is based on a similar motivation as qualitative economics. Basically unaware of the related work in qualitative economics, qualitative reasoning has developed a variety of representation languages and inference mechanisms for qualitative modeling, sometimes reinventing techniques already known in the economics literature. Iwasaki and Simon (1986) first recognized the link between qualitative reasoning and qualitative economics, and Simon et al. (1991) explicate mathematical methods common to both areas. The research in qualitative reasoning has raised new interest in qualitative analysis in economics and first applications can be found in Bridgeland (1989), Farley and Lin (1990), Lin and Farley (1991), and Bemdsen and Daniels (1991). These early applications focus on purely qualitative reasoning methods which are still limited to moderate sized problems. The goals of this paper are: (1) to integrate the developments in artificial intelligence into the qualitative economics field, thereby to introduce to economists the research done in artificial intelligence; (2) to discuss representational issues of qualitative modeling, and (3) to present a new computational approach for analyzing qualitative economic systems. The remainder of the paper is organized as follows. Section 2 summarizes the state of the art in the qualitative reasoning field, that is, we review the artificial intelligence literature on qualitative modeling. The next Section discusses qualitative approaches developed in economics. Based on the mathematical concept of correspondences, which has been widely used in modem mathematical economics (see, for example, (Debreu (1959), Arrow and Hahn (1971), Hildenbrandt (1974), Balasko (1988), and Aliprantis et al. (1990)), we show, in Section 4, how the different techniques for representing and analyzing qualitative systems developed in traditional qualitative economics and qualitative reasoning can be subsumed into a single, unifying framework. We also show how additional quantitative information can be obtained and dynamically incorporated into the analysis in order to tighten the model specification. A resource allocation problem is presented as an illustration of how one might move from an initial, purely qualitative model to a more precise specification; and this example also illustrates a technique (from Moore, Rao and Whinston (1992)) of obtaining "optimal" solutions of a constrained maximization problem having a purely qualitative specification. We conclude our paper, in Section 5, with some comments on future research directions. 2. Qualitative R e a s o n i n g - A R e v i e w

Early research in qualitative reasoning, respectively qualitative physics as it was called then, was driven by the question: how do humans reason about the physical world? The observation was made that humans function quite successfully in

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

3

dally situations like boiling water in a tea kettle, pouring into a cup, avoiding car collisions while driving, etc., without fully understanding the physics of these phenomena. This observation led to the conclusion that it must be possible to develop a qualitative physics, which would not require complex equations as in standard physics, and to build commonsense reasoning systems that would be able to explain and predict the behavior of physical systems. In order to give a rough picture of the behavior of a physical system, which is often all that is needed, it is not necessary to provide a complete and precise mathematical description of the system. Many insightful concepts can be described by qualitatively distinct behaviors of a physical system. Representation languages of qualitative reasoning systems are based on high abstractions of real systems as a model representation. This means that some information is lost, thus the answers derived by the inference mechanism cannot be exact. To resolve this intrinsic ambiguity, more knowledge is required. A qualitative reasoning system has to address the two issues of model representation and model solving. Aimed at continuous dynamic physical problems, most systems provide a qualitative analog to differential equation systems, the most powerful quantitative tool for modeling and solving dynamic systems. The real number line is represented as a set of qualitatively distinct landmark values. Relationships among quantities are incompletely specified, typically as some monotonic function. This abstraction yields more general models with a higher level of expression but weaker inferential power. Next, we summarize the three major qualitative reasoning frameworks. Qualitative simulation (QSIM) (Kuipers (1986)) describes a system in terms of qualitative quantities and functional relationships, from which it generates all consistent behavior the system. QSIM was specifically designed to model continuous dynamic systems traditionally formulated as ordinary differential equations (ODE). A QSIM model is a qualitative equivalent of an ODE. It is basically a generalization or abstraction of an ODE into qualitative differential equations (QDE). However, the corresponding ODE does not need to be known in order to formulate a QSIM model. The general goal of QSIM is to represent the structure of a mechanism or system (modeling), and to predict its possible behaviors (simulation), i.e., reasoning from structure to behavior. QSIM was designed with the following requirements in mind: - Models should express what is known about a system - Models should not require assumptions beyond what is known - Models must he tractable to derive useful predictions Model predictions must match actual behaviors A QSIM model comprises qualitative constraints plus initial state(s) from which it predicts possible behaviors. A system is described in terms of time-varying qualitative variables called quantities. A quantity is defined as a continuously differentiable function of time that ranges over a quantity space. A quantity space is a finite, totally ordered set oflandmarkvalues {I~ < 12 < ... < l~). Landmarks are -

4

KARL R. LANG ET AL.

qualitatively distinct values of a particular quantity, i.e., every quantity has its own quantity space. Qualitative constraints describe relationships among quantities. QSIM offers qualitative arithmetic constraints like addition, multiplication etc., a qualitative first order derivative constraint, and qualitative classes of functional relationships, like the class of monotonically increasing or decreasing functions (M+/M - functions). A state is a description of all quantities in terms of their magnitude (expressed in terms of landmarks values) and their direction of change (increasing, decreasing or steady). A behavior describes the change of a system over time as a sequence of (qualitatively distinct) states. QSIM predicts a tree of behaviors from the structural description and the initial state(s). Each branch of that tree corresponds to a behavior that is consistent with the model formulation. Every observable actual behavior matches (abstracts into) one behavior generated by QSIM, thus QSIM is sound. If this is not true, then there has to be a bug in the model formulation. However, due to the limited inferential power it is possible that QSIM generates behaviors that do not correspond with the real system as described by the corresponding ODE. These extra behaviors are called spurious behaviors. QSIM is incomplete in the sense that it fails to prune out all spurious behaviors. Component Connection modeling (de Kleer and Brown (1984)) is an example of a framework which follows a device-oriented ontology, i.e., a system is to be constructed from a set of devices. It decomposes a whole system into contextfree parts, called components and interconnections. Components have to behave independently of the context of a particular problem instance. Interactions between components are solely modeled via connections, thus applying a closed world assumption. Physical laws of components are represented as constraints and classwide assumptions, e.g., all masses are rigid or all fluids are laminar. It must not contain any problem specific assumptions. The model is represented as a set of confluences, i.e., equations in signs of derivatives. This abstraction of real numbers into their signs, the simplest quantity space, ~ ~ { - , 0, + }, represents the coarsest level of description conceivable. Reasoning is based on constraint propagation, the flow of information mirrors the flow of causality. Solving the model produces a total envisionment, a graph with nodes representing all qualitatively consistent states the dynamic systems can be in, and arcs representing possible transitions. A big disadvantage of this modeling approach is that many dynamic systems are not naturally decomposable into a set of devices. Qualitative Process Theory (QPT) (Forbus (1984)) employs a process-oriented ontology. The basic entity of QPT is a physical process, e.g., heat flow, liquid flow, motion, boiling, bending, compressing, expanding, etc. It is assumed that all changes of a physical situation are caused by processes. QPT models physical mechanisms by identifying and describing relevant objects and influences that affect them. Applicability of QPT relies on the availability of a large knowledge base, that is a library of predefined building blocks. These building blocks are of two categories, views and processes. Views describe objects from different points of view, and processes represent activities or events which cause changes to the

COMPUTATIONALSYSTEMSFOR QUALITATIVEECONOMICS

5

objects. In order to be composable, these model fragments have to be contextfree, i.e., the library of views and processes needs an open world assumption. The Qualitative Process Engine (QPE) (Forbus (1990)) automatically builds the model by instantiating views and processes to individual views and processes which are then plugged together to a process-view structure. Instances are created when the conditions, specified in the views and processes, are satisfied by an individual. Processes and Views can be thought of as rules for deriving influences. After applying a closed world assumption, QPE simulates the resulting model and produces a total envisionment. Alternatively, a post processor, QualitativeProcess Compiler (QPC), can be used to generate a QSIM model (Crawford et al. (1990)). The above frameworks have been applied to a great variety of problem areas, e.g., chemical processing (Dalle Molle and Edgar (1989)), diagnosing fault models (DeKleer and Williams (1987)), designing electrical circuits (Williams (1984)), physiology (Kuipers and Kassirer (1984)), engineering of highway bridges (Roddis and Martin (1991)), macroeconomics (Farley and Lin (1990)), and business (Bailey et al. (1991)]. Despite their success in explaining the functioning and predicting the behavior of simple systems, pure qualitative reasoning (QR) needs to be extended in order to be applicable to more complex systems (Kuipers (1985)). Different approaches have been taken to improve the inferential power of QR systems. In particular, several extensions to QSIM have been developed in order to overcome the problem of intractable branching of the behavior tree. Using additional knowledge such as higher order derivatives and the kinetic energy theorem allows one to filter out some spurious behaviors for certain classes of problems (Kuipers and Chin (1987)). Aggregating behaviors that do not differ significantly is another approach that can be useful on some problems (Fouch6 and Kuipers (1991)). Hierarchical decomposition into slow and fast processes can be used if the system consists of processes that work on significantly different time scales (Kuipers (1987)). Most promising are interval inference methods using constraint propagation (Davis (1987)), e.g., Q2, an interval-analytic post processor to QSIM, which incorporates incomplete quantitative knowledge (Kuipers and Berleant (1990)). Using Q2 it is possible to associate landmark values with intervals, thereby replacing a symbolic value with a range of real numbers. Additionally, the functional relationships can be bounded by user specified envelope functions. Adding incomplete quantitative information has two major benefits. By using interval arithmetic the Q2 filter algorithm can eliminate some spurious behaviors. Since the values of the quantities can now be represented as intervals, the remaining behaviors contain more precise information than with QSIM alone. The hybrid version of QSIM/Q2 has improved inferential power without requiring additional crucial assumptions. In most cases at least some quantitative information about the system is available, and should be taken advantage of. An alternative approach is realized in order-of-magnitude reasoning (Raiman (1988)), which uses knowledge about the relative importance of physical phenom-

6

KARL R. LANG ET AL.

ena. It introduces three new relationships, A Ne B (A is negligible in relation to B), A Vo B (A is close to B), and A Co B (A has same sign and order of magnitude as B). A simple calculus based on a list of inference rules is also presented. (Mavrovouniotis and Stephanopoulos (1988)) extend this approach and suggest seven primitive order-of-magnitude relational operators, << (much smaller), - < (moderately smaller), ~ < (slightly smaller), = = (exactly equal), > ~ (slightly larger), - > (moderately larger), and >> (much larger). Quantitative knowledge about the meaning of these operators is introduced via a domain-specific tolerance parameter e, which denotes the largest value that is considered as smaller than 1. E.g., e = 0.1 represents the usual one order of magnitude corresponding to a factor of 10. The order-of-magnitude relation A << B, for example, is true if

IAI 181

--
Stronger inference rules are also provided. Other methods propose a hybridization of qualitative and quantitative techniques into one framework. (Daniels and Feelders (1991)) propose a method that uses as much quantitative information as possible, and only resorts to weaker qualitative information if nothing better is available. Deriving qualitative properties of dynamic systems analyzing analytic solutions is yet another approach. It has become a feasible task since powerful symbolic computation packages like Mathematica and Macsyma have become widely available (Sacks (1987) and Kalagnanam (1990)).

3. Qualitative Analysis in Economics In this section we shall review some of the qualitative approaches taken in economics to represent and reason about economic systems. We shall begin with a brief discussion of the method of comparative statics, the classic example of qualitative economic analysis, and show some of the limitations of a purely qualitative treatment. Our treatment is based upon the pioneering works of Samuelson (1947, Chapters 2 and 3), Gorman (1964), Lancaster (1962), and James Quirk and various collaborators (for example, Bassett, Maybee, and Quirk (1968)). For a more complete review, see Quirk and Saposnik (1968, Chapter 6), and for more recent work along these lines, see Fontaine, Garbely, and Gilli (1991) who present a graph-theoretical approach for analyzing qualitatively specified systems. In Section 3.2 we summarize some material due to Hanoch and Rothchild (1972) which deals with the economic theory of production, and specifies a way m which empirical observations can be used as an aid in qualitative model specification. We then briefly indicate how recent work on Data Envelopment Analysis (DEA) (see, for example, Charnes et al. (1981 and 1985)) might be used to extend and enrich this earlier approach.

COMPUTATIONALSYSTEMSFOR QUALITATIVEECONOMICS

7

3.1. PURELY QUALITATIVEAPPROACHES

In economics it is quite common to deal with systems of the form:

fi(xl,...,Xm;Zl,...,Zn ) = 0

fori = 1 , . . . , m ;

(1)

or, more compactly,

f(x; z) = O,

(2)

where

f: X

X

Z ~ R m, X C_ R TM, and Z C_ R n.

In a typical economic application, the equations would represent the equilibrium conditions for an interrelated system of markets, the vector x would represent ra variables whose equilibrium values are determined within the system (endogenous variables), and the vector z would represent n variables which influence the system, but whose values are determined outside the system (exogenous variables), and which are often policy variables, that is values which can be directly determined by governmental actions. Writing

9. Of i f j ( x , z * ) = Oxj (x,z)=(x*,z*)

fori=l,...,mandj=l,...,m;

and

i *. f~(x , z * ) =

Of ~

ozk_ I(:,z):(:.,:. )

for/ = 1,...,ra, andk=ra+l,...,ra+n, it is fairly common in economic problems to specify the signs of these partial derivatives globally; for example, we might suppose that: (V(x,z) E X x Z) " fll(x;z ) > O,

(3)

(v(x,z) e x

(4)

or •

z):

0,

etc. Thus, for example, the latter condition (4) would express the hypothesis that the first equation is independent of x2. If each function has continuous first partial derivatives, and for some (x*, z*) E X • Z, we have f(x*; z*) = O, and

IJI

o,

8

KARL R, LANG ET AL.

where

(x*; z*)f (x*; z*).., j=

z*)

f ~ ( x * ; z * ) f 2 ( x * ; z*) 999,m,r Ix*"z*), . . . .

.

.

.

.

.

.

,

.

.

.

.

. . . .

,

.

.

.

.

.

.

.

.

. .

f ~ ( x * ; z * ) f ~ ( x * ; z*) . " " ,m ,r x*"

:

and [d[ denotes the determinant of J, then it follows from the Implicit Function Theorem (see, for example, Apostol (1957, p. 147)) that there exists a neighborhood, N , of z* (contained in Z), and a function g : N ~ X , such that g has continuous first partials, and satisfies: (Vz E N ) " f [ g ( z ) ; z] = 0.

(5)

From (5) and the differentiability of f and g, we also have, for all z E N : m

+ f (z) = 0 j=l for$= 1,...,mandk=m+l,...,m+n.

(6)

Thus from(6) we obtain the system: j __Og

_

OZk--m

__Of

fork=m+l,...,m+n.

OZk-m

(7)

F r o m (7), we obtain: Og ~ Of Ozk = - J - ~ for k = 1 , . . . , n .

(8)

It is often possible to determine whether IJI 7~ 0 (and thus whether J - 1 exists), and, in fact, to determine the sign of IJ] solely on the basis of qualitative assumptions regarding f . Sometimes, though less often, it is possible to determine the sign of Og/Ozk solely on the basis of qualitative information. Even in cases where the latter determination is not possible, however, we may be able to say a great deal about the possible combinations of movements of the variables. The idea here is as follows. Let us hereafter denote the partial derivatives of the functions f i by Ji and J~, etc., and, as in de Kleer and Brown (1984), let us specify only that each f) and f~ (globally) takes on one of the three values

JJ:{ ~,_ and where we use an arithmetic (again, as in de Kleer and Brown) for these symbols as follows; (+).(+)= += ( - ) . ( - ) , ( + ) . ( - ) = ( - ) . ( + ) = - , (+). (o) = ( - ) . (0) = (o). (+) = (o). (-) = (o). (0) = o (+) + (+) = (+) - (-) = +, a~d (-) + (-) = (-) - (+) = -, (9) (+) - ( + ) = ( + ) + ( - ) = ( - ) + ( + ) = ( - ) - (-) =? (+) + (o) = (o) + (+) = +, (o) + (o) = (o) - (o) = o, and (o) - (+) = (-) + (o) = -.

9

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

The idea now is to, on the basis of the possibilities in the table just presented, determine the signs of the partials of g. Having done this, we can often say a great deal about the possible changes in the variable of the system; given the underlying hypothesis that our qualitative specification is correct. We will illustrate these ideas by an extended example. EXAMPLE

Consider the system:

fi(xl,X2;zt,z2)

f o r i = 1,2;

= 0

(10)

and suppose =

,

3 =+,

~=-,}

(11)

+, : = +, s~ = - , I4~ = o. Then IJl=

[:~ ~ f: f~

=

+ -

=(+).(+)-(+)-(-)=

+ +

+.

(12)

Therefore, we know that, locally, the function g : N --+ X will exist, for any system of equations satisfying the qualitative specification in (11).

The first of the systems in (7) here becomes:

[:~ :'

,~

-:~

:i,:.lI,~]--[] -fj

'

or

['~ ~,~[., [-:,:I=~[_:2:1 1 ..,2] [ f2fJ -

-fefJ

- ,2 3 + f l:y 23

= (-)"

]

(+)'(+)-(-)'(-) (-)'(+)'(+)+(+)'(-)

Similarly,

-:a]= ~[-:e = (_). [

(+). ( - ) -

:_~.~§

::]t:a]=~[-:e:~+:::~] {:I1--[+1

( - ) . (o)

9

_

10

KARLR. LANGET AL.

Thus we get the following possibilities with respect to changes in the variables; where in each case, we are treating the zj's as independent variables, and indicating, for each of the xi's, the direction of change which is implied by the changes in z shown in that row. (Note: in the table, a '-t-' in a cell stands for an increase in the value of that variable; and similarly for - and 0. Those variables to which we cannot assign a definite element of { - , 0, +} are indicated by a '?' in the corresponding cell.)

AXl

Ax2

Azl

Az2

?

+

+

0

+ ? ?

? +

0 + +

+ + -

?

-

_

+

Notice that in the xi columns, we have 5 of 10 determinate signs. Thus far, we may conclude that, firstly, purely qualitative analysis is inherently ambiguous, and that exploring all possible behaviors of a qualitative system necessitates strong computational power. 1 Lacking computer support, qualitative economics of the 1950's and 60's was confined to an analytical treatment of qualitative systems, and focused more on showing the existence of a qualitative solution than actually computing it. Secondly, we see ambiguity as a feature and not a deficiency of qualitative analysis. Given incomplete knowledge, computing all solutions consistent with a qualitative model specification might provide more insight into a system than a quantitative analysis that rests on assumptions beyond our state of knowledge. Thirdly, in order to strengthen the inferential power of qualitative analysis it seems inevitable that one would need to incorporate some quantitative information. As a matter of fact, in many cases we do have more knowledge than just signs. In particular, even if do not know the exact value of a variable we can often specify a covering range, or we might be able to specify bounds on functional relationships determining dependent variables. Whenever knowledge of that sort is available or can be obtained it should be taken advantage of, and used in deriving the implications of a model specification. We shall return to this issue in Section 4, below. For a more complete survey of qualitative economics see Quirk and Saposnik (1968, Chapter 6), and Bassett, Maybee, and Quirk (1968). 3.2. SEMI-QUALITATIVE ANALYSIS

The idea of incorporating quantitative information and techniques into qualitative economic analysis has been appealing to many economic theorists. Hanoch and

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

11

Rothschild (1972), for example, propose computational procedures based on empirical observations which test hypotheses in production theory that are formulated qualitatively. It is common practice in production theory to assume that a production process is governed by a production function with certain qualitative properties such as quasi-concavity, monotonicity, and homotheticity. Econometricians usually presuppose a particular model parametrization expressing desirable qualitative properties prior to estimation; for example, a Cobb-Douglas production function, which implies homotheticity. The estimation procedure would never refute the qualitative assumption that the observed outputs were generated by a homothetic production function; a bad fit would only indicate a poor model specification, and would not detect whether homotheticity assumption held. Hanoch and Rothschild suggest test procedures based on linear programming, that examine the issue of whether an observed set of n inputs, {x~}, and associated outputs, {yi}, could have been generated by a production function, f(x), assuming only qualitative properties thereof. For testing monotonicity and quasiconcavity of a multiple-input and single-output production process, for example, they present a linear programming formulation that, if such a function exists, constructs hyperplanes separating input-output combinations at different output levels. A similar method is developed for testing diminishing returns of a multiple-input and multiple-output production process with profit maximization. Again, linear programming is used to find factor prices and output prices such that all observed input-output combinations are boundary points of a convex production possibility set. Supposing error-free data observation, the failure of these test procedures can mean two things. Either the production function underlying the production process in fact does not have the desired qualitative properties or relevant input factors were not included in the model specification. Hanoch and Rothschild realize that, in general, we are not able to include all relevant factors in an empirical study, and that neglecting even minor factors can cause enough distortion to result in test failures. Therefore, they propose some modifications to their procedures that allow input-output points to violate the hypothesized qualitative properties of the underlying production function. Charnes and Cooper developed a framework called data envelopment analysis (DEA) (see, for example, Chames et al. (1981) or Charnes et al. (1985)) which is similar in spirit to Hanoch and Rothschild's work. DEA explores empirical observations stemming from a multiple-input and multiple-output system without assuming profit maximization. A fractional programming formulation is developed to identify Pareto-efficient input-output combinations, and to construct a monotonic piece-wise linear production function as the frontier of the production possibility set. Inefficient input-output combinations are attributed to managerial inefficiencies which do not affect the production frontier. Although DEA was originally developed for comparing the efficiency of non-profit organizations consisting of different production units, it has significance in the context of qualitative analysis. We might want to specify an input-output system qualitatively because we do not

12

KARLR. LANGET AL.

have enough knowledge to exactly formulate a functional relationship between the inputs and the outputs. However, we might know that the input-output transformations must be bounded somehow, and thus seek a qualitative model specification in terms of bounding functions. A set of empirical observations could be viewed as an implicit specification of such a qualitative model. DEA could then be used to compute envelope functions of observed data sets, giving bounds on qualitative relationships. Applying DEA is appealing for two reasons. It is computationally very efficient because it is based on linear programming, and it derives the tightest possible bounds for a given data set. Since the observed data are normally sampled it might be necessary to soften the bounds to account for possible misses of extreme input-output combinations, or one has to revise the bounds whenever observing new data.

4. A New Approach to Qualitative/Quantitative Analysis In recent and ongoing research, we have been working on a new sort of synthesis of qualitative and quantitative methods of analysis. 2 Our work is based upon four basic principles. 1. We believe that a more powerful sort of qualitative analysis can be built upon the idea of treating the functions in a system as being selections from a correspondence. 2. We believe that quantitative information can then be incorporated into the analysis in a bit different way, and to a bit different effect than heretofore. 3. In connection with the "selection from a correspondence idea," we believe that it is possible, with the use of this sort of analysis, to guide and motivate information-acquisition regarding the process under study, and to provide a systematic way of incorporating the new empirical information into the analysis. 4. Finally, we believe that the end result of these methods can be used, in connection with software implementation results obtained by Kuipers and others, to develop a purely qualitative test procedure to be used in empirical testing of economic models (and, presumably, of other social science models) under study. We shall briefly consider these points in turn.

4.1. QUALITATIVE ANALYSIS, CORRESPONDENCES, AND SELECTIONS FROM CORRESPONDENCES

The essence of the motivation of qualitative analysis, as applied to, say, economics would appear to us to revolve around the fact that our knowledge of economics is necessarily fragmentary, imperfect, and inexact. Thus we might believe that an economic system is capable of description as a system of equations, but we lack the knowledge to be able to specify those equations exactly. In a purely qualitative approach, as exemplified, for example, in de Kleer's and Brown's (1984) representation of the simplest possible quantity space, Q = { - , 0, +}, one treats functions of, say, one real variable, as a mapping from R into Q. To take a more

13

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

explicit example, one might think of a particular such function as being specified by:

f(x) =

{ forx<0 } 0 for x = 0, and + for x > 0.

(1)

From a formal point of view, this is equivalent to the following. First, define the correspondence, ~ : R ~ R, by: c2(x ) =

-R+ {0} R+

forx < 0, } for x = 0, and for x > 0.

(2)

We can reexpress the specification of f(.) by specifying that f is a selectionfrom ~; where a function f : X --* Y is said to be a selection from a correspondence, c 2 : X ~ Y iff: forevery x E X , I ( x ) E ~(x). The advantage of this approach; that is, of proceeding with the general specification of the system by first defining correspondences representing the general information on the individual functions in the system, and then specifying that the function is a selection from the given correspondence, are several. First of -all, one can easily incorporate quantitative, as well as purely qualitative information into the specification, and in a systematic way. Thus, for example, suppose we add the following information, which is similar to the M + specification of classes of monotonically increasing functions in QSIM, to our specification of f ( . ) in (1):

0 <~f'(x) ~< 1 for all x E R.

(3)

It is then an immediate consequence of the Mean Value Theorem that if we now define the correspondence ~ : R ~ R by:

r

{ {y E RIx ~ y ~ 0.

_ '

(4)

then we can now sharpen our specification of f(.) by specifying that f be a selection from r As a matter of fact, we can incorporate additional information into the formula sequentially, in a natural way, by specifying that the functions in question be in the intersection of the original correspondence, and a second correspondence reflecting the additional information to be used. For instance, in the example just discussed, we could incorporate the additional information in (3) in an alternative, that is, alternative to the specification (4), and more natural way, by first defining the correspondence qo* by: qa*(x)

{y E Rly >~x} for x ~ 0 S'

(5)

14

KARLR. LANGET AL.

and then noting that the restrictions (1) and (3) together require that f(.) be a selection from the correspondence ~ defined as 9 (x) = q~(x) fq ~2*(x)

for x E / L

(6)

Secondly, we can extend the considerations of the preceding paragraph to note that we can easily incorporate new information regarding values of f(.) at particular points in the domain in a way similar to the following procedure. set r /* initial qualitative model */ while r is not accurate enough /* stopping rule */do acquire new information on f set r /* translate new info into a correspondence */ r := r 71 Cnew /* refine qualitative model */ endwhile Thirdly, there are well-defined [and "well-known"] procedures and results about algebraic and set-theoretic operations with correspondences. These operations can be naturally used to express restrictions on arithmetic operations with the "qualitatively specified" functions. Thus, for example, if fi is specified to be a selection from the correspondence q~ : X ~ R, for i = 1, 2; then we know that the function fl + f2 will be a selection from the correspondence qOl + ~2. Fourthly, and in conjunction with this last point, there is a well-developed set of topological results on correspondences, and selections from them, which can be fruitfully applied in this treatment of "qualitative" specifications, see Michael (1970). For example, it is common in the qualitative analysis literature to suppose that the functions involved are continuous. In our approach, this would mean that f ( . ) might be specified to be a continuous selection from some specified correspondence, call it ~. This condition, per se, only means that we are saying that f ( . ) is a continuous function; however, a necessary condition for a correspondence to have a continuous function definable through each point in its graph is that it be itself lower hemi-continuous (see Michael (1956), p. 362). Thus, if it is natural to specify that f(.) is continuous, it would seem equally natural to specify that the correspondence, ~, from which f ( . ) is a selection, is lower hemi-continuous. But this latter fact can be used in the analysis in and of itself; to give one example: if ~y : X ~ T, where X and T are topological spaces, X is a connected space, qo is lower hemi-continuous, and ~(x) is a connected subset of T, for each x E X , then the image of X under q~, the set q~(X) defined by

~ ( X ) = {y ~ Tl(3x ~ X ) : y = ~ ( x ) ) , is a connected subset of T (Moore (1988, p. 3)). This can be regarded as a sort of "Rolle's Theorem" for correspondences, and can be used in the approach that we are advocating, in much the same way (but in much more general contexts) as DeKleer and Brown (1984) use the usual version of Rolle's Theorem.

15

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

4.2. INCORPORATINGQUANTITATIVEINFORMATIONINTO THE QUALITATIVE ANALYSIS We have already touched upon the way in which quantitative information can be incorporated into the selection from a correspondence approach. We also believe that quantitative information can be used in a rather different way than heretofore to greatly sharpen the sorts of qualitative analysis results we discussed in Seet~on 3.1, above. Returning to the example presented in equations (10)-(13), and the Table at the end of Section 3.1; consider the specification of the function f 1. If we reexamine equation (13), we see that, since the sign of [d[ is positive, the partial derivative of 9 1 with respect to Zl is a positive scalar multiple of the inner product of the vectors ( - f22, f l ) and (fm, f32). If, as in 3.1, we specify only that ( - f22, f l ) is an element of the third quadrant in R 2, then the sign of the inner product,

9~ = ( - f~, f~) . ( fl, f~),

(7)

is determined if, and only if the vector (f~, f2) is an element of the first or the third quadrant in R2; if ( f l , f2) is in (the interior of) the second or fourth quadrants of R 2, the sign of the inner product is indeterminate. However, if some inequality relationships among the partial derivatives of fl are known, we may be able to deduce sharper results regarding the signs of the partial derivatives of g 1. For example, suppose that, in addition to the sign specifications given in (11) of 3.1, it is known that

sJ + fi ,
(s)

Then from (if),(13) and (14)from 3.1,and (9),above,we have

~E(-s~, s~). (sJ, :~) I

21

fl

(-fi,

s~). (s~,o)]

12

= T-~[(-fz,f2)" ( 3 - f4,f3)] 1

2

= ~[-s~ 9(s~ - s4')+ s~ 9fi] 1

i

/> ~-~[f~.(fJ - f) + f~)] I> O;

(9)

where the next-to-the last inequality is from (9) and the fact that fJ - f41 /> O, and the last inequality is from (9), above, and (11) of 3.1. Since we established that, given (11) of 3.1, we have g21 1> O, it now follows from (10) that

g~>O

16

KARL R. LANG ET AL.

as well. Notice that the type of quantitative restriction that we are speaking of here can generally be expressed by the stipulation that:

C1J*C2 <~D1J*D2,

(10)

where J* is the ra(m + n) matrix of first derivatives of the system defined in (1)-(6) of Section 3.1, and where Ci and Di (i = 1, 2) are known (numerically specified) matrices. In our example, for instance, the two inequalities in (9) can be specified in the form of the inequality in (11) by taking

= [1 1],

= [1 0],

and

C2 =

D2 =

00 00 00 01

I n our current research, we are investigating ways in which matrix restrictions of various sorts can be taken into account in a qualitative sort of analysis. 4.3. INCORPORATING NEW INFORMATION INTO THE ANALYSIS

In specific applications in applied economics, the initial state of knowledge is usually sufficient to specify some qualitative model that describes the system under investigation; although in many cases such a purely qualitative problem description will be too weak to derive satisfactory results. Often, however, it is possible to improve the state of knowledge by systematically obtaining additional information from empirical experiments and/or observations. The acquisition of additional information will often result in a sharper, better specified model, and/or more satisfactory solution, but will also generally involve a cost. Balancing the tradeoff between the desire for greater accuracy, and the cost of obtaining said accuracy is always a very difficult problem, and we shall not attempt to develop new answers to this general problem her, 3 but we can show how the approach to qualitative analysis being discussed here can incorporate new knowledge into the system in a simple and systematic way. A convenient illustration can be provided by a slight modification of some material developed in Moore, Rao, and Whinston (1992). They consider a variant of the classical resource allocation problem within the context of an exchange economy. In their model, a central coordinator is with the task of achieving a 'good' allocation of a fixed amount of n commodities among m individual agents, where 'good' is defined in terms of a 'social welfare function', whose values can be expressed as functions of individual utilities. The coordinator is assumed at the outset, however, to know nothing about the individual

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

17

agents' preference relations other than that they are weak orders (total, reflexive, and transitive binary relations). In order to achieve a 'good' allocation, he needs to obtain additional information, but the additional information is assumed to be obtainable only at a positive cost. The coordinator's problem is one of devising a strategy for obtaining additional information about preferences in such a way as to attain the best allocation possible, subject to a constraint on the cost expended to obtain said information. More specifically, they begin by considering an optimization problem of the following form: max W(Xl, . . . , Xm)

wrt

x

=

F [ f l ( x l ) , . . . , fm(Xm)]

m

subject to: ~--~xi ~< :~, andxi E X, f o r i = 1 , . . . , m ;

(1)

i=l

where X is defined by

X = {x E R~.lxj is an integer, f o r j = 1 , . . . , n), and where: m is the number of agents, n is the number of commodities, xi E X is the commodity bundle allocated to the ith agent, for i = 1 , . . . , m, W(.) is the social welfare function to be maximized [which is supposed to to be expressible in the form on the right-hand-side of the first in (1)], with F(.) the "aggregator function" for W(.), fi(') the "utility function" of the ith agent, supposed to represent the ith agent's preference relation, G~, and E X is the aggregate commodity bundle available to the coordinator. If the individual utility functions, fi, were known to the coordinator at the outset, this would be a straightforward mathematical programming problem; however, it is supposed that the coordinator knows only that each Gi is a strictly increasing weak order. It is also supposed, that the coordinator does know the aggregator function, F(.), and the way in which fi is to be obtained from Gi (this last is actually needed to make the social welfare function meaningful). In the remainder of the present discussion, we shall suppose that the method to be used in obtaining fl from Gi is defined by:

fi(xi) = #{Yi E X*lxiGiyi},

where X* =- {x E XI0 ~< x ~< 2},

(2)

and where, for a finite set, A, '#A' denotes the number of elements of A. Suppose in our further discussion, we take a simple case in which n, the number of commodities, and m, the number of agents, are both equal to two; and where 2 = (2, 2). As it happens, there are 197 possible strictly increasing weak orders of the set X* in this case, and the coordinator does not know which of these orders

18

KARL R. LANG ET AL.

is the true preference relation of, say, the first agent. However, the coordinator can use the fact that the first agent's preference relation is a strictly increasing weak order, and that the agent's utility function is to be measured in the way defined by equation (2), to calculate upper and lower bounds for agent l's utility at each commodity bundle which might accrue to agent one in a feasible allocation.4 These lower and upper bounds [call them '~(x)' and 'or(x)', respectively] define, for each commodity bundle, an interval in which the true utility value of that bundle must lie. If we define a correspondence, ~, therefore, by letting/l~(x) be the set of integer values lying within the interval [~(x), or(x)], the coordinator can be said to know that the appropriate utility function for each of the two agents is a selection from g~. In the particular example cited, this correspondence expressing the initial qualitative information is as follows (see Moore et al. (1992)): T A B L E I.

~(~) (0,0) (1, o) (0,1) (0,2) (1, 1) (2,0) (2, 1) (1,2) (2, 2)

{1} {2, 3, 4} {2,3,4} {3,4, 5, 6,7} {4, 5, 6} {3,4,5,6,7} {6, 7, 8} {6, 7, 8} {9}

We can use Table 1 to indicate the peculiar difficulty of the coordinator's position in the following way. Suppose, for the sake of illustration, that the 'aggregator function', F(.) to be used in defining the social welfare function is here given by: ftl

F(x) = ~_~ ui;

(3)

i=1

and thus that, in the context of the example being considered in Table 1 (two each of agents, commodities, and amounts of the commodities) the social welfare function, W(.), is given by:

W(Xl, x2) = fl(Xl) + f2(x2).

(4)

The possible values of social welfare at each possible allocation can then also be thought of as a correspondence, say f~(Xl, x2); where, for example, ~[(0, 2), (2,0)] = {6, 7, 8, 9, 10, 11, 12, 13, 14}, and f~[(1, 1), (1, 1)] = {8,9, 10, 11, 12}.

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

19

Without additional knowledge about the two agents' preferences, it is extremely difficult, if not impossible, to say which of the two allocations [(0, 2), (2, 0)] and [( 1, 1), (1, 1)], both of which are feasible, is better. 5 The coordinator's problem, in effect, is thus to obtain enough additional information about the individual utility functions, fi, as to enable a meaningful optimization of f~ to be done. The particular information-gathering strategy which is pursued by the coordinator in the work under discussion is to ask the agents (individually) to compare pairs of commodity bundles [for example, to compare (2, 0) with (0, 2)], and to state which of the bundles is preferred, or whether the agent is indifferent between the two. The response is then used to calculate new upper and lower bounds for the agent's utility at each point; these new bounds being then used to modify the appropriate correspondence for agent i. The goal of the coordinator is to continue to acquire information regarding the agents' preferences until a sufficiently 'good' allocation can be made, where "sufficiently good," it is meant that the value of the welfare function at the allocation actually made does not differ from the maximum welfare value obtainable by more than some 'acceptable loss', ~5. If the coordinator knew the exact values of the agents' utility functions, this loss could, of course, be reduced to zero. It is supposed, however, that the process of information-gathering is costly, and thus it is generally better to accept a non-zero value of potential welfare loss than to incur the cost of obtaining full information regarding the agents' preferences. In the class of problems investigated, it is shown that, given a value, tS, for the maximum potential welfare loss, there is always some positive value, ~, for the 'diameter' of the approximating utility correspondences, ff~(.), such that whenever the diameter of ~ ( . ) is <~ rl, then the maximum potential welfare loss is no greater than 6; where ~ ( . ) is the approximating correspondence for the ith agent after the tth pair of bundles has been compared, and the diameter of ~ ( . ) is defined by diameter ( ~ )

= max max In - u' I. ~ex* ~,~'e+~(~)

(5)

Setting the maximal acceptable welfare loss, c5, equal to two, and applying to our example the information-gathering strategy as proposed in Moore et al. (1992) obtains the following results. 1. An "efficient" information-gathering strategy can be developed which results, after a maximum of four steps (and a minimum of two steps) in a diameter of ~ less than or equal to one, where (a) the desired representation of agent i's utility function is a selection from 9 ~, and (b) ~ p takes the form 9 ~ ( x i ) = {n E Nlti(x~ ) <<.n <<.ai(xi))}, 6 (6) for each feasible commodity bundle, xl, for i = 1,2. 2. It can then be shown that, if an allocation, x* = (x~, x~), is chosen so as to maximize the sum tl(Xl) + c2(x2) over feasible x = (Xl, x2), where t/(.) is

20

KARLR. LANGET AL.

from (6), above, then the maximum possible welfare loss is no greater than two. To elaborate a bit on this example, the "efficient" information-gathering strategy developed in Moore et al. (1992) begins by asking each agent (the strategy is symmetric over agents) to compare the bundles (2, 0) and (0, 2). The first level of the decision tree for the information-gathering strategy is then as follows [where Pi and Ii are the asymmetric ('strict preference') and symmetric ('indifference') parts of Gi, respectively]: 1. if (2, O)Pi(O, 2) then agent i is asked to compare (1,2) with (2, 0), 2. if (2, O)Ii(O, 2) then agent i is asked to compare (1, 1) with (2, 0), and 3. if (0, 2)Pi(2, 0) then agent i is asked to compare (0, 2) and (2, 1). Since the full strategy involves 25 possible outcomes for each agent, and thus 252 = 625 possible outcomes altogether, we will not set out the full example here. However, we can illustrate the techniques of interest for the present work 7 by considering one possible path through the decision tree. Suppose that the string of responses for the two agents are as follows: agent 1: (2,0)P1(0,2), (2, 0)Pffl, 2), and (0,2)/~

agent 2: (2, 0)P2(0, 2), (1,2)/:'2(2, 0), and (0, 2)Pffl, 1). After these responses have been obtained, it can be shown that the desired utility representations for the two agents are selections from the correspondences ~ r given in Table 2, below. TABLE II.

(1,0) (0,1) (0,2) (1,1) (2,0) (2,1) 0,2)

{2,3} {2,3} {2,3} {2,3} {4,5} {5} {4,5} {4} {7} {6} {8} {7,8} {8}

{7,8}

In this case, it is easily shown that the maximum of the sum bl(Zl) -~- b2(X2) occurs at the allocation z* = ((2, 0), (0, 2)), with / q ( ( 2 , 0 ) ) + 1 2 ( ( 0 , 2 ) ) ' - 12.

Moreover, while the strategy chosen (including the stopping rule: stop as soon as the diameter of ff~ ~< 1) guarantees a welfare loss no greater than two, the possible welfare loss in this case is zero; since, as the reader can easily verify, the maximum possible social welfare sum:

r

+r

COMPUTATIONALSYSTEMSFORQUALITATIVEECONOMICS

21

over feasible allocations other than x* is 11. It is of interest to note that this best allocation is obtained despite the fact that neither utility function is known with certainty.

4.4. USING QUALITATIVE/QUANTITATIVEANALYSIS TO OBTAIN A DISTRIBUTION FREE EMPIRICAL TEST OF MODEL Turning now to the fourth of the points mentioned in the introduction to this section, the use of qualitative analysis to develop a purely qualitative test of economic models, let us return to the context of the example developed at the end of Section 3.1, and suppose we have a time series of x and z values as follows.

period

Xl

x2

zl

z2

0

10

10

1

5

1

15

8

2

4

2

20

7

3

6

3

25

9

4

5

4

30

12

5

4

Thus, defining AtX

i ~

t

t-1

X i -- X i

,

and

Atz

i =

t

t-1

z i -- z i

for i = 1,2, andt = 1 , 2 , 3 , 4 .

we have:

period

Axl

Ax2

AZ 1

Az 2

1

5

-2

1

-1

2

5

-1

1

3

5

2

1

-1

4

5

3

1

-1

or, in terms of our qualitative symbols:

2

22

KARLR. LANGET AL.

period

AXl

Ax2

AZl

Az 2

1

+

-

+

-

2

3

+ +

+

+ +

+ -

4

+

+

+

-

Thus, upon comparison with the table at the end of Section 3.1, we see that this time series is n o t consistent with the qualitative specification of the example. On the other hand, the time series below is consistent with the specification used in Section 3.1.

period

x1

x2

Zl

z2

0

10

8

1

5

1

15

10

2

4

2

20

12

3

4

3

25

12

4

5

4

30

10

4

6

5

35

8

3

7

period

Ax 1

1

5

2

1

2

5

2

1

0

3

5

0

1

1

4 5

5 5

-2 -2

0 -1

1 1

AX2

AZl

Az2

-1

The basic idea of our procedure is that it provides an entirely non-parametric 'pre-test' of the basic specification of an econometric model. Thus, if an investigator finds that with a proposed qualitative specification for a model, the data being used supports (does not refute) the proposed qualitative specification, this provides an entirely non-statistical empirical test of the model to be used. In particular, such a test would provide a sound basis for estimation subject to constraints (those constraints being the qualitative specifications in the pre-test), with well-known benefits insofar as the variance of the estimators is concerned. If, on the other

COMPUTATIONAL SYSTEMS FOR QUALITATIVE ECONOMICS

23

hand, the data is inconsistent with the model, then clearly a reevaluation of the qualitative specification of the model is called for before expensive and timeconsuming quantitative estimation is pursued. Of course, such a qualitative test of a model is of interest in and of itself, whether or not it is done as a preliminary to quantitative estimation. We believe that, possibly with some modifications, the computational techniques developed in the qualitative reasoning field by Kuipers and his collaborators can be used to develop programmatic techniques to implement this sort of qualitative test in a systematic and efficient fashion. Once again, this topic is being investigated in ongoing research. 5. Conclusion

In this paper, we have presented a qualitative modeling framework which unifies techniques that have been developed independently in the areas of economics and artificial intelligence. We have shown the connections between qualitative reasoning and qualitative economics, and have described the synergistic effect which results from combining the computationally-oriented qualitative reasoning methods with the more theoretical approach of qualitative economics. We propose a "selection from correspondences" approach as a versatile, yet efficient means for representing and analyzing qualitative systems; one which, on the one hand, generalizes most representational forms known from qualitative reasoning, and, on the other hand, provides the full analytical strength of this area of mathematics and of theoretical economics. We have developed a procedure to incorporate new quantitative, as well as qualitative, information into the specification by formulating current and new information as correspondences and intersecting them in a sequential manner, thus increasing the exactness of the original model specification. Using a resource allocation problem, we have also demonstrated a way in which this framework can serve as the basis for a type of qualitative optimization procedure. In ongoing research, we are working on a method of implementation of our qualitative modeling framework. We shall conclude this article by indicating a few possible future research directions which, we believe, are of particular interest. First, we believe it is of great importance to design a complete modeling language which is based upon correspondences, yet does not require the user to be familiar with the mathematical theory of correspondences. The QSIM/Q2 modeling language, which includes a feature for specifying envelope functions for describing partially known functions by upper and lower bounding functions, and the RCR language [Hinkkanen, Lang, and Whinston (1993)], a genuine interval-based method, both implicitly contain special cases of correspondences as their main representational vehicle, and could be used as a starting point for designing a language that is specifically tailored for using correspondences to represent qualitative relationships. Also, it would be very interesting to extend current constraint programming languages, which are typically based on a constraint-satisfaction system which deal

24

KARLR. LANGET AL.

primarily with numerical constraints (for example, Leler (1988)) or logical constraints (for example, van Hentenryck (1989)). Developing a constraint-satisfaction system based on a (semi-)qualitative calculus, would offer the possibility to analyze economic models by specifying qualitative relationships in declaritive manner, and let the constraint-satisfaction system find a qualitative solution. Although constraint-satisfaction methods are known to be of limited power, which is due to the large search space they have to work with, this latter approach could provide an ideal modeling environment for deriving quickly the implications of a small set o f qualitatively stated relationships. Secondly, the development of operational information-gathering methods is another crucial issue which needs to be addressed. Data envelope analysis and recent work on knowledge discovery methods [Shapiro and Frawley (1991)] could be applied to automatically construct correspondences derived from data representing additional information. Thirdly, a more general treatment of qualitative optimization, generalizing the method used in the rather specific example presented in Section 4.3 is another open and very interesting research challenge. Finally, we believe that research on more elaborate and formal ways of embedding empirical testing into qualitative analyses is also likely to be very fruitful.

Acknowledgements We are indebted to the referees for the insightful comments which helped us greatly to improve our paper.

Notes 1 The fact that a qualitative calculus like that presented in (9) of the text is unlikely to be sufficient to determine the signs of the derivatives of the g function was pointed out in the economics literature of the 1960's, and is a point which is certainly not original with us. For a further discussion, see Quirk and Saposnik (1968); and for a more recent and definitive discussion, see Pau and Gianotti (1990, Chapter 5, esp. p. 214f). 2 Brouwer et al. (1989), and Fontaine, Garbely, and Gilli (1991) present alternative approaches to synthesizing traditional qualitative economics and semi-qualitative analysis methods. 3 This problem has been analyzed, from two complementary points of view, in Moore and Whinston (1986), and Balakrishnan and Whinston (1991). 4 Details on the calculation of these bounds are presented on pp. 13-18 (NB page 18), of Moore et al. (1992). 5 A reader familiar with statistical decision theory will no doubt immediately think of using some sort of expected value criterion to choose between the allocations. However, there are very thorny difficulties involved in trying to define a meaningful probability distribution over the relevant state space here. For a discussion, the reader is referred to Moore et al. (1992), particularly pp. 27-8. 6 Where 'N' denotes the set of nonnegative integers. 7 It should be noted that, while the information-gathering strategy being discussed here is taken from Moore et al., and the economic example is developed there, the technique being proposed here, treating the true utility functions as being selections from a correspondence, is not utilized in the earlier work.

COMPUTATIONALSYSTEMSFOR QUALITATIVEECONOMICS

25

References Aliprantis, C.D., Brown, D.J. and Burkinshaw, O, 1990, Existence and Optimality of Competitive Equilibria, Springer Veflag. Apostol, Tom M., 1957, MathematicaIAnalysis, Addison-Wesley. Arrow, K.J. and Hahn, F.H., 1971, General CompetitiveAnalysis, Holden-Day. Balasko, Yves, 1988, Foundations of the Theory of General Equilibrium, Academic Press. Bassett, L., Maybee, J. and Quirk, J., 1968, Qualitative economics and the scope of correspondence principle, Econometrica 36, 544-563. Bailey, A.D., Kiang, Y., Kuipers, B. and Whinston, A.B., 1991, Analytic procedures and qualitative reasoning in auditing, In: Applications in Management Science, JAI Press. Balakfishnan, A. and Whinston, A.B., 1991, Information issues in model specification, Information Systems Research 2(4), 263-286. Berndsen, R. and Daniels, H., 1991, Qualitative economics: An implementation in PROLOG, Computer Science in Economics and Management 4, 1-13. Bobrow, D.G., ed., 1985, Reasoning about physical systems, MIT Press, Cambridge, MA. Bridgeland, D.M., 1989, Qualitative simulation extensions for supporting economics models, MCC Technical Report Number ACT-AI-328-89, Austin, Texas. Brouwer, F., Maybee, J., Nijkamp, P. and Voogd, H., 1989, Sign-solvability in economic models through plausible restrictions, Atlantic Economic Journal 17, 21-26. Charnes, A., Cooper, W.W. and Rhodes, E., 1981, Evaluating program and managerial efficiency: An application of data envelope analysis to program follow through, Management Science 27(6), 668-697. Chames, A., Cooper, W.W., Golany, B., Seiford, L. and Stutz, J., 1985, Foundations of data envelope analysis for Pareto-Koopmans efficient empirical production functions, Journal of Econometrics 30, 91-107. Crawford, J., Farquhar, A. and Kuipers, B., 1990, QPC: A compiler from physical models into qualitative differential equations. In: Proceedingsof the National Conferenceon Artificial Intelligence (AAAI-90), Lost Altos, CA. Dalle Molle, D.T. and Edgar, T.E, 1989, Qualitative modeling of chemical reaction systems. In: Mavrovouniotis, M., (ed.), Artificial IntelligenceApplications in ProcessEngineering, Academic Press. Daniels, H.A.M. and Feelders, A.J., 1991, Combining qualitative and quantitative methods for modelbased diagnosis of finns, Working Paper, Tilburg University. Davis, E., 1987, Constraint propagation with interval labels, Artificial Intelligence 32, 281-331. Debreu, Gerard, 1959, Theory of Value, John Wiley & Sons. de Kleer, J. and Browne, J.S., 1984, A qualitative physics based on confluences,ArtificialIntelligence 24, 7-83. de Kleer, J. and Williams, B.C., 1987, Diagnosing multiple faults, Artificial Intelligence 24, 97-130. Farley, A.M. and Lin, K.P., 1990, Qualitative reasoning in economics, Journal of Economic Dynamics and Control 14, 465--490. Fontaine, P., Garbely, M. and Gilli, M., 1991, Qualitative solvability in economic models, Computer Science in Economics and Management 4, 285-301. Forbus, K.D., 1984, Qualitative process theory,Artificial Intelligence 24, 85-168. Forbus, K.D., 1990, The qualitative process engine, in J. de Kleer, and D. Wald (eds.), Readings in Qualitative Reasoning about Physical Systems, Morgan Kaufman. Fouch~, P. and Kuipers, B., 1991, Abstracting irrelevant distinctions in qualitative simulation. In:

Proceedings of the FifthInternational Workshopin QualitativeReasoning about PhysicaISystems (QR-91). Gorman, W.M., 1964, More scope of qualitative economics, Review of Econom& Studies 31, 65-68. Hanoch, G. and Rothschild, M., 1972, Testing the assumptions of production theory: A nonparametfic approach, Journal of Political Economy 80(2), 256-275. Hentenryck van, P., 1989, Constraint Satisfaction in Logic Programming, MIT Press. Hildenbrand, Werner (1974), Core and Equilibria of a Large Economy, Princeton University Press. Hinkkanen, A., Lang, K.R. and Whinston, A.B., 1994, On the usage of qualitative reasoning as approach towards enterprise modeling. Gaul, W., Radermacher, EJ., Schader, M. and Solte, D., eds., Annals of Operations Research 54, special issue: Data, Expert Knowledge and Decisions.

26

KARL R. LANG ET AL.

Iwasaki, Y. and Simon, H.A., 1986, Causality in device behavior, Artificial Intelligence 29, 3-32. Kalagnanam, J., 1990, Integration of symbolic and numeric methods for qualitative reasoning, Tech. Report CMU-EPP-1991-01-01, Dept. of Engineering and Public Policy, Carnegie Mellon University. Kuipers, B. 1985, The limits of qualitative simulation. In: Proceeding of Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), William Kaufman, CA. Kuipers, B., 1986, Qualitative simulation, Artificial Intelligence 29, 289-338. Kuipers, B., 1987, Abstraction by time-scale in qualitative simulation. In: Proceedings of the National Conference on Artificial Intelligence (AAAI-90), Lost Altos, CA. Kuipers, B. and Kassirer, J.P., 1984, Causal reasoning in medicine: Analysis of a Protocol, Cognitive Science 8, 363-385. Kuipers, B. and Chiu, C., 1987, Taming intractable branching in qualitative simulation. In: Proceeding of Eleventh International Joint Conference on Artificial Intelligence (IJCAI-87), William Kaufman, Los Altos, CA. Kuipers, B. and Berleant, D., 1990, A smooth integration of incomplete quantitative knowledge into qualitative simulation, Tech. Report AI90-122, Artificial Intelligence Laboratory, The University of Texas at Austin. Lancaster, K.J., 1962, The scope of qualitative economics, Review of Economic Studies 29, 99-123. Leler, W., 1988, Constraint Programming Languages, Addison-Wesley. Lin, K.P. and Farley, A.M., 1991, Qualitative economic reasoning: A disequilibrium perspective, Computer Science in Economics and Management 4, 117-134. Mavrovounitis, M.L. and Stephanopoulos, G., 1988, Formal Order-of-Magnitude Reasoning in Process Engineering, Computer Chemical Engineering 12, 867-880. Michael, E., 1956, Continuous Selections, I, Ann. Math. 63, 361-82. Michael, E., 1970, A Survey of Continuous Selections, in: Fleischman, W.M., ed., Set-ValuedMappings, Selections and Topological Properties of 2x. Lecture Notes in Math. No. 171, SpringerVerlag. Moore, James C., 1988, Lower hemi-continuous and continuous correspondences, and maximum theorems. Notes distributed to Economics 660, Fall, 1988, Purdue University. Moore, J.C., Rao, H.R. and Whinston, A.B., 1992, Information processing for a finite resource allocation mechanism. Center for the Management of Manufacturing Enterprises, Purdue University; Working Paper No. 92-9-1. Moore, J.C. and Whinston, A.B., 1986, A Model of Decision-Making with Sequential InformationAcquisition (Part 1), Decision Support Systems 2, 285-307. Paul, L.E and Gianotti, C., 1990, Economic and Financial Knowledge-Based Processing, Springer Verlag. Quirk, J. and S aposnik, R., 1968, Introduction to General Equilibrium Theory and Welfare Economics, McGraw-Hill. Raiman O., 1988, Order of Magnitude Reasoning. In: Proceedings of the National Conference on Artificial Intelligence (AAAI-88), Lost Altos, CA. Ritschard, G., 1983, Computable qualitative comparative static techniques, Econometrica 51, 11451168. Roddis, K. -nd Martin, J.L., 1991, Qualitative reasoning about steel bridge fatigue and fracture. In: Proceedings of the Fifth International Workshop in Qualitative Reasoning about Physical Systems (QR-91). Sacks, E., 1987, Hierarchical Reasoning about inequalities. In: Proceedings of the National Conference on Artificial Intelligence (AAAI-87), Lost Altos, CA. Samuelson, P.A., 1947, Foundations of economic analysis, Harvard University Press. Simon, H., Kalagnanam, J. and Iwasaki, Y., 1991, The mathematical bases for qualitative reasoning, IEEE Expert, April 1991. Shapiro G.P. and Frawley, W.J., eds., 1991, Knowledge discovery in databases, AAAI Press/The MIT Press, Menlo Park, CA. Weld, Daniel S., 1988, Comparative Analysis, Artificial Intelligence 36, 333-373. Weld, D.S. and de IOeer, J., eds., 1990, Reading in qualitative reasoning about physical systems, Morgan Kanfman, San Mateo, CA. Williams, B., 1984, Qualitative Analysis of MOS Circuits, Artificial Intelligence 24, 281-346.