Skip to main content
SpringerLink
Log in

An Empirical Approach to a Theory of Coordination. Part I: Design Principles and First Results

  • Published:
Computational & Mathematical Organization Theory Aims and scope Submit manuscript

Abstract

Coordination is understood to consist of a set of mechanisms necessary for the effective operation of Intelligent Agent Societies (IASs). In building such societies, it is important to design and implement coordination in accordance with the known requirements and anticipated working conditions of the IAS in question. Currently, there is little theoretical support that could help in this process. We outline the approach and design principles of our work on automatically generating an empirically-based theory of coordination. We also describe the first set of results obtained, which prove the feasibility of the approach.

We are concerned with Distributed Problem Solving (DPS) systems in which all agents share an identical goal structure and fully collaborate, as opposed to Multi-Agent Systems (MAS) in which agents may also compete with one another. Our investigation is based on an easily modifiable and parametrizable generic IAS, the P-system, a metaphorical and abstract version of our earlier work, the Distributed Control of Nationwide Manufacturing Operations. The P-system shares characteristic properties with most, if not all, IASs. It was used for a sequence of rigorously designed experiments in which control variables operated under well-defined conditions and performance measures were observed. We infer, from the statistical analysis of these data, characteristic and important descriptors of the organization and functioning of IASs in general. The resulting relations should produce insight into the fundamental issues of coordination, provide design tools and guidelines for the construction of new IASs, and lend support in trouble-shooting existing ones.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Axelrod, R. (1984), The Evolution of Cooperation. Basic Books, New York, NY.

    Google Scholar 

  • Axelrod, R. (1987), “The Evolution of Strategies in the Iterated Prisoner's Dilemma, ” in L. Davis (Ed.) Genetic Algorithms and Simulated Annealing. Morgan Kaufmann, Los Altos, CA, Ch. 3, pp. 32–41.

    Google Scholar 

  • Axelrod, R. and W. Hamilton (1981), “The Evolution of Cooperation, ” Science, 211/1390–1396.

  • Bankes, S. (1994), “Exploring the Foundations of Artificial Societies: Experiments in Evolving Solutions to Iterated n-Player Prisoner's Dilemma, ” in Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems. Cambridge, MA, pp. 337–342.

  • Carley, K. (1994), “Sociology-Computational Organization Theory, ” Social Science Computer Review, 12, 611–624.

    Google Scholar 

  • Carley, K., J. Kjaer-Hansen, A. Newell and M. Prietula (1992), “Plural-SOAR:AProlegomenon to Artificial Agents and Organizational Behavior, ” in M. Masuch and M. Warglien (Eds.) Artificial Intelligence in Organization and Management Theory. North-Holland, Amsterdam, Ch. 4, pp. 87–118.

    Google Scholar 

  • Carley, K. and M.J. Prietula (1994), “ACTS Theory: Extending the Model of Bounded Rationality, ” in K. Carley and M.J. Prietula (Eds.) Computational Organizational Theory. Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 55–87.

    Google Scholar 

  • Crowston, K. (1992), “Modeling Coordination in Organizations, ” in M. Masuch and M. Warglien (Eds.) Artificial Intelligence in Organization and Management Theory. North-Holland, Amsterdam, Ch. 9, pp. 215–234.

    Google Scholar 

  • Crowston, K. (1994), “A Taxonomy of Organizational Dependencies and Coordination Mechanisms, ” CCS Working Paper 174, Center for Coordination Science, Massachusetts Institute of Technology.

  • Crowston, K. (1994), “Evolving Novel Organizational Forms, ” in K. Carley and M.J. Prietula (Eds.) Computational Organizational Theory. Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 19–38.

    Google Scholar 

  • Decker, K.S. (1995a), “Environment-Centered Analysis and Design of Coordination Mechanisms, ” Ph.D. Dissertation, University of Massachusetts at Amherst, Department of Computer Science.

    Google Scholar 

  • Decker, K.S. (1995b), “T'EAMS: A Framework for Analysis and Design of Coordination Mechanisms, ” in G. O'Hare and N. Jennings (Eds.) Foundations of Distributed Artificial Intelligence. Wiley Interscience.

  • Decker, K.S. (1998), “Task Environment Centered Simulation, ” in M. Prietula, K. Carley and L. Gasser (Eds.) Simulating Organizations: Computational Models of Institutions and Groups. AAAI Press, Menlo Park, CA.

    Google Scholar 

  • Decker, K.S., E.H. Durfee and V.R. Lesser (1989), “Evaluating Research in Cooperative Distributed Problem Solving, ” in L. Gasser and M.N. Huhns (Eds.) Distributed Artificial Intelligence. Morgan Kaufmann Publishers, San Mateo, CA, Vol. 2, Ch. 19, pp. 485–519.

    Google Scholar 

  • Decker, K.S. and V.R. Lesser (1993), “Quantitative Modeling of Complex Computational Task Environments, ” in Proceedings of the Eleventh National Conference on Artificial Intelligence. Washington, DC, pp. 217–224

  • Decker, K.S. and V.R. Lesser (1995), “Designing a Family of Coordination Mechanisms, ” in Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), pp. 73–80.

  • Durfee, E.H. and T.A. Montgomery (1991), “Coordination as Distributed Search in a Hierarchical Behavior Space, ” IEEE Trans. on Systems, Man, and Cybernetics, SMC-21, 1363–1378.

    Google Scholar 

  • Findler, N.V. (1989), “Distributed Knowledge-Based Systems in Manufacturing, ” in G. Rzevski (Ed.) Artificial Intelligence in Manufacturing. Springer-Verlag, New York, pp. 17–33.

    Google Scholar 

  • Findler, N.V. (1993), “A Knowledge-Based Approach to Urban Traffic Control, ” in Proceedings of the Conference on Applications of Artificial Intelligence in Engineering. Toulouse, Vol. 2, pp. 235–248.

    Google Scholar 

  • Findler, N.V. (1999), “Harmonization for Omnidirectional Progression in Urban Traffic Control, ” Computer-Aided Civil and Infrastructure Engineering, 14, 369–377.

    Google Scholar 

  • Findler, N.V. and G.D. Elder (1994), “Multi-Agent Coordination and Cooperation in a Dynamic Environment with Limited Resources, ” Artificial Intelligence in Engineering, 9, 229–238.

    Google Scholar 

  • Findler, N.V. and J. Gao (1987), “Dynamic Hierarchical Control for Distributed Problem Solving, ” Data and Knowledge Engineering, 2, 285–301.

    Google Scholar 

  • Findler, N.V. and Q. Ge (1989), “Perceiving and Planning Before Acting-An Approach to Enhance Global Network Coherence, ” International Journal of Intelligent Systems, 4, 459–470.

    Google Scholar 

  • Findler, N.V. and Q. Ge (1994), “Distributed Goal-Directed Dynamic Plan Revision, ” International Journal of Intelligent Systems, 9, 183–210.

    Google Scholar 

  • Findler, N.V. and R. Lo (1986), “An Examination of Distributed Planning in the World of Air Traffic Control, ” Journal of Parallel and Distributed Processing, 3, 411–431.

    Google Scholar 

  • Findler, N.V. and R. Lo (1993a), “Empirical Studies on Distributed Planning for Air Traffic Control. Part I: A Dynamic Hierarchical Structure for Concurrent Distributed Control and the Location-Centered Cooperative Planning System, ” Journal of Transportation Engineering, 119, 681–692.

    Google Scholar 

  • Findler, N.V. and R. Lo (1993b), “Empirical Studies on Distributed Planning for Air Traffic Control. Part II: Experimental Results, ” Journal of Transportation Engineering, 119, 693–704.

    Google Scholar 

  • Findler, N.V. and R.M. Malyankar (1994), “Procedure-Oriented Studies of Collective Phenomena in Multi-Agent Systems, ” in Proceedings of the 1994 IEEE Conference on Systems, Man, and Cybernetics. San Antonio, TX, pp. 97–102.

  • Findler, N.V. and R.M. Malyankar (1995), “Emergent Behavior in Societies of Heterogeneous, Interacting Agents: Alliances and Norms, ” in R. Conte and N. Gilbert (Eds.) Artificial Societies: The Computer Simulation of Social Life. University College (London) Press, London, UK, Ch. 11, pp. 212–237.

    Google Scholar 

  • Findler, N.V. and R.M. Malyankar (2000), “Social Structures and the Problem of Coordination in Intelligent Agent Societies, ” in Special Session on Agent-Based Simulation, Planning and Control in IMACS World Congress 2000. Lausanne, Switzerland.

  • Findler, N.V. and U.K. Sengupta (1993), “On Some Innovative Concepts in Distributed Systems For Planning and Collaboration, ” in Proceedings of the Operational Research Society, 35th Annual Conference. University of York, UK, pp. 79–93.

    Google Scholar 

  • Findler, N.V. and U.K. Sengupta (1994), “Multi-Agent Collaboration in Time-Constrained Domains, ” Artificial Intelligence in Engineering, 9, 39–52.

    Google Scholar 

  • Findler, N.V., S. Surender and S. Catrava (1997), “A note Concerning On-Line Decisions About Permitted/ Protected Left-Turn Phases, ” Engineering Applications of Artificial Intelligence, 10, 315–320.

    Google Scholar 

  • Findler, N.V., S. Surender, Z. Ma and S. Catrava (1997), “A Distributed Knowledge-Based System for Reactive and Predictive Control of Street Traffic Signals: A Macroscopic Model in the Steady-State Domain, ” Engineering Applications of Artificial Intelligence, 10, 281–292.

    Google Scholar 

  • Finin, T., Y. Labrou and J. Mayfield (1977), “KQML as an Agent Communication Language, ” in J. Bradshaw (Ed.) Software Agents. MIT Press, Cambridge, MA.

    Google Scholar 

  • Gasser, L. (1992), “DAI Approaches to Coordination, ” in N.M. Avouris and L. Gasser, (Eds.) Distributed Artificial Intelligence: Theory and Praxis. Kluwer, Boston, MA, pp. 31–51.

    Google Scholar 

  • Glance, N.S. and B.A. Huberman (1993), “The Outbreak of Cooperation, ” Journal of Mathematical Sociology, 17(4), 281–302.

    Google Scholar 

  • Harsanyi J.C. (1977), Rational Behavior and Bargaining Equilibrium in Games and Social Situations. Cambridge University Press, Cambridge, UK.

    Google Scholar 

  • Hogg, T. and B.A. Huberman (1991), “Controlling Chaos in Distributed Systems, ” IEEE Transactions on Systems, Man and Cybernetics, 21(6), 1325–1332.

    Google Scholar 

  • Huberman, B.A. and N. Glance (1993a), “Diversity and Collective Action, ” in H. Haken and A. Mikhailov (Eds.) Interdisciplinary Approaches to Nonlinear Systems. Springer, Berlin/Heidelberg.

    Google Scholar 

  • Huberman, B.A. and N. Glance (1993b), “Evolutionary Games and Computer Simulation, ” Proceedings of the National Academy of Sciences (USA), Vol. 90, No. 16, pp. 7715–7718.

    Google Scholar 

  • Huberman, B.A. and T. Hogg (1988), “The Behavior of Computational Ecologies, ” in B.A. Huberman (Ed.) The Ecology of Computation. Elsevier Science Publishers B.V., Amsterdam, pp. 77–115.

    Google Scholar 

  • Jennings, N.R. (1993a), “Commitments and Conventions: The Foundation of Coordination in Multi-Agent Systems, ” Knowledge Engineering Review, 8, 223–250.

    Google Scholar 

  • Jennings, N.R. (1993b), “Controlling Cooperative Problem Solving in Industrial Multi-Agent Systems Using Joint Intentions, ” Artificial Intelligence, 75, 195–240.

    Google Scholar 

  • Kephart, J.O., T. Hogg and B.A. Huberman (1989), “Dynamics of Computational Ecosystems: Implications for DAI, ” in L. Gasser and M. N. Huhns (Eds.) Distributed Artificial Intelligence. Morgan Kaufmann, Publishers, San Mateo, CA, Vol. 2, Ch. 4, pp. 79–95.

    Google Scholar 

  • Kephart, J.O., T. Hogg and B.A. Huberman (1990), “Collective Behavior of Predictive Agents, ” Physica D, 42(1–3), 48–65.

    Google Scholar 

  • Malone, T.W. (1987), “Modeling Coordination in Organizations and Markets, ” Management Science, 33(10), 1317–1332.

    Google Scholar 

  • Malone, T.W. (1992), “Analogies Between Human Organizations and Artificial Intelligence Systems: Two Examples and Some Reflections, ” in M. Masuch and M. Warglien (Eds.) Artificial Intelligence in Organization and Management Theory. North-Holland, Amsterdam, Ch. 1, pp. 21–40.

    Google Scholar 

  • Malone, T.W. and K. Crowston (1994), “The Interdisciplinary Study of Coordination, ” ACM Computing Surveys, 26(1):87–119.

    Google Scholar 

  • Malyankar, R.M. (1993), “Emergent Behavior in Societies of Intelligent Agents: Alliances and Norms” Ph.D. Dissertation, Department of Computer Science and Engineering, Arizona State University.

  • Malyankar, R.M. and N.V. Findler (1995), “Agent Modelling in Distributed Intelligent Systems, ” Systems Analysis-Modelling-Simulation, 22, 53–74.

    Google Scholar 

  • Malyankar, R.M. and N.V. Findler (1998), “A Methodology for Modeling Coordination in Intelligent Agent Societies, ” Computational and Mathematical Organization Theory, 4, 317–345.

    Google Scholar 

  • Malyankar, R.M., N.V. Findler and P.S. Heck (1998), “The Effects of Satisficing Models on Coordination, ” in Satisficing Models: Papers from the 1998 AAAI Spring Symposium, TR SS–98–05, AAAI Press, Palo Alto, CA, pp. 39–45.

    Google Scholar 

  • Nagendra Prasad, M.V. and V. Lesser (1997), “The Use of Meta-Level Information in Learning Situation-Specific Coordination, ” in Proceedings of the International Joint Conference on Artificial Intelligence. Nagoya, Japan, pp. 640–646.

  • Oliphant, M. (1994), “Evolving Cooperation in the Non-Iterated Prisoner's Dilemma: The Importance of Spatial Organization, ” in Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems. Cambridge, MA, pp. 349–352.

  • Parker, G.R. and S.L. Parker (1985), Factions in House Committees. University of Tennessee Press, Knoxville, TN.

    Google Scholar 

  • Pollack, M.E. (1992), “The Uses of Plans, ” Artificial Intelligence, 57, 43–68.

    Google Scholar 

  • Rapoport, A. (1966), Two-Person Game Theory: The Essential Ideas. University of Michigan Press, Ann Arbor, MI.

    Google Scholar 

  • Rapoport, A. (1970), N-Person Game Theory: Concepts and Applications. University of Michigan Press, Ann Arbor, MI.

    Google Scholar 

  • Rasmusen, E. (1994), Games and Information: An Introduction to Game Theory. Blackwell, Oxford, UK.

    Google Scholar 

  • Rosenschein, J.S. and M. Genesereth (1988), “Deals Among Rational Agents, ” in B.A. Huberman (Ed.) The Ecology of Computation. Elsevier Science Publishers B.V., Amsterdam, pp. 117–132.

    Google Scholar 

  • Rosenschein, J.S. and G. Zlotkin (1994), Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT Press, Cambridge, MA.

    Google Scholar 

  • Sandholm, T.W. (1999), “Distributed Rational Decision Making, ” in G. Weiss (Ed.) Multiagent Systems. MIT Press, Cambridge, MA, pp. 201–258.

    Google Scholar 

  • Sandholm, T.W. and V.R. Lesser (1997), “Coalition Formation Among Computationally Bounded Agents, ” Artificial Intelligence, 94, 99–137.

    Google Scholar 

  • Shoham, Y. and M. Tennenholt (1992), “On the Synthesis of Useful Social Laws for Artificial Agent Societies, ” in Proceedings of the Tenth National Conference on Artificial Intelligence. San Jose, CA, pp. 276–281.

  • Wilkinson, D. (1976), Cohesion and Conflict: Lessons from the Study of Three-Party Interaction. St. Martin's Press, New York, NY.

    Google Scholar 

  • Zlotkin, G. and J.S. Rosenschein (1990), “Negotiation and Conflict Resolution in Non-Cooperative Domains, ” in Proceedings of the Eighth National Conference on Artificial Intelligence. Boston, MA, pp. 100–105.

  • Zlotkin, G. and J.S. Rosenschein (1994), “Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task Oriented Domains, ” in Proceedings of the National Conference on Artificial Intelligence. Washington, DC, pp. 432–437.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Arizona State University;, Tempe, AZ, 85287-5406, USA

    Nicholas V. Findler & Raphael M. Malyankar

Authors
  1. Nicholas V. Findler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raphael M. Malyankar
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Findler, N.V., Malyankar, R.M. An Empirical Approach to a Theory of Coordination. Part I: Design Principles and First Results. Computational & Mathematical Organization Theory 6, 119–144 (2000). https://doi.org/10.1023/A:1009681418003

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009681418003

Search

Navigation