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"}
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)