Collective Intelligence, Data Routing and Braess' Paradox
  We consider the problem of designing the the utility functions of the
utility-maximizing agents in a multi-agent system so that they work
synergistically to maximize a global utility. The particular problem domain we
explore is the control of network routing by placing agents on all the routers
in the network. Conventional approaches to this task have the agents all use
the Ideal Shortest Path routing Algorithm (ISPA). We demonstrate that in many
cases, due to the side-effects of one agent's actions on another agent's
performance, having agents use ISPA's is suboptimal as far as global aggregate
cost is concerned, even when they are only used to route infinitesimally small
amounts of traffic. The utility functions of the individual agents are not
"aligned" with the global utility, intuitively speaking. As a particular
example of this we present an instance of Braess' paradox in which adding new
links to a network whose agents all use the ISPA results in a decrease in
overall throughput. We also demonstrate that load-balancing, in which the
agents' decisions are collectively made to optimize the global cost incurred by
all traffic currently being routed, is suboptimal as far as global cost
averaged across time is concerned. This is also due to 'side-effects', in this
case of current routing decision on future traffic. The mathematics of
Collective Intelligence (COIN) is concerned precisely with the issue of
avoiding such deleterious side-effects in multi-agent systems, both over time
and space. We present key concepts from that mathematics and use them to derive
an algorithm whose ideal version should have better performance than that of
having all agents use the ISPA, even in the infinitesimal limit. We present
experiments verifying this, and also showing that a machine-learning-based
version of this COIN algorithm in which costs are only imprecisely estimated
via empirical means (a version potentially applicable in the real world) also
outperforms the ISPA, despite having access to less information than does the
ISPA. In particular, this COIN algorithm almost always avoids Braess' paradox.
