Dilemmas in Computational Societies

Natalie S. Glance and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com

@INPROCEEDINGS {,
 AUTHOR = "Natalie S. Glance and Tad Hogg",
 TITLE = "Dilemmas in Computational Societies",
 BOOKTITLE = "Proc. of the 1st International Conference on Multi-Agent Systems (ICMAS95)",
 EDITOR = "V, Lesser",
 PAGES = "117-124",
 PUBLISHER = "AAAI Press",
 ADDRESS = "Menlo Park, CA",
 MONTH = "June",
 YEAR = "1995"}

Abstract

World-wide interlinked computer networks are forming the foundation for computational societies of software agents. Already, these new societies have encountered problems endemic to human communities, such as overusing common resources with thrashing over virtual memory and competition by packets for network time. Unlike with human societies, these inefficiencies can be overcome by re-working the algorithms governing the protocols. However, the public good problem, in which a common good is available to all regardless of contribution, can arise computationally in more subtle ways. We discuss how this can happen using Braess' Paradox and demonstrate that adding resources to a computational system can counterintuitively lower the overall performance. This is thus a case in which distributed algorithms are provably unable to achieve globally optimal performance. We illustrate our claim using a genetic algorithm and computational ecosystem.
postcript (351K, available on-line only within Xerox)

topic areas

conceptual and theoretical foundations of multiagent systems cooperation, coordination, and conflict