Computational Social Dilemmas

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

Natalie S. Glance and Tad Hogg, Computational Social Dilemmas,
Xerox PARC Technical Report, 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 over-using 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. Thus, this is 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. We further argue that inefficiencies arising from public good problems will occur commonly in computational societies of agents that choose among strategies based on utilities that depend upon the choices of other agents. Finally, we suggest borrowing several constructs from human societies to avoid common good problems in computational ones, such as taxation, privatization, and the establishment of norms.
Keywords: Braess' Paradox, distributed systems, common goods
postcript (377K)