Verifying Organizations Regulated by Institutions

Verifying Organizations Regulated by Institutions

Francesco Viganò (Università della Svizzera italiana, Switzerland) and Marco Colombetti (Università della Svizzera italiana, Switzerland and Politecnico di Milano, Italy)
DOI: 10.4018/978-1-60566-256-5.ch015
OnDemand PDF Download:


Institutions have been proposed to explicitly represent norms in open multi-agent systems, where agents may not follow them and which therefore require mechanisms to detect violations. In doing so, they increase the efficiency of electronic transactions carried out by agents, but raise the problem of ensuring that such institutions are not characterized by contradictory norms, and provide agents with all the needed powers to fulfill their objectives. In this chapter we present a framework to verify organizations regulated by institutions, which is characterized by a precise formalization of institutional concepts, a language to describe institutions, and a tool to model check them. Finally, to evaluate and exemplify our approach, we model and verify the Chaired Meeting Institution, showing that the verification of institutional rules constitutes a necessary step to define sound institutions.
Chapter Preview


To automate tasks whose performance is regulated by norms, like the allocation of human organs (Vázquez-Salceda, Dignum, & Dignum., 2005) or the bargain of goods in competitive markets (Noriega, 1997), electronic institutions have been proposed as a mechanism to represent norms in agent organizations (Noriega, 1997) where agents are developed by different entities and their internal states are not accessible. The term “electronic institution” is often used to refer to either the rules that regulate open multiagent systems, the organization that enforces them (Esteva, Rodríguez-Aguilar, Sierra, García, & Arcos, 2001), the software implementation of institutional rules (Esteva, Rodríguez-Aguilar, Rosell, & Arcos, 2004), or a specific formalism to describe them (Esteva, Rodríguez-Aguilar, Sierra, & Vasconcelos, 2004). For the sake of clarity, in this chapter we will adopt the term “institution” to refer to a set of rules and concepts regulating agent interactions and which may be enforced by an organization (an electronic institution according to Esteva et al. (2001)). This use of the terms “institution” and “organization” is inspired by (Searle, 1995), where an institution is any collectively accepted system of rules which creates institutional facts, and by (North, 1990), where institutions are the rules of a society regulating interactions and activities of organizations.

In contrast with (Moses & Tennenholtz, 1995), where norms (also named social laws) are assumed to be respected by agents because they are designed by a single organization, in open systems it is unrealistic to expect that autonomous agents will always comply with norms. In particular, like other social concepts (e.g., expectations (Alberti, Gavanelli, Lamma, Chesani, Mello, & Torroni, 2006) or commitments (Yolum & Singh, 2004) (Fornara, Viganò, & Colombetti, 2007)), norms describe interactions in terms of public observable entities which reflect how an agent should behave. For this reason, most efforts have been devoted to the development of normative languages amenable to automatic monitoring (e.g., (García-Camino, Noriega, & Rodríguez-Aguilar, 2005)) and tools to either avoid violations (Hübner, Simão Sichman, & Boissier, 2005) or detect and sanction them at runtime (e.g., (Esteva, Rodríguez-Aguilar, Rosell, & Arcos, 2004)). Doing so increases the efficiency of transactions carried out by agents (Noriega, 1997), but raises the problem of ensuring that such systems of rules are not characterized by contradictory norms, and allow agents to fulfill the objectives of the organization that has developed the system. This is especially important when norms of institutions are complex and cannot be reduced to a simple protocol that agents should follow, making it prohibitive to foresee all possible evolutions admitted by them.

Unfortunately, most approaches do not provide tools to automatically verify what properties are guaranteed when norms are followed or violated. As a consequence, designers can specify a set of norms which can be enforced at runtime, but they cannot check if such norms are consistent, undesirable behaviors are actually forbidden, and interactions terminate with positive outcomes when norms are correctly followed. For instance, in (Viganò & Colombetti, 2007) we showed that the rules of the Dutch Auction Institution discussed in (García-Camino, Rodríguez-Aguilar, Sierra, & Vasconcelos, 2006) admit infinite bidding rounds. The lack of tools for the verification of norms defined by institutions may be problematic, since institutions have been put forward to provide safe and reliable environments for agents (Esteva, Rodríguez-Aguilar, Sierra, García, & Arcos, 2001).

Key Terms in this Chapter

Multi-Agent System Organization: The organizational part of a multi-agent system. This part of a multi-agent system consists of entities that aim at coordinating the behavior of individual agents.

Norm-Based Artifact: An organizational artifact that is designed and implemented in terms of normative concepts.

Organizational Artifact: A (computational) entity that is designed and implemented to coordinate the behavior of individual agents. An organizational artifact is the implementation of a multi-agent system organization.

Multi-Agent Programming Language: A programming language that provides constructs to implement various multi-agent system concepts such as roles, communication, environment, resources, services, access relation, norms and sanctions.

Enforcement Mechanism: A (computational) mechanism that can enforce norms by changing the state of a multi-agent system. Such a mechanism is an integral part of multi-agent system organizations.

Regimentation: A (computational) mechanism by means of which the system is prevented to be in a violated state.

