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.
翻译:我们考虑在多试剂系统中设计工具最大化工具的效用功能,以便它们能协同地工作,最大限度地发挥全球效用。我们所探讨的特殊问题领域是将代理人安置在网络中的所有路由器上,从而控制网络路线。任务的传统方法使代理人都使用“理想最短路径 ” 路由Algorithm (ISPA) 。我们表明,在许多情况下,由于一个代理人的行为对另一个代理人的性能的副作用,使它们使用ISPA的算法,就全球总费用而言,它们不是最佳的,即使它们只是用来处理极小的交通量。 单个代理人的效用功能与全球效用并不“一致 ”, 直截然地说,作为一个例子,我们展示的是Braess CO的悖论,在网络上添加新的联系,因为ISPA的这个代理商只用来降低整个耗时的效能。 我们还表明,负荷平衡,对于全球总费用来说, 代理人的决定是集体作出的, 其核心性作用是最佳的,在目前平均运算中, 其成本是远远的。