Multiagent Task Allocation in Social Networks
Speaker
Abstract
| We propose a new variant of the task allocation problem, where the agents are connected in a social network and tasks arrive at the agents distributed over the network. We show that the complexity of this problem is NP-complete, and we develop an efficient greedy algorithm for this problem. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a broad set of experiments to evaluate the performance and scalability of the proposed algorithm in terms of solution quality and computation time. |
| Three different types of networks, namely small-world, random and scale-free networks, are used to represent various social relationships among agents in realistic applications. The results demonstrate that our algorithm works well and also that it scales well to large-scale applications. In addition we consider the same problem in a setting where the agents holding the resources are self-interested. For this, we show how the optimal algorithm can be used to incentivize these agents to be truthful with a Vickrey-Clarke-Groves mechanism. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated. This talk is based on a paper published in the Journal of Autonomous Agents and Multi Agent Systems. |
| This is a joint work with Mathijs de Weerdt and Tomas Klos from TU Delft. |
| Contact information: |
| Dr. Wolf Ketter |
