Abstract
In normative multi-agent systems, the question of “how an agent identifies norms in an open agent society” has not received much attention. This paper aims at addressing this question. To this end, this paper proposes an architecture for norm identification for an agent. The architecture is based on observation of interactions between agents. This architecture enables an autonomous agent to identify prohibition norms in a society using the prohibition norm identification (PNI) algorithm. The PNI algorithm uses association rule mining, a data mining approach to identify sequences of events as candidate norms. When a norm changes, an agent using our architecture will be able to modify the norm and also remove a norm if it does not hold in the society. Using simulations of a park scenario we demonstrate how an agent makes use of the norm identification framework to identify prohibition norms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
This is true in most countries.
In this work, we do not model how humans learn about norms in societies. However, the model proposed for artificial agents is inspired by how humans learn (e.g. observational learning, experiential learning and communication-based learning (Hamada 2008)).
Beliefs are statements of properties of the world the agent is situated in that can either be true or false; desires are states/situations that an agent prefers to bring about or actions that it wants to perform and intentions are those feasible actions, plans or desired situations that an agent has selected and committed to performing or achieving (c.f. Dignum et al. 2002).
Some works in the legal domain have investigated the extraction of rules from large databases using association rule mining approach (Bench-Capon et al. 2000; Governatori and Stranieri 2001). In the work of Bench-Capon et al. (2000), rules are identified from large sets of legal description data stored in a database. In a similar vein, Governatori and Stranieri (2001) employ association rule mining to extract rules and have used defeasible logic to formally encode the knowledge extracted. Our work is different from these two works employing association rule mining. First, those works identify rules rather than norms. Second, sanctions are not considered in these works. In our work the starting point of norm identification is the recognition of sanctions. Third, the data considered in those works comes from stored data repository which is static, while the data in our work is highly dynamic since it is based on observation of an agent which changes from time to time. Fourth, the notion of distributed agents each inferring norms in our work is unique. These works on the other hand explore rule extraction using a centralized component.
In this work we consider only punishments, although the process developed in this work can also be applied to rewards.
The term base is used to represent the repository used by an agent (e.g. an agent’s run-time memory or a persistent storage used by an agent such as a database).
Our usage of signalling in this work differs from the views in Biology and Economics. Biologists have observed that animals send signals to indicate that they are a desirable mate (Smith and Harper 2003). For example, a peacock displays its quality to peahens through its bright plumage and a long ornate tail. Economists have noted that human agents send signals to others that they are credible through some form of signalling (e.g. acquiring a university degree signals that someone has skills for a particular job (Spence 1973)). In our work, signalling is special type of event whose occurrence can be interpreted as a punishment signal (a sanction). These signals are responses or feedback of the observing agents on the actions performed by the observed agent. While the actions performed by agents themselves are viewed as signals in disciplines such as Biology and Economics, the signals in our work are the feedback of other agents on the actions performed by an agent
The sanction can also be any other disapproval gesture.
If the event is not a special event, nothing happens. We have only shown the branching conditions which have some consequences in Fig. 1.
Please refer to work of Savarimuthu et al. (2010).
An agent may collect more evidence about sanctions if it waits for certain period of time.
In human societies norm re-evaluation happens rarely as the norms tend to be largely permanent (e.g. the norms of cooperation and reciprocity). However, some social norms may change (e.g. smoking in a restaurants which was originally permitted is now prohibited) that require re-evaluation on the part of agents. We believe, in virtual environments, the norms can change at a faster rate as the composition of an open agent society changes. Hence, agents need to re-evaluate norms in regular intervals of time. We note that an agent can modify how often it re-evaluates norms using a parameter which can be used to model either frequent or rare re-evaluations.
Note that how an agent internalizes a norm is out of the scope of this work. Other researchers have studied how norms are internalized (Verhagen 2001). The focus of our work is on norm identification.
We have experimented with two types of scenarios where agents remember the norms of the society they leave and where agents remove the norms of the society they leave.
The reasons for asking another agent just for verification are twofold. First, an agent entering a society may not be interested to find out all the norms of a society (an agent might give a long list of norms followed in the society). It may be interested to find the norms in a particular context. An agent has to first infer what the context is (by observing the interactions) and then it can ask another agent in the neighborhood if its inference of a norm is valid (e.g. Am I obliged to tip in this society?). In our view this is more effective (in terms of computation and memory required) than asking another agent what the norms are, as there could be a long list of norms that apply, and most of those may not be of interest to an agent. The agent employing the architecture will be able to infer what the potential norms might be. Hence, it can be confident in asking for norm referral, as the actual norm might be one of the candidate norms in its list. The search space for the actual norm has been narrowed by the norm identification process. An agent can also precisely formulate a query for another agent (e.g. Is it prohibited to litter in this society?). Second, an agent may not completely trust other agents in an open society. When an agent asks another agent without norm inference, the other agent could potentially lie about a norm (Savarimuthu et al. 2011). So, an agent may want to make sure that it identifies candidate norms, before it asks for norm verification. This process helps an agent from being misled by the referring agent if it were to ask what the norm is, since it knows that one of the candidate norms could potentially be a norm. Note that this does not solve the lying problem, since the referrer agent can lie when an agent asks if something is a norm in the society. At the least, the mechanism we use here allows the agent to have a set of candidate norms. We discuss a potential solution to the lying problem in Sect. 10.
Permutations with repetitions are considered, because an agent does not know whether littering once (l) is a reason for sanction or littering twice (ll) is the reason for the sanction. It could be that littering once may be allowed but an agent littering twice may be punished.
Other alternative mechanisms are also possible. For example, an agent can verify whether its candidate norms hold by undertaking actions that it observes to be sanctioned (e.g. dropping a litter). Based on the outcome of tests the agent carries out it can infer what the norms could be. This is a meta-level norm testing mechanism of an agent.
It could be that there are no sanctions in the society because all the agents have internalized a norm (i.e. they abide by the norm). However, the process of norm internalization has not been considered in this work. Norm internalization can depend upon the personality of agents (e.g. social agents, rebellious agents). We note this can be included in our architecture. Additionally, norm internalization is a separate issue from the issue of norm identification studied here.
We note that other mechanisms are also possible. For example, an agent can ask certain number of agents in its vicinity instead of asking just one. In this work, agents ask one other agent for norm verification. There is a parameter in the system which can be used to change the number of agents that are asked for verifying a norm. This is akin to the referral process which has been studied by other researchers (Candale and Sen 2005; Yu and Singh 2002) which show that increasing the number of referrals leads to faster convergence.
The simulation of this scenario can be viewed http://unitube.otago.ac.nz/view?m=3d8h11fu1xa.
This was because the probability of a punishment for littering was higher than eating. In the opposite case, the norm against littering would have been found first.
In this work we have focused on simple co-existing norms (e.g. norms against eating and littering).
We have used a value of 5 in our simulations to model small fluctuations (increase or decrease) in the NIF value. This discrete amount is a parameter in our system which can be changed.
We assume that the agent knows when it enters a new society. For example, the agent may know the physical boundaries of the society in which it is situated. For example, an avatar in SecondLife explicitly knows that it is moving from one community to another.
Cleaning commons area such as a public park that has been littered would be at a cost which would be paid by the rate-payers of the city. From this point of view, bearing the cost of a litter has been distributed to all members of the society including the litterer.
Simulation can be viewed at http://unitube.otago.ac.nz/view?m=SE7M11esZnI. The litterers are in black, non-litterers are in green and the punishers are in red.
We note this is an improvement from the game-theory based works which have typically considered only two options for agents based on coordination or cooperation games (Pujol 2006; Sen and Airiau 2007; Shoham and Tennenholtz 1992; Villatoro et al. 2009) (e.g. drive on the left or the right). Additionally those works do not deal with sanctions, therefore only cater for recognizing a convention.
We acknowledge that the scenarios that can be modeled using Second Life are far richer than the ones presented in this paper. Those scenarios will require richer norm identification mechanisms.
This has been demonstrated by Savarimuthu et al. (2010). In the case of identifying both types of norms together, first obligation norms should be inferred followed by the prohibition norms in order to avoid false positives of prohibition norms (future work).
This is a granularity issue. An agent can choose to record all the events or only some of the key events that happen around it. By choosing to record key events, the agent may have a coarser but longer history which can be used to infer norms. Additionally, if sanction follows long after the action has been performed, it is difficult to associate a sanction with the action that triggered it (i.e. it is computationally expensive).
References
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Bocca JB, Jarke M, Zaniolo C (eds) Proceedings of the 20th international conference on very large data bases (VLDB’94). Morgan Kaufmann, Santiago de Chile, Chile, pp 487–499
Akerlof GA (1976) The economics of caste and of the rat race and other woeful tales. Q J Econ 90(4):599–617
Aldewereld H, Dignum F, García-Camino A, Noriega P, Rodríguez-Aguilar JA, Sierra C (2006) Operationalisation of norms for usage in electronic institutions. In: Proceedings of the 5th international joint conference on autonomous agents and multiagent systems (AAMAS). ACM Press, New York, NY, USA, pp 223–225
Andrighetto G, Conte R, Turrini P, Paolucci M (2007) Emergence in the loop: simulating the two way dynamics of norm innovation. In: Boella G, van der Torre L, Verhagen H (eds) Normative multi-agent systems, no. 07122 in Dagstuhl seminar proceedings. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany
Andrighetto G, Campenni M, Cecconi F, Conte R (2010) The complex loop of norm emergence: a simulation model. In: Chen SH, Cioffi-Revilla C, Gilbert N, Kita H, Terano T, Takadama K, Cioffi-Revilla C, Deffuant G (eds) Simulating interacting agents and social phenomena. Agent-based social systems, vol 7. Springer, New York, pp 19–35
Arcos JL, Esteva M, Noriega P, Rodríguez-Aguilar JA, Sierra C (2005) Environment engineering for multiagent systems. Eng Appl Artif Intell 18(2):191–204
Axelrod R (1986) An evolutionary approach to norms. Am Political Sci Rev 80(4):1095–1111
Bandura A (1977) Social learning theory. General Learning Press, Morristown, NJ
Becker GS (1978) The economic approach to human behavior. University of Chicago Press, Chicago
Bench-Capon T, Coenen F, Leng P (2000) An experiment in discovering association rules in the legal domain. In: 11th International workshop on database and expert systems applications, 2000, pp 1056 –1060
Bicchieri C (2006) The grammar of society: the nature and dynamics of social norms. Cambridge University Press, New York, NY, USA
Boella G, van der Torre L (2006) An architecture of a normative system: counts-as conditionals, obligations and permissions. In: Proceedings of the 5th international joint conference on autonomous agents and multiagent systems (AAMAS). ACM Press, New York, NY, USA, pp 229–231
Boella G, van der Torre L (2007) The ontological properties of social roles in multi-agent systems: definitional dependence, powers and roles playing roles. Artif Intell Law 15(3):201–221
Boella G, van der Torre L, Verhagen H (2006) Introduction to normative multiagent systems. Comput Math Organ Theory 12(2–3):71–79
Boella G, van der Torre L, Verhagen H (2008) Introduction to the special issue on normative multiagent systems. Auton Agents Multi Agent Syst 17(1):1–10
Boman M (1999) Norms in artificial decision making. Artif Intell Law 7(1):17–35
Boyd S, Ghosh A, Prabhakar B, Shah D (2006) Randomized gossip algorithms. IEEE Trans Inf Theory 52(6):2508–2530
Broersen J, Dastani M, Hulstijn J, Huang Z, van der Torre L (2001) The boid architecture: conflicts between beliefs, obligations, intentions and desires. In: AGENTS ’01: proceedings of the 5th international conference on autonomous agents. ACM, New York, NY, USA, pp 9–16
Campbell EQ (1964) The internalization of moral norms. Sociometry 27(4):391–412
Candale T, Sen S (2005) Effect of referrals on convergence to satisficing distributions. In: Proceedings of the 4th international joint conference on autonomous agents and multiAgent systems, (AAMAS’05). ACM, New York, NY, USA, pp 347–354
Ceglar A, Roddick JF (2006) Association mining. ACM Comput Surv 38(2):5
Chwe MSY (2001) Rational ritual: culture, coordination and common knowledge. Princeton University Press, Princeton
Coleman J (1990) Foundations of social theory. Belknap Press, Cambridge, MA
Conte R, Castelfranchi C (1995) Understanding the effects of norms in social groups through simulation. In: Gilbert N, Conte R (eds) Artificial societies: the computer simulation of social life. UCL Press, London, pp 252–267
Conte R, Castelfranchi C (1999) From conventions to prescriptions. Towards an integrated view of norms. Artif Intell Law 7(4):323–340
Conte R, Dignum F (2001) From social monitoring to normative influence. J Artif Soc Soc Simul 4(2). http://jasss.soc.surrey.ac.uk/4/2/7.html
Conte R, Paolucci M (2001) Intelligent social learning. J Artif Soc Soc Simul 4(1)
Cranefield S, Li G (2009) Monitoring social expectations in second life. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems—volume 2, AAMAS ’09. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, pp 1303–1304
Criado N, Argente E, Botti V (2010) Rational strategies for autonomous norm adoption. In: Proceeding of the 9th international workshop on coordination, organization, institutions and norms in agent systems (COIN@AAMAS 2010), pp 9–16
de Pinninck AP, Sierra C, Schorlemmer WM (2008) Distributed norm enforcement: Ostracism in open multi-agent systems. In: Casanovas P, Sartor G, Casellas N, Rubino R (eds) Computable models of the law: languages, dialogues, games, ontologies, Lecture Notes in Computer Science, vol 4884. Springer, New York, pp 275–290
Dictionary.com: empirical. http://dictionary.reference.com/browse/empirical (2010). Accessed 12 November 2010
Dignum F (1999) Autonomous agents with norms. Artif Intell Law 7(1):69–79
Dignum F, Kinny D, Sonenberg L (2002) From desires, obligations and norms to goals. Cogn Sci Q 2(3–4):407–430
Elster J (1989) Social norms and economic theory. J Econ Perspect 3(4):99–117
Epstein JM (2001) Learning to be thoughtless: social norms and individual computation. Comput Econ 18(1):9–24
EsperTech: Esper tutorial. http://esper.codehaus.org/tutorials/tutorial/tutorial.html (2010). Accessed 15 June 2011
Gaertner D, García-Camino A, Noriega P, Rodríguez-Aguilar JA, Vasconcelos WW (2007) Distributed norm management in regulated multi-agent systems. In: Proceedings of the 6th international joint conference on autonomous agents and multiagent systems (AAMAS’07). ACM, Honolulu, Hawaii, pp 624–631
García-Camino A, Rodríguez-Aguilar JA, Sierra C, Vasconcelos WW (2006) Norm-oriented programming of electronic institutions. In: Proceedings of the 5th international joint conference on autonomous agents and multiagent systems (AAMAS). ACM Press, New York, NY, USA, pp 670–672
Gibbs JP (1965) Norms: the problem of definition and classification. Am J Sociol 60:586–594
Governatori G, Stranieri A (2001) Towards the application of association rules for defeasible rule discovery. In: Fourteenth annual international conference on legal knowledge and information systems, vol 4. IOS Press, Amsterdam, pp 63–75
Habermas J (1985) The theory of communicative action, volume 1: reason and the rationalization of society. Beacon Press, Boston
Hamada M (2008) Web-based environment for active computing learners. In: ICCSA, vol 1, pp 516–529
Han J, Kamber M (2006) Data mining: concepts and techniques. Morgan Kaufmann, San Francisco
Hoffmann MJ (2003) Entrepreneurs and norm dynamics: an agent-based model of the norm life cycle. Technical report, Department of Political Science and International Relations, University of Delaware, USA
Johansson M, Verhagen H (2009) Massively multiple online role playing games as normative multiagent systems. In: Boella G, Noriega P, Pigozzi G, Verhagen H (eds) Normative multi-agent systems, no. 09121 in Dagstuhl seminar proceedings. Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany
Jones AJI, Sergot MJ (1996) A formal characterisation of institutionalised power. Logic J IGPL 4(3):427–443
Koda T, Ruttkay Z (2009) Cultural differences in using facial parts as cues to recognize emotions in avatars. In: IVA ’09: proceedings of the 9th international conference on intelligent virtual agents, pp 517–518. Springer, Berlin, Heidelberg
López Y, López F (2003) Social powers and norms: impact on agent behaviour. Ph.D. thesis, Department of Electronics and Computer Science, University of Southampton, UK
López Y, López F, Luck M, d’Inverno M (2002) Constraining autonomy through norms. In: Proceedings of the 1st international joint conference on autonomous agents and multiagent systems (AAMAS), vol 2. ACM, New York, NY, USA, pp 674–681. citeseer.ist.psu.edu/lopez02constraining.html
López Y, López F, Márquez AA (2004) An architecture for autonomous normative agents. In: Proceedings of the 5th Mexican international conference in computer science (ENC). IEEE Computer Society, Los Alamitos, CA, USA, pp 96–103
Lotzmann U, Möhring M (2009) Simulating norm formation: an operational approach. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems, pp 1323–1324
Mannila H, Toivonen H, Inkeri Verkamo A (1997) Discovery of frequent episodes in event sequences. Data Min Knowl Discov 1(3):259–289
McAfee RP, McMillan J (1987) Auctions and bidding. J Econ Lit 25(2):699–738
Meneguzzi FR, Luck M (2009) Norm-based behaviour modification in BDI agents. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems (AAMAS). IFAAMAS, pp 177–184
Neumann M (2010) A classification of normative architectures. In: Takadama K, Cioffi-Revilla C, Deffuant G (eds) Simulating interacting agents and social phenomena: the second world congress, agent-based social systems, vol 7, Springer, Berlin/Heidelberg, pp 3–18
Neviarouskaya A, Tsetserukou D, Prendinger H, Kawakami N, Tachi S, Ishizuka M (2009) Emerging system for affectively charged interpersonal communication. In: Proceedings of ICROS-SICE international joint conference, pp 3376–3381
Nwana HS (1996) Software agents: an overview. Knowl Eng Rev 11(03):205–244
Paolucci M, Marsero M, Conte R (2000) What is the use of gossip? a sensitivity analysis of the spreading of respectful reputation. In: Tools and techniques for social science simulation. Physica Verlag, pp 302–314
Picard RW (1998) Toward agents that recognize emotion. In: Actes proceedings IMAGINA, pp 153–165
Pujol JM (2006) Structure in artificial societies. Ph.D. thesis, Departament de Llenguatges i Sistemes Informàtics, Universitat Politènica de Catalunya
Sadri F, Stathis K, Toni F (2006) Normative kgp agents. Comput Math Organ Theory 12(2–3):101–126
Salazar N, Rodríguez-Aguilar JA, Arcos JL (2008) Infection-based norm emergence in multi-agent complex networks. In: Proceedings of the 2008 conference on ECAI 2008. IOS Press, Amsterdam, The Netherlands, pp 891–892
Salazar N, Rodríguez-Aguilar JA, Arcos JL (2009) Handling uncertainty in the emergence of social conventions. In: Third IEEE international conference on self-adaptive and self-organizing systems (SASO’09), pp 282–283
Savarimuthu BTR, Cranefield S (2011) Norm creation, spreading and emergence: a survey of simulation models of norms in multi-agent systems. Multiagent Grid Syst 7(1):21–54
Savarimuthu B, Arulanandam R, Purvis M (2011) Aspects of active norm learning and the effect of lying on norm emergence in agent societies. In: Kinny D, Hsu J, Governatori G, Ghose A (eds) Agents in principle, agents in practice. Lecture Notes in Computer Science, vol 7047, Springer, Berlin/Heidelberg, pp 36–50
Savarimuthu BTR, Cranefield S, Purvis MA, Purvis MK (2010) Obligation norm identification in agent societies. J Artif Soc Soc Simul 13(4):3. http://jasss.soc.surrey.ac.uk/13/4/3.html
Searle JR (1969) Speech acts. Cambridge University Press, Cambridge, UK
Sen S, Airiau S (2007) Emergence of norms through social learning. In: Proceedings of the 20th international joint conference on artificial intelligence (IJCAI). AAAI Press, Menlo Park, CA, pp 1507–1512
Shoham Y, Tennenholtz M (1992) Emergent conventions in multi-agent systems: initial experimental results and observations. In: Proceedings of the 3rd international conference on the principles of knowledge representation and reasoning (KR). Morgan Kaufmann, San Mateo, CA, USA, pp 225–231
Shoham Y, Tennenholtz M (1995) On social laws for artificial agent societies: off-line design. Artif Intell 73(1–2):231–252
Sills DL (1968) International encyclopedia of the social sciences. New York
Smith JM, Harper D (2003) Animal signals. Oxford University Press, Oxford, USA
Spence M (1973) Job market signaling. Q J Econ 87(3):355–374
Tuomela R (1995) The importance of us: a philosophical study of basic social notions. Stanford series in philosophy. Stanford University Press, California
Ullmann-Margalit E (1977) The emergence of Norms. Clarendon Press, Oxford
Vázquez-Salceda J (2003) Thesis: the role of norms and electronic institutions in multi-agent systems applied to complex domains. The harmonia framework. AI Commun 16(3):209–212
Vázquez-Salceda J, Aldewereld H, Dignum F (2005) Norms in multiagent systems: from theory to practice. Comput Syst Sci Eng 20(4):95–114
Verhagen H (2001) Simulation of the learning of norms. Soc Sci Comput Rev 19(3):296–306
Villatoro D, Sabater-Mir J (2009) Categorizing social norms in a simulated resource gathering society. In: Coordination, organizations, institutions and norms in agent systems IV: COIN 2008 international workshops, revised selected papers. Springer, Berlin/Heidelberg, , pp 235–249
Villatoro D, Sen S, Sabater-Mir J (2009) Topology and memory effect on convention emergence. In: WI-IAT ’09: proceedings of the 2009 IEEE/WIC/ACM international joint conference on web intelligence and intelligent agent technology, pp 233–240. IEEE Computer Society, Washington, DC, USA
Walker A, Wooldridge M (1995) Understanding the emergence of conventions in multi-agent systems. In: Lesser V (ed) Proceedings of the 1st international conference on multi-agent systems (ICMAS), pp 384–389. AAAI Press, Menlo Park, CA, USA
Watkins CJCH, Dayan P (1992) Q-learning. Mach Learn 8(3–4):279–292
Weisstein EW (2010) Torus. http://mathworld.wolfram.com/Torus.html Accessed on 01 December 2009
von Wright GH (1951) Deontic logic. Mind 60(237):1–15
Yu B, Singh MP (2002) Emergence of agent-based referral networks. In: Proceedings of the first international joint conference on autonomous agents and multiagent systems (AAMAS). ACM, New York, NY, USA, pp 1268–1269
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Acronyms and expansions of the terms used in this paper are given below based on the alphabetical ordering of the acronyms (Table 3).
Rights and permissions
About this article
Cite this article
Savarimuthu, B.T.R., Cranefield, S., Purvis, M.A. et al. Identifying prohibition norms in agent societies. Artif Intell Law 21, 1–46 (2013). https://doi.org/10.1007/s10506-012-9126-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10506-012-9126-7