摘要翻译：
考虑了多Agent系统中效用最大化Agent的效用函数设计问题，使它们协同工作以最大化全局效用。我们研究的特定问题领域是通过在网络中的所有路由器上放置代理来控制网络路由。传统的解决方法都是采用理想最短路径路由算法(ISPA)。我们证明了在许多情况下，由于一个Agent的行为对另一个Agent的性能的副作用，使Agent使用ISPA就全局总成本而言是次优的，即使它们只用于路由极小数量的通信量。直观地说，单个代理的效用函数并不与全局效用“对齐”。作为一个特殊的例子，我们给出了一个Braess悖论的例子，在这个悖论中，向一个代理都使用ISPA的网络添加新的链路会导致总吞吐量的下降。我们还证明了负载平衡是次优的，在负载平衡中，代理集体做出决策以优化当前路由的所有通信量所引起的全局代价，就跨时间的全局平均代价而言，负载平衡是次优的。这也是由于“副作用”，在这种情况下，当前的路由决定对未来的流量。集体智能数学(COIN)精确地关注在多智能体系统中避免这种有害的副作用的问题，无论是在时间上还是在空间上。我们从数学中提出了关键概念，并用它们导出了一个算法，其理想版本应该比所有代理都使用ISPA的算法具有更好的性能，即使在无穷小极限下也是如此。我们给出了验证这一点的实验，也表明这种硬币算法的基于机器学习的版本，其中成本仅通过经验方法进行不精确的估计（一个可能在现实世界中适用的版本），尽管获得的信息比ISPA少，但它的性能也优于ISPA。特别是，这种硬币算法几乎总是避免了Braess悖论。
---
英文标题：
《Collective Intelligence, Data Routing and Braess' Paradox》
---
作者：
K. Tumer, D. H. Wolpert
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1106.1821