Skip to main content
SpringerLink
Log in

Interleaving multi-agent systems and social networks for organized adaptation

  • Published:
Computational and Mathematical Organization Theory Aims and scope Submit manuscript

Abstract

Ad hoc networks can be formed from arbitrary collections of sensors, mobile routers, or business processes. These networks are open systems, in the sense that the network nodes share a common language but do not necessarily share a common goal or common knowledge, and there is no centralised controller or global data repository. Such systems have numerous advantages in terms of enabling autonomous, heterogeneous components to achieve individual goals without central direction and with only partial knowledge. However, operational problems stem from potential conflicts over resource allocation, miscommunication, and sub-ideal operation, and the general need of embedded systems to change behaviour according to changes in the environment. To address these problems, we propose to converge aspects of norm-governed specification from distributed multi-agent systems, opinion formation from social networks, and voting procedures from computational social choice. In particular, we develop a prototype system which interleaves gossiping, expressed preferences (voting) and norms, to configure rules and assign roles. This is another demonstration of the use of socially-inspired mechanisms for regulation of decentralised systems and a key step towards the realization of organized adaptation for open multi-agent systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Akyildiz I, Su W, Sankarasubramaniam Y, Cayirci E (2002) Wireless sensor networks: a survey. Comput Netw 38:393–422

    Article  Google Scholar 

  • Amini H, Draief M, Lelarge M (2009) Marketing in a random network. In: Altman E, Chaintreau A (eds) Network control and optimization. Springer, Berlin, pp 17–25

    Chapter  Google Scholar 

  • Artikis A (2009) Dynamic protocols for open agent systems. In: Proceedings international conference on autonomous agents and multi-agent systems (AAMAS). ACM, New York, pp 97–104

    Google Scholar 

  • Artikis A, Kamara L, Pitt J, Sergot M (2005) A protocol for resource sharing in norm-governed ad hoc networks. In: Proceedings of workshop on declarative agent languages and technologies (DALT). LNCS, vol 3476. Springer, Berlin, pp 221–238

    Chapter  Google Scholar 

  • Artikis A, Sergot M, Pitt J (2009a) An executable specification of a formal argumentation protocol. Artif Intell 171(10–15):776–804

    Google Scholar 

  • Artikis A, Sergot M, Pitt J (2009b) Specifying norm-governed computational societies. ACM Trans Comput Logic 10(1):1–42

    Article  Google Scholar 

  • Bartholdi J, Orlin J (1991) Single transferable vote resists strategic voting. Soc Choice Welf 8:341–354

    Google Scholar 

  • Bartholdi J, Tovey C, Trick M (1989) The computational difficulty of manipulating an election. Soc Choice Welf 6:227–241

    Article  Google Scholar 

  • Bench-Capon TJM, Dunne PE (2007) Argumentation in artificial intelligence. Artif Intell 171(10–15):619–641

    Article  Google Scholar 

  • Buckland MK (1991) Information as thing. J Am Soc Inf Sci 42(5):351–360

    Article  Google Scholar 

  • Boella G, van der Torre L (2003) Permissions and obligations in hierarchical normative systems. In: Proc of ICAIL 03, Edinburgh

    Google Scholar 

  • Boyson S, Corsi T (2002) Managing the real-time supply chain. In: HICSS’02, Washington, DC, USA. IEEE Computer Society, Los Alamitos, p 70

    Google Scholar 

  • Carr H, Pitt J (2008) Adaptation of voting rules in agent societies. In: Vouros G, Artikis A, Stathis K, Pitt J (eds) Proceedings AAMAS workshop on organized adaptation in multi-agent systems. LNAI, vol 5368. Springer, Berlin

    Google Scholar 

  • Carr H, Pitt J, Artikis A (2008) Peer pressure as a driver of adaptation in agent societies. In: Artikis A, Picard G, Vercouter L (eds) Proceedings AAMAS workshop on organized adaptation in multi-agent systems. Springer, Berlin

    Google Scholar 

  • Cevenini C (2003) Legal considerations on the use of software agents in virtual enterprises. In: Bing J, Sartor G (eds) The law of electronic agents. CompLex, vol 4/03. Unipubskriftserier, Oslo, pp 133–146

    Google Scholar 

  • Chevaleyre Y, Endriss U, Lang J, Maudet N (2007) A short introduction to computational social choice. In: SOFSEM: theory and practice of computer science, pp 51–69

    Chapter  Google Scholar 

  • Chong C, Kumar S (2003) Sensor networks: evolution, opportunities, and challenges. Proc IEEE 91(8):1247–1256

    Article  Google Scholar 

  • Chopra A, Singh M (2006) Contextualizing commitment protocols. In: Proc autonomous agents and multi-agent systems AAMAS08. ACM, New York, pp 1345–1352

    Chapter  Google Scholar 

  • Conitzer V, Sandholm T (2002) Complexity of manipulating elections with few candidates. In: Eighteenth national conference on artificial intelligence. American Association for Artificial Intelligence, Menlo Park, pp 314–319

    Google Scholar 

  • Conitzer V, Sandholm T (2003) Universal voting protocol tweaks to make manipulation hard. In: Proc 18th international join conference on artificial intelligence, pp 781–788

    Google Scholar 

  • Conitzer V, Sandholm T, Lang J (2007) When are elections with few candidates hard to manipulate? J Assoc Comput Mach 54(3):14

    Google Scholar 

  • Craven R, Sergot M (2008) Agent strands in the action language nc+. J Appl Log 6:172–191

    Article  Google Scholar 

  • Dastani M, Dignum V, Dignum F (2003) Role-assignment in open agent societies. In: Proceedings conference on autonomous agents and multi-agent systems (AAMAS), pp 489–496

    Chapter  Google Scholar 

  • Deffuant G, Neau D, Amblard F, Weisbuch G (2000) Mixing beliefs among interacting agents. Adv Complex Syst 3(1–4):87–98

    Article  Google Scholar 

  • Dignum V (ed) (2009) Handbook of research on multi-agent systems: semantics and dynamics of organizational models. ISI

    Google Scholar 

  • Dignum V, Dignum F (2009) A logic for agent organizations. In: Dignum V, Dignum F (eds) Handbook of research on multi-agent systems: semantics and dynamics of organizational models

    Chapter  Google Scholar 

  • Draief M (2006) Epidemic processes on complex networks. Phys A, Stat Mech Appl 363(1):120–131

    Article  Google Scholar 

  • Draief M, Ganesh A (2006) Efficient routing in poisson small-world networks. J Appl Probab 43(3):678–686

    Article  Google Scholar 

  • Draief M, Ganesh A (2009) A random walk model for infection on graphs. In: ACM proc int conference on performance evaluation methodologies and tools (Valuetools’ 09), pp 1–8

    Google Scholar 

  • Draief M, Ganesh A, Massoulié L (2009) Exponential random graphs as models of overlay networks. J Appl Probab 46(1):199–220

    Article  Google Scholar 

  • Dodds P, Watts D (2004) Universal behaviour in a generalized model of contagion. Phys Rev Lett 92:218701

    Article  Google Scholar 

  • Esteva M, Padget J, Sierra C (2002) Formalizing a language for institutions and norms. In: Meyer J-J, Tambe M (eds) Intelligent agents VIII: agent theories, architectures, and languages. LNAI, vol 2333. Springer, Berlin, pp 348–366

    Google Scholar 

  • Fornara N, Colombetti M (2007) Agent communication and artificial institutions. Auton Agents Multi-Agent Syst 14:121–142

    Article  Google Scholar 

  • French J (1956) A formal theory of social power. Psychol Rev 63:181–194

    Article  Google Scholar 

  • Friedkin NE, Johnsen EC (1990) Social influence and opinions. J Math Sociol 15:193–205

    Article  Google Scholar 

  • Giunchiglia E, Lee J, Lifschitz V, McCain N, Turner H (2004) Nonmonotonic causal theories. Artif Intell 153(1–2):49–104

    Article  Google Scholar 

  • Gruhl D, Liben-Nowell D, Guha RV, Tomkins A (2004) Information diffusion through blogspace. In: Feldman SI, Uretsky M, Najork M, Wills CE (eds) Proceedings of the 13th international world wide web conference. ACM, New York, pp 491–501

    Google Scholar 

  • Haenni R, Hartmann S (2006) Modeling partially reliable information sources: A general approach based on Dempster-Shafer theory. Inf Fusion 7:361–379

    Article  Google Scholar 

  • Hartmann S, Pigozzi G (2007) Aggregation in multi-agent systems and the problem of truth-tracking. In: Proceedings of the sixth international conference on autonomous agents and multi-agent systems (AAMAS), pp 674–676

    Google Scholar 

  • Hegselmann R, Krause U (2002) Opinion dynamics and bounded confidence: models, analysis and simulation. J Artif Soc Simul 5(3):1–24

    Google Scholar 

  • Heinzelman W, Kulik J, Balakrishnan H (1999) Adaptive protocols for information dissemination in wireless sensor networks. In: Proceedings of the 5th annual ACM/IEEE international conference on mobile computing and networking, pp 174–185

    Chapter  Google Scholar 

  • Heinzelman W, Chandrakasan A, Balakrishnan H (2000) Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences

    Google Scholar 

  • Hewitt C (1986) Offices are open systems. ACM Trans Inf Syst Secur 4(3):271–287

    Google Scholar 

  • Iraqi Y, Boutaba R, Leon-Garcia A (1999) QoS control in wireless ATM. Mob Netw Appl 5:137–145

    Article  Google Scholar 

  • Jones A, Sergot M (1996) A formal characterisation of institutionalised power. J IGPL 4(3):429–445

    Google Scholar 

  • Kearns M, Surit S, Monfort N (2006) An experimental study of the coloring problem on human subject networks. Science 313:824–827

    Article  Google Scholar 

  • Kowalski R, Sergot M (1986) A logic-based calculus of events. New Gener Comput 4(1):67–96

    Article  Google Scholar 

  • Krishnamachari B, Estrin D, Wicker S (2002) The impact of data aggregation in wireless sensor networks. In: Proceedings of the 22nd international conference on distributed computing systems, pp 575–578

    Google Scholar 

  • Kumar S, Lai T, Balogh J (2004) On k-coverage in a mostly sleeping sensor network. In: Proceedings of the 10th annual international conference on mobile computing and networking, pp 144–158

    Chapter  Google Scholar 

  • Leskovec J, Adamic L, Huberman B (2006) The dynamics of viral marketing. In: Feigenbaum J, Chuang JC-I, Pennock DM (eds) Proceedings of the 7th ACM conference on electronic commerce. ACM, New York, pp 228–237

    Chapter  Google Scholar 

  • Makinson D (1986) On the formal representation of rights relations. J Philos Logic 15:403–425

    Article  Google Scholar 

  • Mantilla C, Marzo J (2004) A QoS framework for heterogeneous wireless networks using a multiagent system. In: 5th European wireless conference, pp 61–67

    Google Scholar 

  • Marík V, Brennan R, Pechoucek M (eds) (2005) Second international conference on industrial applications, of holonic and multi-agent systems, HoloMAS 2005. LNCS, vol 3593. Springer, Berlin

    Google Scholar 

  • Meyer J-J, Wieringa R (1993) Deontic logic in computer science: normative system specification. Wiley, New York

    Google Scholar 

  • Neville B, Pitt J (2009) Presage: a programming environment for the simulation of agent societies. In: Proc AAMAS workshop on programming multi-agent systems (ProMAS). Springer, Berlin

    Google Scholar 

  • Ostrom E (1990) Governing the commons: the evolution of institutions for collective action. Cambridge University Press, Cambridge

    Google Scholar 

  • Pörn I (1977) Action theory and social science: some formal models. In: Number 120 in synthese library. Reidel, Dordrecht

    Google Scholar 

  • Pigozzi G, Hartmann S (2006) Merging judgments and the problem of truth-tracking. In: Endriss U, Lang J (eds) Proceedings of the 1st international workshop on computational social choice, ILLC, pp 408–421

  • Pitt J, Mamdani A, Charlton P (2001) The open agent society and its enemies: a position statement and research programme. Telemat Inform 18(1):67–87

    Article  Google Scholar 

  • Pitt J, Kamara L, Sergot M, Artikis A (2006) Voting in multi-agent systems. Comput J 49(2):156–170

    Article  Google Scholar 

  • Procaccia A, Rosenschein J, Zohar A (2007) Multi-winner elections: Complexity of manipulation, control and winner-determination. In: Veloso M (ed) Proceedings of the 20th international joint conference on artificial intelligence (IJCAI), pp 1476–1481

    Google Scholar 

  • Ramirez-Cano D, Pitt J (2006) Follow the leader: Profiling agents in an opinion formation model of dynamic confidence and individual mind-sets. In: Proceedings of the 2006 IEEE/WIC/ACM international conference on intelligent agent technology, pp 660–667

    Chapter  Google Scholar 

  • Robert H et al (2000) Robert’s rules of order newly, 10th edn revised. Perseus Publishing, Cambridge

    Google Scholar 

  • Rogers E (1995) Diffusion of innovations, 4th edn. Free Press, New York

    Google Scholar 

  • Romer K, Matter F (2004) The design space of wireless sensor networks. IEEE Wirel Commun 11(6):54–61

    Article  Google Scholar 

  • Sadighi B, Sergot M (2002) Contractual access control. In: Proceedings of workshop on security protocols. LNCS, vol 2845. Springer, Berlin, pp 96–102

    Google Scholar 

  • Schultz T, Kaufmann-Kohler G, Langer D, Bonnet V (2001) Online dispute resolution: The state of the art and the issues. Technical report, Report of the E-Com/E-Law Research Project of the University of Geneva

  • Searle J (1969) Speech acts. Cambridge University Press, Cambridge

    Google Scholar 

  • Searcóid MÓ (2006) Metric spaces. Springer, Berlin

    Google Scholar 

  • Sergot M (2008) Action and agency in norm-governed multi-agent systems. In: Proceedings of ESAW VIII. LNAI, vol 4995. Springer, Berlin, pp 1–54

    Google Scholar 

  • Shin S, Lee T, In H (2009) Defending battery exhaustion attacks on mobile systems. In: 33rd annual IEEE international computer software and applications conference, vol 2, pp 347–352

    Chapter  Google Scholar 

  • Slate W II (2002) Online dispute resolution: Click here to settle your dispute. Disput Resolut J. http://findarticles.com/p/articles/mi_qa3923/is_200111/ai_n9166058/?tag=content;col1

  • Suganuma T, Lee S, Kinoshita T, Shiratori N (2001) An agent architecture for strategy-centric adaptive QoS control in flexible videoconference system. New Gener Comput 19(2):173–192

    Article  Google Scholar 

  • Tipton F, Krause M (2003) Information security management handbook. CRC Press, Boca Raton

    Google Scholar 

  • Travers J, Milgram S (1969) An experimental study of the small world problem. Sociometry 32:425–443

    Article  Google Scholar 

  • Wang L, Xiao Y (2005) Energy saving mechanisms in sensor networks. In: Proceedings of the IEEE broadnets

    Google Scholar 

  • Ye W, Heidemann J, Estrin D (2004) Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM Trans Netw (TON) 12(3):493–506

    Article  Google Scholar 

  • Yolum P, Singh M (2002a) Commitment machines. In: Meyer J-J, Tambe M (eds) Intelligent agents VIII: agent theories, architectures, and languages. LNAI, vol 2333. Springer, Berlin, pp 235–247

    Google Scholar 

  • Yolum P, Singh M (2002b) Flexible protocol specification and execution: applying event calculus planning using commitments. In: Castelfranchi C, Johnson L (eds) Proceedings of conference on autonomous agents and multiagent systems (AAMAS). ACM, New York, pp 527–535

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical & Electronic Engineering, Imperial College London, Exhibition Road, London, SW7 2BT, UK

    Jeremy Pitt, Daniel Ramirez-Cano & Moez Draief

  2. Software & Knowledge Engineering Laboratory, Institute of Informatics & Telecommunications, National Centre for Scientific Research “Demokritos”, Athens, 15310, Greece

    Alexander Artikis

Authors
  1. Jeremy Pitt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Ramirez-Cano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Moez Draief
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Alexander Artikis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremy Pitt.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pitt, J., Ramirez-Cano, D., Draief, M. et al. Interleaving multi-agent systems and social networks for organized adaptation. Comput Math Organ Theory 17, 344–378 (2011). https://doi.org/10.1007/s10588-011-9089-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10588-011-9089-3

Keywords

Search

Navigation