Collective Intelligence and Braess' Paradox

Collective Intelligence and Braess' Paradox
To appear in AAAI 2000 in Austin, Tx (Postscript - 330 KB )

Abstract: We consider the use of multi-agent systems to control network routing. Conventional approaches to this task are based on Ideal Shortest Path routing Algorithm (ISPA), which in some cases can lead to large global cost. In particular, in a simulation of Braess' paradox we see that adding new capacity to a network with ISPA agents can decrease overall throughput. The theory of COllective INtelligence (COIN) design concerns precisely the issue of avoiding the side effects of ones action to harm a global utility. We show that COIN-based routing substantially improves performance and in particular avoids Braess' paradox.