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 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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdallah, S., & Lesser, V. (2005). Modeling task allocation using a decision theoretic model. In Proceedings of the 4th international conference on autonomous agents and multiagent systems (AAMAS 2005) (pp. 719–726). New York: ACM.
Alon N., Feige U., Wigderson A., Zuckerman D. (1995) Derandomized Graph Products. Computational Complexity 5(1): 60–75
Andersson, M. R., & Sandholm, T. W. (1998). Contract types for satisficing task allocation: II experimental results. In AAAI spring symposium series: Satisficing models. California: Stanford University
van Assen M. A. L. M., de Rijt A. (2007) Dynamic exchange networks. Social Networks 29(2): 266–278
Babanov, A., & Gini, M. (2006). Deciding task schedules for temporal planning via auctions. In AAAI Spring Symposium.
Barabási A. L., Albert R. (1999) Emergence of scaling in random networks. Science 286(5439): 509–512
Barton, L., & Allan, V. H. (2007). Methods for coalition formation in adaptation-based social networks. In Cooperative information agents XI, LNAI (vol. 4676, pp. 285–297). Heidelberg: Springer.
Braun N., Gautschi T. (2006) A nash bargaining model for simple exchange networks. Social Networks 28(1): 1–23
Chakraborty, T., Kearns, M., & Khanna, S. (2009). Network bargaining: Algorithms and structural results. In Proceedings of the tenth ACM conference on electronic commerce (pp. 159–168).
Chevaleyre Y., Dunne P. E., Endriss U., Lang J., Lemaitre M., Maudet N., Padget J., Phelps S., Rodríguez-Aguilar J. A., Sousa P. (2006) Issues in multi-agent resource allocation. Informatica 30: 3–31
Chevaleyre, Y., Endriss, U., & Maudet, N. (2007). Allocating goods on a graph to eliminate envy. In Proceedings of the 22nd national conference on artificial intelligence (AAAI 2007) (pp. 700–705).
Coase R. H. (1937) The nature of the firm. Economica NS 4(16): 386–405
Coase R. H. (1995) My evolution as an economist. In: Breit W., Spencer R. W. (eds) Lives of the laureates. MIT Press, Cambridge, MA, pp 227–249
Dantzig G. (1957) Discrete variable problems. Operations Research 5: 266–277
Dias M. B., Zlot R. M., Kalra N., Stentz A. T. (2005) Market-based multirobot coordination: A survey and analysis. Technical report CMU-RI-TR-05-13. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA
Dunne P. E., Kraus S., Manisterski E., Wooldridge M. (2010) Solving coalitional resource games. Artificial Intelligence 174(1): 20–50
Easwaran A. M., Pitt J. (2002) Supply chain formation in open, market-based multi-agent systems. International Journal of Computational Intelligence and Applications 2(3): 349–363
Eberling, M., & Kleine Büning, H. (2010). Self-adaptation strategies to favor cooperation. In Agent and multi-agent systems: Technologies and Applications, LNAI (vol. 6070, pp. 223–232). New York: Springer.
Ferreira P., dos Santos F., Bazzan A., Epstein D., Waskow S. (2010) Robocup rescue as multiagent task allocation among teams: Experiments with task interdependencies. Autonomous Agents and Multi-Agent Systems 20: 421–443
Foster, I., Jennings, N. R., & Kesselman, C. (2004). Brain meets Brawn: why grid and agents need each other. In Proceedings of the 3rd international conference on autonomous agents and multiagent systems (AAMAS 2004) (pp. 8–15). Washington, DC: IEEE Computer Society.
Garey M. R., Johnson D. S. (1979) Computers and intractability—a guide to the theory of NP-completeness. W.H. Freeman and company, New York
Gaston, M. E., & DesJardins, M. (2005). Agent-organized networks for dynamic team formation. In Proceedings of the 4th interence confere on autonomous agents and multiagent systems (AAMAS 2005) (pp. 230–237). New York: ACM Press.
Gaston M. E., DesJardins M. (2008) The effect of network structure on dynamic team formation in multi-agent systems. Computational Intelligence 24(2): 122–157
Girvan M., Newman M. E. J. (2002) Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America 99(12): 7821–7826
Goldberg, D., Cicirello, V., Dias, M. B., Simmons, R., Smith, S., & Stentz, A. T. (2003). Market-based multi-robot planning in a distributed layered architecture. In Multi-robot systems: From swarms to intelligent automata: Proceedings from the 2003 international workshop on multi-robot systems (Vol. 2, pp. 27–38). Dordrecht: Kluwer Academic Publishers.
Groves T. (1973) Incentives in teams. Econometrica 41(4): 617–631
Gulati R. (1995) Does familiarity breed trust? The implications of repeated ties for contractual choice in alliances. Academy of Management Journal 38(1): 85–112
Heydenreich B., Muller R., Uetz M. (2007) Games and mechanism design in machine scheduling—an introduction. Production and Operations Management 16(4): 437–454
Hirayama K., Yokoo M., Sycara K. (2004) An easy-hard-easy cost profile in distributed constraint satisfaction. Transactions of the Information Processing Society of Japan 45(9): 2217–2225
Kafalı, Ö., & Yolum, P. (2008). Improving self-organized resource allocation with effective communication. In Seventh international workshop on agents and peer-to-peer computing, AAMAS (pp. 7–18).
Kleinberg, J., & Tardos, E. (2008). Balanced outcomes in social exchange networks. In Proceedings of the 40th annual ACM symposium on theory of computing (pp. 295–304).
Klos T., Nooteboom B. (2001) Agent-based computational transaction cost economics. Economic Dynamics and Control 25(3–4): 503–526
Koutsoupias E. (2003) Selfish task allocation. Bulletin of EATCS 81: 79–88
Kraus, S., Shehory, O., & Taase, G. (2003). Coalition formation with uncertain heterogeneous information. In Proceedings of the 2nd international conference on autonomous agents and multiagent systems (AAMAS 2003) (pp. 1–8). New York: ACM.
Kraus, S., Shehory, O., & Taase, G. (2004). The advantages of compromising in coalition formation with incomplete information. In Proceedings of the 3rd international conference on autonomous agents and multiagent systems (AAMAS 2004) (pp. 588–595).
van der Krogt, R., de Weerdt, M., & Zhang, Y. (2008). Of mechanism design and multiagent planning. In ECAI (pp. 423–427). Amsterdam: IOS Press.
Lerman, K., & Shehory, O. (2000). Coalition formation for large-scale electronic markets. In Proceedings of 4th international conference on multi-agent systems (ICMAS 2000) (pp. 167–174). Boston, MA: IEEE Computer Society.
Makhorin, A. (2004). GLPK. GNU linear programming kit http://www.gnu.org/software/glpk/.
Manisterski, E., David, E., Kraus, S., & Jennings, N. (2006). Forming efficient agent groups for completing complex tasks. In H. Nakashima, M. P. Wellman, G. Weiss& P. Stone (Eds.),Proceedings of the 5th international conference on autonomous agents and multiagent systems (AAMAS 2006) (pp. 257–264). Hakodate: ACM.
Mitchell, D. G., Selman, B., & Levesque, H. J. (1992). Hard and easy distributions of SAT problems. In Proceedings of the national conference on artificial intelligence (AAAI 1992) (pp. 459–465).
Myerson R. (1979) Incentive-compatibility and the bargaining problem. Econometrica 47: 61–73
Myerson R. B., Satterthwaite M. A. (1983) Efficient mechanisms for bilateral trading. Journal of Economic Theory 29(2): 265–281
Nair, R., Ito, T., Tambe & Marsella, S. (2002). Task allocation in the robocup rescue simulation domain: A short note. In A. Birk, S. Coradeschi & S. Tadokoro (Eds.), RoboCup 2001: Robot Soccer world cup V, lecture notes in computer science (Vol.2377 , pp. 1–22). Springer Berlin, Heidelberg.
Niedermeier R. (2006) Invitation to fixed-parameter algorithms, Oxford lecture series in mathematics. Oxford University Press, Oxford
Nisan N. (2007) Introduction to mechanism design (for computer scientists). In: Nisan N., Roughgarden T., Tardos E., Vazirani V. (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 209–242
Nisan, N., & Ronen, A. (2000). Computationally feasible VCG mechanisms. In Proceedings of the 2nd ACM conference on electronic commerce (pp. 242–252). New York: ACM.
Nisan N., Ronen A. (2001) Algorithmic mechanism design. Games and Economic Behavior 35(1–2): 166–196
Patel J., Teacy W. L., Jennings N. R., Luck M., Chalmers S., Oren N., Norman T. J., Preece A., Gray P. M., Shercliff G., Stockreisser P. J., Shao J., Gray W. A., Fiddian N. J., Thompson S. (2005) Agent-based virtual organizations for the grid. Multi-Agent and Grid Systems 1(4): 237–249
Rothkopf M. H., Pekec˘ A., Harstad R. M. (1998) Computationally manageable combinational auctions. Management Science 44: 1131–1147
Sander, P. V., Peleshchuk, D., & Grosz, B. J. (2002). A scalable, distributed algorithm for efficient task allocation. In Proceedings of the 1st international conference on autonomous agents and multiagent systems (AAMAS 2002) (pp. 1191–1198). New York: ACM Press.
Shehory, O. (2000). A scalable agent location mechanism. In N. R. Jennings & Y. Lespérance (Eds.), Proceedings of intelligent agents VI, agent theories, architectures, and languages (ATAL), LNCS (Vol. 1757, pp. 162–172). Heidelberg: Springer
Shehory O., Kraus S. (1998) Methods for task allocation via agent coalition formation. Artificial Intelligence 101(1–2): 165–200
Shehory O., Kraus S. (1999) Feasible formation of coalitions among autonomous agents in nonsuperadditive environments. Computational Intelligence 15(3): 218–251
Shoham Y., Leyton-Brown K. (2008) Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, Cambridge
Smith R. G. (1981) The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers C-29(12): 1104–1113
Sreenath R. M., Singh M. P. (2004) Agent-based service selection. Web Semantics 1(3): 261–279
Vazirani V. V. (2001) Approximation algorithms. Springer-Verlag New York Inc, New York
Vidal J. M. (2003) A method for solving distributed service allocation problems. Web Intelligence and Agent Systems 1(2): 139–146
Walsh, W. E., & Wellman, M. P. (1999). Efficiency and equilibrium in task allocation economies with hierarchical dependencies. In International joint conference on artificial intelligence (IJCAI) (pp. 520–526)
Walsh, W. E., & Wellman, M. P. (2000). Modeling supply chain formation in multiagent systems. In Agent-mediated electronic commerce II, LNAI (Vol. 1788, pp. 94–101). Heidelberg: Springer.
Watts D. J., Strogatz S. H. (1998) Collective dynamics of “small world” networks. Nature 393: 440–442
de Weerdt, M., Zhang, Y., & Klos, T. B. (2007). Distributed task allocation in social networks. In Proceedings of the 6th international conference on autonomous agents and multiagent systems (AAMAS 2007) (pp. 17–24). New York: ACM.
Acknowledgments
This work is supported by the Technology Foundation STW, applied science division of NWO, and the Ministry of Economic Affairs.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
de Weerdt, M.M., Zhang, Y. & Klos, T. Multiagent task allocation in social networks. Auton Agent Multi-Agent Syst 25, 46–86 (2012). https://doi.org/10.1007/s10458-011-9168-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10458-011-9168-3