The WALRAS Design Economy
A market-oriented programming approach to the distributed configuration design problem.
WALRAS formulation:
Configuration Design Problem
Roughly speaking, the configuration design problem is to select a set of parts to perform a set of specified functions, maximizing some criteria subject to feasibility constraints. The set of choices is defined by a collection of catalogs, which list the parts available to perform each function and specifies their features.
In the distributed version of the problem, we decentralize the decision making according to function, with separate design teams responsible for choosing a part to satisfy each function.
Goods
In the WALRAS formulation of the problem, we include two types of goods.
- Basic resource goods. These are resources required by the components in order to realize the desired performance, but are limited or costly or both. Generally, we desire to minimize our overall use of resources.
- Performance attributes, which measure the capabilities of the designed artifact, and which we typically desire to maximize.
Agents
- Producers: Catalog producers
- Consumer: The "end user" consumer
Catalog Producers
Each part in a catalog is associated with a vector of resource and performance goods. The resources can be interpreted as input goods, and the performance goods as output. In this view, the catalog producer is an agent that transforms resources to performance. Thus, to specify a catalog producerŐs technology, we simply form a set of the attribute-value tuples characterizing each part. We then go through and negate the values for the resource goods, leaving the values for performance goods intact.
Catalog agents submit bids reflecting their choice of parts maximizing profits (or no part, if all are unprofitable at the going prices).
The "End User" Consumer
The consumer agent in a design economy is conceptually the end user or customer for the overall design. The consumer is endowed with the basic resource goods. The idea is that the consumer then (effectively) sells these resources to the various catalog agents, in exchange for performance goods. Its utility function reflects the desire to maximize performance as well as to minimize resource usage.
The consumer agent bids to maximize utility subject to its budget constraint, in the conventional manner.
Results
We have run the design economy on several small problems, both real and contrived. In some cases, it produces an optimal or near-optimal design with a few iterations. In others, however, it fails to produce reasonable or even feasible designs at all. The problem is that non-convexities inherent in the discreteness of the catalog (or real economies of scale) mean that there is often no competitive equilibrium of the system (or no smooth path for the progressive equilibration method to find one).
Extensions
In ongoing and future work, we are extending the design economy in several ways:
- relax the competitiveness assumption for producers with increasing returns
- use the solution for a smoothed and convexified version of the problem as a bound or approximation to the actual solution
- combine market- and constraint-based methods in a hybrid search scheme
References
This work was first reported in the proceedings of AAAI-94. An extended version will be published in AI EDAM:
A computational market model for distributed configuration design. AI EDAM, to appear, 1995.
See the references in this paper for other related work.
Updated by Michael Wellman on 10/18/94