Normative Multi-Agent System: A multi-agent system in which the behavior of individual agents are coordinated by means of norms.

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Liz Sonenberg
Virginia Dignum
Virginia Dignum
Chapter 1
Virgina Dignum
Agent Organization can be understood from two perspectives: organization as a process and organization as an entity. That is, organization is... Sample PDF
The Role of Organization in Agent Systems
Chapter 2
Luciano R. Coutinho, Jaime S. Sichman, Olivier Boissier
In this chapter, we discuss the concepts of agent organization, organizational model, and review some existing organizational models. Before the... Sample PDF
Modelling Dimensions for Agent Organizations
Chapter 3
Jacques Ferber, Tiberiu Stratulat, John Tranier
In this chapter, we stress the importance of thinking a MAS in all its aspects (agents, environment, interactions, organizations, and institutions)... Sample PDF
Towards an Integral Approach of Organizations in Multi-Agent Systems
Chapter 4
Scott A. DeLoach
This chapter introduces a suite of technologies for building complex, adaptive systems. It is based in the multi-agent systems paradigm and uses the... Sample PDF
OMACS: A Framework for Adaptive, Complex Systems
Chapter 5
Christopher Cheong, Michael Winikoff
Although intelligent agents individually exhibit a number of characteristics, including social ability, flexibility, and robustness, which make them... Sample PDF
Hermes: Designing Flexible and Robust Agent Interactions
Chapter 6
Viara Popova, Alexei Sharpanskykh
This chapter introduces a formal framework for modeling and analysis of organizations. It allows representing and reasoning about all important... Sample PDF
A Formal Framework for Organization Modeling and Analysis
Chapter 7
Maksim Tsvetovat
Agent-based approaches provide an invaluable tool for building decentralized, distributed architectures and tying together sets of disparate... Sample PDF
Describing Agent Societies: A Declarative Semantics
Chapter 8
Davide Grossi, Frank Dignum
In this chapter we investigate how organizations can be represented as graphs endowed with formal semantics. We distinguish different dimensions of... Sample PDF
Structural Aspects of Organizations
Chapter 9
Virgina Dignum, Frank Dignum
Organization concepts and models are increasingly being adopted for the design and specification of multi-agent systems. Agent organizations can be... Sample PDF
A Logic for Agent Organizations
Chapter 10
Cristiano Castelfranchi
This chapter presents organizations as a macro-micro notion and device; they presuppose autonomous proactive entities (agents) playing the... Sample PDF
Grounding Organizations in the Minds of the Agents
Chapter 11
Paolo Torroni, Pinar Yolum, Munindar P. Singh, Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello
Organizational models often rely on two assumptions: openness and heterogeneity. This is, for instance, the case with organizations consisting of... Sample PDF
Modelling Interactions via Commitments and Expectations
Chapter 12
Gita Sukthankar, Katia Sycara, Joseph A. Giampapa, Christopher Burnett
This chapter discusses the problem of agent aiding of ad-hoc, decentralized human teams so as to improve team performance on time-stressed group... Sample PDF
Communications for Agent-Based Human Team Support
Chapter 13
Bob van der Vecht, Frank Dignum, John-Jules Ch. Meyer
This chapter discusses how autonomous agents can adopt organizational rules into their reasoning process. Agents in an organization need to... Sample PDF
Autonomous Agents Adopting Organizational Rules
Chapter 14
Nicoletta Fornara, Marco Colombetti
The specification of open interaction systems is widely recognized to be a crucial issue, which involves the problem of finding a standard way of... Sample PDF
Specifying Artificial Institutions in the Event Calculus
Chapter 15
Francesco Viganò, Marco Colombetti
Institutions have been proposed to explicitly represent norms in open multi-agent systems, where agents may not follow them and which therefore... Sample PDF
Verifying Organizations Regulated by Institutions
Chapter 16
Mehdi Dastani, Nick A.M. Tinnemeier, John-Jules Ch. Meyer
Multi-agent systems are viewed as consisting of individual agents whose behaviors are regulated by an organizational artifact. This chapter presents... Sample PDF
A Programming Language for Normative Multi-Agent Systems
Chapter 17
Antônio Carlos da Rocha Costa, Graçaliz Pereira Dimuro
This chapter presents the Population-Organization model, a formal tool for studying the organization of open multi-agent systems and its functional... Sample PDF
A Minimal Dynamical MAS Organization Model
Chapter 18
Shaheen Fatima, Michael Wooldridge
This chapter presents an adaptive organizational policy for multi-agent systems called TRACE. TRACE allows a collection of multi-agent organizations... Sample PDF
A Framework for Dynamic Agent Organizations
Chapter 19
Alexander Artikis, Dimosthenis Kaponis, Jeremy Pitt
We have been developing a framework for executable specification of norm-governed multi-agent systems. In this framework, specification is a... Sample PDF
Dynamic Specifications for Norm-Governed Systems
Chapter 20
Marco Lamieri, Diana Mangalagiu
In this chapter we present a model of organization aimed to understand the effect of formal and informal structures on the organization’s... Sample PDF
Interactions Between Formal and Informal Organizational Networks
Chapter 21
Steven Okamoto, Katia Sycara, Paul Scerri
Intelligent software personal assistants are an active research area with the potential to revolutionize the way that human organizations operate... Sample PDF
Personal Assistants for Human Organizations
Chapter 22
Sachin Kamboj, Keith S. Decker
This chapter presents an approach to organizational-self design (OSD), a method of designing organizations at run-time in which the agents are... Sample PDF
Organizational Self-Design in Worth-Oriented Domains
Chapter 23
Olivier Bonnet-Torrès, Catherine Tessier
This chapter focuses on a Petri Net-based model for team organization and monitoring. The applications considered are missions performed by several... Sample PDF
A Formal Petri Net Based Model for Team Monitoring
About the Contributors