Dilemmas in Computational Societies
Nathalie Glance, Tad Hogg
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
contribtuion, can arise computationally in more subtle ways. We discuss how this can happen using
Braess' Paradox and demonstrate that adding resources to a compuational 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 a computational ecosystem.
Proceedings of ICMAS'95, 1995
dilemmas.pdf (331.38 kB)