Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-04T18:14:38.979Z Has data issue: false hasContentIssue false

A computational market model for distributed configuration design

Published online by Cambridge University Press:  27 February 2009

Michael P. Wellman
Affiliation:
Al Laboratory, University of Michigan, 1101 Beal Avenue, Ann Arbor, MI 48109-2110, U.S.A.

Abstract

A precise market model for a well-defined class of distributed configuration design problems is presented. Given a design problem, the model defines a computational economy to allocate basic resources to agents participating in the design. The result of running these “design economies” constitutes the market solution to the original problem. After defining the configuration design framework, the mapping to computational economies and the results to date are described. For some simple examples, the system can produce good designs relatively quickly. However, analysis shows that the design economies are not guaranteed to find optimal designs, and some of the major pitfalls are identified and discussed. Despite known shortcomings and limited explorations thus far, the market model offers a useful conceptual viewpoint for analyzing distributed design problems.

Type
Articles
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Arrow, K.J., & Hurwicz, L., Eds. (1977). Studies in Resource Allocation Processes. Cambridge University Press, Cambridge, United Kingdom.CrossRefGoogle Scholar
Balkany, A., Birmingham, W.P., & Tommelein, I.D. (1993). An analysis of several configuration design systems. AI EDAM 7, 1–17.Google Scholar
Bertsekas, D.P., & Tsitsiklis, J.N. (1989). Parallel and distributed computation. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Bowen, J., & Bahler, D. (1993). Constraint-based software for concurrent engineering. Computer 26(1), 6668.CrossRefGoogle Scholar
Cheriton, D.R., & Harty, K. (1993). A market approach to operating system memory allocation. Technical Report. Department of Computer Science, Stanford University, Stanford, CA.Google Scholar
Clearwater, S., Ed. (1995). Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific.Google Scholar
Cutkosky, M.R., Englemore, R.S., Fikes, R.E. et al. , (1993). PACT: An experiment in integrating concurrent engineering systems. Computer 26(1), 2837.CrossRefGoogle Scholar
Darr, T.P., & Birmingham, W.P. (1994). Automated design for concurrent engineering. IEEE Expert 5(9), 3542.CrossRefGoogle Scholar
Davis, R., & Smith, R.G. (1983). Negotiation as as metaphor for distributed problem solving. Artif. Intell. 20, 63109.CrossRefGoogle Scholar
Drexler, K.E., & Miller, M.S. (1988). Incentive engineering for computational resource management. In The Ecology of Computation (Huberman, B.A., Ed.), pp. 231236. Elsevier, North-Holland.Google Scholar
Edmonds, E.A., Candy, L., Jones, R. et al. , (1994). Support for collaborative design: Agents and emergence. Commun. ACM 37(7), 4147.CrossRefGoogle Scholar
Etzioni, O., & Weld, D. (1994). A softbot-based interface to the internet. Commun. ACM 37(7), 7276.CrossRefGoogle Scholar
Genesereth, M.R., & Ketchpel, S.P. (1994). Software agents. Commun. ACM 37(7), 4853.CrossRefGoogle Scholar
Hildenbrand, W., Kirman, A.P. (1976). Introduction to Equilibrium Analysis: Variations on Themes by Edgeworth and Walras. North-Holland, Amsterdam.Google Scholar
Huberman, B.A., Ed. (1988). The Ecology of Computation. North-Holland, Amsterdam.Google Scholar
Koopmans, T.C. (1970). Uses of prices. In Scientific Papers of Tjalling C. Koopmans, pp. 243257. Springer-Verlag, New York.Google Scholar
Kurose, J.F., & Simha, R. (1989). A microeconomic approach to optimal resource allocation in distributed computer systems. IEEE Trans. Comput. 38, 705717.CrossRefGoogle Scholar
Milgrom, P., & Roberts, J. (1991). Adaptive and sophisticated learning in normal form games. Games and Economic Behavior 3, 82100.CrossRefGoogle Scholar
Miller, M.S., & Drexler, K.E. (1988). Markets and computation: Agoric open systems. In The Ecology of Computation (Huberman, B.A., Ed.), pp. 133176. North-Holland, Amsterdam.Google Scholar
Mittal, S., & Frayman, F. (1989). Towards a generic model of configuration tasks. Proc. Eleventh Int. Joint Conf. on Artificial Intelligence, Detroit, MI. Morgan Kaufmann, Palo Alto, CA.Google Scholar
Newell, A. (1982). The knowledge level. Artif. Intell. 18, 87127.CrossRefGoogle Scholar
Reddy, Y.V.R., Srinivas, K., Jagannathan, V. et al. , (1993). Computer support for concurrent engineering. Computer 26(1), 1216.Google Scholar
Sandholm, T. (1993). An implementation of the contract net protocol based on marginal cost calculations. Proc. Nat. Conf. on Artificial Intelligence. AAAI Press, Washington, DC.Google Scholar
Shoham, Y. (1993). Agent-oriented programming. Artif. Intell. 60, 5192.CrossRefGoogle Scholar
Shoven, J.B., & Whalley, J. (1992). Applying General Equilibrium. Cambridge University Press, Cambridge, United Kingdom.Google Scholar
Varian, H.R. (1984). Microeconomic Analysis. W.W. Norton, New York.Google Scholar
Waldspurger, C.A., Hogg, T., Huberman, B.A. et al. , (1992). Spawn: A distributed computational economy. IEEE Trans. Software Engrg. 18, 103117.CrossRefGoogle Scholar
Wellman, M.P. (1993). A market-oriented programming environment and its application to distributed multicommodity flow problems. J. Artif. Intell. Res. 1(1), 123.CrossRefGoogle Scholar
Wellman, M.P. (1995). Market-oriented programming: Some early lessons. In Market-Based Control: A Paradigm for Distributed Resource Allocation, (Clearwater, S., Ed.). World Scientific.Google Scholar
Wiederhold, G. (1992). Mediators in the architecture of future information systems. Computer 26(3), 3849.CrossRefGoogle Scholar