Heterogeneity, Root-finding, and Decentralization

James D. Thomas and Katia Sycara
Artificial Societies and Computational Markets (ASCMA) Workshop at the Second International Conference on Autonomous Agents (AA '98), May, 1998.


Download
  • Adobe portable document format (pdf) (103KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Increasing interest in agent-based systems both in AI (in terms of multiagent systems and distributed artificial intelligence) and in computational approaches to the social sciences calls for a greater understanding of their computational properties. Often, problems that are difficult for agent-based systems because of issues of coordination or delayed information could be solved using a centralized root-finding algorthim. This paper proposes a method that allows for the approximation of such centralized root-finding solutions by systems of decentralized agents. By making each agent's responses to payoff signals heterogeneous, proper coordination emerges among the agents without the need for communication or negotiation. We apply this technique to both Newton's method and Gallager's algorithm for multi-commodity flow. In empirical simulations, the method is shown to produce results comparable to the original algorithm.

Notes
Sponsor: NSF IRI-9612131 and ONR N-00014-96-1-1222
Number of pages: 4

Text Reference
James D. Thomas and Katia Sycara, "Heterogeneity, Root-finding, and Decentralization," Artificial Societies and Computational Markets (ASCMA) Workshop at the Second International Conference on Autonomous Agents (AA '98), May, 1998.

BibTeX Reference
@inproceedings{Thomas_1998_2785,
   author = "James D Thomas and Katia Sycara",
   title = "Heterogeneity, Root-finding, and Decentralization",
   booktitle = "Artificial Societies and Computational Markets (ASCMA) Workshop at the Second International Conference on Autonomous Agents (AA '98)",
   month = "May",
   year = "1998",
}