An Bo, Lesser Victor
Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA.
IEEE Trans Syst Man Cybern B Cybern. 2010 Jun;40(3):575-86. doi: 10.1109/TSMCB.2009.2035100. Epub 2009 Dec 1.
We consider a multiagent resource allocation problem where individual users intend to route traffic by requesting the help of entities across a network, and a cost is incurred at each network node that depends on the amount of traffic to be routed. We propose to study contract-based network resource allocation. In our model, users and nodes in the network make contracts before nodes route traffic for the users. The problem is an interesting self-interested negotiation problem because it requires the complete assembly of a set of distinct resources, and there are multiple combinations of distinct resources that could satisfy the goal of negotiation. First, we characterize the network allocation problem and show that finding optimal allocations is NP-complete and is inapproximable. We take both Nash equilibrium and pairwise Nash equilibrium as the solution concepts to characterize the equilibrium allocations. We find that, for any resource allocation game, Nash equilibrium and pairwise Nash equilibrium always exist. In addition, socially optimal allocations are always supported by Nash equilibrium and pairwise Nash equilibrium. We introduce best-response dynamics in which each agent takes a myopic best-response strategy and interacts with each other to dynamically form contracts. We analyze the convergence of the dynamics in some special cases. We also experimentally study the convergence rate of the dynamics and how efficient the evolved allocation is as compared with the optimal allocation in a variety of environments.
我们考虑一个多智能体资源分配问题，其中各个用户打算通过请求网络中实体的帮助来路由流量，并且每个网络节点会产生取决于要路由的流量量的成本。我们提议研究基于合同的网络资源分配。在我们的模型中，网络中的用户和节点在节点为用户路由流量之前签订合同。这个问题是一个有趣的自利谈判问题，因为它需要完整地组装一组不同的资源，并且有多种不同资源的组合可以满足谈判目标。首先，我们对网络分配问题进行了刻画，表明找到最优分配是NP完全问题且不可近似。我们将纳什均衡和成对纳什均衡都作为刻画均衡分配的解概念。我们发现，对于任何资源分配博弈，纳什均衡和成对纳什均衡总是存在的。此外，社会最优分配总是由纳什均衡和成对纳什均衡支持。我们引入了最佳响应动态，其中每个智能体采取近视最佳响应策略并相互作用以动态形成合同。我们分析了在一些特殊情况下动态的收敛性。我们还通过实验研究了动态的收敛速度以及与各种环境中的最优分配相比，演化后的分配效率如何。
