Dilemmas in Computational Societies

Natalie S. Glance and 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 reworking 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.