Multiagent task allocation in social networks

M. de Weerdt, Yingqian Zhang, T.B. Klos

Research output: Contribution to journalArticleAcademicpeer-review

60 Citations (Scopus)
114 Downloads (Pure)


This paper proposes 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 remains NP-complete. Moreover, it is not approximable within some factor. In contrast to this, 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. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated.
Original languageEnglish
Pages (from-to)46-86
JournalAutonomous Agents and Multi-Agent Systems
Issue number1
Publication statusPublished - 2012


Dive into the research topics of 'Multiagent task allocation in social networks'. Together they form a unique fingerprint.

Cite this