Distributed Task Allocation in Social Networks

Conference paper (2007)
Department
Software Computer Technology (EEMCS) (TU Delft)
Copyright: © 2007 IFAAMAS
Social networks Task allocation Agents Resources Computational complexity
More Info
expand_more

Published Date

14-05-2007

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

AAMAS 2007: Proceedings of the 6th International Conference on Autonomous Agents and Multiagent Systems, Honolulu, Hawaii, 14-18 May 2007

ISBN:

978-81-904262-7-5

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Computer Technology

Abstract

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 NPhard. Moreover, it is not approximable within some factor. We develop an algorithm based on the contract-net protocol. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a 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 that it scales well to large-scale applications.

Files

DeWeerdt_2007.pdf
(pdf | 0.357 Mb)