M. P. Wellman

Volume 1, 1993

**Links to Full Text:**

Market price systems constitute a well-understood class of mechanisms that under certain conditions provide effective decentralization of decision making with minimal communication overhead. In a

Journal of Artificial Intelligence Research 1 {1993} 1-23 Submitted 5/93; published 8/93 A Market-Oriented Programming Environment and its Application to Distributed Multicommodity Flow Problems MichaelP. Wellman wellman@engin.umich.edu University of Michigan, Dept. of Electrical Engineering and Computer Science, Ann Arbor, MI 48109 USA Abstract Market price systems constitute a well-understood class of mechanisms that under certain conditions provide effective decentralization of decision making with minimalcom- munication overhead. Ina market-oriented programming approach to distributed problem solving, we derive the activities and resource allocations for a set of computational agents by computing the competitive equilibrium of an artificial economy. Walras provides basic constructs for defining computational market structures, and protocols for deriving their corresponding price equilibria. In a particular realization of this approach for a form of multicommodity flow problem, we see that careful construction of the decision process ac- cording to economic principles can lead to efficient distributed resource allocation, and that the behavior of the system can be meaningfully analyzed in economic terms. 1. Distributed Planning and Economics In a distributed or multiagent planning system, the plan for the system as a whole is a com- posite of plans produced by its constituent agents. These plans may interact significantly in both the resources required by each of the agents' activities {preconditions} and the prod- ucts resulting from these activities {postconditions}. Despite these interactions, it is often advantageous or necessary to distribute the planning process because agents are separated geographically, have different information, possess distinct capabilities or authority, or have been designed and implemented separately. In any case, because each agent has limited competence and awareness of the decisions produced by others, some sort of coordination is required to maximize the performance of the overall system. However, allocating resources via central control or extensive communication is deemed infeasible, as it violates whatever constraints dictated distribution of the planning task in the first place. The task facing the designer of a distributed planning system is to define a computa- tionally efficient coordination mechanism and its realization for a collection of agents. The agent configuration may be given, or may itself be a design parameter. Bythe term agent, I refer to a module that acts within the mechanism according to its own knowledge and interests. The capabilities of the agents and their organization in an overall decision-making structure determine the behavior of the system as a whole. Becauseit concerns the collec- tive behavior of self-interested decision makers, the design of this decentralized structure is fundamentally an exercise in economics or incentive engineering. The problem of developing architectures for distributed planning fits within the framework of mechanism design {Hur- wicz, 1977; Reiter, 1986}, and many ideas and results from economics are directly applicable. In particular, the class of mechanisms based on price systems and competition has been deeply investigated by economists, who have characterized the conditions for its efficiency c fl1993 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.Wellman and compatibility with other features of the economy. When applicable, thecompetitive mechanism achieves coordination with minimal communication requirements {in a precise sense related to the dimensionality of messages transmitted among agents {Reiter, 1986}). The theory of general equilibrium {Hildenbrand & Kirman, 1976} provides the founda- tion for a general approach to the construction of distributed planning systems based on price mechanisms. In this approach, we regard the constituent planning agents as consumers and producers in an artificial economy, and define their individual activities in terms of pro- duction and consumption of commodities. Interactions among agents are cast as exchanges, the terms of which are mediated by the underlying economic mechanism, or protocol. By specifying the universe of commodities, the configuration of agents, and the interaction protocol, we can achieve a variety of interesting and often effective decentralized behaviors. Furthermore,we can apply economic theory to the analysis of alternative architectures, and thus exploit a wealth of existing knowledge in the design of distributed planners. I use the phrase market-oriented programming to refer to the general approach of de- riving solutions to distributed resource allocation problems by computing the competitive equilibrium of an artificial economy. 1 In the following, I describe this general approach and a primitive programming environment supporting the specification of computational markets and derivation of equilibrium prices. An example problem in distributed trans- portation planning demonstrates the feasibility of decentralizing a problem with nontrivial interactions, and the applicability of economic principles todistributed problem solving. 2. WALRAS: A Market-Oriented Programming Environment To explore the use of market mechanisms for the coordination of distributed planning mod- ules, I have developed a prototype environment for specifying and simulating computational markets. Thesystem is called walras, after the 19th-century French economist Leon Wal- ras, who was the first to envision a system of interconnected markets in price equilibrium. Walras provides basic mechanisms implementing various sorts of agents, auctions, and bidding protocols. To specify a computational economy, one defines a set of goods and instantiates a collection of agents that produce or consume those goods. Depending on the context, some of the goods or agents may be fixed exogenously, for example, they could cor- respond to real-world goods or agents participating in the planning process. Others might be completely artificial ones invented by the designer to decentralize the problem-solving process in a particular way. Given a market configuration, walras then runs these agents to determine an equilibrium allocation of goods and activities. This distribution of goods and activities constitutes the market solution to the planning problem.1. The name was inspired by Shoham's use of agent-oriented programming to refer to a specialization of object-oriented programming where the entities are described in terms of agent concepts and interact viaspeech acts {Shoham, 1993}. Market-orientedprogramming is an analogous specialization, where the entities are economic agents that interact according to market concepts of production and exchange. The phrase has also been invoked by Lavoie, Baetjer, and Tulloh {1991} to refer to real markets in software components. 2Market-Oriented Programming 2.1 General Equilibrium The walras framework is patterned directly after general-equilibrium theory. A brief expo- sition, glossing over many fine points, follows; for elaboration see any text on microeconomic theory {e.g., {Varian, 1984}). We start with k goods and n agents. Agentsfall in two general classes. Consumers can buy, sell, and consume goods, and their preferences for consuming various combinations or bundles ofgoods are specified by their utility function. If agent i is a consumer, then its utility function, u i : < k + ! <, ranks the various bundles of goods according to preference. Consumers may also start with an initial allocation of some goods, termed their endow- ment. Let e i;j denote agent i's endowment of good j, and x i;j the amount of good j thati ultimately consumes. The objective of consumer i is to choose a feasible bundle ofgoods, {x i;1 ; : : : ; x i;k } {rendered in vector notation as x i }, so as to maximize its utility. A bundle is feasible for consumer i if its total cost at the going prices does not exceed the value of i's endowment at these prices. The consumer's choice can be expressed as the following constrained optimization problem: max x i u i {x i } s.t. p 001 x i 024 p 001 e i ; {1} where p = {p 1 ; : : : ; p k } is the vector of prices for the k goods. Agents of the second type, producers, can transform some sorts of goods into some others, according to their technology. The technology specifies the feasible combinations of inputs and outputs for the producer. Let us consider the special case where there is one output good, indexed j, and the remaining goods are potential inputs. In that case, the technologyfor producer i can be described by a production function, y i =000x i;j = f i {x i;1 ; : : : ; x i;j0001 ; x i;j+1 ; : : : ; x i;k }; specifying the maximum output producible from the given inputs. {When a good is an input in its own production, the production function characterizes net output.} In this case, the producer's objective is to choose a production plan that maximizes profits subject to its technology and the going price of its output and input goods. This involves choosing a production level, y i , along with the levels of inputs that can produce y i at the minimum cost. Let x i;026 - and p 026 - denote the consumption and prices, respectively, of the input goods. Then thecorresponding constrained optimization problem is to maximize profits, the difference between revenues and costs: max y i 024 p j y i 000 024 min x i;026 - p 026 - 001 x i;026 - s.t. y i 024 f i {x i;026 - } 025025 ; or equivalently, min x i p 001 x i s.t. 000 x i;j 024 f i {x i;026 - }: {2} An agent acts competitively when it takes prices as given, neglecting any impact of its own behavior on prices. The above formulation implicitly assumes perfect competition, in that the prices are parameters of the agents' constrained optimization problems. Perfect competition realistically reflects individual rationality when there are numerous agents, each small with respect to the entire economy. Even when this is not the case, however, we can 3Wellman implement competitive behavior in individual agentsif we so choose. The implications of therestriction to perfect competition are discussed further below. A pair {p; x} of a price vector and vector of demands for each agent constitutes a competitive equilibrium for the economy if and only if: 1. For each agent i, x i is a solution to its constrained optimization problem|{1} or {2}|at prices p, and 2. the net amount of each good produced and consumed equals the total endowment, n X i=1 x i;j = n X i=1 e i;j ; for j = 1; : : :; k: {3} In other words, the total amount consumed equals the total amount produced {counted as negative quantities in the consumption bundles of producers}, plus the total amount the economy started out with {the endowments}. Under certain \classical" assumptions {essentially continuity, monotonicity, and concav- ity of the utility and production functions; see, e.g., {Hildenbrand & Kirman, 1976; Varian, 1984}), competitive equilibria exist, and are unique given strictness of these conditions. From the perspective of mechanism design, competitive equilibria possess several desirable properties, in particular, the two fundamental welfare theorems of general equilibrium the- ory: {1} all competitive equilibria are Pareto optimal {no agent can do better without some other doing worse}, and {2} any feasible Pareto optimum is a competitive equilibrium for some initial allocation of the endowments. These properties seem to offer exactly what we need: a bound on the quality of the solution, plus the prospect that we can achieve the most desired behavior by carefully engineering the configuration of the computational market. Moreover, in equilibrium, theprices reflect exactly the information required for distributed agents to optimally evaluate perturbations in their behavior without resorting to communication or reconsideration of their full set of possibilities {Koopmans, 1970}. 2.2 Computing Competitive Equilibria Competitive equilibria arealso computable, and algorithms based on fixed-point meth- ods {Scarf, 1984} and optimization techniques {Nagurney, 1993} have been developed. Both sorts of algorithms in effect operate by collecting and solving the simultaneous equilib- rium equations {1}, {2}, and {3}). Without an expressly distributed formulation, however, these techniques may violate the decentralization considerations underlying our distributed problem-solving context. This is quite acceptable for the purposes these algorithms were originallydesigned, namely to analyze existing decentralized structures, such as transporta- tion industries or even entire economies {Shoven & Whalley, 1992}. But because our purpose is to implement a distributed system, we must obey computational distributivityconstraints not relevant to the usual purposes of applied general-equilibrium analysis. In general, ex- plicitly examining the space of commodity bundle allocations in the search for equilibrium undercuts our original motive for decomposing complex activities into consumption and production of separate goods. 4Market-Oriented Programming Another important constraint is that internal details of the agents' state {such as utility or production functions and bidding policy} should be considered private in order to maxi- mize modularity and permit inclusion of agents not under the designers' direct control. A consequence of this is that computationally exploiting global properties arising from spe- cial features of agents would not generally be permissible for our purposes. For example, the constraint that profits be zero is a consequence of competitive behavior and constant- returns production technology. Since information about the form of the technology and bidding policy is private to producer agents, it could be considered cheating to embed the zero-profit condition into the equilibrium derivation procedure. Walras's procedure is a decentralized relaxation method, akin to the mechanism of tatonnement originally sketched by Leon Walras to explain how prices might be derived. Inthe basic tatonnement method, we begin with an initial vector of prices, p 0 . Theagents determine their demands at those prices {by solving their corresponding constrained op- timization problems}, and report the quantities demanded to the \auctioneer". Based on these reports, the auctioneer iteratively adjusts the prices up or down as there is an excess of demand or supply, respectively. For instance, an adjustment proportional to the excess could be modeled by the difference equation p t+1 = p t + ff{ n X i=1 x i 000 n X i=1 e i }: If the sequence p 0 ;p 1 ; : : : converges, then the excess demand in each market approaches zero, and the result is a competitive equilibrium. It is well known, however, that tatonnement processes do not converge to equilibrium in general {Scarf, 1984}. The class of economies in which tatonnement works are those with so-called stable equilibria {Hicks, 1948}. A sufficient condition for stability is gross substitutability {Arrow & Hurwicz, 1977}: that if the price for one good rises, then the net demands for the other goods do not decrease. Intuitively, gross substitutability will be violated when there are complementarities in preferences or technologies such that reduced consumption for one good will cause reduced consumption in others as well {Samuelson, 1974}. 2.3 WALRAS Bidding Protocol The method employed by walras successively computes an equilibrium price in each sep- arate market, in a manner detailed below. Like tatonnement, it involves an iterative ad- justment of prices based on reactions of the agents in the market. However, it differs from traditional tatonnement procedures in that {1} agents submit supply and demand curves rather than single point quantities for a particular price, and {2} the auction adjusts in- dividual prices to clear, rather than adjusting the entire price vector by some increment {usually a function of summary statistics such as excess demand}. 2 Walras associates an auction with each distinct good. Agents act in the market by submitting bids toauctions. Inwalras, bids specify a correspondence between prices and2. Thisgeneral approach is called progressiveequilibration by Dafermos and Nagurney {1989}, who applied it to a particular transportation network equilibrium problem. Although this model of market dynamics does not appear to have been investigated very extensively in general-equilibrium theory, it does seem to match the kind of price adjustment process envisioned by Hicks in his pioneering study of dynamics and stability {Hicks, 1948}. 5Wellman quantities of the good that the agent offers to demand or supply. The bid for a particular good corresponds to one dimension of the agent's optimal demand, which is parametrized by the prices for all relevant goods. Let x i {p} be the solution to equation {1} or {2}, as appropriate, for prices p. A walras agent bids for good j under the assumption that prices for the remaining goods are fixed at their current values, p 026 - . Formally, agent i's bid for good j is a function x i;j :< + ! <, from prices to quantities satisfying x i;j {p j } = x i {p j ; p 026 - } j ; where the subscript j on the right-hand side selects the quantity demanded of good j from the overall demand vector. Theagent computes and sends this function {encoded in any of a variety of formats} to the auction for good j. Given bids from all interested agents, the auction derives a market-clearing price, at which the quantity demanded balances that supplied, within some prespecified tolerance. This clearing price is simply the zero crossing of the aggregate demand function, which is the sum of the demands from all agents. Sucha zero crossing will exist as long as the aggregate demand is sufficiently well-behaved, in particular, if it is continuous and decreasing in price. Gross substitutability, along with the classical conditions for existence of equilibrium, is sufficientto ensure the existence of a clearing price at any stage of the bidding protocol. Walras calculates the zero crossing of the aggregate demand function via binary search. If aggregate demand is not well-behaved, the result of the auction may be a non-clearing price. When the current price is clearing with respect to the current bids, we say the market for that commodity is in equilibrium. We say that an agent is in equilibrium if its set of outstanding bids corresponds to the solution of its optimization problem at the going prices. If all the agents and commodity markets are in equilibrium, the allocation of goods dictated by the auction results is a competitive equilibrium. Figure 1 presents a schematic view of the walras bidding process. There is an auction for each distinct good, and for each agent, a link to all auctions in which it has an interest. There is also a \tote board" of current prices, kept up-to-date by the various auctions. In the current implementation the tote board is a global data structure, however, since price changenotifications are explicitly transmitted to interested agents, this central information could be easily dispensed with. Each agent maintains an agenda of bid tasks, specifying the markets in which it must update its bid or compute a new one. In Figure 1, agent A i has pending tasks to submit bids to auctions G 1 , G 7 , and G 4 . The bidding process is highly distributed, in that each agent need communicate directly only with the auctions for the goods of interest {those in the domain of its utility or production function, or for which it has nonzero endowments}. Each of these interactions concerns only a single good; auctions never coordinate with each other. Agentsneed not negotiate directly with other agents, nor even know of each other's existence. As new bids are received at auction, the previously computed clearing price becomes obsolete. Periodically, each auction computes a new clearing price {if any new or updated bids have been received} and posts it on the tote board. When a price is updated, this may invalidate some of an agent's outstanding bids, since these were computed under the assumption that prices for remaining goods were fixed at previous values. On finding out 6Market-Oriented Programming %ERROR: msave/mrestore stack underflow: Offending command 'mrestore'%ERROR: msave/mrestore stack overflow: Offending command 'msave'_Times-RomanG_Times-Roman1_Times-RomanG_Times-Roman2_Times-RomanG_Times-Romank_Times-RomanA_Times-Roman1_Times-RomanA_Times-Roman2_Times-RomanA_Times-Romani_Times-RomanA_Times-Romann_Times-ItalicTask Agenda_Times-Roman[1], [7], [4]_Times-Romanp_Times-Roman1_Times-Romanp_Times-Roman2_Times-Romanp_Times-Romank_Times-Italictote board_Times-Roman}_Times-Roman}Figure 1: Walras's bidding process. G j denotesthe auction for the jth good, and A i the ith trading agent. An item [j] on the task agenda denotes a pending task to compute and submit a bid for good j. about a price change, an agent augments its task agenda to include the potentially affected bids. At all times, walras maintains a vector of going prices and quantities that would be exchanged at those prices. While the agents have nonempty bid agendas or the auctions new bids, some or all goods may be in disequilibrium. When all auctions clear and all agendas are exhausted, however, the economy is in competitive equilibrium {up to some numeric tolerance}. Using a recent result of Milgrom and Roberts {1991, Theorem 12}, it can be shown that the condition sufficient for convergence of tatonnement|gross substitutability| is also sufficient for convergence of walras's price-adjustment process. The key observation is that in progressive equilibration {synchronous or not} the price at each time is based on some set of previous supply and demand bids. Although I have no precise results to this effect, the computational effort required for convergence to a fixed tolerance seems highly sensitive to the number of goods, and much less so to the number of agents. Eydeland and Nagurney {1989} have analyzed in detail the convergence pattern of progressive equilibration algorithms related to walras for par- ticular special cases, and found roughly linear growth in the number of agents. However, general conclusions are difficult to draw as the cost of computing the equilibrium fora par- ticular computational economy may well depend on the interconnectedness and strength of interactions among agents and goods. 2.4 Market-Oriented Programming As described above, walras provides facilities for specifying marketconfigurations and computing their competitive equilibrium. We can also view walras as a programming environment for decentralized resource allocation procedures. The environment provides constructs for specifying various sorts of agents and defining their interactions via their 7Wellman relations to common commodities. After setting up the initial configuration, the market can be run to determine the equilibrium level of activities and distribution of resources throughout the economy. To cast a distributed planning problem as a market, one needs to identify {1} the goods traded, {2} the agents trading, and {3} the agents' bidding behavior. These design steps areserially dependent, as the definition of what constitutes an exchangeable or producible commodity severely restricts the type of agents that it makes sense to include. And as mentioned above, sometimes we have to take as fixed some real-world agents and goods presented as part of the problem specification. Once the configuration is determined, it might be advantageous to adjust some general parameters of the bidding protocol. Below, I illustrate the design task with a walras formulation of the multicommodity flow problem. 2.5 Implementation Walras is implemented in Common Lisp and the Common Lisp Object System {CLOS}. The current version provides basic infrastructure for running computational economies, including the underlying bidding protocol and a library of CLOS classes implementing a varietyof agent types. The object-oriented implementation supports incremental develop- ment of market configurations. In particular, new types of agents can often be defined as slight variations on existing types, for example by modifying isolated features of the demand behavior, bidding strategies{e.g., management of task agenda}, or bid format. Wang and Slagle {1993} present a detailed case for the use of object-oriented languages to represent general-equilibrium models. Their proposed system is similar to walras with respect to formulation, although it is designed as an interface to conventional model-solving packages, rather than to support a decentralized computation of equilibrium directly. Although it models a distributed system, walras runs serially on a single processor. Distribution constraints on information and communication are enforced by programming and specification conventions rather than by fundamental mechanisms of the software en- vironment. Asynchrony is simulated by randomizing the bidding sequences so that agents are called on unpredictably. Indeed, artificial synchronization can lead to an undesirable oscillation in the clearing prices, as agents collectively overcompensate for imbalances in the preceding iteration. 3 The current experimental system runs transportation models of the sort described be- low, as well as some abstract exchange and production economies with parametrized utility and production functions {including the expository examples of Scarf {1984} and Shoven and Whalley {1984}). Customized tuning of the basic bidding protocol has not been nec- essary. In the process of getting walras to run on these examples, I have added some generically useful building blocks to the class libraries, but much more is required to fill out a comprehensive taxonomy of agents, bidding strategies, and auction policies.3. In some formal dynamic models {Huberman, 1988; Kephart, Hogg, & Huberman, 1989}, homogeneous agents choose instantaneously optimal policies without accounting for others that are simultaneously makingthe same choice. Since the value of a particular choice varies inversely with the number of agents choosing it, this delayed feedback about the others' decisions leads to systematic errors, and hence oscillation. I have also observed this phenomenon empirically in a synchronized version of WALRAS. By eliminating the synchronization, agents tend to work on different markets at any one time, and hence do not suffer as much from delayed feedback about prices. 8Market-Oriented Programming 3. Example: Multicommodity Flow In a simple version of the multicommodity flow problem, the task is to allocate a given set of cargo movements over a given transportation network. The transportation network is a collection of locations, with links {directed edges} identifying feasible transportation operations. Associated with each link is a specification of the cost of moving cargo along it. We suppose further that the cargo is homogeneous, and that amounts of cargo are arbitrarily divisible. A movement requirement associates an amount of cargo with an origin-destination pair. The planning problem is to determine the amount to transport on each link in order to move all the cargo at the minimum cost. This simplification ignores salient aspects of real transportation planning. For instance, this model is completely atemporal, and is hence more suitable for planning steady-state flows than for planning dynamic movements. A distributed version of the problem would decentralize the responsibility for trans- porting separate cargo elements. For example, planning modules corresponding to geo- graphically or organizationally disparate units might arrange the transportation for cargo within their respective spheres of authority. Or decision-making activity might be decom- posed along hierarchical levels of abstraction, gross functional characteristics, or according to any other relevant distinction. This decentralization might result from real distribution of authority within a human organization, from inherent informational asymmetries and communication barriers, or from modularity imposed to facilitate software engineering. Consider, for example, the abstract transportation network of Figure 2, taken from Harker {1988}. There are four locations, with directed links as shown. Consider two move- ment requirements. The first is to transport cargo from location 1 to location 4, and the second in the reverse direction. Suppose we wish to decentralize authority so that separate agents {called shippers} decide how to allocate the cargo for each movement. The first ship- per decides how to split its cargo units between the paths 1 ! 2 ! 4 and 1 ! 2 ! 3 ! 4, while the second figures the split between paths 4 ! 2 ! 1 and 4 ! 2 ! 3 ! 1. Note that the latter paths for each shipper share a common resource: thelink 2 ! 3.%ERROR: msave/mrestore stack underflow: Offending command 'mrestore'%ERROR: msave/mrestore stack overflow: Offending command 'msave'_Times-Roman1_Times-Roman2_Times-Roman4_Times-Roman3Figure 2: A simple network {from Harker {1988}). Because of their overlapping resource demands, the shippers' decisions appear to be necessarily intertwined. In a congested network, for example, the cost for transporting a unit of cargo over a link is increasing in the overall usage of the link. A shipper planning its cargo movements as if it were the only user on a network would thus underestimate its costs and potentially misallocate transportation resources. 9Wellman For the analysis of networks such as this, transportation researchers have developed equilibrium concepts describing the collective behavior of the shippers. In a system equi- librium, the overall transportation of cargo proceeds as if there were an omniscient central planner directing the movement of each shipment so as to minimize the total aggregate cost of meeting the requirements. In a user equilibrium, the overall allocation of cargo movements is such that each shipper minimizes its own total cost, sharing proportionately the cost of shared resources. The system equilibrium is thus a global optimum, while the userequilibrium corresponds to a composition of locally optimal solutions to subproblems. There are also some intermediate possibilities, corresponding to game-theoretic equilibrium concepts such as the Nash equilibrium, where each shipper behaves optimally given the transportation policies of the remaining shippers {Harker, 1986}. 4 From our perspective as designer of the distributed planner, we seek a decentralization mechanism that will reach the system equilibrium, or come as close as possible given the distributed decision-making structure. In general, however, we cannot expect to derive a system equilibrium orglobally optimal solution without central control. Limits on coordi- nation and communication may prevent the distributed resource allocation from exploiting all opportunities and inhibiting agentsfrom acting at cross purposes. But under certain conditionsdecision making can indeed be decentralized effectively via market mechanisms. General-equilibrium analysis can help us to recognize and take advantage of these opportu- nities. Note that for the multicommodity flow problem, there is an effective distributed solution due to Gallager {1977}. One of the market structures described below effectively mimics this solution, even though Gallager's algorithm was not formulated expressly in market terms. The point here is not to crack a hitherto unsolved distributed optimization problem {though that would be nice}, but rather to illustrate a general approach on a simply described yet nontrivial task. 4. WALRAS Transportation Market In this section, I present a series of three transportation market structures implemented in walras. The first and simplest model comprises the basic transportation goods and shipper agents, which are augmented in the succeeding models to include other agent types. Com- parative analysis of the three market structures reveals the qualitatively distinct economic and computational behaviors realized by alternate walras configurations. 4.1 Basic Shipper Model The resource of primary interest in the multicommodity flow problem is movement of cargo. Because the value and cost of a cargo movement depends on location, we designate as a distinct good the capacity on each origin-destination pair in the network {see Figure 2}. To capture the cost or input required to move cargo, we define another good denoting generic transportation resources. In a more concrete model, these might consist of vehicles, fuel, labor,or other factors contributing to transportation.4. In the Nash solution, shippers correctly anticipate the effect of their own cargo movements on the average cost on each link. The resulting equilibrium converges to the user equilibrium as the number of shippers increases and the effect of any individual's behavior on prices diminishes {Haurie & Marcotte, 1985}. 10Market-Oriented Programming To decentralize the decision making, we identify each movement requirement with a distinct shipper agent. These shippers, or consumers, have an interest in moving various units of cargo between specified origins and destinations. The interconnectedness of agents and goods defines the market configuration. Figure 3 depicts the walras configuration for the basic shipper model corresponding to the example network of Figure 2. In this model there are two shippers, S 1;4 and S 4;1 , where S i;j denotes a shipper with a requirement to move goods from origin i to destination j. Shippers connect to goods that might serve their objectives: in this case, movement along links that belong to some simple path from the shipper's origin to its destination. Inthe diagram, G i;j denotes the good representing an amount of cargo moved over the link i ! j. G 0 denotes the special transportation resource good. Notice that the only goods of interest to both shippers are G 0 , for which they both have endowments, and G 2;3 , transportation on the link serving both origin-destination pairs. G0G4,2G2,1G3,1S4,1G2,4G1,2S1,4G2,3G3,4Figure 3: Walras basic shipper market configuration for the example transportation net- work. The model we employ for transportation costs is based on a network with congestion, thus exhibiting diseconomies of scale. In other words, the marginal and average costs {in terms of transportation resources required} are both increasing in the level of service on a link. Using Harker's data, we take costs to be quadratic. The quadratic cost model is posed simply for concreteness, and does not represent any substantive claim about transportation networks. The important qualitative feature of this model {and the only one necessary for the example to work} is that it exhibits decreasing returns, a defining characteristic of congested networks. Note also that Harker's model is in terms of monetary costs, whereas we introduce an abstract input good. Let c i;j {x} denote the cost in transportation resources {good G 0 } required to transport x units of cargo on the link from i to j. The complete cost functions are: c 1;2 {x}= c 2;1 {x} = c 2;4 {x} = c 4;2 {x} = x 2 + 20x; c 3;1 {x} = c 2;3 {x} = c 3;4 {x} = 2x 2 + 5x: Finally, each shipper's objective is to transport 10 units of cargo from its origin to its destination. 11Wellman In the basic shipper model, we assume that the shippers pay proportionately {in units of G 0 } for the total cost on each link. This amounts to a policy of average cost pricing. We take the shipper's objective to be to ship as much as possible {up to its movement requirement} in the least costly manner. Notice that this objective is not expressible in termsof the consumer's optimization problem, equation {1}, and hence this model is not technically an instance of the general-equilibrium framework. Given a network with prices on each link, the cheapest cargo movement corresponds to the shortest path in the graph, where distances are equated with prices. Thus, for a given link, a shipper would prefer to ship its entire quota on the link if it is on the shortest path, and zero otherwise. In the case of ties, it is indifferent among the possible allocations. To bid on link i; j, the shipper can derive the threshold price that determines whether the link is on a shortest path by taking the difference in shortest-path distance between the networks where link i; j's distance is set to zero and infinity, respectively. In incrementally changing its bids, the shipper should also consider its outstanding bids and the current prices. The value of reserving capacity on a particular link is zero if it cannot get service on the other links on the path. Similarly, if it is already committed to shipping cargo on a parallel path, it does not gain by obtaining more capacity {even at a lower price} until it withdraws these other bids. 5 Therefore, the actual demand policy of ashipper is to spend its uncommitted income on the potential flow increase {derived from maximum-flow calculations} it could obtain by purchasing capacity on the given link. It is willing to spend up to the threshold value of the link, as described above. This determines one point on its demand curve. If it has some unsatisfied requirement and uncommitted income it also indicates a willingness to pay a lower price for a greater amount of capacity. Boundary points such as this serve to bootstrap the economy; from the initial conditions it is typically the case that no individual link contributes to overall flow between the shipper's origin and destination. Finally, the demand curve is completed by a smoothing operation on these points. Details of the boundary points and smoothing operation are rather arbitrary, and I make no claim that this particular bidding policy is ideal or guaranteed to work for a broad class of problems. This crude approach appears sufficient for the present example and some similar ones, as long as the shippers' policies become more accurate as the prices approach equilibrium. Walras successfully computes the competitive equilibrium for this example, which in the case of the basic shipper model corresponds to a user equilibrium {UE}for the transportation network. In the UE for the example network, each shipper sends 2.86 units of cargo over the shared link 2 ! 3, and the remaining cargo over the direct link from location 2 to the destination. This allocation is inefficient, as its total cost is 1143 resource5. Evenif a shipper could simultaneously update its bids in all markets, it would not be a good idea to do so here. A competitive shipper would send all its cargo on the least costly path, neglecting the possibility that this demand may increase the prices so that it is no longer cheapest. The outstanding bids provide some sensitivity to this effect, as they are functions of price. But they cannot respond to changes in many prices at once, and thus the policy of updating all bids simultaneously can lead to perpetual oscillation. For example, in the network considered here, the unique competitive equilibrium has each shipper splitting its cargo between two different paths. Policiesallocating all cargo to one path can never lead to this result, and hence convergence to competitive equilibrium depends on the incrementality of bidding behavior. 12Market-Oriented Programming units, which is somewhat greater than the global minimum-cost solution of 1136 units. In economic terms, the cause of the inefficiency is an externality with respect to usage of the shared link. Because the shippers are effectively charged average cost|which in the case of decreasing returns is below marginal cost|the price they face does not reflect the full incremental social cost of additional usage of the resource. In effect, incremental usage of the resource by one agent is subsidized by the other. The steeper the decreasing returns, the more the agents have an incentive to overutilize the resource. 6 This is a simple example of the classic tragedy of the commons. The classical remedy to such problems is to internalize the externality by allocating ownership of the shared resource to some decision maker who has the proper incentives to use it efficiently. We can implement such a solution in walras by augmenting the market structure with another type of agent. 4.2 Carrier Agents We extend the basic shipper model by introducing carriers, agents of type producer who have the capability to transport cargo units over specified links, given varying amounts of transportation resources. In the model described here, we associate one carrier with each available link. The production function for each carrier is simply the inverse of the cost function described above. To achieve a global movement of cargo, shippers obtain transportation services from carriers in exchange for the necessary transportation resources. Let C i;j denote the carrier that transports cargo from location i to location j. Each carrier C i;j is connected to the auction for G i;j , its output good, along with G 0 |its input in the production process. Shipper agents are also connected to G 0 , as they are endowed with transportation resources to exchange for transportation services. Figure 4 depicts the walras market structure when carriers are included in the economy. C1,2G0CG4,24,2G2,1G3,1S4,1C3,1C2,3G2,4G1,2S1,4C3,4G2,3C2,1G3,4C2,4Figure 4: Walras market configuration for the example transportation network in an econ- omy with shippers and carriers.6. Average-cost pricing is perhaps the most common mechanism for allocating costs of a shared resource. Shenker {1991} points out problems with this scheme|with respect to both efficiency and strategic behavior|in thecontext of allocating access to congested computer networks, a problem analogous to our transportation task. 13Wellman In the case of a decreasing returns technology, the producer's {carrier's} optimization problem has a unique solution. The optimal level of activity maximizes revenues minus costs, which occurs at the point where the output price equals marginal cost. Using this result, carriers submit supply bids specifying transportationservices as a function of link prices {with resource price fixed}, and demand bids specifying required resources as a function of input prices {for activity level computed with output price fixed}. For example, consider carrier C 1;2 . At output price p 1;2 and input price p 0 , the carrier's profit is p 1;2 y 000 p 0 c 1;2 {y}; where y is the level of service it chooses to supply. Given the cost function above, this expression is maximized at y = {p 1;2 000 20p 0 }=2p 0 . Taking p 0 as fixed, the carrier submits a supply bid with y a function of p 1;2 . On the demand side, the carrier takes p 1;2 as fixed and submits a demand bid for enough good G 0 to produce y, where y is treated as a function of p 0 . With the revised configuration and agent behaviors described, walras derives the sys- tem equilibrium {SE}, that is, the cargo allocation minimizing overall transportation costs. The derived cargo movements are correct to within 10045 in 36 bidding cycles, and to 1045 in 72, where in each cycle every agent submits an average of one bid to one auction. The total cost {in units of G 0 }, its division between shippers' expenditures and carriers' profits, and the equilibrium prices are presented in Table 1. Data for the UE solution of the ba- sic shipper model are included forcomparison. That the decentralized process produces a global optimum is perfectly consistent with competitive behavior|the carriers price their outputs at marginal cost, and the technologies are convex. pricingTC expense profitp 1;2 p 2;1 p 2;3 p 2;4 p 3;1 p 3;4 p 4;2MC {SE}1136 1514 37840.0 35.7 22.1 35.7 13.6 13.6 40.0 AC {UE}1143 1143 030.0 27.1 16.3 27.1 10.7 10.7 30.0 Table 1: Equilibria derived by walras for the transportation example. TC, MC, and AC stand for total, marginal, and average cost, respectively. TC = shipper expense 000 carrier profit. As a simple check on the prices of Table 1, we can verify that p 2;3 + p 3;4 = p 2;4 and p 2;3 + p 3;1 = p 2;1 . Both these relationships must hold in equilibrium {assuming all links have nonzero movements}, else a shipper could reduce its cost by rerouting some cargo. Indeed, for a simple {small and symmetric} example such as this, it is easy to derive the equilibrium analytically using global equations such as these. But as argued above, it would be improper to exploit these relationships in the implementation of a truly distributed decision process. The lesson from this exercise is that we can achieve qualitatively distinct results by sim- ple variations in the market configuration or agent policies. From our designers' perspective, we prefer the configuration that leads to the more transportation-efficient SE. Examination ofTable 1 reveals that we can achieve this result by allowing the carriers to earn nonzero profits {economically speaking, these are really rents on the fixed factor represented by the 14Market-Oriented Programming congested channel} and redistributing these profits to the shippers to cover their increased expenditures. {In the model of general equilibrium withproduction, consumers own shares in the producers' profits. This closes the loop so that all value is ultimately realized in consumption. We can specify these shares as part of the initial configuration, just like the endowment.} In this example, we distribute the profits evenly between the two shippers. 4.3 Arbitrageur Agents The preceding results demonstrate that walras can indeed implement a decentralized solution to the multicommodity flow problem. Butthe market structure in Figure 4 is not as distributed as it might be, in that {1} all agents are connected to G 0 , and {2} shippers need to know about all links potentially serving their origin-destination pair. The first of these concerns is easily remedied, as the choice of a single transportation resource good was completely arbitrary. For example, it would be straightforward to consider some collection of resources {e.g., fuel, labor, vehicles}, and endow each shipper with only subsets of these. The second concern can also be addressed within walras. To do so, we introduce yet another sort of producer agent. These new agents, called arbitrageurs, act as specialized middlemen, monitoringisolated pieces of the network for inefficiencies. An arbitrageur A i;j;k produces transportation from i to k by buying capacity from i to j and j to k. Its production function simply specifies that the amount of its output good, G i;k , is equal to the minimum of its two inputs, G i;j and G j;k . If p i;j + p j;k < p i;k , then its production is profitable. Its bidding policy in walras is to increment its level of activity at each iteration by an amount proportional to its current profitability {or decrement proportional to the loss}. Such incremental behavior is necessary for all constant-returns producers in walras, as the profit maximization problem has no interior solution in the linear case. 7 To incorporate arbitrageurs into the transportation market structure, we first create new goods corresponding to the transitive closure of the transportation network. In the example network, this leads to goods for every location pair. Next, we add an arbitrageur A i;j;k for every triple of locations such that {1} i ! j is in the original network, and {2} there exists a path from j tok that does not traverse location i. These two conditions ensure that there is an arbitrageur A i;j;k for every pair i; k connected by a path with more than one link, and eliminate some combinations that are either redundant or clearly unprofitable. The revised market structure for the running example is depicted in Figure 5, with new goods and agents shaded. Some goods and agents that are inactive in the market solution have been omitted from the diagram to avoid clutter. Notice that in Figure 5 the connectivity of the shippers has been significantly decreased, as the shippers now need be aware of only the good directly serving their origin-destination pair. This dramatically simplifies their bidding problem, as they can avoid all analysis of the price network. The structure as a whole seems more distributed, as no agent is concerned with more than three goods.7. Without such a restriction on its bidding behavior, the competitive constant-returns producer would choose to operate at a level of infinity or zero, depending on whether its activity were profitable or unprofitable at the going prices {at break-even, the producer is indifferent among all levels}. This would lead to perpetual oscillation, a problem noticed {and solved} by Paul Samuelson in 1949 when he considered the use of market mechanisms to solve linear programming problems {Samuelson, 1966}. 15Wellman G0C2,3G2,3C1,2G2,4G1,23,4G3,41,2,4AS1,4CC2,4A2,3,4G1,4A2,3,1CCCSGGGAG2,13,14,24,12,13,14,24,2,14,1Figure 5: The revised walras market configuration with arbitrageurs. Despite the simplified shipper behavior, walras still converges to the SE, or optimal solution, in this configuration. Although the resulting allocation of resources is identical, a qualitative change in market structure here corresponds to a qualitative change in the degreeof decentralization. In fact, the behavior of walras on the market configuration with arbitrageurs is vir- tually identical to a standard distributed algorithm {Gallager, 1977} for multicommodity flow {minimum delay on communication networks}. In Gallager's algorithm, distributed modules expressly differentiate the cost function to derive the marginal cost of increasing flow on a communication link. Flows are adjusted up or down so to equate the marginal costs along competing subpaths. This procedure provably converges to the optimal solution as long as the iterative adjustment parameter is sufficiently small. Similarly, convergence in walras for this model requires that the arbitrageurs do not adjust their activity levels too quickly in response to profit opportunities or loss situations. 4.4 Summary The preceding sections have developed three progressively elaborate market configurations for the multicommodity flow problem. Table 2 summarizes the size and shape of the con- figuration for a transportation network with V locations and E links, and M movement requirements. The basic shipper model results in the user equilibrium, while both of the augmentedmodels produce the globally optimal system equilibrium. The carrier model re- quires E new producer agents to produce the superior result. The arbitrageur model adds O{V E} more producers and potentially some new goods as well, but reduces the number of goods of interest to any individual agent from O{E} to a small constant. These market models represent three qualitatively distinct points on the spectrum of potential configurations. Hybrid models are also conceivable, forexample, where a partial set of arbitrageurs are included, perhaps arranged in a hierarchy or some other regular 16Market-Oriented Programming modelgoods shippers carriers arbitrageursBasic shipperE + 1 M [O{E}] - - : : : plus carriersE+ 1 M [O{E}] E [2] - : : : plus arbitrageursO{V 2 } M [2] E [2] O{V E} [3] Table 2: Numbers of goods and agents for the three market configurations. For each type of agent, the figure in brackets indicates the number of goods on which each individual bids. structure. I would expect such configurations to exhibit behaviors intermediate to the specific models studied here, with respect to both equilibrium produced and degree of decentralization. 5. Limitations One serious limitation of walras is the assumption that agents act competitively. As mentioned above, this behavior is rational when there are many agents, each small with respect to the overall economy. However, when an individual agent is large enough to affect prices significantly {i.e., possesses market power}, it forfeits utility or profits by failing to take this into account. There are two approaches toward alleviating the restriction of perfect competition in a computational economy. First, we could simply adopt models of imperfect competition, perhaps based on specific forms of imperfection {e.g., spatial monopolistic competition}or on general game-theoretic models. Second, as architects we can configure the markets to promote competitive behavior. For example, decreasing the agent's grain size and enabling free entry of agents should enhance the degree of competition. Perhaps most interestingly, by controlling the agents' knowledge of the market structure {via standard information-encapsulation techniques}, we can degrade their ability to exploit whatever market power they possess. Uncertainty has been shown to increase competitiveness among risk-averse agents in some formal bidding models {McAfee & McMillan, 1987}, and in a computationalenvironment we have substantial control over this uncertainty. The existence of competitive equilibria and efficient market allocations also depends critically on the assumption of nonincreasing returns to scale. Although congestion is a real factor in transportation networks, for example, for many modes of transport there are often other economies of scale and density that may lead to returns that are increasing overall{Harker, 1987}. Note that strategic interactions, increasing returns, and other factors degrading the effectiveness of market mechanisms also inhibit decentralization in general, and so would need to be addressed directly in any approach. Having cast walras as a general environment for distributed planning, it is natural to askhow universal \market-oriented programming" is as a computational paradigm. We can characterize the computational power of this model easily enough, by correspondence to the class of convex programming problems represented by economies satisfying the classical con- ditions. However, the more interesting issue is how well the conceptual framework of market 17Wellman equilibrium corresponds to the salient features of distributed planning problems. Although itis too early to make a definitive assertion about this, it seems clear that many planning tasks are fundamentally problems in resource allocation, and that the units of distribution often correspond well with units of agency. Economics has been the most prominent {and arguably the most successful} approach to modeling resource allocation with decentralized decision making, and it is reasonable to suppose that the concepts economists find useful in the social context will prove similarly useful in our analogous computational context. Of course, just as economics is not ideal for analyzing all aspects of social interaction, we should expect that many issues in the organization of distributed planning will not be well accounted-for in this framework. Finally, the transportation network model presented here is a highly simplified ver- sion of the actual planning problem for this domain. A more realistic treatment would cover multiple commodity types, discrete movements, temporal extent, hierarchical net- work structure, and other critical features of the problem. Some of these may be captured by incremental extensions to the simple model, perhaps applying elaborations developed by the transportation science community. For example, many transportation models {in- cluding Harker's more elaborate formulation {Harker, 1987}) allow for variable supply and demand of the commodities and more complex shipper-carrier relationships. Concepts of spatial price equilibrium, based on markets for commodities in each location, seem to offer the most direct approach toward extending the transportation model within walras. 6. Related Work 6.1 Distributed Optimization The techniques and models described here obviously build on much work in economics, transportation science, and operations research. The intended research contribution here is not to these fields, but rather in their application to the construction of a computational framework for decentralized decision making in general. Nevertheless, a few words are in order regarding the relation of the approach described here to extant methods for distributed optimization. Although the most elaborate walras model is essentially equivalent to existing algo- rithms for distributed multicommodity flow {Bertsekas & Tsitsiklis, 1989; Gallager, 1977}, the market framework offers an approach toward extensions beyond the strict scope of this particular optimization problem. For example, we could reduce the number of arbitrageurs, and while this would eliminate the guarantees of optimality, we might still have a reasonable expectation for graceful degradation. Similarly, we could realize conceptual extensions to thestructure of the problem, such as distributed production of goods in addition to trans- portation, by adding new types of agents. For any given extension, there may very well be a customized distributed optimization algorithm that would outperform the computational market, but coming up with this algorithm would likely involve a completely new analysis. Nevertheless, it must be stated that speculations regarding the methodological advantages of the market-oriented framework are indeed just speculations at this point, and the relative flexibility of applications programming in this paradigm must ultimately be demonstrated empirically. 18Market-Oriented Programming Finally, there is a large literature on decomposition methods for mathematical program- ming problems, which is perhaps the most common approach to distributed optimization. Manyof these techniques can themselves be interpreted in economic terms, using the close relationship between prices and Lagrange multipliers. Again, the main distinction of the approach advocated here is conceptual. Rather than taking a global optimization prob- lem and decentralizing it, our aim is to provide a framework for formulating a task in a distributed manner in the first place. 6.2 Market-Based Computation The basic idea of applying economic mechanisms to coordinate distributed problem solving is not new to the AI community. Starting with the contract net {Davis & Smith, 1983}, many have found the metaphor of markets appealing, and have built systems organized around markets or market-like mechanisms {Malone, Fikes, Grant, & Howard, 1988}. The original contract net actually did not include anyeconomic notions at all in its bidding mechanism, however, recent work by Sandholm {1993} has shown how cost and price can be incorporated in the contract net protocol to make it more like a true market mecha- nism. Miller and Drexler {Drexler & Miller, 1988; Miller & Drexler, 1988} have examined the market-based approach in depth, presenting some underlying rationale and addressing specific issues salient in a computational environment. Waldspurger, Hogg, Huberman, Kephart, and Stornetta {1992} investigated the concepts further by actually implementing market mechanisms to allocate computational resources in a distributed operating system. Researchers in distributed computing {Kurose & Simha, 1989} have also applied specialized algorithms based on economic analyses to specific resource-allocation problems arising in distributed systems. Forfurther remarks on this line of work, see {Wellman, 1991}. Recently, Kuwabaraand Ishida {1992} have experimented with demand adjustment methods for a task very similar to the multicommodity flow problem considered here. One significant difference is that their method would consider each path in the network as a separate resource, whereas the market structures here manipulate only links or location pairs. Although they do not cast their system in a competitive-equilibrium framework,the results are congruent with those obtained by walras. Walras is distinct from these prior efforts in two primary respects. First, it is con- structed expressly in terms of concepts from general equilibrium theory, to promote math- ematical analysis of the system and facilitate the application of economic principles to architectural design. Second, walras is designed to serve as a general programming envi- ronment for implementing computational economies. Although not developed specifically to allocate computational resources, there is no reason these could not be included in mar- ket structures configured for particular application domains. Indeed,the idea of grounding measures of the value of computation in real-world values {e.g., cargo movements} follows naturally from the general-equilibrium view of interconnected markets, and is one of the more exciting prospects for future applications of walras to distributed problem-solving. Organizational theorists have studied markets as mechanisms for coordinating activities and allocating resources within firms. For example, Malone {1987} models information requirements, flexibility and other performance characteristics of a variety of market and non-market structures. In his terminology, walras implements a centralized market, where 19Wellman the allocation of each good is mediated by an auction. Using such models, we can determine whether this gross form of organization is advantageous, given information about the cost of communication, the flexibility of individual modules, and other related features. In this paper, we examine in greater detail the coordination process in computational markets, elaboratingon the criteria for designing decentralized allocation mechanisms. We take the distributivity constraint as exogenously imposed; when the constraint is relaxable, both organizational and economic analysis illuminate the tradeoffs underlying the mechanism designproblem. Finally, market-orientedprogramming shares with Shoham's agent-oriented program- ming {Shoham,1993} the view that distributed problem-solving modules are best designed and understood as rational agents. Thetwo approaches support different agent operations {transactions versus speech acts}, adopt different rationality criteria, and emphasize dif- ferent agent descriptors, but are ultimately aimed at achieving the same goal of specifying complex behavior in terms of agent concepts {e.g., belief, desire, capability} and social orga- nizations. Combining individual rationality with laws of social interaction provides perhaps the most natural approach to generalizing Newell's \knowledge level analysis" idea {Newell, 1982} to distributed computation. 7. Conclusion In summary, walras represents a general approach to the construction and analysis of distributed planning systems, based on general equilibrium theory and competitive mech- anisms. The approach works by deriving the competitive equilibrium corresponding to a particular configuration of agents and commodities, specified using walras's basic con- structs for defining computational market structures. In a particular realization of this approach for a simplified form of distributed transportation planning, we see that qualita- tive differences in economic structure {e.g., cost-sharing among shippers versus ownership of shared resources by profit-maximizing carriers} correspond to qualitatively distinct be- haviors{user versus system equilibrium}. This exercise demonstrates that careful design of the distributed decision structure according to economic principles can sometimes lead to effective decentralization, and that the behaviors of alternative systems can be meaningfully analyzed in economic terms. The contribution of the work reported here lies in the idea of market-oriented program- ming, an algorithm for distributed computation of competitive equilibria of computational economies, and an initial illustration of the approach on a simple problem in distributed resource allocation. A great deal of additional work will be required to understand the pre- cise capabilities and limitations of the approach, and to establish a broader methodology for configuration of computational economies. Acknowledgements This paper is a revised and extended version of {Wellman, 1992}. I have benefited from discussions of computational economies with many colleagues, and would like to thank in particular Jon Doyle, Ed Durfee, Eli Gafni, Daphne Koller, Tracy Mullen, Anna Nagurney, 20Market-Oriented Programming Scott Shenker, Yoav Shoham, Hal Varian, Carl Waldspurger, Martin Weitzman, and the anonymousreviewers for helpful comments and suggestions. References Arrow, K. J., & Hurwicz, L. {Eds.}. {1977}. Studies in Resource Allocation Processes. Cambridge University Press, Cambridge. Bertsekas, D. P., & Tsitsiklis, J. N. {1989}. Parallel and Distributed Computation. Prentice- Hall, Englewood Cliffs, NJ. Dafermos, S., & Nagurney, A. {1989}. Supply and demand equilibration algorithms for a class of market equilibrium problems. Transportation Science, 23, 118{124. Davis, R., & Smith, R. G. {1983}. Negotiation as a metaphor for distributed problem solving. ArtificialIntelligence,20, 63{109. Drexler, K. E., & Miller, M. S. {1988}. Incentive engineering for computational resource management. InHuberman {1988}, pp. 231{266. Eydeland, A., & Nagurney, A. {1989}. Progressive equilibration algorithms: The case of linear transaction costs. Computer Science in Economics and Management, 2, 197{ 219. Gallager,R. G. {1977}. A minimum delay routing algorithm using distributed computation. IEEE Transactions on Communications, 25, 73{85. Harker, P. T. {1986}. Alternative models of spatial competition. Operations Research, 34, 410{425. Harker, P. T. {1987}. Predicting Intercity Freight Flows. VNU Science Press, Utrecht, The Netherlands. Harker, P. T. {1988}. Multiple equilibrium behaviors on networks. Transportation Science, 22, 39{46. Haurie, A., & Marcotte, P. {1985}. On the relationship between Nash-Cournot and Wardrop equilibria. Networks, 15, 295{308. Hicks, J. R. {1948}. Value and Capital {second edition}. Oxford University Press, London. Hildenbrand, W.,& Kirman, A. P. {1976}. Introduction to Equilibrium Analysis: Vari- ations on Themes by Edgeworth and Walras. North-Holland Publishing Company, Amsterdam. Huberman, B. A. {Ed.}. {1988}. The Ecology of Computation. North-Holland. Hurwicz, L. {1977}. The design of resource allocation mechanisms. InArrow and Hurwicz {1977}, pp. 3{37. Reprinted from American Economic Review Papers and Proceedings, 1973. 21Wellman Kephart, J. O., Hogg, T., & Huberman, B. A. {1989}. Dynamicsof computational ecosys- tems. PhysicalReview A, 40, 404{421. Koopmans, T. C. {1970}. Uses of prices. InScientific Papers of Tjalling C. Koopmans, pp. 243{257. Springer-Verlag. Originally published in the Proceedings of the Conference on Operations Research in Production and Inventory Control, 1954. Kurose, J. F., & Simha, R. {1989}. A microeconomic approach to optimal resource allocation in distributed computer systems. IEEETransactions on Computers, 38, 705{717. Kuwabara, K., & Ishida, T. {1992}. Symbiotic approach to distributed resource allocation: Toward coordinated balancing. In Pre-Proceedings of the 4th European Workshop on Modeling Autonomous Agents in a Multi-Agent World. Lavoie, D., Baetjer, H., & Tulloh, W.{1991}. Coping with complexity: OOPS and the economists' critique of central planning. Hotline on Object-Oriented Technology, 3 {1}, 6{8. Malone, T. W., Fikes, R. E., Grant, K. R., & Howard, M. T. {1988}. Enterprise: A market- like task scheduler for distributed computing environments. In Huberman {1988}, pp. 177{205. Malone, T. W. {1987}. Modeling coordination in organizations and markets. Management Science, 33, 1317{1332. McAfee, R. P., & McMillan, J. {1987}. Auctions and bidding. Journalof Economic Litera- ture, 25, 699{738. Milgrom, P., & Roberts, J. {1991}. Adaptive and sophisticated learning in normal form games. Games and Economic Behavior, 3, 82{100. Miller, M. S., & Drexler, K. E. {1988}. Markets and computation: Agoric open systems. In Huberman {1988}, pp. 133{176. Nagurney, A. {1993}. Network Economics: A Variational Inequality Approach. Kluwer Academic Publishers. Newell, A. {1982}. The knowledge level. Artificial Intelligence,18, 87{127. Reiter, S. {1986}. Information incentive and performance in the {new} 2 welfare economics. In Reiter, S. {Ed.}, Studies in Mathematical Economics. MAA Studies in Mathematics. Samuelson, P. A. {1966}. Market mechanisms and maximization. In Stiglitz, J. E. {Ed.}, The Collected Scientific Papers of Paul A. Samuelson, Vol. 1, pp. 415{492. MIT Press, Cambridge, MA. Originally appeared in RAND research memoranda, 1949. Samuelson, P. A. {1974}. Complementarity: An essay on the 40th anniversary of the Hicks- Allen revolution in demand theory. Journalof Economic Literature, 12, 1255{1289. 22Market-Oriented Programming Sandholm, T. {1993}. An implementation of the contract net protocol based on marginal costcalculations. InProceedings of the National Conference on Artificial Intelligence, pp. 256{262 Washington, DC. AAAI. Scarf, H. E. {1984}. The computation of equilibrium prices. InScarf, H. E., & Shoven, J. B. {Eds.}, Applied General Equilibrium Analysis,pp. 1{49. Cambridge University Press, Cambridge. Shenker, S. {1991}. Congestion control in computer networks: An exercise in cost-sharing. Prepared for delivery at Annual Meeting of the American Political Science Association. Shoham, Y. {1993}. Agent-oriented programming. Artificial Intelligence,60, 51{92. Shoven, J. B., & Whalley, J. {1984}. Applied general-equilibrium models of taxation and international trade: Anintroduction and survey. Journal of Economic Literature, 22, 1007{1051. Shoven, J. B., & Whalley, J. {1992}. Applying General Equilibrium. Cambridge University Press. Varian, H. R. {1984}. Microeconomic Analysis {second edition}. W. W. Norton & Company, New York. Waldspurger, C. A., Hogg, T., Huberman, B. A., Kephart, J. O., & Stornetta, S. {1992}. Spawn: A distributed computational economy. IEEE Transactions on Software En- gineering, 18, 103{117. Wang,Z., & Slagle, J. {1993}. An object-oriented knowledge-based approach for formulating applied general equilibrium models. In Third International Workshop on Artificial Intelligence in Economics and Management Portland, OR. Wellman, M. P. {1991}. Review of Huberman {1988}. Artificial Intelligence, 52, 205{218. Wellman, M. P. {1992}. A general-equilibrium approach to distributed transportation plan- ning. In Proceedings of the National Conference on Artificial Intelligence, pp. 282{289 San Jose, CA. AAAI. 23