Characterizing Contract-Based Multiagent Resource Allocation in Networks

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.