Natalie S. Glance and Tad Hogg, Computational Social Dilemmas, Xerox PARC Technical Report, 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 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)